Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
26 lines (13 sloc) 964 Bytes

第4章要点

消除二义性 (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)

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