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

标签 parsing context-free-grammar lookahead dfa lr

我很难理解如何计算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/

相关文章:

c - 在C glib中解析url查询参数?

iphone - 使用 CHCSVParser 的基础介绍

c# - 搜索百分比字符串

regex - 需要一个正则表达式来匹配不能全为零的可变长度数字字符串

regex - 正则表达式匹配字符串-正向提前

python - 为什么 readlines() 读取的内容比 sizehint 多得多?

parsing - LALR解析器生成器实现问题

c++ - LBNF、C函数声明/定义、reduce减少冲突

JavaScript 语法符号

java - 正则表达式匹配计时器与 h :m:s