方向和自顶向下相反:从输入串出发,反复把产生式右部"归约"成左部,直到归约成开始符号 S[1]。借助一个栈,四个动作:移进(输入符压栈)、归约(栈顶若干符号换成某产生式左部)、接受、报错。
| 概念 | 定义 | 在语法树上 |
|---|---|---|
| 短语 | 句型 αβδ 中,若 S⇒*αAδ 且 A⇒⁺β,则 β 是相对于 A 的短语 | 某棵子树的全部叶子 |
| 直接短语 | 若 A⇒β(恰好一步),β 是直接短语 | 只有两代(父+子叶)的子树的叶子 |
| 句柄 | 句型的最左直接短语 | 最左边那个"两代子树"的叶子 |
| 规范归约 | 每步都归约句柄 | 是最右推导(规范推导)的逆 |
① 给句型画语法树;② 找所有"只有两代"的子树 → 它们的叶子是直接短语;③ 其中最左边的那个,就是句柄。
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(两个直接短语里最左的那个) |
i*(i+i),自己画树找句柄,发我核对。