Лексер ANTLR вообще не может смотреть вперед

У меня такая грамматика:

rule: 'aaa' | 'a' 'a';

Он может успешно проанализировать строку 'aaa', но не может проанализировать 'aa' со следующей ошибкой:

line 1:2 mismatched character '<EOF>' expecting 'a'

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

@members {
  public static void main(String[] args) throws Exception {
    RecipeLexer lexer = new RecipeLexer(new ANTLRInputStream(System.in));
    for (Token t = lexer.nextToken(); t.getType() != EOF; t = lexer.nextToken())
      System.out.println(t.getType());
  }
}

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

rule: AAA | A A;
AAA: 'aaa';
A: 'a';

Очевидно, лексер ANTLR пытается сопоставить входное значение «aa» с правилом AAA, которое не выполняется. Помимо того, что ANTLR является парсером LL (*) или чем-то еще, лексер должен работать отдельно от парсера и уметь разрешать двусмысленность. Грамматика прекрасно работает со старым добрым lex (или flex), но не похоже на ANTLR. Так в чем проблема?

Спасибо за помощь!


person K J    schedule 30.08.2012    source источник
comment
Как токены определены в вашем лексере? Мне кажется, что лексический анализатор предпочитает сопоставлять a вместо aaa, учитывая один a в качестве входных данных.   -  person Dervall    schedule 30.08.2012
comment
@Dervall Файл токенов выглядит так: A=4 AAA=5 Он предпочитает aaa a. И он может анализировать aaa и a, но не aa.   -  person K J    schedule 30.08.2012
comment
@AustinHenley: Да, он жадный в том смысле, что предпочитает более длинные токены, когда есть несколько вариантов. Но с вводом «аа» выбор «ааа» невозможен.   -  person K J    schedule 30.08.2012
comment
Ознакомьтесь с этой невероятно подробной, но простой в использовании страницей: wincent.com/wiki/ANTLR_lexers_in_depth. Это очень помогло мне понять причуды ANTLR Lexer. Особенно удивительно то, что по умолчанию. + И. * Не являются жадными!   -  person TFuto    schedule 09.08.2013


Ответы (1)


Сгенерированные ANTLR парсеры являются (или могут быть) LL (*), а не его лексерами.

Когда лексер видит ввод "aa", он пытается сопоставить токен AAA. Когда это не удается, он пытается сопоставить любой другой токен, который также соответствует "aa" (лексический анализатор не выполняет обратный поиск для сопоставления A!). Поскольку это невозможно, возникает ошибка.

Обычно это не проблема, поскольку на практике часто можно использовать какое-то правило идентификатора "aa". Итак, какую реальную проблему вы пытаетесь решить, или вас интересовала только внутренняя работа? Если это первая проблема, отредактируйте свой вопрос и опишите настоящую проблему.

person Bart Kiers    schedule 30.08.2012
comment
Спасибо за разъяснение, Барт. Думаю, это ближе ко второму. Я использую lex / yacc и пытаюсь перейти на ANTLR. У парсера ANTLR уже есть свои ограничения как у парсера LL, но, как вы отметили, речь идет о лексере, а не о парсере. Честно говоря, я буду немного разочарован, если лексер ANTLR не сможет справиться с такой сложностью, в отличие от других лексеров, таких как lex. Стоимость обратного отслеживания не будет огромной, в худшем случае O (n ^ 2), и может быть лучше, если с ней обращаться с умом. - person K J; 30.08.2012
comment
@KJ, конечно, есть способы решить эту проблему. Но вместо того, чтобы объяснять, как решить ваш пример с соломенным человеком, я лучше попытаюсь предложить решение реальной проблемы (иначе я отвечу дважды ...). - person Bart Kiers; 30.08.2012
comment
Боюсь, я не ищу решение конкретной проблемы. Как я уже сказал, это больше похоже на любопытство, поскольку я рассматривал возможность использования ANTLR, потому что он поддерживает JAVA, в отличие от yacc, но я проявляю осторожность. Я знаю, что есть обходной путь к этой проблеме с помощью предварительного просмотра вручную (я видел ваш предыдущий пост), но мне приходится иметь дело с подобными проблемами в каждом конкретном случае кажется ненадежным .. Тем не менее, спасибо за ответ! - person K J; 30.08.2012