ANTLR链接1到1个语法规则一起解决条件

Question

如果你看一下ObjectiveC antlr v3语法(http://www.antlr3.org/grammar/1212699960054/ObjectiveC2ansi.g),以及许多其他流行的语法,他们为解决条件问题做了类似的结构

conditional_expression : logical_or_expression 
  ('?' logical_or_expression ':' logical_or_expression)? ;

constant_expression : conditional_expression ;

logical_or_expression : logical_and_expression 
  ('||' logical_and_expression)* ;

logical_and_expression : inclusive_or_expression 
  ('&&' inclusive_or_expression)* ;

inclusive_or_expression : exclusive_or_expression 
  ('|' exclusive_or_expression)* ;

exclusive_or_expression : and_expression ('^' and_expression)* ;

and_expression : equality_expression ('&' equality_expression)* ;

equality_expression : relational_expression 
  (('!=' | '==') relational_expression)* ;

relational_expression : shift_expression
 (('<' | '>' | '<=' | '>=') shift_expression)* ;

shift_expression : additive_expression (('<<' | '>>') additive_expression)* ;

additive_expression : multiplicative_expression
  (('+' | '-') multiplicative_expression)* ;

multiplicative_expression : cast_expression 
  (('*' | '/' | '%') cast_expression)* ;

cast_expression : '(' type_name ')' cast_expression | unary_expression ;

unary_expression 
  : postfix_expression
  | '++' unary_expression
  | '--' unary_expression
  | unary_operator cast_expression
  | 'sizeof' ('(' type_name ')' | unary_expression) ;

unary_operator : '&' | '*' | '-' | '~' | '!' ;

如果你读它,你会发现他们做的条件句这个很长的1对1链从conditional_expression到logical_or_expression到logical_and_expression到inclusive_or_expression到exclusive_or_expression.

现在,当涉及到ANTLR时,我很天真,但这让我觉得是一种解析条件的奇怪方法.对于logical_or_expression的定义来说,扭曲每个其他条件表达式类型似乎非常复杂.毕竟,逻辑的定义OR与左按位移位有什么关系？

是否有更好的方法,或者是否需要这种方法？

Answer 1

如前所述,需要"链"来正确处理运算符优先级.没有它,输入就像1+2*3被解析为:

     *
    / \
   +   3
  / \
 1   2

代替:

  +
 / \
1   *
   / \
  2   3

由于ANTLR 4支持直接左递归规则:

foo
 : foo '?' foo
 | TOKEN
 ;

所以不是间接的左递归规则:

foo
 : bar
 | TOKEN
 ;

bar
 : foo '?' foo
 ;

您可以按如下方式重写这些规则:

expression
 : '-' expression
 | '(' type_name ')' expression
 | expression ('*' | '/' | '%') expression
 | expression ('+' | '-') expression
 | expression ('<<' | '>>') expression
 | expression ('<' | '>' | '<=' | '>=') expression
 | expression ('!=' | '==') expression
 | expression '&' expression
 | expression '^' expression
 | expression '|' expression
 | expression '&&' expression
 | expression '||' expression
 | expression '?' expression ':' expression
 | IDENTIFIER
 | NUMBER
 ;

如果解析器现在偶然发现expression,它将首先查找('*' | '/' | '%'),如果不存在,则会查找('+' | '-'),等等.换句话说,规则中首先放置的备选项将优先于规则中较低的备选项.

现在我从你之前的问题中得知,一旦语法完成,走ANTLR v4树的最佳方法是什么？,你正在使用一个监听器"走"树.如果您expression按照我刚刚展示的那样创建规则,则需要在您enterExpression(...)和exitExpression(...)方法中进行大量手动检查,以找出哪些替代方案匹配expression.这就是"标签"派上用场的地方.您只需在expression规则中标记每个备选项:

expression
 : '-' expression                                  #unaryExpr
 | '(' type_name ')' expression                    #castExpr
 | expression ('*' | '/' | '%') expression         #multExpr
 | expression ('+' | '-') expression               #addExpr
 | expression ('<<' | '>>') expression             #...
 | expression ('<' | '>' | '<=' | '>=') expression 
 | expression ('!=' | '==') expression
 | expression '&' expression
 | expression '^' expression
 | expression '|' expression
 | expression '&&' expression
 | expression '||' expression
 | expression '?' expression ':' expression
 | IDENTIFIER
 | NUMBER
 ;

(请注意,当您标注一个时,您必须将它们全部标记!)

然后基础监听器类将具有enter- 和exit所有替代方法:

public void enterUnaryExpr(...)
public void exitUnaryExpr(...)

public void enterCastExpr(...)
public void exitCastExpr(...)

public void enterMultExpr(...)
public void exitMultExpr(...)

...