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 可能会进行一些错误的规约,但最终会在输入任何新的符号之前发现这个错误。
图 4-10,如何得出这个消除方法的?
为什么图 4-11 的算法能消除文法中的左递归?
消除递归需满足两个条件:
算法 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 行消除了替换后的产生式中的立即左递归。
自发生成的和传播的向前看符号