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 回答