简单LR解析器闭包项的创建

Question

假设我们有一个增强的文法 G：

E' - > E
E  - > E+T|T
T  - > T*F|F
F -  > (E)|id

在创建确定性有限自动机（dfa）的过程中，我达到了这个状态：（在《龙书》中是 I6）

    I6                   I9
 ---------            ---------
|E -> E+.T|          | E->E+T. |   
|T -> .T*F|     T    | T->T.*F |
|T -> .F  |  ----->   ---------
|F -> .(E)|       
|F -> .id |
 ---------

我在想，为什么我们不把 T->.F 和 F->.(E) 以及 F->.id 加到 I9 中呢？

当我们在输入字符串中遇到 T 时，我们应该添加 T->.F，然后我们就达到了 F，接着应该添加 F->.(E) 和 F->.id。

为什么 I9 不会包含这些呢？

Answer 1

这是因为闭包和跳转算法的工作原理。当你用 GOTO(T) 从 I6 创建 I9 时，点会向右移动一步，经过的每个 T 都会被加入到一个新的集合中。这个集合就是 I9 的 GOTO 集合。而在 I6 中，点右边没有 T 的那些项就不会被加入到 I9 的 GOTO 集合里。完成 GOTO 操作后，你就得到了集合 I9。

E->E+T.
T->T.*F

当你对集合 I9 应用闭包时，你会扩展点右边的每一个非终结符。在 I9 中，点右边没有非终结符，所以没有东西可以扩展。

我最近发过一篇关于一个非常相似但稍微复杂一点的问题的帖子，如果你需要更多的解释，可以参考一下，计算 LR1 闭包