前缀表示法中的算术表达式语法(Java Cup)

Question

我正在为前缀表示法中的算术表达式编写语法。然而，我在解析负数或子字符串时遇到了一个问题。语法示例如下：

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处给我一个语法错误。正确的应该是5作为E，接下来是4作为E，然后是- E E作为E。如何使用关联性解决此问题？还是我需要重写语法？

Answer 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))

Answer 2

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

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

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

请检查以上几次，因为我已经生疏了。