parsing - LR(1) - 物品，向前看

Question

我很难理解 LR(1) 中的前瞻原理 - 项目。如何计算前瞻集？

举个例子，我有以下语法：

S -> AB
A -> aAb | b
B -> d

然后第一个状态将如下所示：

S -> .AB , {look ahead}
A -> .aAb, {look ahead}
A -> .b,   {look ahead}

我知道前瞻是什么，但我不知道如何计算它们。我已经用谷歌搜索了答案，但找不到以简单方式解释这一点的网页。

提前致谢

Answer 1

我将为您的示例写下前两个状态：

S -> AB
A -> aAb | b
B -> d

状态 0：

(1) S -> .AB, {$}   # Once we have done this rule it's EOF ($) 
(2) A -> .aAb, {d}  # from (1), after A there has to be a B whose first symbol has to be d
(3) A -> .b, {d}    # as above

状态 1：

(4) A -> a.Ab, {d}   # from (2)
(5) A -> .aAb, {b}   # from (4), the symbol after the A has to be b
(6) A -> .b, {b}     # from (4), as above
(7) A -> b., {d}     # from (3)
(8) S -> A.B, {$}    # from (1) and (7)
(9) B -> .B, {$}     # from (8)

依此类推，继续遵循与 LR(0) 解析器相同的移位/减少/关闭，但跟踪（前瞻）下一个符号......
（状态 2+ 更长，我不推荐手工制作它们！）

我建议查看Udacity 的编程语言课程，以了解有关词法分析和解析的更多信息。还有一个关于 wikipedia 的例子和一个相关的 SO question。