奇怪的 Shift/Reduce 明确的（我认为）语法冲突

Question

所以在我的语言中我想要点语法表达式：

myObject.myProperty
myObject.myProperty.subProperty

我想要声明

Object myObject = 1

此外，对象类型可以命名空间：

Object.SubObject mySubObject = 1

简化语法如下：

program:
    declaration;
    | expression;

declaration: 
    TOKEN_IDENTIFIER TOKEN_IDENTIFIER '=' TOKEN_INTEGER;
    | TOKEN_IDENTIFIER '.' TOKEN_IDENTIFIER TOKEN_IDENTIFIER '=' TOKEN_INTEGER;

expression:
    TOKEN_IDENTIFIER;
    | expression '.' TOKEN_IDENTIFIER;

不幸的是，用 Bison 编译这个语法会产生移位归约冲突。查看状态机输出，在我看来，Bison 解释它的方式存在错误。下面是状态1，也就是读取第一个标识符后的状态：

State 1

    3 declaration: "identifier" . "identifier" '=' "integer"
    4            | "identifier" . '.' "identifier" "identifier" '=' "integer"
    5 expression: "identifier" .

    "identifier"  shift, and go to state 5
    '.'           shift, and go to state 6

    "end of code"  reduce using rule 5 (expression)
    '.'            [reduce using rule 5 (expression)]

而状态6（读取点时的默认移位状态）仅用于声明：

State 6

    4 declaration: "identifier" '.' . "identifier" "identifier" '=' "integer"

    "identifier"  shift, and go to state 10

在我看来，在状态 1 中，应该不可能在读取点时减少。它应该向前看，如果它看到两个紧接着的标识符（中间没有点），它应该转移到仅声明状态，但如果它看到第二个点或代码结尾，它就会减少到表达式.事实上，声明规则是唯一可以并排找到两个标识符且中间没有点的实例，这一事实应该可以消除语法歧义，因此不会出现移位归约错误。

我用 ielr 和 canonical-lr 试过了，结果相同（不知道这是否重要）。

有什么想法吗？我对它应该如何工作的解释不正确吗？

Answer 1

It should look ahead, and if it sees two identifiers right after each other …

LALR(1)中的1表示"one token of lookahead"。所以解析器不会在前瞻中看到两个紧接着的标识符，因为它只能看到一个标识符。

I thought the ielr option was supposed to fix that.

没有。 ielr 解析器是 LR(1)（几乎）。 canonical-lr 是 LR(1)（准确）。在所有情况下，它都是相同的 1.

简单的解决方案是使用 GLR 解析器 (%glr-parser)，它不限于一个先行标记，因为它根本不使用先行。相反，它会并行维护所有可能的解析堆栈，直到它找到一种方法来确定哪个是有效的，或者它知道无法解决歧义。显然，保留多个堆栈会降低性能，但它可能不会成为编译器的瓶颈。 GLR 解析器无需修改即可处理任何明确的语法，并且在大多数情况下也不需要修改解析器操作，因此它通常是一个不错的选择。

否则，您可以添加 "seemingly redundant" 产生式（该短语来自流行的编译器文本）：

expression: TOKEN_IDENTIFIER
          | compound_expression
compound_expression
          : TOKEN_IDENTIFIER '.' TOKEN_IDENTIFIER
          | compound_expression '.' TOKEN_IDENTIFIER

不过，该解决方案并不总能很好地扩展到更复杂的语法。

Answer 2

在 LALR(1) 解析器中处理这类事情的正常方法是找出导致冲突的表达式和声明之间的共同点。在您的情况下，这是一个可选范围的名称，它可以是声明中的类型名称，也可以是表达式中的字段引用。所以你重构为

name: TOKEN_IDENTIFIER
    | name '.' TOKEN_IDENTIFIER

declaration: name TOKEN_IDENTIFIER '=' expression

expression: name
          | ... other expression rules

之所以可行，是因为它现在可以只识别开头的 name，而不关心它是 declaration 还是 expression 的开头——决定被推迟，直到它看到完整 name.

之后的下一个标记

请注意，如果您的规则允许两个连续的表达式且它们之间没有标记，这仍然会失败。

此外，此语法与您的原始语法略有不同，因为它允许在声明中进行多级范围界定，例如

Object.SubObject.SubSubObject mySubSubObject = 1

而您的语法只允许 0 或一个范围级别。

奇怪的 Shift/Reduce 明确的（我认为）语法冲突

Weird Shift/Reduce Conflict for Unambiguous (I think) Grammar

bison