我很难理解如何计算LR(1)项的提前量。
可以说我有这个语法:
S -> AB
A -> aAb | a
B -> d
LR(1)项是具有超前功能的LR(0)项。因此,我们将获得状态0的以下LR(0)项目:
S -> .AB , {lookahead}
A -> .aAb, {lookahead}
A -> .a, {lookahead}
状态:1
A -> a.Ab, {lookahead}
A -> a. ,{lookahead}
A -> .aAb ,{lookahead}
A ->.a ,{lookahead}
有人可以解释如何计算提前量吗?一般的方法是什么?
先感谢您
最佳答案
LR(1)解析器中使用的前瞻计算如下。首先,开始状态具有以下形式的项目
S -> .w ($)
对于每个产品S-> w,其中S是开始符号。此处,$标记表示输入的结尾。
接下来,对于包含形式为A-> x.By(t)的任何状态,其中x是任意的终端和非终端字符串,而B是非终端,则添加形式B-> .w (s)对于每个产品B-> w以及集合FIRST(yt)中的每个终端。 (在这里,FIRST指的是FIRST sets,通常在谈论LL解析器时引入。如果您以前没有看过它们,我将花几分钟查看这些讲义。)
让我们在语法上尝试一下。我们首先创建一个包含以下内容的项目集
S -> .AB ($)
接下来,使用第二条规则,对于A的每个生产,我们都添加一个与该生产相对应的新项目,并在FIRST(B $)中使每个终端提前行。由于B总是产生字符串d,FIRST(B $)= d,所以我们介绍的所有产生都将提前d。这给
S -> .AB ($)
A -> .aAb (d)
A -> .a (d)
现在,让我们建立对应于在此初始状态下看到一个“a”的状态。首先,对于每个以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)
如果有帮助,我去年夏天教了一个编译器类(class),并设置了 all the lecture slides available online 。自底向上解析的幻灯片应涵盖LR解析和解析表构造的所有细节,希望您发现它们有用!
希望这可以帮助!
关于parsing - LR(1)项目DFA-计算前瞻,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14103199/