LR(1)项目DFA - 计算前瞻

Question

我无法理解如何计算LR(1)-items的前瞻.

让我们说我有这个语法:

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

LR(1)-item是具有前瞻的LR(0)项.所以我们将为状态0得到以下LR(0)-item:

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

州:1

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

有人可以解释如何计算前瞻吗？一般方法是什么？

先感谢您

Answer 1

LR(1)解析器中使用的前瞻计算如下.首先,开始状态有一个表单项

S -> .w  ($)

对于每个生产S - > w,其中S是起始符号.这里,$ marker表示输入的结束.

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

让我们试试你的语法.我们首先创建一个包含的项目集

S -> .AB ($)

接下来,使用我们的第二条规则,对于A的每次生产,我们添加一个与该生产相对应的新项目,并在FIRST(B $)中查看每个终端的前瞻.由于B总是产生字符串d,FIRST(B $)= d,因此我们引入的所有产品都将具有前瞻性.这给了

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

现在,让我们构建对应于在此初始状态中看到'a'的状态.我们首先将每个生产点的一个点移动一步:

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

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

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

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

[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解析和解析表构造的所有细节,我希望你发现它们很有用!

希望这可以帮助!