conditional - 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 : '&' | '*' | '-' | '~' | '!' ;

如果您阅读它，您会注意到他们执行了来自 conditional_expression 的非常长的 1 对 1 条件链。至 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 ，它将首先查找 ('*' | '/' | '%') ，如果不存在，它将查找 ('+' | '-')等。换句话说，在规则中排在第一位的备选方案将优先于在规则中排在较低位置的备选方案。

现在我从你之前的问题中知道，Once grammar is complete, what's the best way to walk an ANTLR v4 tree? ，您正在使用监听器“行走”树。如果您创建一个 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(...)

...