3

我写了这个语法：

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规则，因为'（'而模棱两可，我找不到解决方案，你能给我一个解决方案吗？

4

4 回答 4

5

为什么不简单地做：

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/tree 中行走时，可能会检查此类语义。

编辑

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

你会得到：

在此处输入图像描述

于 2012-02-15T20:27:24.033 回答
2

您的问题源于这样一个事实，即 '(' 可能是 的第一个替代方案c2或最后一个替代方案的开始atom。例如，给定输入 like ((x+y) > (a+b))，第一个开放括号是 a 的开头c2，但第二个是.的开头atom[编辑：并且解析器没有指示要走哪条路，直到以后的某个任意点——例如，它不知道第一个打开的括号是 a 的开头，c2直到它遇到>. 例如，如果那是 a *，那么两个开头的括号都是atoms 的开头。]

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

编辑：例如，在 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
于 2012-02-15T20:28:54.300 回答
0

您不能将 c1 定义为以下内容吗？

('not')? (('(' condition ')') | boolean)
于 2012-02-15T19:58:14.643 回答
0

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

于 2012-02-15T19:58:58.590 回答