Кажущийся недетерминизм в разборе ANTLR - PullRequest
Новая
       2

Кажущийся недетерминизм в разборе ANTLR

2 голосов
/ 14 июня 2011

Если у меня есть грамматика ANTLR следующим образом: 

grammar Test;
options {
  language = Java;
}

rule : (foo | bar);


foo : FOO ',' FOO;   
bar : BAR; 

FOO: ('0'..'9')+;
BAR: ('a'..'z' | 'A'..'Z' | '0'..'9' | ' ')+;
WHITESPACE: (' ' | '\t')+ { $channel=HIDDEN; };

И я использую тестовую строку:

12abc3

это (я полагаю) токен BAR, который удовлетворяет правилу bar и анализируется как таковой. Браво.

Однако, если у меня есть эта строка: 

12

Я получаю line 1:2 mismatched input '' expecting ','

Это кажется довольно недетерминированным, хотя я уверен, что это не так. Я понимаю, что у меня уже есть проблема с двумя токенами: FOO и BAR, которые принимают цифры. Но если синтаксический анализатор собирается преуспеть или потерпеть неудачу, он должен преуспеть или последовательно терпеть неудачу. Другими словами, в первом случае первый символ равен 1 и, по-видимому, оценивается как член токена BAR, и, таким образом, анализатор направляется по успешному пути. Во втором случае один и тот же первый символ оценивается как токен FOO, и поэтому путь обречен на неудачу, несмотря на то, что строка МОЖЕТ быть успешным bar анализом. Почему несоответствие? Или я упускаю что-то более фундаментальное в ANTLR и / или разборе?

Ответы [ 2 ]

3 голосов
/ 14 июня 2011

ANTLR не определяет тип токена, пока не увидит первый символ для следующего токена (или EOF). ANTLR также попытается провести самый длинный матч, поэтому вы видите «12abc3» как BAR, а не как FOO BAR. Во втором случае ANTLR будет использовать FOO для «12», потому что он указан первым в грамматике.

Основы ANTLR

Лексеры ANTLR

0 голосов
/ 14 июня 2011

В дополнение к ответу Адама вы должны понимать, что лексер и парсер, хотя и определены в одной и той же грамматике, создаются в разное время. Сначала входной источник токенизируется, и когда это происходит, только тогда парсер работает с этими токенами. Токены создаются , а не , когда анализатор проходит через источник (поток символов), чтобы обеспечить полное совпадение (т. Е. Токенизацию "12" как BAR). Тот факт, что "12" маркируется как FOO, объясняется тем, что FOO предшествует правилу BAR и имеет более высокий приоритет в случае равного длинного совпадения.

Вкратце: грамматики ANTLR не PEG .

...