Блог

Я пытаюсь создать грамматику ANTLR для анализа последовательностей ключей, которые необязательно имеют количество повторений. Например, (a b c r5) означает «повторить ключи a, b и c пять раз».

У меня есть грамматика, работающая для KEYS : ('a'..'z'|'A'..'Z') .

Но когда я пытаюсь добавить цифровые ключи KEYS : ('a'..'z'|'A'..'Z'|'0'..'9') с помощью входного выражения like (a 5 r5) , синтаксический анализ завершается неудачно в середине 5, потому что он не может определить, является ли 5 ЦЕЛЫМ числом или КЛЮЧОМ. (Или я так думаю; сообщения об ошибках трудно интерпретировать как «NoViableAltException»).

Я пробовал эти грамматические формы, которые работают (‘r’ означает «количество повторений»):

 repeat : '(' LETTERKEYS INTEGER ')' - works for a-zA-Z
repeat : '(' LETTERKEYS 'r' INTEGER ')'; - works for a-zA-Z
  

Но я терплю неудачу с

 repeat : '(' LETTERSandDIGITKEYS INTEGER ')' - fails on '(a 5 r5)'
repeat : '(' LETTERSandDIGITKEYS 'r' INTEGER ')'; - fails on '(a 5 r5)'
  

Может быть, грамматика не может выполнить распознавание; может быть, мне нужно распознать все ключи 5 таким же образом (как КЛЮЧИ, ЦИФРЫ или ЦЕЛЫЕ ЧИСЛА), и в дереве синтаксического анализа посетитель интерпретирует экземпляры средних ЦИФР как ключи, а последний набор ЦИФР — как ЦЕЛОЕ число?

Можно ли определить грамматику, которая позволяет мне повторять цифровые ключи, а также буквенные ключи, чтобы такие выражения, как (a 5 123 r5) будут распознаны правильно? (То есть «повторите ключи a, 5, 1, 2,3 пять раз».) Я не привязан к этому конкретному синтаксису, хотя было бы неплохо использовать что-то подобное.

Спасибо.

синтаксический анализ завершается неудачно в середине 5, потому что он не может определить, является ли 5 ЦЕЛЫМ числом или КЛЮЧОМ.

Если вы определили следующие правила:

 INTEGER : [0-9] ;
KEY     : [a-zA-Z0-9];
  

тогда одна цифра, как 5 в вашем примере, всегда будет INTEGER токеном. Даже если
анализатор пытается сопоставить KEY токен, 5 он станет an INTEGER .
Вы ничего не можете с этим поделать: так работает лексер ANTLR. Лексер работает следующим образом:

1. постарайтесь использовать как можно больше символов (выигрывает самое длинное совпадение)
2. если 2 или более правил соответствуют одним и тем же символам (например INTEGER , и KEY в случае 5 ), пусть правило, определенное первым, «выиграет»

Если вы хотите, чтобы a 5 было an INTEGER , но иногда a KEY , сделайте что-то вроде этого:

 key     : KEY | SINGLE_DIGIT | R;
integer : INTEGER | SINGLE_DIGIT;
repeat  : R integer;

SINGLE_DIGIT : [0-9];
INTEGER      : [0-9] ;
R            : 'r';
KEY          : [a-zA-Z];
  

и в ваших правилах синтаксического анализа вы используете key and integer вместо KEY and INTEGER .

Вы можете разделить свою грамматику на две части. Один будет грамматикой лексера, один будет грамматикой синтаксического анализатора. Грамматика lexer разбивает входные символы на токены. Грамматика синтаксического анализатора использует строку токенов для синтаксического анализа и построения синтаксического дерева. Я работаю над Tunnel Grammar Studio (TGS), которая может генерировать синтаксические анализаторы с помощью этих двух грамматик, подобных ABNF (RFC 5234):

 key         = 'a'-'z' / 'A'-'Z' / '0'-'9'
repeater    = 'r' 1*('0'-'9')
  

Это грамматика лексера, которая имеет два правила. Каждый символ, который не обрабатывается грамматикой lexer, преобразуется в токен, созданный из самого символа. Значение, которое a является a key , r11 является a repeater и ( , например, будет передано анализатору в качестве токена ( .

 document    = *ws repeat
repeat      = '(' *ws *({key} *ws) [{repeater} *ws] ')' *ws
ws          = ' ' / %x9 / %xA / %xD
  

Это грамматика синтаксического анализа, которая имеет 3 правила. Сначала document правило принимает (распознает) пробелы, затем одно repeat правило. repeat Правило начинается с области видимости, за которой следует любое количество пробелов. После этого отображается список ключей, которые могут быть разделены пробелами, и после всех ключей есть необязательный токен повторителя, за которым следует необязательный пробел, закрывающий область видимости и снова необязательный пробел. Пробел space tab carriage return и line feed в таком порядке.

Время выполнения этого синтаксического анализа линейно как для лексера, так и для синтаксического анализатора, поскольку обе грамматики равны LL(1) . Ниже приведено общее дерево синтаксического анализа из онлайн-лаборатории TGS, где вы можете запустить эти грамматики для ввода (a 5 r5) , и вы получите это дерево:

Если вы хотите иметь более сложный key , вы можете использовать это:

 key = 1*('a'-'z' / 'A'-'Z' / '0'-'9')
  

Однако в этом случае key repeater оба правила лексера и будут распознавать последовательность r7 , но поскольку repeater правило определено позже, оно будет иметь приоритет (т. Е. перезаписывает предыдущее правило). Другими словами r7 будет repeater токен, и синтаксический анализ все равно будет линейным. Вы получите предупреждение от TGS, если ваши правила лексера перезаписывают друг друга.