parsing - ANTLR 重写规则的替代方案

Question

我正在编写一个支持任意 bool 表达式的语法。语法用于表示程序，随后通过静态分析工具进行传递。静态分析工具有一定的局限性，所以我想应用以下重写规则:

严格不等式用 epsilon 来近似:

expression_a > expression_b -> expression_a >= expression_b + EPSILON

使用“or”语句近似不等式:

expression_a != expression_b -> expression_a > expression_b || expression_a < expression_b

有没有简单的方法可以使用 ANTLR 来做到这一点？目前我的语法如下所示:

comparison          : expression ('=='^|'<='^|'>='^|'!='^|'>'^|'<'^) expression;

我不确定如何根据运算符应用不同的重写规则。如果运算符是(“==”、“<=”或“">=”)，我希望树保持原样，否则根据上面定义的规则递归地转换它。

Answer 1

[...] and to recursively transform it otherwise, [...]

你可以部分完成。

你不能告诉 ANTLR 重写 a > b至^('>=' a ^('+' b epsilon))然后定义a != b成为^('||' ^('>' a b) ^('<' a b))然后让 ANTLR 自动重写 ^('>' a b)和^('<' a b)至^('>=' a ^('+' b epsilon))和^('<=' a ^('-' b epsilon))分别。

这里需要一些手动工作。诀窍是你不能只使用像 >= 这样的 token 。如果这个标记实际上没有被解析。解决方案是使用 imaginary tokens .

快速演示:

grammar T;

options {
  output=AST;
}

tokens {
  AND;
  OR;
  GTEQ;
  LTEQ;
  SUB;
  ADD;
  EPSILON;
}

parse
 : expr
 ;

expr
 : logical_expr
 ;

logical_expr
 : comp_expr ((And | Or)^ comp_expr)*
 ;

comp_expr
 : (e1=mult_expr -> $e1) ( Eq   e2=mult_expr -> ^(AND ^(GTEQ $e1 $e2) ^(LTEQ $e1 $e2))
                         | LtEq e2=mult_expr -> ^(LTEQ $e1 $e2)
                         | GtEq e2=mult_expr -> ^(GTEQ $e1 $e2)
                         | NEq  e2=mult_expr -> ^(OR ^(GTEQ $e1 ^(ADD $e2 EPSILON)) ^(LTEQ $e1 ^(SUB $e2 EPSILON)))
                         | Gt   e2=mult_expr -> ^(GTEQ $e1 ^(ADD $e2 EPSILON))
                         | Lt   e2=mult_expr -> ^(LTEQ $e1 ^(SUB $e2 EPSILON))
                         )?
 ;

add_expr
 : mult_expr ((Add | Sub)^ mult_expr)*
 ;

mult_expr
 : atom ((Mult | Div)^ atom)*
 ;

atom
 : Num
 | Id
 | '(' expr ')'
 ;

Eq    : '==';
LtEq  : '<=';
GtEq  : '>=';
NEq   : '!=';
Gt    : '>';
Lt    : '<';
Or    : '||';
And   : '&&';
Mult  : '*';
Div   : '/';
Add   : '+';
Sub   : '-';
Num   : '0'..'9'+ ('.' '0'..'9'+)?;
Id    : ('a'..'z' | 'A'..'Z')+;
Space : ' ' {skip();};

从上面的语法生成的解析器将产生以下结果:

<小时/>

a == b

<小时/>

a != b

<小时/>

a > b

<小时/>

a < b

<小时/>