LR(1) 项DFA - 计算展望符

Question

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

有人能解释一下如何计算向前看符号吗？一般的方法是什么？

提前谢谢。

- mrjasmin

Answer 1

LR（1）分析器中使用的前瞻符号计算如下。首先，起始状态具有以下形式的项目：

S -> .w  ($)

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

接下来，对于任何包含形如A -> x.By(t)的项目的状态，其中x是任意终结符和非终结符的字符串，B是一个非终结符，您需要为每个产生式B -> w和FIRST(yt)集合中的每个终结符添加一个形如B -> .w(s)的项目。(这里，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分析和语法分析表构建的所有细节，希望你会发现它们很有用！希望这可以帮到你！

- templatetypedef

---

@mrjasmin- 我需要看到更多的语法才能知道FIRST和lookahead集应该是什么; 你能发帖子吗？此外，请注意，您不应在任何地方计算FIRST($A)。如果您有A -> .AA ($), 那么产生的项的lookahead将是FIRST(A$)中的终端符号，而不是FIRST($A)。这样有帮助吗？ - templatetypedef

@mrjasmin- 不，这两个符号后面不应该跟着$。产生式S -> AB意味着A产生的项以FIRST(B$)开头，它只是d。第二种情况中使用$向前看的原因是，产生式S -> A在A之后没有任何内容，所以向前看是FIRST($)，它只是$。 - templatetypedef

@tgoneil 我第一次错过了其中两个状态 - 感谢你的指出！至于第三个状态 - 看起来你通过添加一个产生式 S' -> S 来增强语法，而我没有这样做，所以我认为第三个状态取决于你是否这样做。 - templatetypedef

@snb 生成LALR(1)解析器通常需要使用FOLLOW集。然而，这个问题是关于LR(1)解析的，通常情况下LR(1)解析器是使用FIRST集合而不是FOLLOW集合创建的。 - templatetypedef

@snb 不用担心！LR分析通常按照LR(0)、SLR(1)、LR(1)、LALR(1)的顺序进行教学，尽管有时会看到LALR(1)和LR(1)互换。需要一些练习才能掌握它们！ - templatetypedef

Answer 2

以下是翻译的结果：

这是该文法的LR(1)自动机，上面已经进行了相应操作。

我认为尝试绘制自动机并展示流程能够更好地理解，这将使向前看符号的概念更加清晰。

- M.Alamer

Answer 3

我也得到了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 .

- tgoneil

Answer 4

你构建的LR(1)项集应该再增加两个项。

I8 A--> aA.b , b 来自 I2

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

- Ajay