如何解决这个模棱两可的语法？(How to resolve this ambiguous grammar?)

如何解决这个模棱两可的语法？(How to resolve this ambiguous grammar?)

我写过这样的语法：

expr : multExpr ( ('+' | '-') multExpr )*; multExpr : atom ( ('*' | '/') atom )*; atom : INT | FLOAT | ID | '(' expr ')'; condition : cond ('or' cond)*; cond : c1 ('and' c1)*; c1 : ('not')? c2; c2 : '(' condition ')' | boolean; boolean : expr (relop expr | ²) | 'true' | 'false'; relop : '<' | '<=' | '>' | '>=' | '==' | '!=';

我已经省略了INT，FLOAT，ID的词法规则，因为它很明显。

问题在于c2规则，由于'（'，我找不到解决方案，您能否提供解决方案？

I have written this grammar:

expr : multExpr ( ('+' | '-') multExpr )*; multExpr : atom ( ('*' | '/') atom )*; atom : INT | FLOAT | ID | '(' expr ')'; condition : cond ('or' cond)*; cond : c1 ('and' c1)*; c1 : ('not')? c2; c2 : '(' condition ')' | boolean; boolean : expr (relop expr | ²) | 'true' | 'false'; relop : '<' | '<=' | '>' | '>=' | '==' | '!=';

I have omitted the lexer rules for INT,FLOAT,ID as it is obvious.

The problem is c2 rule, it is ambiguous because of '(', I could not find the solution, can you offer me a solution?

最满意答案

为什么不简单地做：

expr : orExpr; orExpr : andExpr ('or' andExpr)*; andExpr : relExpr ('and' relExpr)*; relExpr : addExpr (relop addExpr)?; relop : '<' | '<=' | '>' | '>=' | '==' | '!='; addExpr : multExpr (('+' | '-') multExpr)*; multExpr : unaryExpr (('*' | '/') unaryExpr)*; unaryExpr : 'not'? atom; atom : INT | FLOAT | ID | 'true' | 'false' | '(' expr ')';

一元通常not比你现在要做的更高的优先级。

这将允许像42 > true这样的表达式，但是当你行走AST /树时检查这样的语义。

编辑

输入"not(a+b >= 2 * foo/3.14159) == false"现在将被解析为这样（忽略空格）：

如果将输出设置为AST，并将其混合到某些树重写操作符（ ^和! ）中：

options { output=AST; } // ... expr : orExpr; orExpr : andExpr ('or'^ andExpr)*; andExpr : relExpr ('and'^ relExpr)*; relExpr : addExpr (relop^ addExpr)?; relop : '<' | '<=' | '>' | '>=' | '==' | '!='; addExpr : multExpr (('+' | '-')^ multExpr)*; multExpr : unaryExpr (('*' | '/')^ unaryExpr)*; unaryExpr : 'not'^ atom | atom; atom : INT | FLOAT | ID | 'true' | 'false' | '('! expr ')'!;

你会得到：

Why not simply do:

expr : orExpr; orExpr : andExpr ('or' andExpr)*; andExpr : relExpr ('and' relExpr)*; relExpr : addExpr (relop addExpr)?; relop : '<' | '<=' | '>' | '>=' | '==' | '!='; addExpr : multExpr (('+' | '-') multExpr)*; multExpr : unaryExpr (('*' | '/') unaryExpr)*; unaryExpr : 'not'? atom; atom : INT | FLOAT | ID | 'true' | 'false' | '(' expr ')';

The unary not usually has a higher precedence than you're trying to do now.

This will allow for expressions like 42 > true, but checking such semantics can come when you're walking the AST/tree.

EDIT

The input "not(a+b >= 2 * foo/3.14159) == false" would now be parsed like this (ignoring spaces):

And if you set the output to AST and mix in some tree rewrite operators (^ and !):

options { output=AST; } // ... expr : orExpr; orExpr : andExpr ('or'^ andExpr)*; andExpr : relExpr ('and'^ relExpr)*; relExpr : addExpr (relop^ addExpr)?; relop : '<' | '<=' | '>' | '>=' | '==' | '!='; addExpr : multExpr (('+' | '-')^ multExpr)*; multExpr : unaryExpr (('*' | '/')^ unaryExpr)*; unaryExpr : 'not'^ atom | atom; atom : INT | FLOAT | ID | 'true' | 'false' | '('! expr ')'!;

you'd get: