为什么我的解析器生成报告说这个LALR(1)语法不是LALR(1)？

Question

好的，我继续我的解析器生成器的冒险。这一次，我掌握了一种经典语法，据说这是一种LALR语法：

start -> a a
a -> "A" a
a -> "B"

当我将它放入解析器生成器时，它会给出输出：

LIST OF STATES:
-----------------------
<0: S' -> . start , $
start -> . a a , $
a -> . "A" a , "A" / "B"
a -> . "B" , "A" / "B"
{NTerm(start): 1, Term(A): 2, Term(B): 3, NTerm(a): 4}>(3104365621624877555)

--------------------
<1: S' -> start .  , $
{}>(3969511602615904846)

--------------------
<2: a -> "A" . a , "A" / "B"
a -> . "A" a , "A" / "B"
a -> . "B" , "A" / "B"
{Term(A): 2, Term(B): 3, NTerm(a): 5}>(5490562805113673592)

--------------------
<3: a -> "B" .  , "A" / "B"
{}>(-4845209343945471034)

--------------------
<4: start -> a . a , $
a -> . "A" a , $
a -> . "B" , $
{Term(A): 6, Term(B): 7, NTerm(a): 8}>(598157158659875896)

--------------------
<5: a -> "A" a .  , "A" / "B"
{}>(436327415052220213)

--------------------
<6: a -> "A" . a , $
a -> . "A" a , $
a -> . "B" , $
{Term(A): 6, Term(B): 7, NTerm(a): 9}>(5490562805113673592)

--------------------
<7: a -> "B" .  , $
{}>(-4845209343945471034)

--------------------
<8: start -> a a .  , $
{}>(5795088700656730485)

--------------------
<9: a -> "A" a .  , $
{}>(436327415052220213)

POSSIBLE STATES TO JOIN: (2, 6), (3, 7), (5, 9)
ATTEMPTING CONVERSION TO LALR GRAMMAR...FAILED
CONTINUING WITH CLR(1)...

这些状态与我在其他资源中可以看到的编译LALR语法的内容相匹配--这个步骤看起来没问题，它会产生正确的状态，就像我手工完成它一样。生成器建议--同样是其他消息来源所说的将CLR(1)语法转换为LALR --声明可以加入(2,6)、(3,7)、(5,9)，但它无法这样做。当我查看生成的动作和goto表时，我可以看出为什么：

​

​

如您所见，状态2和6不能连接，因为存在不兼容的项s2 <> s6、s3 <> s7等等。

但最令我惊讶的是，发电机完成了工作，并产生了一个运行程序。当我在测试数据上运行这个程序时，它接受数据！所以，我的发电机产生了正确的表。

这是否意味着这种经典的" LALR“语法只有在人类手工编译时才是LALR？我的解析器生成器有什么不同？

Answer 1

我认为问题在于：

您可以看到，

状态2和6不能连接，因为存在不兼容的项s2 <> s6、s3 <> s7等等。

其实这并不完全正确。请注意，在状态2中，shift项分别带您进入状态2和状态3。在状态6中，shift项分别带您进入6和7状态。但是那里没有不兼容性，因为您试图将状态2和状态6合并在一起，并将状态3和状态7合并在一起。换句话说，是的，这些变化现在说要去不同的地方，但是当你把所有拥有相同核心的国家一起崩溃之后，你最终会和他们一起说去同一个地方。

更广泛地说，我不认为合并两个LR(1)状态会引入"shift/shift“冲突。要了解为什么会这样，请注意每个LR(1)状态对应于LR(0)解析器中的状态，但每个LR项都使用一组查找项进行注释。在从LR(1)到LALR(1)的过程中，您在将LR(1)状态与忽略外观的相同项结合在一起，这意味着您实际上是将与相同LR(0)状态相对应的LR(1)状态组合在一起。

因此，如果有一个LR(1)状态S，它表示“转到符号a上的状态T”，那么对应于S的LR(0)状态有一个与T对应的LR(0)状态的转换，对于任何将与S合并的LR(1)状态也是如此。

在构建LALR(1)解析器过程中可能出现的唯一冲突是减少/减少冲突，这是您需要警惕的。

Answer 2

我不知道解析器生成器是做什么的，但是标准的解析器生成器在语法方面没有问题。例如，这里是bison的状态转换表，它是用以下方法生成的：

bison --report-file=aa.output --report=all --graph=aa.dot --output=/dev/null \
      <(printf "%%%%\n%s" "start: a a; a: 'A' a | 'B'")
dot -o aa.png -Tpng aa.dot

(Bison是一个非常方便的工具；即使您正在编写自己的解析器生成器，也可以利用它的功能。还请参见其XML输出。)

​

下面是稍微编辑过的报告文件(我删除了终端和非终端的列表，以及一些空白行，以减少空间)。

Grammar

    0 $accept: start $end
    1 start: a a
    2 a: 'A' a
    3  | 'B'

State 0
    0 $accept: . start $end
    1 start: . a a
    2 a: . 'A' a
    3  | . 'B'

    'A'  shift, and go to state 1
    'B'  shift, and go to state 2

    start  go to state 3
    a      go to state 4

State 1
    2 a: . 'A' a
    2  | 'A' . a
    3  | . 'B'

    'A'  shift, and go to state 1
    'B'  shift, and go to state 2

    a  go to state 5

State 2
    3 a: 'B' .

    $default  reduce using rule 3 (a)

State 3
    0 $accept: start . $end

    $end  shift, and go to state 6

State 4
    1 start: a . a
    2 a: . 'A' a
    3  | . 'B'

    'A'  shift, and go to state 1
    'B'  shift, and go to state 2

    a  go to state 7

State 5
    2 a: 'A' a .

    $default  reduce using rule 2 (a)

State 6
    0 $accept: start $end .

    $default  accept

State 7
    1 start: a a .

    $default  reduce using rule 1 (start)