4

如果您查看 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 条件链 from conditional_expressionto logical_or_expressionto logical_and_expressionto inclusive_or_expressionto exclusive_or_expression。

现在，当谈到 ANTLR 时，我很天真，但这让我觉得这是一种奇怪的解析条件的方式。将logical_or_expression 的定义扭曲到所有其他条件表达式类型似乎非常复杂。毕竟，逻辑的定义OR与左移位有什么关系？

是否有更好的方法，或者是否有特定的原因需要这种方法？

4

2 回答 2

7

如前所述，需要“链”来正确处理运算符优先级。没有它，输入 like1+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(...)

...
于 2013-02-27T22:15:13.717 回答
0

这样做有一个很好的理由：运算符优先级。以逻辑 OR 和左移位为例，考虑类似

if (a << b || c)

Objective-C 优先规则说 '<<' 具有优先权，因此评估它的正确方法是

(a << b) || c

解析器规则通过使用您提到的链来管理它，因为 '||' 的规则 在链中较高的位置，解析正确地给出了一个 << b 作为 || 的子表达式 操作员。

在 Antl3 中没有更好的方法，但是在 Antlr4 中，有，因为 Antlr4 允许直接左递归规则。我强烈推荐“Definitive Antlr4 reference”，因为它对这个问题有很好的解释。

于 2013-02-27T17:04:45.507 回答