21

我很难理解如何计算 LR(1) 项的前瞻。

可以说我有这个语法：

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}

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

先感谢您

4

4 回答 4

35

LR(1) 解析器中使用的前瞻计算如下。首先，开始状态有一个项目的形式

S -> .w  ($)

对于每个产生式 S -> w，其中 S 是开始符号。这里，$ 标记表示输入的结束。

接下来，对于包含 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，所以我们介绍的所有产生式都会有前瞻 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)

如果有帮助，我去年夏天教了一个编译器课程，并在网上提供了所有的讲座幻灯片。自底向上解析的幻灯片应该涵盖了 LR 解析和解析表构建的所有细节，希望对您有用！

希望这可以帮助！

于 2013-01-02T18:35:35.163 回答
4

这是语法的 LR(1) 自动机，因为上面已经完成了以下操作

这是语法的自动机

于 2015-03-14T06:55:52.080 回答
0

你构建的 LR(1) 项集应该还有两个项。

I8 A--> aA.b ，来自 I2 的 b

I9 A--> aAb。, b 来自 I8

于 2013-04-03T06:39:30.287 回答
0

我也得到 11 个州，而不是 8 个：

State 0
        S: .A B ["$"]
        A: .a A b ["d"]
        A: .a ["d"]
    Transitions
        S -> 1
        A -> 2
        a -> 5
    Reductions
        none
State 1
        S_Prime: S .$ ["$"]
    Transitions
        none
    Reductions
        none
State 2
        S: A .B ["$"]
        B: .d ["$"]
    Transitions
        B -> 3
        d -> 4
    Reductions
        none
State 3
        S: A B .["$"]
    Transitions
        none
    Reductions
        $ => S: A B .
State 4
        B: d .["$"]
    Transitions
        none
    Reductions
        $ => B: d .
State 5
        A: a .A b ["d"]
        A: .a A b ["b"]
        A: .a ["b"]
        A: a .["d"]
    Transitions
        A -> 6
        a -> 8
    Reductions
        d => A: a .
State 6
        A: a A .b ["d"]
    Transitions
        b -> 7
    Reductions
        none
State 7
        A: a A b .["d"]
    Transitions
        none
    Reductions
        d => A: a A b .
State 8
        A: a .A b ["b"]
        A: .a A b ["b"]
        A: .a ["b"]
        A: a .["b"]
    Transitions
        A -> 9
        a -> 8
    Reductions
        b => A: a .
State 9
        A: a A .b ["b"]
    Transitions
        b -> 10
    Reductions
        none
State 10
        A: a A b .["b"]
    Transitions
        none
    Reductions
        b => A: a A b .
于 2015-10-29T07:33:02.817 回答