在 LR(1) 解析中向前看

Question

我在理解如何在 LR(1) 中向前看时遇到一些问题。我已经找到关于同一问题的问题 LR(1) - Items, Look Ahead 但这对我没有帮助。

S'->.S,$
S->.L=R,$
S->.R,$
L->.*R,=/$
L->.id,=/$
R->.L,$

我了解 S' 和 S 产品的前瞻性，但不了解 L 和 R 产品... 你能帮我吗？提前谢谢你。

Answer 1

为了更好地处理 LR/SLR/LALR 解析，我推荐 The Dragon Book。

构造 LR(1) 项集在第 4.7.2 节中，过程 CLOSURE。

对于您的示例，考虑执行 "expanding"（在 CLOSURE 期间）LR(1) 项 S->.L=R,$：结果是 LR(1) 项

L->.*R,=
L->.id,=

先行是FIRST("=R$")中的每个终结符号，即点前非终结符后面的所有内容，加上先行，新项的先行就是=点.

接下来，考虑 S->.R,$ 的 "expansion"。同样，新项目中的前瞻是 FIRST("$" 中的所有终端符号）：R 之后没有任何内容，因此只有前瞻。这会产生项目

R ->.L,$

进一步扩展此项，使用 FIRST("$") 中的所有非终结符作为前瞻给我们

L->.*R,$
L->.id,$

因此，您可以看到原始示例中的 L->.*R,=/$ 只是两个单独项目 L->.*R,= 和 L->.*R,$ 的 shorthand 符号，它们中的每一个沿着单独的 "expansion" 链获得。

Look ahead in LR(1) parsing