P→Pα,左部 P 又出现在右部最左端。递归下降时会 P 调 P 调 P… 死循环。A→αβ₁ | αβ₂),看到 α 不知道走哪条,只能试错回退。套路(背下来):
P → Pα | β ⟹ P → β P′
P′ → α P′ | ε
一般形式 P→Pα₁|…|Pαₘ | β₁|…|βₙ(β 们不以 P 打头):
P → β₁P′ | β₂P′ | … | βₙP′ P′ → α₁P′ | α₂P′ | … | αₘP′ | ε
间接左递归(如 A→Bα、B→Aβ 绕一圈又回到 A):先给非终结符排序,把前面的代入后面,化成直接左递归再消。
A → αβ₁ | αβ₂ ⟹ A → α A′
A′ → β₁ | β₂
消左递归:①找 P→Pα|β;②造新符号 P′;③写成 P→βP′、P′→αP′|ε。
提左因子:把相同的开头 α 提出来,剩下的塞进一个新非终结符。
原文法: E → E+T | T T → T*F | F F → (E) | iE、T 都是直接左递归(
E→E+T、T→T*F)。套公式 P→Pα|β ⟹ P→βP′, P′→αP′|ε:
结果: E → T E′ E′ → + T E′ | ε
T → F T′ T′ → * F T′ | ε
F → (E) | i
原文法: S → iEtS | iEtSeS | a (i=if, t=then, e=else)前两条有公共左因子
iEtS,提出来:
结果: S → iEtS S′ | a S′ → eS | ε