一个文法G,若存在P经过一次或多次推导得到Pa(即能推导出以P开头的式子), 则称G是左递归的。
左递归分为直接左递归和间接左递归。 直接左递归经过一次推导就可以看出文法存在左递归,如P→Pa|b。 间接左递归侧需多次推导才可以看出文法存在左递归,如文法:S→Qc|c,Q→Rb|b,R→Sa|a有S =>Qc =>Rbc =>Sabc 消除直接左递归的方法: 1、把所有产生式写成候选式形式。如A→Aa1|Aa2……|Aan|b1|b2……|bm。其中每个a都不等于ε,而第个b都不以A开头。 2、变换候选式成如下形式: A→b1A’|b2A’……|bmA’ A’ →a1A’|a2A’……|anA’|ε 例1:文法E→E+T|T,T→T*F|F,F →(E)|id消除直接左递归后有: E→TE’,E’ →+TE’|ε,T→FT’,T’ →*FT’|ε,F→(E)|id 消除间接左递归的方法: 要求文法不存在A 经过一次或多次能推导出A和不存在ε产生式(形如A→ε)。 1、以某种顺序排列非终结符A1,A2,……,An; 2、for i = 1 to n do {for j = 1 to i - l do { 用产生式Ai→a1b|a2b|……|akb代替每个开如Ai→Ajb的产生式,其中,Aj→a1|a2|……|ak是所有的当前Aj产生式;} 消除关于Ai产生式中的直接左递归性} } 3、化简由步骤2所得到的文法。 例2:有文法S→Qc|c,Q→Rb|b,R→Sa|a,消除文法的左递归。 以非终结符号排序为R,Q,S 把R的产生式代入Q中有: Q → (Sa|a)b|b Q → Sa b|ab|b 把Q的产生式代入S中有: S → (Sa b|ab|b)c|c S → Sa bc|abc|bc|c 消除直接左递归得到结果: S → abcS’|bc S’|cS’ S’→ abcS’|ε Q → Sa b|ab|b R → Sa|a Q 和 R的产生式是多余的删除,得到最终结果: S → abcS’|bc S’|cS’ S’→ abcS’|ε
-------------------------------------------------------------------------------
|
|