Compilers Principles, Techniques, & Tools (purple dragon book) second edition exercise answers

第4章要点

!LR(0), SLR, LR, LALR 之间的区别

p157: LR(0) 自动机是如何做出移入-规约决定的?假设文法符号串 γ 使得 LR(0) 自动机从开始状态 0 运行到某个状态 j,那么如果下一个输入符号为 a 且状态 j 有一个在 a 上的转换,就移入 a,否则就进行规约。

这种方法会导致一些错误的规约,假定规约后的符号为 X,但 a 并不在 FOLLOW(X) 中,这种情况下就会有问题。所以 SLR 在这方面进行了改进。

p161:构造一个 SLR 分析表时,如果 [A -> α.] 在 I_i 中,那么对于 FOLLOW(A) 中的所有 a,将 ACTION[i, a] 设置为 “规约 A -> α”

SLR 一定程度上解决了错误规约的问题,但没有完全解决。因为虽然 a 在 FOLLOW(A) 中才会选择规约,但是就当前所处的状态 I_i 而言,并不是每个 FOLLOW(A) 中的终结符都可以出现在状态 I_i 中的 A 后面。

p166: 用更正式一点的语言来讲,必须要为 I_i 精确得指明哪些输入符号可以更在句柄 α 后面,从而使 α 可以被规约为 A。

LR 通过在项中加入第二个分量,即向前看符号来解决这个问题。但新的问题是 LR 会使得状态表及其庞大,而 LALR 就是一种比较经济的做法,它具有和 SLR 一样多的状态。

p170:一般地说,通过将具有相同核心项集的 LR 项集合并,可以得到 LALR 项集。虽然 LALR 可能会进行一些错误的规约,但最终会在输入任何新的符号之前发现这个错误。

消除二义性 (p134)

图 4-10,如何得出这个消除方法的?

消除左递归 (p135)

为什么图 4-11 的算法能消除文法中的左递归?

消除递归需满足两个条件:

  1. 不存在立即左递归,即不存在形似这样的产生式 A -> Aα 。
  2. 不存在由多步推导可产生的左递归。

算法 3~5 行循环的结果使得形如 A_i -> A_m α 的产生式一定满足 m >= i ,就消除了形如 S => Aa => Sda 这样的转换可能,也就是说由 A_m 一定推导不出以 A_i 开头的产生式,A_m α 就不存在产生 A-i 左递归的可能。

同时需要注意的是: 只需要处理 A_i -> A_j α 这样的产生式,而不需要处理形如 A_i -> α A_j β 这样的产生式

循环完成后,第 6 行消除了替换后的产生式中的立即左递归。

使用 LR(0) 创建出 LALR(1) 项集的内核 (p173)

自发生成的和传播的向前看符号

CNF 和 BNF