0

我正在用前缀表示法编写算术表达式的语法。但是，在解析负数或减法时我遇到了问题。语法示例是这样的：

precedence right +, -;
precedence right *, /;
precedence right uminus;

E ::= + E E
   |  - E E
   |  * E E
   |  / E E
   |  ( E )
   |  - E %prec uminus
   |  id
   |  digit
   ;

但是，如果我的输入是- 5 4，它会减少5为E，然后它会减少- E（负数），然后解析器会在 处给我一个语法错误4。正确的应该是5as E, next 4asE和- E Eas E。如何使用关联性解决这个问题？还是我需要重写我的语法？

4

2 回答 2

1

（从评论中提升）

您的语法确实模棱两可，优先声明对您没有一点帮助。

考虑输入，输入由N -标记组成，然后是M 1标记。

- - - - - - - ... - 1 1 1 ... 1

为了使它成为一个表达式，标记必须是二进制的，其余M-1的必须是一元的，但是没有办法分辨哪个是哪个（除非它们都是二进制的）。-N-(M-1)

即使你随意说第一个N-(M-1) -s 是一元的，在你读取整个输入之前你也无法知道它的值N-(M-1)是什么，这意味着你不能用有限的前瞻来解析。

但是前缀表示法的全部意义在于避免使用括号。像上面这样的任意声明使得无法表示替代解释，因此某些表达式不可能用前缀表示法表示。那是完全错误的。

这是一个简单的案例：

- 5 - - - 4 3 1

或者是

5 - (- (4 - (3 - 1)))
5 - ((- (4 - 3)) - 1)
5 - (((- 4) - 3) - 1)

在前缀表示法中，您需要声明每个运算符的“arity”，或者隐式（每个运算符都有已知数量的参数），或者显式使用从 Prolog 借来的这样的表示法：

-/2 5 -/2 -/2 -/1 4 3 1

或者，您可以使用强制括号分隔参数，如 Lisp/Scheme "s-exprs"：

(- 5 (- (- (- 4) 3) 1))
于 2013-09-01T04:57:31.107 回答
0

首先，删除所有优先级声明。前缀语法中不需要它们。事实上，这应该足以解决任何解析器生成器中的问题。顺便说一句，您使用的是哪一个？

Cup 有一个有限的前瞻。正如@rici 指出的那样，在这种情况下无法解决歧义。您可以做的是限制语法，以便只能-使用一个连续的一元。

    B ::= E
       |  - E
       ;
    E ::= + B B
       |  - B B
       |  * B B
       |  / B B
       |  ( B )
       |  id
       |  digit
       ;

请检查以上几次，因为我很生疏。

于 2013-09-01T01:49:03.280 回答