第章语法分析——自顶.pptVIP

E→TE’ T→FT’ F→i? T’→ε E’→+TE’? T→FT’ F→i? T’→*FT’? F→i? T’→ε E’→ε E→TE’ →FT’ E’ →i?T’ E’ → i?E’ → i +TE’? → i + FT’ E’ → i + i?T’ E’ →i + i *FT’ E’ ? →i + i *i?T’ E’ → i + i *i?E’ → i + i *i? 4.4.2 LL(1)分析表的构造方法 对于不同的LL(1)文法，LL(1)的分析算法是相同的，不同的仅仅是分析表。显然，如何根据文法来构造分析表是LL(1)分析的关键。 对于任意给定的已化简的文法G，为了构造分析表，首先我们要求出每个非终结符号的FOLLOW集合和每个后选式的FIRST集合。然后对文法G中的每个产生式A→α，按下列规则确定分析表中的元素M： 1) 对FIRST(α)中的每个终结符a，置M[A，a]=“POP，PUSH(α’)”，其中α’为α的倒置。 2) 若ε∈FIRST(α)，则对属于FOLLOW(A)的每个符号b(b为终结符或#)，置M[A，b]=“POP”。 3) 把M中的所有M[a，a]置为“POP，NEXTSYM”。 4) 把M中所有不按规则1、2定义的元素均置为空或“ERROR”。 4.4.2 LL(1)分析表的构造方法 例如，有文法E→TE’，E’→+TE’，E’→ε，T→FT’， T’→*FT’，T’→ε，F→(E)|i， 对规则E→TE’：FIRST(TE’)= {(，i)}，那么在分析表的符号E所在的行、符号(和i所在的列对应的位置分别填入“POP,PUSH(E’T)”,见表4.1的E行。 对规则E’→+TE’：FIRST(+TE’)={+}，在符号E行符号+列对应的位置填入“POP,PUSH(E’T’+)” ，见表4.1的E’行。 对规则E’→ε：因为ε∈FIRST(α)，FOLLOW(E’)={}，#}，所以在符号E行符号)和#列对应的位置填入“POP”，见表4.1的E’行。 对于一个文法，若按上述方法构造的分析表M不含多重定义，则称它是一个LL(1)文法。 4.4.2 LL(1)分析表的构造方法 观察表4.1的LL(1)分析表及表4.2的分析过程，会发现当压栈的最后一个符号是终结符时，那么下一步的分析动作肯定是这个终结符号出栈，因此，我们可以对分析表进行简化。方法是当压栈的最后一个符号是终结符时，那么，这个终结符不入栈，并加入读下一个符号，这样，分析表中所有的终结符行都可以去掉。对表4.1的分析表简化后的分析表如表4.3所示。 符 号 输入符号 i + * ( ) # E E’ T T’ F POP, PUSH(E’T) ? POP, PUSH(T’F) ? POP, NEXTSYM ? POP, PUSH(E’T’), NEXTSYM ?POP ? ? ? ? ? ? POP, PUSH( T’F ), NEXTSYM ? ? POP, PUSH(E’T) ? POP, PUSH(T’F) ? POP, PUSH( )E ), NEXTSYM ? POP ? POP ? ? ? ? POP ? POP ? ? ? 4.2.3 LL(1)分析的主要问题及解决方法 1、左递转成右递归 LL(1)分析不能处理左递归文法，但也不能像递归下降分析那样将左递归改为采用扩充BNF表示。在LL(1)分析中，必须将左递归文法变成右递归文法，其变换方法如下： 1）?对形如U::=x|y|…|z|Uv的直接左递归文法规则，增加一个新的非终结符号U’，令U为左递归规则中的不含左递归符号的部分加上新的非终结符号U’，即U::= (x|y|….|z )U’。 2）?新的非终结符号U’有两个侯选式，一为含左递归符号的部分去掉含左递归符号，再加上新的非终结符号U’，即U’::=vU’。另一个为ε，即U’::=ε。 按上面的两步，我们就可将左递归规则改成等价的右递归规则。 例如，对左递归规则E→E+T|T，如果像递归下降分析那样改成 E→T{+T}无法形成逆序入栈，但可改成右递归：令E’为新的非终结符号，则等价的右递归规则为： E→TE’，E’→+TE’|ε 实际上，在递归下降分析方法中，也可将左递归规则改成右递归进行处理。 2、解决分析表多重定义问题 若一个LL(1)文法的分析表不出现多重定义，当且仅当对于文法G的每个非终结符A的任何两条不同规则A→α|β ，下面条件成立： ?FIRST(α)∩FIRST(β)=φ 即头符号集不相交。 ?假若β==*ε，那么，FIRST(α)∩FOLLOW(A)=