ANTLR: синтаксический анализ дерева дает неожиданные результаты - PullRequest
Новая
       13

ANTLR: синтаксический анализ дерева дает неожиданные результаты

0 голосов
/ 11 июня 2019

Я пытаюсь создать свою собственную грамматику ANTLR4, чтобы я мог разобрать некоторые выражения, такие как:

STARTS_WITH (this.sequence, "startSeq")

ENDS_WITH ("sequenceToTest", "endSeq")

(у меня есть сочетание констант и переменных в качестве параметров функции).

Правила Lexer и Parser созданы, но когда я пытаюсь отобразить функцию ToStringTree , создается впечатление, что дерево анализируется неправильно.

Я использую Antlr 4 с ASP.Net Core 2.1.

Файл грамматики: 

grammar expression;

expression : bool_function (OPERATOR bool_function)* ;

bool_function : (FUNCTION_NAME PAR_OPEN parameter (COMMA parameter)* PAR_CLOSE) ;

parameter : constant | current_object_field ;

constant : DOUBLE_QUOTE ANY_BUT_DOUBLE_QUOTE DOUBLE_QUOTE ;

current_object_field : THIS ALPHANUM ;

WHITESPACE : (' ' | '\t' | '\n' |'\r' )+ -> skip ;

COMPARATOR : ('==' | '<=' | '>=' | '<>') ;

OPERATOR : ('&&' | '||') ;

PAR_OPEN : '(' ;

PAR_CLOSE : ')' ;

COMMA : ',' ;

DOLLAR : '$' ;

DOUBLE_QUOTE : '"' ;

THIS : 'this.' ;

NUMBER : [0-9]+ ;

ALPHANUM : [a-zA-Z_0-9]+ ;

ANY_BUT_DOUBLE_QUOTE    : ~('"')+ ;

FUNCTION_NAME : ('STARTS_WITH' | 'ENDS_WITH' | 'CONTAINS' | 'EQUALS') ;

Модульное тестирование, пытающееся разобрать одно базовое выражение: 

        try
        {
            expressionParser expressionParser = Setup("STARTS_WITH(this.sequence, \"startSeq\")");
            expressionParser.ExpressionContext expressionContext = expressionParser.expression();

            var a = expressionContext.ToStringTree(expressionParser);
        }
        catch (Exception e)
        {
            var a = e.Message;
            throw;
        }

Вывод, который я получаю для анализа моего выражения через ToStringTree , выглядит следующим образом: 

(expression (bool_function STARTS_WITH(this.sequence,  " startSeq " )))

Но я бы ожидал более глубокого результата, такого как: 

(expression (bool_function STARTS_WITH((parameter(current_objet_field this.sequence)),(parameter(constant "startSeq")))))

Есть ли очевидные ошибки в том, как я определил свой Lexer / Parser?

1 Ответ

1 голос
/ 11 июня 2019

Вы не получите нужное дерево, потому что ваши входные данные не анализируются вообще. Сбой анализа со следующей синтаксической ошибкой:

строка 1: 0 не соответствует вводу 'STARTS_WITH (this.sequence', ожидая FUNCTION_NAME

Итак, первое, что вы должны проверить, это почему вы не видите сообщение об ошибке. Слушатель ошибок по умолчанию выводит синтаксические ошибки в stderr. Если вы работаете в среде, где вы не видите stderr, вы должны установить свой собственный прослушиватель ошибок, который информирует пользователя о синтаксических ошибках во входе таким образом, чтобы это было заметно.

Теперь, почему вход не анализируется? Ну, сообщение об ошибке кажется подозрительным, потому что оно жалуется на отсутствие FUNCTION_NAME в начале, когда это именно то, чем является STARTS_WITH (или должно быть, по крайней мере). Также кажется, что STARTS_WITH(this.sequence, рассматривается как один токен, что явно не то, что мы хотим. Так что, похоже, что-то не так с вашими правилами лексера.

Первое, что вы должны сделать, когда думаете, что лексер может производить неправильные токены, - это распечатать токены, произведенные лексером. Вы можете сделать это, используя grun с опцией -tokens (которая требует, чтобы вы проходили через Java, но это не составляет особой проблемы, поскольку ваша грамматика не содержит действий), или перебирая поток токенов в вашем коде C # (примечание что вам придется сбросить поток после итерации, иначе анализатор увидит только пустой поток).

Сделав это, мы увидим, что лексер создал следующие токены: 

[@0,0:26='STARTS_WITH(this.sequence, ',<ANY_BUT_DOUBLE_QUOTE>,1:0]
[@1,27:27='"',<'"'>,1:27]
[@2,28:35='startSeq',<ALPHANUM>,1:28]
[@3,36:36='"',<'"'>,1:36]
[@4,37:37=')',<')'>,1:37]
[@5,38:37='<EOF>',<EOF>,1:38]

Теперь первая проблема, которую мы можем увидеть здесь - это токен ANY_BUT_DOUBLE_QUOTE в начале. Ясно, что мы хотим, чтобы это было несколько токенов, ни один из которых не является ANY_BUT_DOBULE_QUOTE. Это происходит потому, что ANY_BUT_DOUBLE_QUOTE может соответствовать всей строке STARTS_WITH(this.sequence,, тогда как FUNCTION_NAME будет соответствовать только STARTS_WITH. Сгенерированные ANTLR лексеры следуют правилу максимального значения munch, которое говорит, что всегда следует использовать правило, дающее самое длинное совпадение (используя правило, которое стоит первым в грамматике в случае связей).

Другая проблема в том, что startSeq является ALPHANUM, поскольку единственная вещь, которую ваша грамматика допускает между двумя двойными кавычками, это ANY_BUT_DOUBLE_QUOTE. Здесь лексер выдал ALPHANUM вместо ANY_BUT_DOUBLE_QUOTE, потому что оба правила дали бы совпадение одинаковой длины, но ALPHANUM стоит первым в грамматике. Обратите внимание, что если вы просто переключитесь на порядок ALPHANUM и ANY_BUT_DOUBLE_QUOTE, лексер никогда не выдаст токен ALPHANUM, что тоже не то, что вам нужно.

Обе эти проблемы проистекают из того факта, что ANY_BUT_DOUBLE_QUOTE может совпадать в основном с чем угодно и таким образом пересекается с большинством других ваших правил. Это плохо.

Вместо этого вам нужно иметь единственное правило лексера для строковых литералов (поэтому constant превращается в правило лексера и превращает DOUBLE_QUOTE и ANY_BUT_DOUBLE_QUOTE в фрагменты или вставляет их непосредственно в CONSTANT). Таким образом, больше не существует правила ANY_BUT_DOUBLE_QUOTE, которое конфликтует со всем, и CONSTANT не будет конфликтовать ни с чем, потому что это единственное правило, которое начинается с двойных кавычек. Это также предотвратит выброс пустого пространства в двойных кавычках.

Как только вы это сделаете, вы получите ошибку о том, что STARTS_WITH является ALPHANUM вместо FUNCTION_NAME, но вы можете это исправить, переместив FUNCTION_NAME до ALPHANUM в грамматике. Обратите внимание, это означает, что имена ваших функций никогда не могут использоваться в качестве имен членов. Если вы этого не хотите, вы не должны делать ключевые слова именами функций (то есть вы должны просто разрешить произвольные идентификаторы в качестве имен функций, а затем проверить позже, знаете ли вы функцию с таким именем) или сделать их контекстными ключевыми словами (есть правило синтаксического анализатора, которое может соответствовать либо ALPHANUM, либо любому имени функции).

...