注：这是递归下降precedence解析缺失preFIX EX pression

我要建一个简单的语言解析器，并有一个问题，较低的precedence preFIX EX pressions。下面是一个例子语法：

I'm building a simple language parser, and having an issue with lower precedence prefix expressions. Here's an example grammar:

E = E8
E8 = E7 'OR' E8 | E7
E7 = E6 'XOR' E7 | E6
E6 = E5 'AND' E6 | E5
E5 = 'NOT' E5 | E4
E4 = E3 '==' E4 | E3 '!=' E4 | E3
E3 = E2 '<' E3 | E2 '>' E3 | E2
E2 = E1 '+' E2 | E1 '-' E2 | E1 '*' E2 | E1 '+' E2 | E1
E1 = '(' E ')' | 'true' | 'false' | '0'..'9'

不过，这种语法不正确的不能正常工作，如果它作为一个更高的precedence缀操作符的右手边，即：

However, this grammar doesn't work correctly for the NOT, if it's used as the RHS of a higher precedence infix operator, i.e.:

true == NOT false

这是由于==操作符要求 E3 在RHS，而不能是不的操作。

This is due to the == operator requiring E3 on the RHS, which cannot be a 'NOT' operation.

我不能确定正确的方法前preSS这个语法？难道还要用这个简单的递归下降的方法，或者我需要移动到更多特色算法（调车场或precedence爬山）。

I'm unsure the correct way to express this grammar? Is it still possible using this simplistic recursive descent approach, or will I need to move to a more featured algorithm (shunting yard or precedence climbing).

下面是一些例子，需要正确地分析：

Here are some examples that would need to parse correctly:

输入真正的== 1＆LT; 2 ，输出 ==（真的，≤（1，2）） 输入 1＆LT; 2 ==真，输出 ==（≤（1，2），真） 输入哪句==假，输出 NOT（==（真，假）） 输入真正的==没有虚假记载，，输出 ==（真的，不是（假）） **没有按'T工作 输入真＆LT;没有虚假记载，，输出≤（真，否则为（false）） **不能正常工作 input true == 1 < 2, output ==(true, <(1, 2)) input 1 < 2 == true, output ==(<(1, 2), true) input NOT true == false, output NOT(==(true, false)) input true == NOT false, output ==(true, NOT(false)) ** doesn't work input true < NOT false, output <(true, NOT(false)) ** doesn't work

我试图改变水平 E4 ， E3 和 E2 使用 E5 上的缀EX pression的RHS，如的递归下降precedence解析缺失preFIX EX pression （即 E3'=='E5 ， E3'＆LT;E5 等）。然而，这打破了这些层次之间的precedence，即真正的== 1＆LT; 2 将不当解析为＆LT;（==（真，1），2）`

I have attempted to alter the levels E4, E3, and E2 to use E5 on the RHS of the infix expression, as suggested in Recursive Descent precedence parsing missing prefix expression (i.e. E3 '==' E5, E3 '<' E5, etc). However this breaks the precedence between these levels, i.e. true == 1 < 2 would be incorrectly parsed as<(==(true, 1), 2)`.

推荐答案

在坚持你的语言的定义方式，你不能有

When sticking to the way your language is defined, you cannot have

true == NOT false 

在您的语言的有效期。因为那时

as a valid term in your language. Because then

NOT false == true

将ambigous：解析树可以是

would be ambigous: the parse tree could be either

    NOT
     | 
    ==
   /  \
false true

或

   ==
  /  \
 NOT true
  |
false

注意

true == NOT (false)

在您的语言的有效期。你的语言中的可能更直观的定义是把不是 -level从 E5 到 E2 。然后

is a valid term in your language. A probably more intuitive definition of your language would be to put the NOT-level from E5 down to E2. Then

true == NOT false 
NOT false == true

都是有效且不是绑定与假。而第二个前pression的另一个意思是pssed为

are both valid and NOT binds with false. And the alternative meaning of the second expression would be expressed as

NOT (false == true)

如果这些选项还是不能满足你，你必须改变/延长刀具。例如。在YACC /野牛解析器允许明确地定义运算符precedences;例如见这里

If these options still do not satisfy you, you have to change/extend the tool. E.g. the yacc/bison parser allows to explicitely define operator precedences; see e.g. here