LR(1)项目DFA-计算前瞻 [英] LR(1) Item DFA - Computing Lookaheads

问题描述

我很难理解如何计算LR(1)项的提前期.

I have trouble understanding how to compute the lookaheads for the LR(1)-items.

让我们说我有这个语法:

Lets say that I have this grammar:

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

LR(1)项是具有超前功能的LR(0)项.因此，我们将获得状态0的以下LR(0)项目:

A LR(1)-item is an LR(0) item with a lookahead. So we will get the following LR(0)-item for state 0:

S -> .AB , {lookahead} 
A -> .aAb,  {lookahead} 
A -> .a,  {lookahead}

状态:1

A ->  a.Ab, {lookahead} 
A ->  a. ,{lookahead} 
A -> .aAb ,{lookahead} 
A ->.a ,{lookahead}

有人可以解释如何计算提前量吗?什么是一般方法?

Can somebody explain how to compute the lookaheads ? What is the general approach ?

提前谢谢

推荐答案

在LR(1)解析器中使用的先行计算如下.首先，开始状态的项目形式为

The lookaheads used in an LR(1) parser are computed as follows. First, the start state has an item of the form

S -> .w  ($)

对于每个产品S-> w，其中S是开始符号.在这里，$标记表示输入的结尾.

for every production S -> w, where S is the start symbol. Here, the $ marker denotes the end of the input.

接下来，对于包含形式A-> x.By(t)的任何状态，其中x是任意的终端和非终端字符串，而B是非终端，则添加形式B- > .w(s)对于每个产品B-> w以及集合FIRST(yt)中的每个终端. (在这里，FIRST指的是 FIRST集，通常在谈论LL解析器时会引入它们.如果您以前从未看过它们，我将花几分钟查看这些讲义).

Next, for any state that contains an item of the form A -> x.By (t), where x is an arbitrary string of terminals and nonterminals and B is a nonterminal, you add an item of the form B -> .w (s) for every production B -> w and for every terminal in the set FIRST(yt). (Here, FIRST refers to FIRST sets, which are usually introduced when talking about LL parsers. If you haven't seen them before, I would take a few minutes to look over those lecture notes).

让我们在语法上尝试一下.我们首先创建一个包含

Let's try this out on your grammar. We start off by creating an item set containing

S -> .AB ($)

接下来，使用第二条规则，对于A的每个生产，我们在FIRST(B $)中添加一个与该生产相对应的新项目，并且每个终端的前瞻性都很高.由于B总是产生字符串d，FIRST(B $)= d，所以我们介绍的所有产生都将提前d.这给出了

Next, using our second rule, for every production of A, we add in a new item corresponding to that production and with lookaheads of every terminal in FIRST(B$). Since B always produces the string d, FIRST(B$) = d, so all of the productions we introduce will have lookahead d. This gives

S -> .AB ($)
A -> .aAb (d)
A -> .a (d)

现在，让我们构建一个与在此初始状态下看到一个"a"相对应的状态.首先，对于以a:

Now, let's build the state corresponding to seeing an 'a' in this initial state. We start by moving the dot over one step for each production that starts with a:

A -> a.Ab (d)
A -> a. (d)

现在，由于第一个项目在非终结符之前有一个点，因此我们使用规则为A的每个生成添加一个项目，使这些项目先行FIRST(bd)= b.这给出了

Now, since the first item has a dot before a nonterminal, we use our rule to add one item for each production of A, giving those items lookahead FIRST(bd) = b. This gives

A -> a.Ab (d)
A -> a. (d)
A -> .aAb (b)
A -> .a (b)

继续此过程将最终构造此LR(1)解析器的所有LR(1)状态.显示在这里:

Continuing this process will ultimately construct all the LR(1) states for this LR(1) parser. This is shown here:

[0]
S -> .AB  ($)
A -> .aAb (d)
A -> .a   (d)

[1]
A -> a.Ab (d)
A -> a.   (d)
A -> .aAb (b)
A -> .a   (b)

[2]
A -> a.Ab (b)
A -> a.   (b)
A -> .aAb (b)
A -> .a   (b)

[3]
A -> aA.b (d)

[4]
A -> aAb. (d)

[5]
S -> A.B  ($)
B -> .d   ($)

[6]
B -> d.   ($)

[7]
S -> AB.  ($)

[8]
A -> aA.b (b)

[9]
A -> aAb. (b)

如果有帮助，我去年夏天教过一个编译器课程，并且 全部讲座幻灯片可在线获得 .自底向上解析的幻灯片应涵盖LR解析和解析表构造的所有细节，我希望您发现它们有用！

In case it helps, I taught a compilers course last summer and have all the lecture slides available online. The slides on bottom-up parsing should cover all of the details of LR parsing and parse table construction, and I hope that you find them useful!

希望这会有所帮助！

这篇关于LR(1)项目DFA-计算前瞻的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！