python - 创建简单的 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 算法的工作原理。因为当您在 I6 上使用 GOTO(T) 创建 I9 时，点在任何 T 上向右移动一步，并将它们添加到新集合中。该组就是 I9 GOTO 组。 I6 中点右侧没有 T 的那些将不会添加到 I9 GOTO 集中。执行 GOTO 后，您将设置 I9

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

当您在集合 I9 上应用闭包时，您将展开点右侧的每个非终结符。在 I9 上，点右侧没有非终结符，因此无需展开。

我最近发表了一篇关于一个非常相似但更复杂的问题的帖子，如果您需要额外的说明，可能会有所帮助，Computing LR1 closure