Почему произошла эта ошибка? - «Следующие альтернативы никогда не могут быть сопоставлены»

Question

Я заинтересован в создании компилятора, парсера и генератора парсеров, но я не знаю о них много.

Прочитав ответ на этот вопрос , я попытался создать «очень» простой синтаксический анализатор LaTeX.

Это код:

grammar Latex;

latex   :   ITEM*;
ITEM    :   CMD|LAWTEXT;
CMD :   CHEAD ARGS;
CHEAD   :   '\\' LETTER(LETTER|DIGIT)*;
LETTER  :   'A'..'Z'|'a'..'z';
DIGIT   :   '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9';
ARGS    :   '{' ITEM* '}';
LAWTEXT :   (LETTER|DIGIT|WHITESPACE|PUNC)*;
WHITESPACE
    :   ' '|'\t'|'\n'|'\r';
PUNC    :   '!'|'^';

(в тесте PUNC только два символа)

И это сообщение об ошибке:

[18:39:09] warning(200): C:\Users\***\Documents\Latex.g:9:12: Decision can match input such as "{'\t'..'\n', '\r', ' '..'!', '0'..'9', 'A'..'Z', '\\', '^', 'a'..'z', '}'}" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
[18:39:09] error(201): C:\Users\***\Documents\Latex.g:9:12: The following alternatives can never be matched: 2

[18:39:09] error(211): C:\Users\***\Documents\Latex.g:1:8: [fatal] rule Tokens has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.

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

И это диаграмма, и два способа что-то можно интерпретировать (возможно).

... но как \ и } можно перепутать?

Answer 1

JiminP писал:

Я заинтересован в создании компилятора, парсера и генератора парсера, но я не знаю о них много.

ANTLR создает для вас лексер и анализатор на основе написанной вами грамматики.ANTLR сам по себе является генератором парсера, поэтому вы не пишете сам генератор парсера (к счастью!).Компилятор - это приложение, которое берет дерево, которое генерирует ваш синтаксический анализатор, и переводит входные данные в другую форму: это то, что вам нужно сделать самостоятельно.Итак, чтобы подчеркнуть: ANTLR only поможет вам создать синтаксический анализатор для вашего языка, остальное зависит от вас.

Теперь проблема (ы).

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

LETTER  :   'A'..'Z'|'a'..'z';
...
LAWTEXT :   (LETTER|DIGIT|WHITESPACE|PUNC)*;

могут заставить лексера самостоятельно создавать токен LETTER.Если вы всегда хотите, чтобы строчная или прописная буква ascii стала токеном LAWTEXT, то вам нужно сделать LETTER правило фрагмента следующим образом:

fragment LETTER  :   'A'..'Z'|'a'..'z';
...
LAWTEXT :   (LETTER|DIGIT|WHITESPACE|PUNC)+;

И, как вы видите, я закончилLAWTEXT правило с + вместо *: вы не хотите создавать токены, которые ничего не содержат (пустая строка).

Также, args, item и cmd не являются подходящими кандидатами для правила лексера: вместо этого они должны быть правилами парсера.

Вот грамматика, которая генерирует лексер и парсер без ошибок:

grammar Latex;

latex
  :  item* EOF
  ;

item 
  :  cmd
  |  LAWTEXT
  ;

cmd
  :  CHEAD args
  ;

args
  :  '{' item* '}'
  ;

CHEAD 
  :  '\\' LETTER (LETTER | DIGIT)*
  ;  

LAWTEXT
  :  (LETTER | DIGIT | WHITESPACE | PUNC)+
  ;

fragment  
WHITESPACE 
  :  ' ' | '\t' | '\n' | '\r'
  ;

fragment  
PUNC       
  : '!' | '^'
  ;

fragment
LETTER
  :  'A'..'Z' | 'a'..'z'
  ;

fragment
DIGIT
  :  '0'..'9'
  ;

EDIT

Как я уже упоминал: правила лексера начинаются с заглавной буквы, а правила синтаксического анализатора начинаются со строчной буквы.Лексер, который иногда называют токенизатором или сканером, отвечает за измельчение входного источника.Исходный источник начинается как поток символов.Эти символы затем группируются лексером.Итак, учитывая следующие правила лексера:

Identifier
  :  (Letter | '_') (Letter | '_' | Digit)*
  ;

Assign
  :  '='
  ;

Number
  :  Digit+ ('.' Digit+)?
  ;

fragment Digit
  :  '0'..'9'
  ;

fragment Letter
  :  'a'..'z' | 'A'..'Z'
  ;

Spaces
  :  (' ' | '\t' | '\r' | '\n') {skip();}
  ;

может принимать входной источник, например:

foo = 12.34

, который лексер видит как:

'f', 'o', 'o', ' ', '=', ' ', '1', '2', '.', '3', '4', EOF

и создастследующие токены:

• Identifier "foo"
• Assign "="
• Number "12.34"

(обратите внимание, что токенов нетсоздается из пробелов: я пропустил их!)

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

assignment
  :  Identifier Assign Number
  ;

Важно помнить, что входной источник сначала маркируется лексером, и только после этого процесса правила синтаксического анализаторавойти в игру.