本文介绍了LR(1)-物品,向前看的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我在理解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)-物品,向前看的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-03 17:53