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

递归下降分析程序构造

每个非终结符写一个函数，最直观的自顶向下分析。对应教材第 4 章 4.4。
🎯 本课唯一目标
会为一个（已消左递归、已提左因子的）文法，给每个非终结符写出递归下降子程序。
为什么学它？　它是 LL(1) 思想的"手写版"，考试常考"为下面文法写递归下降程序"。套路极固定——非终结符 → 函数，右部 → 函数体，照搬即可。

一、核心思想

为每个非终结符写一个（可能递归调用的）子程序，负责识别该非终结符能推出的串[1]。

对文法的要求：无左递归、无回溯（即适合 LL(1)）。否则：左递归 → 无限递归；有公共左因子 → 不知走哪条。

⚑ 写子程序的套路

按产生式右部从左到右处理每个符号：

· 遇终结符 → 调用 match（与当前输入符比较，相符就读下一个，不符报错）；

· 遇非终结符 → 调用它的子程序；

· 有多个候选 → 看当前输入符落在哪个候选的 FIRST 集，选那条分支；

· ε 产生式 → 不消耗输入、直接返回（由当前符/FOLLOW 决定走 ε）。

二、老师示范一题

例题　为文法 E→TE′, E′→+TE′|ε, T→FT′, T′→*FT′|ε, F→(E)|i 写递归下降程序。
// sym = 当前输入单词；advance() = 读入下一个单词

procedure E:           // E → T E′
    T;  Eprime;

procedure Eprime:      // E′ → + T E′ | ε
    if sym = '+' then { advance();  T;  Eprime; }
    // 否则走 ε：什么都不做，直接返回

procedure T:           // T → F T′
    F;  Tprime;

procedure Tprime:      // T′ → * F T′ | ε
    if sym = '*' then { advance();  F;  Tprime; }
    // 否则走 ε

procedure F:           // F → (E) | i
    if sym = 'i' then advance();
    else if sym = '(' then {
        advance();  E;
        if sym = ')' then advance();  else error();
    }
    else error();
💡 对照看：每个非终结符 = 一个 procedure；右部里终结符就 advance、非终结符就调用同名过程、| 用 if 当前符 选分支、ε 就是"啥也不干返回"。

三、你来做

1. 递归下降分析对文法的要求是？
2. 在递归下降里，什么对应一个子程序？
3. 子程序里遇到一个终结符时应？
4. 文法含左递归，会让递归下降程序？
5. ε（空）产生式分支靠什么决定要不要走？
得分：0 / 5
非终结符 → 函数；终结符 → match；| → 看当前符选支；ε → 直接返回
📺 主源推荐　哈工大《编译原理》自顶向下分析（递归下降）讲 — 中国大学MOOC[1]。
🙋 给你一个新文法练手：试着为 S→(L)|a, L→L,S|S（先消左递归）写递归下降，写完发我看。
  1. [1] 递归下降分析程序构造：陈火旺《程序设计语言编译原理》4.4；哈工大 MOOC语法分析讲。