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

自下而上分析基础

短语 · 直接短语 · 句柄 —— 移进归约的核心概念。对应教材第 5 章 5.1。
🎯 本课唯一目标
理解移进-归约的思想;会在一个句型上找出短语、直接短语、句柄
为什么学它? 这是第 5 章的概念地基,"找句柄/短语"是高频填空/简答题,也是下一课算符优先分析的前提。概念清楚,分稳拿。

一、自下而上 = 移进-归约

方向和自顶向下相反:从输入串出发,反复把产生式右部"归约"成左部,直到归约成开始符号 S[1]。借助一个,四个动作:移进(输入符压栈)、归约(栈顶若干符号换成某产生式左部)、接受报错

二、四个必背概念

概念定义在语法树上
短语句型 αβδ 中,若 S⇒*αAδ 且 A⇒⁺β,则 β 是相对于 A 的短语某棵子树的全部叶子
直接短语若 A⇒β(恰好一步),β 是直接短语只有两代(父+子叶)的子树的叶子
句柄句型的最左直接短语最左边那个"两代子树"的叶子
规范归约每步都归约句柄最右推导(规范推导)的逆
⚑ 找句柄的套路

① 给句型画语法树;② 找所有"只有两代"的子树 → 它们的叶子是直接短语;③ 其中最左边的那个,就是句柄

三、老师示范一题

例题 文法 E→E+T|T, T→T*F|F, F→(E)|i。对句型 T*F+i,求全部短语、直接短语、句柄。
先画语法树(由 E ⇒ E+T ⇒ T+T ⇒ T*F+T ⇒ T*F+F ⇒ T*F+i):
            E
        /   |   \
       E    +    T
       |         |
       T         F
     / | \       |
    T  *  F      i
找子树叶子:
· 整棵树(根E)的叶子        → T*F+i      【短语】
· 左 E 子树的叶子          → T*F        【短语】
· 中间 T 子树(T→T*F)的叶子 → T*F        【短语 + 直接短语】(只有两代)
· 右 T 子树的叶子          → i          【短语】
· F 子树(F→i)的叶子        → i          【短语 + 直接短语】(只有两代)
短语T*F+i 、 T*F 、 i
直接短语T*F(来自 T→T*F) 、 i(来自 F→i)
句柄T*F(两个直接短语里最左的那个)
💡 区分要点:直接短语是"一步就能归约"的(对应只有两代的子树);句柄是其中最左的——规范归约下一步就归约它。

四、你来做

1. 句柄的定义是?
2. 规范归约是哪种推导的逆过程?
3. 移进-归约分析使用什么数据结构?
4. 自下而上分析从什么开始?
5. 直接短语对应语法树里的什么?
得分:0 / 5
短语=子树叶子;直接短语=两代子树叶子;句柄=最左直接短语
规范归约 = 最右推导的逆
📺 主源推荐 哈工大《编译原理》自底向上语法分析讲 — 中国大学MOOC[1]
🙋 "短语 vs 直接短语 vs 句柄"最容易混。给你个句型 i*(i+i),自己画树找句柄,发我核对。
  1. [1] 移进归约、短语/直接短语/句柄、规范归约:陈火旺《程序设计语言编译原理》5.1;哈工大 MOOC自底向上分析讲。