LR（1）-物品，向前看 [英] LR(1) - Items, Look Ahead

问题描述

我在理解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!)

我建议调查 Udacity的编程语言 课程可进一步了解词法分析和语法分析。 还有关于维基百科的示例和相关的SO问题。

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）-物品，向前看的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！