ANTLR связывает грамматические правила 1 к 1 вместе для решения условных выражений

Если вы посмотрите на грамматики 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 имеет к побитовому сдвигу влево?

Возможно, есть лучший способ или есть конкретная причина, по которой этот метод требуется?


antlr4 conditional
person Nucleon    schedule 27.02.2013    source источник

Ответы (2)


arrow_upward
7
arrow_downward

Как уже упоминалось, «цепочка» необходима для правильной обработки приоритета операторов. Без него ввод типа 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(...)

...
person Bart Kiers    schedule 27.02.2013

arrow_upward
0
arrow_downward

Для этого есть очень веская причина: приоритет операторов. Взяв ваш пример логического ИЛИ и побитового сдвига влево, подумайте о чем-то вроде

if (a << b || c)

Правила приоритета Objective-C говорят, что '‹‹' имеет приоритет, поэтому правильный способ оценить это

(a << b) || c

Правила синтаксического анализатора управляют этим, используя упомянутую вами цепочку, потому что правило для '||' находится выше в цепочке, синтаксический анализ правильно дает a ‹‹ b в качестве подвыражения для || оператор.

В Antl3 нет лучшего способа, однако в Antlr4 он есть, так как Antlr4 допускает прямо левые рекурсивные правила. Я настоятельно рекомендую «Окончательный справочник по Antlr4», так как в нем есть очень хорошее объяснение этой проблемы.

person Peter Kooiman    schedule 27.02.2013