问题描述
我在理解LR(1)-项目中的超前原理方面遇到困难。
I am having difficulties understanding the principle of lookahead in LR(1) - items. How do I compute the lookahead sets?
以一个具有以下语法的示例为例:
Say for an example that I have the following grammar:
S -> AB
A -> aAb | b
B -> d
然后,第一个状态如下所示:
Then the first state will look like this:
S -> .AB , {look ahead}
A -> .aAb, {look ahead}
A -> .b, {look ahead}
我知道向前看是什么,但我不知道如何计算它们。 我已经在Google上搜索了答案,但找不到一个以简单的方式解释这一问题的网页。
I know what look aheads are, but I don't know how to compute them. I have googled for answers but couldn't find a webpage which explains this in a simple manner.
预先感谢
推荐答案
我将为您的示例写下前两个状态:
I'll write down the first two states for your example:
S -> AB
A -> aAb | b
B -> d
状态0:
State 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:
State 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+较长,我不建议您手工解决!)
and so on, keep following the same shift/reduce/closure as you would for an LR(0) parser, but keep track of (lookahead for) the next symbol...
(State 2+ are longer, I don't recommend working them out by hand!)
我建议调查课程可进一步了解词法分析和语法分析。 还有和。
I suggest looking into Udacity's Programming Languages course to learn more about lexing and parsing. There is also an example on wikipedia and a related SO question.
这篇关于LR(1)-物品,向前看的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!