Antlr проблема с набором правил - PullRequest
Новая
       26

Antlr проблема с набором правил

0 голосов
/ 07 сентября 2018

Я попытался создать грамматику, которая понимает приоритеты выражений для C # -подобного языка: 

var a = expression0.expression1(expression2 + expression3() * expression4)

При правильной расстановке приоритетов становится: 

var a = (expression0.expression1)(expression2 + ((expression3()) * expression4))

Для этого я отсортировал выражения по правилам по приоритету. Вот соответствующая выдержка из моей грамматики: 

expression: assignmentExpression;
assignmentExpression
    : equalityExpression ASSIGNMENT assignmentExpression
    | equalityExpression
    ;
equalityExpression
    : logicalExpression equals equalityExpression
    | logicalExpression notEquals equalityExpression
    | logicalExpression
    ;
logicalExpression
    : relationalExpression and logicalExpression
    | relationalExpression or logicalExpression
    | relationalExpression
    ;
relationalExpression
    : addExpression greaterThan relationalExpression
    | addExpression lessThan relationalExpression
    | addExpression greaterOrEquals relationalExpression
    | addExpression lessOrEquals relationalExpression
    | addExpression
    ;
addExpression
    : multiplyExpression add addExpression
    | multiplyExpression subtract addExpression
    | multiplyExpression
    ;
multiplyExpression
    : conversionExpression multiply multiplyExpression
    | conversionExpression divide multiplyExpression
    | conversionExpression
    ;
conversionExpression
    : unaryExpression AS conversionExpression
    | unaryExpression
    ;
unaryExpression
    : subtract unaryExpression
    | add unaryExpression
    | ifExpression
    ;
ifExpression
    : IF PAREN expression ENDPAREN expression (ELSE expression)?
    | instantiationExpression
    ;
instantiationExpression
    : NEW invocationExpression
    | invocationExpression
    ;
invocationExpression
    : reachExpression PAREN arguments? ENDPAREN
    | reachExpression
    ;
reachExpression
    : primeExpression DOT primeExpression
    | primeExpression
    ;

Используя его в следующем коде: 

{ int a = 7 }

Создает следующий вывод: 

expression
 assignmentExpression
  equalityExpression
   logicalExpression
    relationalExpression
     addExpression
      multiplyExpression
       conversionExpression
        unaryExpression
         ifExpression
          instantiationExpression
           invocationExpression
            reachExpression
             primeExpression
              blockExpression
               "{"
               statement
                variableDeclaration
                 variableType
                  type
                   identifier
                    "int"
                 identifier
                  "a"
                 variableInitialization
                  "="
                  expression
                   assignmentExpression
                    equalityExpression
                     logicalExpression
                      relationalExpression
                       addExpression
                        multiplyExpression
                         conversionExpression
                          unaryExpression
                           ifExpression
                            instantiationExpression
                             invocationExpression
                              reachExpression
                               primeExpression
                                literal
                                 integer
                                  "7"
               "}"

Возможно, у него есть проблемы, но я не могу это проверить, так как этот вид грамматики влечет за собой безумное снижение производительности. Моя предыдущая грамматика, которая анализировала выражения слева направо, занимала пару миллисекунд для анализа, а эта - целых 2 минуты.

Я отследил его до ParserATNSimulator.AdaptivePredict, и глубже, проблема в безумном глубоком стеке 

ParserATNSimulator.Closure
ParserATNSimulator.ClosureCheckingStopState
ParserATNSimulator.Closure_

Вместо того, чтобы спускаться по кроличьей норе один раз, чтобы получить правильное выражение (число: 7), кажется, что оно спускается до конца по одному разу для каждого уровня правила. Таким образом, вместо того, чтобы быть O (n), требуется O (n ^ n), чтобы просто добраться до этого проклятого "7".

Это проблема с Antlr, моей грамматикой или просто так?

EDIT: Хорошо, мне удалось устранить проблему с производительностью, переписав мою грамматику в этом стиле: 

assignmentExpression: equalityExpression (ASSIGNMENT assignmentExpression)?;

Но я все еще не понимаю, почему это происходит и как это изменение решило проблему.

...