递归下降precedence解析缺失preFIX EX pression [英] Recursive Descent precedence parsing missing prefix expression

问题描述

我要建一个简单的语言解析器，并有一个问题，较低的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 = E5
E5 = E4 'OR' E4 | E4
E4 = E3 'AND' E3 | E3
E3 = 'NOT' E3 | E2
E2 = E1 '==' E1 | E1
E1 = '(' E ')' | 'true' | 'false'

不过，这种语法不正确的不是，如果它作为一个更高的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

这是由于 == 运营商需要E1在RHS，不能是一笔不操作。

This is due to the == operator requiring E1 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).

推荐答案

假设下面的输入和预期的解析是正确的：

Assuming the following input and expected parses are correct:

1. 在测试1
   • 输入：真正的==没有虚假记载，
   • 输出：（真==（不假））

1. test 1
   • input: true == NOT false
   • output: (true == (NOT false))

• 输入：哪句==假
• 输出：（NOT（真== FALSE））

• input: NOT true == false
• output: (NOT (true == false))

• 输入：哪句==没有虚假记载，
• 输出：（NOT（真==（不是假的）））

• input: NOT true == NOT false
• output: (NOT (true == (NOT false)))

下面是一个（ANTLR4）语法，做的伎俩：

Here's an (ANTLR4) grammar that does the trick:

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创建的：

Parses ANTLR created:

这篇关于递归下降precedence解析缺失preFIX EX pression的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！