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
   • 输入：NOT 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

Answer 2

您的语言也（不必要地）模棱两可。修复它也可以帮助您解决此问题。

在这里，D是“析取”的简写，是合取的简写C，N是否定的简写P，主要E是相等的简写。

D = C | C 'OR'  D
C = N | N 'AND' C
N = E |   'NOT' N
E = P | P '=='  P
P = '(' E ')' | 'true' | 'false'

Answer 3

也许使用波兰符号？

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