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到inclusive_or_expression到exclusive_or_expression的1:1条件链中执行了很长的时间.

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
 ;

如果解析器现在偶然发现了expression，它将首先查找('*' | '/' | '%')，如果不存在，它将查找('+' | '-')，依此类推.换句话说，替代项放在规则的最前面将优先于规则中较低的替代方案.

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.

现在，我从您之前的问题中知道了，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屋！