如何解决这个不明确的语法？

Question

我写了这个语法：

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规则，由于'('而含糊不清，我找不到解决方案，你能给我一个解决方案吗？

Answer 1

为什么不简单地这样做：

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 ')'!;

您会得到：

Answer 2

您的问题源于这样一个事实：“(”可能是 c2 的第一个替代方案的开始，也可能是 atom 的最后一个替代方案的开始。例如，给定输入如下((x+y) > (a+b))，第一个左括号是 c2 的开头，但第二个是 c2 的开头>atom. [编辑：解析器没有指示要走哪条路，直到稍后某个任意点 - 例如，它无法知道第一个左括号是 c2 的开头，直到遇到 >例如，如果它是 *，那么两个左括号都是 atom 的开头。]

处理它的一种可能方法是统一算术和布尔表达式的规则，所以你只有一个规则与'('表达式')，并且表达式可能是算术或布尔值，但是，这通常会产生相当松散的类型的副作用，并且相对自由。算术表达式和布尔表达式之间的转换（至少在解析器级别——然后您可以在语义中按照您喜欢的方式严格强制执行类型）。

编辑：例如，在 Pascal 中，规则运行如下（稍微简化了一点）：

expression: simple_expression ( rel_op simple_expression )*

simple_expression: ( '+' | '-')? term ( ('+' | '-' | 'or' ) term )*

term: factor ( ( '/' | '*' | 'div' | 'mod' | 'and') factor )*

factor: constant | variable | function_call | '(' expression ')' | 'not' factor

Answer 3

您不能将 c1 定义如下吗？

('not')? (('(' condition ')') | boolean)

Answer 4

解决这个问题的一种方法是将其分成两组词法分析器规则，并按顺序将它们应用于输入（一组用于数学内容，另一组用于布尔值）。