Two parsing strategy

两种语法分析器的分析策略

• Top-down parsing（自顶向下解析）
  • predictive recursive descent（预测递归下降）
• Bottom-up parsing（自底向上解析）
  • The concept of reduction（归约的概念）
  • Use of the parse stack（分析栈的使用）

Bottom-Up Parsing

Bottom-Up Parsing（自底向上分析） 的核心思想是：

• 从输入串的 叶子结点/终结符 开始
• 一步步向上构造语法树
• 最终把整个输入串 归约（reduce） 成开始符号 S

属于是 Shift-Reduce Parsing（移进-归约分析） 的框架

其实就是将输入串不断带入产生式，不断用右边代替左边，最终得到开始符号的过程

Parse Stack

bottom-up parsing 要用 parse stack（分析栈）。

它的作用是：

• 每读入一个符号，就先把它压入栈中
• 再检查栈顶是否能形成某条产生式右部
• 如果能，就进行归约

所以栈是整个 bottom-up parsing 的核心数据结构。

可以把它理解成：

• 输入缓冲区：还没处理的内容
• 分析栈：已经读进来、等待归约的内容

Example:

Input: “real A, B, C” 演示了 bottom-up parsing 过程

其大致过程是：

1. 先把 real 读入栈
2. 再读 A 入栈
3. 用产生式 ID → A|B|C|D 把 A 归约成 ID
4. 再用 IDLIST → ID 把 ID 归约成 IDLIST
5. 继续读入 B
6. 把 B 归约成 ID
7. 再把前面的 IDLIST, ID 归约成 IDLIST
8. 再读入 C
9. 把 C 归约成 ID
10. 再把 IDLIST, ID 归约成 IDLIST
11. 最后把 real IDLIST 归约成 S

这个例子说明了自底向上分析的本质：

读入 → 压栈 → 找可归约片段 → 归约 → 继续直到整个串变成开始符号。

Shift-Reduce Parsing Workprocess

• 从左到右扫描输入串
• 不断执行 shift，把符号压入栈
• 当栈顶形成某条产生式右部时，执行 reduce
• 重复该过程
• 直到：
  • 发现错误，或者
  • 栈中只剩开始符号，且输入已经读完

当栈中只包含句子（distinguished）符号，并且整个输入句子都已经读完时，分析完成

也就是：

• 栈中只剩 开始符号
• 输入缓冲区为空

这也是 bottom-up parsing 接受输入的条件

自底向上分析中的核心难点

问题 1：如何决定用哪条规则做 reduction？

也就是说：

• 栈顶可能匹配多个右部
• 到底该按哪条产生式归约？

问题 2：如何决定什么时候读下一个 token？

也就是：

• 当前到底应该 shift 还是 reduce？

这两个问题将在 LR(0) 中解决