algorithm - 递归下降优先级解析缺失前缀表达式

Question

我正在构建一个简单的语言解析器，但遇到了低优先级前缀表达式的问题。这是一个示例语法:

E = E5
E5 = E4 'OR' E4 | E4
E4 = E3 'AND' E3 | E3
E3 = 'NOT' E3 | E2
E2 = E1 '==' E1 | E1
E1 = '(' E ')' | 'true' | 'false'

但是，如果将 NOT 用作更高优先级中缀运算符的 RHS，则此语法无法正常工作，即:

true == NOT false

这是由于 == 运算符要求 RHS 上的 E1，这不能是 NOT 运算。

我不确定表达这种语法的正确方法？是否仍然可以使用这种简单的递归下降方法，或者我是否需要转向更具特色的算法(调车场或优先攀登)。

Answer 1

假设以下输入和预期的解析是正确的:

1. 测试 1
   • 输入:true == NOT false
   • 输出:(true == (NOT false))
2. 测试 2
   • 输入:不是 true == false
   • 输出:(NOT (true == false))
3. 测试 3
   • 输入:NOT true == NOT false
   • 输出:(NOT (true == (NOT false)))

这是一个可以解决问题的 (ANTLR4) 语法:

grammar Expr;

e : e5;
e5 : e4 'OR' e5 | e4;
e4 : e3 'AND' e4 | e3;
e3 : 'NOT' e3 | e2;
e2 : e1 '==' e3 | e1;
e1 : '(' e ')' | 'true' | 'false';

S : [ \t\r\n] -> skip;

解析 ANTLR 创建的:

1

2

3