Устранение возможных неоднозначностей грамматики ANTLR (и общие советы по улучшению) - PullRequest
Новая
       58

Устранение возможных неоднозначностей грамматики ANTLR (и общие советы по улучшению)

2 голосов
/ 25 марта 2012

У меня проблема с построением грамматики, которая способна анализировать формат дампа AST в Python 3 и преобразовывать его в формат AST, с которым мне легче играть. Я решил написать для этого грамматику ANTLR, но у меня возникла проблема с обработкой блоков ключевых слов (но почему-то только блоков ключевых слов). Я выделил грамматику ключевого слова, как показано: 

grammar kwds;
options {output=AST;}

keywords:   'keywords=['((', '?)keyword)*']' -> keyword*
    ;

keyword :   'keyword(arg='STRING', value='str')'
    ;
str :   'Str(s='STRING')' -> STRING
    ;

STRING
    :  '\'' ( ESC_SEQ | ~('\\'|'\'') )* '\''
    ;

fragment
ESC_SEQ
    :   '\\' ('b'|'t'|'n'|'f'|'r'|'\"'|'\''|'\\')
    |   UNICODE_ESC
    |   OCTAL_ESC
    ;

EMPTYBRACKETS
    :   '[]';

fragment
OCTAL_ESC
    :   '\\' ('0'..'3') ('0'..'7') ('0'..'7')
    |   '\\' ('0'..'7') ('0'..'7')
    |   '\\' ('0'..'7')
    ;

fragment
UNICODE_ESC
    :   '\\' 'u' HEX_DIGIT HEX_DIGIT HEX_DIGIT HEX_DIGIT
    ;

fragment
HEX_DIGIT : ('0'..'9'|'a'..'f'|'A'..'F') ;

Он предназначен для приема списка ключевых слов (0 или более с разделителями-запятыми) в формате, указанном в правиле ключевых слов.

Если вы введете вышеуказанную грамматику для следующего (действительного) ввода,

ключевые слова = [ключевое слово (arg = 'name', значение = Str (s = 'UGA')), ключевое слово (arg = 'rank', значение = Str (s = '2'))]

грамматика распознает это, как и должно.

Тем не менее, используя написанную мной «полную» грамматику формата AST на языке Python 3 (в http://pastebin.com/ETrSVXvf для экономии места, с двумя приведенными выше правилами в строках 106 и 109 соответственно), который использует практически те же самые правила грамматики, поток токенов, кажется, отключается на несколько символов после синтаксического анализа первого соответствия ключевого слова из примера, показанного выше, что приводит к следующему выводу при анализе правила ключевых слов: 

sample3.txt line 1:52 mismatched character 'e' expecting 'w'
sample3.txt line 1:53 no viable alternative at character 'y'
sample3.txt line 1:54 no viable alternative at character 'w'
sample3.txt line 1:55 no viable alternative at character 'o'
sample3.txt line 1:56 no viable alternative at character 'r'
sample3.txt line 1:57 no viable alternative at character 'd'
sample3.txt line 1:58 no viable alternative at character '('
sample3.txt line 1:59 missing ENDBR at 'arg='

Я могу думать только об одной возможности для этого: что-то неправильно маркируется из-за неоднозначности в грамматике, так как шаблон, который я использовал для обнаружения нескольких операторов ключевого слова, работает для других типов операторов. Тем не менее, я полностью застрял в том, где эта неопределенность в грамматике.

Кроме того, любые общие советы по улучшению того, как я могу улучшить свою грамматику в целом, будут оценены!

1 Ответ

1 голос
/ 25 марта 2012

Если добавить правило: 

parse
 : (t=. {System.out.printf("type=\%-20s text='\%s'\n", tokenNames[$t.type], $t.text);})* EOF
 ;

, который просто сопоставляет ноль или более токенов и печатает тип и текст этих токенов, вы увидите, что лексер не может справиться с вводом , keyword из вашего примера: 

keywords=[keyword(arg='name', value=Str(s='UGA')), keyword(arg='rank', value=Str(s='2'))]
                                                 ^^^^^^^^^

Так что в одном из ваших правил парсера нет проблем, но на лексическом уровне все идет не так, как надо.

Я советую вам удалить все буквальные токены из вашего парсера и создать для них правило лексера. Затем добавьте одно правило parse, как я писал выше, с помощью которого вы можете проверить лексер, чтобы увидеть, созданы ли правильные токены. После того, как будут созданы правильные токены, напишите правила парсера.

Я почти уверен, что проблема в том, что у вас нет токена ', keyword' и что, когда лексер "видит" ', k', он пытается создать токен ', kwargs', который не работает, конечно. Поэтому я также рекомендую вам не включать запятые и пробелы в свои токены, но пусть они будут собственными токенами.

Кроме того, вы не хотите иметь правило переписывания, подобное этому: 

stmtlist:       ((', '?) stmt)* -> stmt*
        ;

, который потенциально не может ничего соответствовать. Если это произойдет, ANTLR сгенерирует исключение при создании AST. Всегда позволяйте правилу перезаписи создавать что-то : 

...

tokens {
  ...
  STMTLST;
  ...
}

...

stmtlist:       ((', '?) stmt)* -> ^(STMTLST stmt*)
        ;
...