ANTLR 将 1 对 1 语法规则链接在一起以解决条件 [英] ANTLR chaining 1 to 1 grammar rules together to solve conditionals

问题描述

如果您查看 ObjectiveC antlr v3 语法 (http://www.antlr3.org/grammar/1212699960054/ObjectiveC2ansi.g)，以及许多其他流行的语法，它们使用与此类似的结构来解决条件

If you look at the ObjectiveC antlr v3 grammars (http://www.antlr3.org/grammar/1212699960054/ObjectiveC2ansi.g), and many of the other popular grammars out there they do a similar structure to this for solving conditionals

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 到 logical_or_expression 到 logical_and_expression 的非常长的 1 对 1 条件链inclusive_or_expression 到 exclusive_or_expression.

If you read it you'll notice they do this very long 1 to 1 chain of conditionals from conditional_expression to logical_or_expression to logical_and_expression to inclusive_or_expression to exclusive_or_expression.

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

Now, I am quite naive when it comes to ANTLR but this strikes me as an odd way to parse conditionals. It seems very complicated for the definition of a logical_or_expression to twist through every single other conditional expression type. Afterall, what does the definition of a logical OR have to do with a left bitwise shift?

也许有更好的方法，或者需要这种方法的具体原因是什么?

Is there perhaps a better way, or is there a specific reason this method is required?

推荐答案

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

As already mentioned, the "chain" is needed to properly handle operator precedence. Without it, input like 1+2*3 would be parsed as:

     *
    / \
   +   3
  / \
 1   2

代替:

  +
 / \
1   *
   / \
  2   3

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

Since ANTLR 4 supports direct left recursive rules:

foo
 : foo '?' foo
 | TOKEN
 ;

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

so not indirect left recursive rules:

foo
 : bar
 | TOKEN
 ;

bar
 : foo '?' foo
 ;

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

You can rewrite these rules as follows:

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
 ;

如果解析器现在偶然发现一个表达式，它将首先查找('*' | '/' | '%')，如果不存在, 它将查找 ('+' | '-') 等.换言之，规则中排在首位的备选方案将优先于规则中较低的备选方案.

If the parser now stumbles upon an expression, it will first look for ('*' | '/' | '%'), and if that's not there, it will look for ('+' | '-'), etc. In other words, the alternatives placed first in the rule will get precedence over alternatives placed lower in the rule.

现在我从你之前的问题中知道，语法完成后，遍历 ANTLR v4 树的最佳方法是什么?，您正在使用侦听器遍历"树.如果你像我刚刚展示的那样创建一个 expression 规则，你需要在你的 enterExpression(...) 和 exitExpression(...) 方法找出哪些替代品与 expression 匹配.这就是标签"派上用场的地方.您只需在 expression 规则中标记每个选项:

Now I know from your earlier question, Once grammar is complete, what's the best way to walk an ANTLR v4 tree?, that you're using a listener to "walk" the tree. If you create an expression rule as I just showed, you'd need to do a lot of manual inspections in your enterExpression(...) and exitExpression(...) methods to find out which of the alternatives matched an expression. This is where "labels" come in handy. You simply label each alternative in your expression rule:

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
 ;

(注意，当你标记一个时，你必须标记它们！)

(note that when you label one, you must label them all!)

然后基本侦听器类将为所有替代方案提供 enter- 和 exit 方法:

And then the base listener class will have enter- and exit method for all alternatives:

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

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

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

...

这篇关于ANTLR 将 1 对 1 语法规则链接在一起以解决条件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！