为什么我的解析器生成报告说此 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) 可以连接，但它不能这样做所以。当我查看生成的 action 和 goto 表时，我明白了原因：

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

但最让我惊讶的是生成器完成了它的工作并生成了一个运行ning 程序。当我运行这个程序测试数据时，它接受了数据！因此，我的生成器生成了正确的表格。

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

Answer 1

我不知道您的解析器生成器是做什么的，但标准解析器生成器可以处理该语法。例如，这里是野牛的状态转换 table，生成方式：

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 输出。）

这里是稍微编辑过的报告文件（我删除了终端和非终端列表，以及一些空行，以减少使用space。）

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)

Answer 2

我认为问题出在这里：

As you can see states 2 and 6 can't be joined, because there are incompatible items s2 <> s6, s3 <> s7 and so on.

这实际上不太正确。请注意，在状态 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) 状态。

因此，如果您有一个表示 "go to state T on symbol a" 的 LR(1) 状态 S，则对应于 S 的 LR(0) 状态会转换为对应于 T 的 LR(0) 状态，对于 S 将与之合并的任何 LR(1) 状态也是如此。

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

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

Why is my parser generating reporting that this LALR(1) grammar is not LALR(1)?

parsing

lalr