0

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

这是我语法的一部分：

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

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

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


element
    : VAR
    | INT
    | GREEK
    | math
;

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

谢谢！

4

1 回答 1

0

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

让我们考虑一个类似的表达式a + b + c。在您的原始语法中，您有math binop math. 鉴于a+b+c，它应该将其视为aa math、+is abinop和b+cis another math，还是应该将其视为a+b数学、+is abinop和cis a math（然后将math命名a+b进一步分解为a、+和b）？从稍微不同的角度来看，应该a + b + c被解析为(a + b) + c或a + (b + c)? 在这种情况下，+它没有任何真正的区别——但对于-（举一个明显的例子）来说，它确实有所作为。

根据您的第一个语法，任何一个都可以接受。事实上，即使是你的第二个，也可以接受（但是通过使element某种...从属于math，你已经隐含地为 yacc 提供了一些关于如何解析它的指导）。

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

这就留下了一个相当基本的问题。我们要如何处理不同运算符的优先级？例如，至少在通常的方案中，我们希望*and/具有比+or更高的优先级-。

在 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
       ;

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

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

于 2015-10-25T05:10:15.813 回答