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)解析器一样的shift/reduce/closure,但跟踪(lookahead)下一个符号...
(状态2+更长,我不建议用手工作!)

我建议查看Udacity的编程语言课程,以了解有关lexing和解析的更多信息.维基百科上还有一个例子和相关的SO问题.