如何解决这种有歧义的语法？

Question

我正在创建一个编译器，我正在使用 lex 和 bison。

这是我语法的一部分：

math
    : math binop math
    | VAR
    | INT
    | GREEK
    | "(" math ")"
    | math comp math
    | "-" math
    | math math
    | "\sqrt" "{" math "}"
;

我已将上面的内容更改为此，但它增加了 reduce/reduce 错误的数量。它减少了 shift/reduce 错误的数量。

math
    : math binop element
    | VAR
    | INT
    | GREEK
    | "(" math ")"
    | math comp element
    | "-" element
    | math element
    | "\sqrt" "{" element "}"
;


element
    : VAR
    | INT
    | GREEK
    | math
;

有什么办法可以让他们都减少吗？

谢谢！

Answer 1

您已经朝着正确的总体方向迈出了一点点，但也许最好退一步思考一下事情是如何开始的，以及如何将其应用于实际表达。

让我们考虑像 a + b + c 这样的表达式。在你原来的语法中，你有 math binop math。鉴于 a+b+c，它是否应该将其视为 a 是一个 math，+ 是一个 binop，而 b+c 是另一个 [=17] =]，还是应该将其视为 a+b 是数学，+ 是 binop，c 是数学（然后是 math a+b进一步细分为a、+和b）？从稍微不同的角度来看，a + b + c 应该解析为 (a + b) + c 还是 a + (b + c)？在 + 的情况下，它没有任何真正的区别——但是对于 -（对于一个明显的例子），它确实有区别。

根据你的第一个语法，任何一个都可以接受。事实上，即使是你的第二个，也可以接受（但是通过使 element 有点......从属于 math，你已经隐含地给了 yacc 一些关于解析它的方式的指导).

这将我们带到下一点：您（认为您）在什么情况下需要使用 math binop math 生产？如果我们定义一个 math 来解析任意复杂度的表达式，那么 element 是否可以限制为基本上是单个操作数？如果我们这样做，那么像 a + b + c 这样的每个表达式都必须解析为 math binop operand，对吗？在这种情况下没有歧义（并且 a+b 部分将进一步解析为 operand binop operand.

剩下一个相当基本的问题。我们要如何处理不同运算符的优先级？例如，至少在通常的方案中，我们希望 * 和 / 的优先级高于 + 或 -.

在像 yacc 这样的东西中，有（至少）两种根本不同的处理方式。一个是在语法中，通过定义几个不同类型的子表达式：

add_expr : mul_expr '+' mul_expr
         | mul_expr '-' mul_expr
         ;

mul_expr : factor '*' factor
         | factor '/' factor
         ;

另一种是在指令中设置优先级，如：

%left '+' '-'
%left '*' '/'
%left UNARYMINUS

这让我们让语法本身保持歧义，然后告诉解析器生成器如何解决歧义。

所以，使用这个，我们可以得到类似的东西：

expr : expr '+' operand
     | expr '-' operand
     | expr '*' operand
     | expr '/' operand
     ;

operand: VAR
       | INT
       | '(' expr ')'
       | '-' expr %prec UNARYMINUS
       ;

最后一位（%prec UNARYMINUS）告诉它将 -（在本例中）视为具有我们在上面为 UNARYMINUS 指定的优先级（我们定义的最高优先级，因为这是列表中的最后一个）。

我没有尝试涵盖您的整个语法，但我认为这至少涵盖了您可能需要（或至少想要）应用于的大部分基本转换消除大部分歧义。可能还值得注意的是 shift/reduce 冲突通常是相当无害的。解析器生成器为这种情况提供的解决方案通常会很好地工作，并且在某些情况下，这种有歧义的语法实际上会比解决所有歧义的语法更有效，所以相当多的语法不会尝试修复所有的歧义他们。

如何解决这种有歧义的语法？

How to solve this ambiguous grammar?

bison

yacc

flex-lexer

context-free-grammar

ambiguous-grammar