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

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 только помогает вам создать синтаксический анализатор для вашего языка, остальное зависит от вас.

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

Ваша грамматика содержит почти только правила лексера. Правила 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'
  ;

РЕДАКТИРОВАТЬ

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

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
  ;

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