reduce/reduce 野牛语法冲突

Question

以下 bison 语法产生 reduce/reduce 冲突：

%token LEFT_PARENTHESIS
%token RIGHT_PARENTHESIS
%token NAME
%token RELATION_INFIX

%%

formula:
  term RELATION_INFIX term 
| NAME
| LEFT_PARENTHESIS formula RIGHT_PARENTHESIS
;

term:
  NAME
| LEFT_PARENTHESIS term RIGHT_PARENTHESIS
;

我没看出歧义在哪里。 LEFT_PARENTHESIS NAME RIGHT_PARENTHESIS一定是公式，因为没有RELATION_INFIX.

bison 详细输出的开头是

State 0

    0 $accept: . formula $end

    LEFT_PARENTHESIS  shift, and go to state 1
    NAME              shift, and go to state 2

    formula  go to state 3
    term     go to state 4


State 1

    3 formula: LEFT_PARENTHESIS . formula RIGHT_PARENTHESIS
    5 term: LEFT_PARENTHESIS . term RIGHT_PARENTHESIS

    LEFT_PARENTHESIS  shift, and go to state 1
    NAME              shift, and go to state 2

    formula  go to state 5
    term     go to state 6


State 2

    2 formula: NAME .
    4 term: NAME .

    RIGHT_PARENTHESIS  reduce using rule 2 (formula)
    RIGHT_PARENTHESIS  [reduce using rule 4 (term)]
    RELATION_INFIX     reduce using rule 4 (term)
    $default           reduce using rule 2 (formula)

所以好像被RIGHT_PARENTHESIS搞糊涂了。而且各州似乎接受 NAME RIGHT_PARENTHESIS，即使语法要求在 LEFT_PARENTHESIS 之前。

有什么想法吗？

编辑

上面的语法被简化以关注 reduce/reduce 冲突。我的真正意图是解析一阶逻辑公式：术语是运算符的组合，公式是术语关系的逻辑组合（不是，和，或，暗示）。

术语和公式有时是很长的表达式，所以我们给它们起名字以便于调用它们。所有名称最终都会扩展到它们的连接器和运算符树，稍后在程序中（而不是在 bison 解析器中）。

终端符号中有变量（逻辑建模的对象）；公式是关于这些对象的陈述。它类似于 C++ 中的类型和函数：可以对所有类型和函数使用相同的命名方案。

Answer 1

按照您的语法 LEFT_PARENTHESIS NAME RIGHT_PARENTHESIS 可能匹配公式或术语。

由于它涉及减少特定状态下的输入，因此不能保证成功（在 NAME RIGHT_PARENTHESIS 表达式的情况下也不会）。状态进展表示这是唯一可能的明确方向。从语法的角度来看，在不正确的输入上失败并不是一个断点。但是有几个 reduce 替代品肯定是。

Answer 2

没有歧义。这并不意味着没有解析冲突。

LR(k) 解析器无法解析歧义文法；试图生成解析自动机必然会失败，因为同一个句子存在两种不同的推导。但反之则不然。有冲突的文法可能有歧义，也可能没有歧义。 [注1]

要通过 LR(k) 语法解析，每个非终结符都需要在读取超过 k 个符号之前解析。

所以，虽然你说得很对

LEFT_PARENTHESIS NAME RIGHT_PARENTHESIS must be a formula, because there is no RELATION_INFIX.

这并不能说明全部情况。对于 LEFT_PARENTHESIS NAME RIGHT_PARENTHESIS 是 formula，NAME 也必须是 formula，并且 NAME 到 formula 的减少必须在 1 个符号内发生（因为 k 在 bison LR 解析器中总是一个）。但是只读NAME后面的一个符号，是不可能知道“没有RELATION_INFIX”的。因此减少-减少冲突。

如果我对你的理解正确，你所拥有的基本上是一个表达式语法，其中有两种类型的表达式（“公式”和“术语”）具有不同的运算符，其中标识符可以是原始变量或名称任一类型的表达式。一个限制是“术语”运算符的操作数只能是“术语”，而“公式”运算符的操作数可以是“公式”或“术语”。（这没有反映在简化的语法中，它不允许 term AND (term AND term) （带或不带括号）；我只是假设它是需要的，因为否则公式不可能复杂，但是你的注意说他们经常是。）

如果短语包含可见运算符，则句法类别（“公式”或“术语”）很明显，但仅由标识符组成的句法短语可能被多余的括号包围，可以是“术语” ”或“公式”。这使得在不知道每个标识符的句法类别的情况下基本上不可能在句法上完全表达限制。

如果在第一次使用标识符之前知道每个标识符的句法类别，则可以使用词法反馈来允许在解析期间完全执行限制。否则，或者如果词法反馈被认为是不可取的，则有必要在随后的语义分析过程中验证包含标识符的任何子表达式，也许是扩展宏标识符的同一子表达式。

由于无论如何都需要进行语义检查，因此也很容易检查 formula 永远不是 term 运算符的操作数。在那种情况下，可以使用普通的表达式语法，包括正常使用优先级声明来简化表示。该语法将直接为任何正确的输入生成正确的 AST；语义检查只需要拒绝不正确的输入。以这种方式进行检测还有助于生成信息性错误消息。恕我直言，这个解决方案的缺点真的很少。

但是，编写一个语法来表达对名称以外的情况的句法限制也是相当直接的。诀窍是使用 three 表达式类型，因为确实存在三种句法类别，如上面的讨论所示：

明显的公式
明显的条款
可能是公式或术语的短语（即可能带括号的名称）

正确使用带括号的子表达式有点烦人，而且会使语法混乱。在我看来，没有真正的好处。但是如果你想尝试这个，这里有一个简单的例子，只使用一个术语运算符和一个公式运算符以及将显式 check/conversion 操作插入 AST 的样本缩减操作：

formula: formula_not_term
       | term_not_name     { $$ = mkform("TERM->FORM", , NULL); }
       | name              { $$ = mkform("NAME->FORM", , NULL); }
formula_not_term
       : formula FORMULA_OPERATOR formula
                           { $$ = mkform("FORM_OP", , ); }
       | '(' formula_not_term ')'
                           { $$ = ; }
term   : term_not_name
       | name              { $$ = mkterm("NAME->TERM", , NULL); }
term_not_name
       : term TERM_OPERATOR term
                           { $$ = mkterm("TERM_OP", , ); }
       | '(' term_not_name ')'
                           { $$ = ; }
name   : NAME
       | '(' name ')'      { $$ = ; }

备注

确定文法是否有歧义是不可判定的，这意味着不存在可以肯定地回答任何文法问题的算法。如果所有有歧义的文法都产生了 LR(1) 解析冲突，您可以使用 LR(1) 解析器构造来检测歧义，这将与不可判定性相矛盾。因此，期望找到产生解析冲突的明确语法。

reduce/reduce 野牛语法冲突

reduce/reduce conflict in bison grammar

bison

备注