消除改写文法的左递归

1文法等价变换文法的等价对文法G1和G2，若有：L(G1)=L(G2)，则称文法G1和G2等价,记作:G1=G2.文法等价变换有些语法分析方法要求被分析的文法满足一定的约束条件，当被分析的文法不满足这些条件是，常常要进行文法变换。2增补产生式消除空产生式消除不可达产生式消除特型产生式消除公共前缀消除左递归重要的文法等价变换31.增补产生式何时需要增补：在自底向上语法分析中需要。定理：对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，且G2的开始符唯一且不出现于任何产生式的右部。证明：假设S是G1的开始符，则只要在G1中扩充一条新产生式ZS即可，其中Z是新的开始符。另这样扩充后的文法为G2，则它显然满足定理的要求。34例:G1[S]:S→abSA|aA→bG2[Z]:Z→SS→abSA|aA→b52.消除空产生式定理：对任一文法G1，可构造文法G2，使得L(G1)=L(G2)，且G2中无空产生式。证明：根据G1，构造G2的方法如下：1.令={A|A}，={A|A+,+}；2.从G1中删除所有形如A的产生式。3.从G1删除只能导出空串的非终极符。4.对于文法中任意产生式AX1X2…Xi-1XiXi+1…Xn,若Xi，补充规则AX1X2…Xi-1Xi+1…Xn；重复以上过程，直到不出现新的产生式。6例：设有如下文法AaBcDBb|DBB|d消除该文法中的空产生式.解：(1)={B}={B,D}(2)AaBcDBbDBB|dAacD(3)AaBcDAaBcAacDBDBB得到新的文法如下:AaBcD|acD|aBc|acBbDBB|B|d73.消除不可达产生式定理：对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，且G2中的每个非终极符必出现在它的某个句型中。证明：根据G1，构造文法G2的方法如下：1.令={S|S是文法的开始符}。2.递归扩充={B|AxByG1,BVN,A}。3.若A，则删除以A为左部的所有产生式。84：消除特型产生式特型产生式若文法中的产生式具有形式AB（B为非终极符），则称该产生式为特型产生式.特型产生式的缺点是在语法分析中会降低分析的速度，因此应该消除这样的产生式.9证明：构造无特型产生式的文法G2的方法如下：–(1)对文法G1中每个非终极符A，求集合:A={B|A=+B,BVN}.–(2)若BA，且B是文法G中的一个非特型产生式，则补充如下规则：A–(3)去掉文法G1中的所有的特型产生式.–(4)去掉新的文法中的无用产生式.定理对任一文法G1，可以构造文法G2，使得L(G1)=L(G2)，并且在G2中没有特型产生式.10例设有如下文法AB|D|aBBC|bCcDB|d消除该文法中的特型产生式.解：A={B,D,C}B={C}C={}D={B,C}根据算法第2步在文法中补充如下规则Ab|d|cBcDb|c去掉文法中的特型产生式，得到如下文法AaB|b|d|cBb|cCcDb|c|d其中关于C和D的产生式是无用产生式，应去掉.115：消除公共前缀公共前缀:A→，A→这种情形不满足自顶向下的语法分析条件.消除方法：可用提取左因子的方法.假定关于Ａ的规则是：A1|2|…|n|1|2|…|γm则将这些规则写成：AA’|1|γ2|…|γmA’1|2|…|n126.消除左递归一个文法含有下列形式的产生式时（1）AA|，称为直接左递归其中AVN；,(VNVT)*（2）AB|BA|其中A,BVN；,,,(VNVT)*称为间接左递归文法中只要有A+A…，则称文法为左递归的。13（1）对直接左递归形如：AA|消除左递归得：AAAA|（2）间接左递归形如：AB|BA|转为直接左递归形式：AA||或者BB||按照直接左递归方式消除。去掉多余的产生式。对于不含回路或空产生式，消除左递归方法为：14ET|E+TTF|T*FFid|(E)例：TFT’T’*FT’|ETE’E’+TE’|Fid|(E)15增加拓广产生式消除空产生式消除不可达产生式消除特型产生式消除公共前缀消除左递归重要的文法等价变换16练习：1.设有如下文法，画出句型（adSdS）的语法树并写出其短语、简单短语和句柄。Sa|b|(A)ASdA|S2、试将描述命题演算公式的二义性文法G(S)改写为等价的无二义性文法。优先级：()非not合取and析取orSSandS|SorS|notS|p|q|(S)参照表达式文法转换3、消除改写文法的左递归。EE+EEE*EE(E)|iEE+T|TTT*F|FF(E)|i171.设有如下文法，画出句型（adSdS）的语法树并写出其短语、简单短语和句柄。Sa|b|(A)ASdA|S(A)SdAaSSdAS短语:(adSdS),adSdS,a,SdS,S简单短语:a,S句柄:a182、试将描述命题演算公式的二义性文法G(S)改写为等价的无二义性文法。优先级：()非not合取and析取orSSandS|SorS|notS|p|q|(S)参照表达式文法转换EE+EEE*EE(E)|iEE+T|TTT*F|FF(E)|iSSorA|AAAandB|BBnotB|CCp|q|(S)SAS’S’orAS’|ABA’A’andBA’|BnotB|CCp|q|(S)ETE’E’+TE’|εTFT’T’*FT’|εF(E)|i