编译原理冲刺 · 第 05 课 ⏱ 冲刺模式 · ≤1周

消除左递归 与 提取左公因子

给文法"动手术",让它能被自顶向下分析。对应教材第 4 章 4.2。
🎯 本课唯一目标
拿到一个文法,会消除左递归、会提取左公因子——这是下两课 FIRST/FOLLOW、LL(1)、递归下降能跑起来的前提。
为什么学它? 自顶向下分析(第 4 章)有两个"天敌":左递归会让程序无限递归、回溯会让程序乱试。这一课就是两把手术刀,先把文法改造好,后面才好做。常作为大题的第一步出现。

一、两大障碍

二、消除直接左递归

套路(背下来):

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) | i
E、T 都是直接左递归(E→E+TT→T*F)。套公式 P→Pα|β ⟹ P→βP′, P′→αP′|ε
结果:  E  → T E′          E′ → + T E′ | ε
        T  → F T′          T′ → * F T′ | ε
        F  → (E) | i
⭐ 这个改造结果务必记牢——L06、L07、L08 三课都用它当例子!
例题② 提取左公因子(典型的 if 语句)。
原文法:  S → iEtS | iEtSeS | a      (i=if, t=then, e=else)
前两条有公共左因子 iEtS,提出来:
结果:  S  → iEtS S′ | a          S′ → eS | ε

五、你来做

1. 直接左递归的一般形式是?
2. 消除直接左递归后,会引入什么?
3. 提取左公因子的目的是?
4. 下列哪个文法含左递归
5. 文法含左递归,会让递归下降分析程序?
得分:0 / 5
P→Pα|β ⟹ P→βP′,P′→αP′|ε
左递归→无限递归,提左因子→消回溯
📺 主源推荐 哈工大《编译原理》自顶向下语法分析讲 — 中国大学MOOC[1]
🙋 间接左递归(要先代入再消)最容易出错——遇到了把文法发我,我带你一步步代入化简。
  1. [1] 消除左递归(直接/间接)、提取左公因子:陈火旺《程序设计语言编译原理》4.2;哈工大 MOOC语法分析讲。