自顶向下语法分析方法.pptVIP

B?(aBc|d)B?B??bcB?|εA?BbA?aB＋消除文法中一切左递归的算法。对文法中一切左递归的消除要求文法中不含回路，即无A?A的推导。满足该文法的充分条件是：文法中不包含形如A?A的有害规则和A?ε的产生式。算法步骤*自顶向下语法分析方法*以某种顺序将文法非终结符排列A1,A2…An从A1开始消除左部为A1的产生式的直接左递归，然后把左部为A1的所有规则的右部逐个替换左部为A2右部以A1开始的产生式中的A1，并消除左部为A2的产生式中的直接左递归。继而以同样方式把A1,A2的右部代入左部为A3右部以A1或A2开始的产生式中，消除左部为A3的产生式之直接左递归，直到把左部为A1,A2,…An-1的右部替换左部为An的产生式中，从An中消除直接左递归。0102*自顶向下语法分析方法*（1）以某种顺序将文法非终结符排列A1,A2…An（2）fori:=1tondobeginforj:=1toi-1do 若Aj的全部产生式为： Aj??1|?2|…|?k 替代形如Ai?Ajr的产生式变为：Ai??1r|?2r|…|?krend消除Ai规则的一切直接左递归;end;（3）去掉无用产生式方法一：根据定义计算对于每一个文法符号x?V，计算first(x)的方法如下：若x?VT，则first(x)＝{x}若x?VN，且有x?a…，a?VT，则a?first(x)若x?VN，x??，则??first(x)若x?VN，y1，y2，…，yi都?VN，若有产生式x?y1y2…yn，当y1，y2，…yi-1都??时(1≤i≤n)，则first(y1)－{?}，first(y2)－{?}，…，first(yi－1)－{?}，first(yi)都包含在first(x)中。e)当上式中所有yi??(1≤i≤n)，则first(x)＝(first(y1)-{?})∪(first(y2)-{?})∪…∪(first(yn)-{?})∪{?}**first(S)=(first(A)-{?})∪(first(B)-{?})∪{?}∪{b}={a,b,?}first(A)={b}∪{?}={b,?}first(B)={?}∪{a}={a,?}first(C)=(first(A)-{?})∪first(D)∪first(b)={a,b,c}first(D)={a}∪{c}={a,c}S?AB|bCA?ε|bB?ε|aDC?AD|bD?aS|c一个文法符号串的first集合计算方法：如果文法符号串??V*,?=X1X2…Xn,1、当X1?ε，则first(?)=first(X1)2、当对任何j（1≤j≤i-1，2≤i≤n），ε?first(Xj)ε?first(Xi)，则first(?)=(first(X1)-{ε})∪(first(X2)-{ε})∪…∪(first(Xi-1)-{ε})∪first(Xi)3、当first(Xj)都含有ε时(1≤j≤n)，则first(?)=first(X1)∪first(X2)∪…∪first(Xj)∪{ε}*first(A)∪first(B)∪{ε}={a,b,ε}{b}{ε}{a}(first(A)-{ε})∪first(D)={a,b,c}{b}{a}{c}first(AB)=first(bC)=first(ε)=first(aD)=first(AD)=first(b)=first(aS)=first(c)=文法G[S]： S→AB|bC A→ε|b B→ε|aD C→AD|b D→aS|c方法二：由关系图法求文法符号的first集合每个文法符号对应图中的一个结点，终结符结点用符号本身标记，非终结符结点用first(A)标记。若文法中有A??X?，??ε，则从对应A的结点到对应X结点连一条箭弧。凡是从first(A)结点有路径可到达的终结符结点所标记的终结符都为first(A)的成员。根据判别步骤1)确定ε是否为某非终结符first的成员，若是则将ε加入该非终结符的first集中。*自顶向下语法分析方法*first(S)first(B)first(C)first(A)first(D)bac文法为：S?AB|bCA?ε