为什么会发生此错误？ - "以下替代品永远无法匹配"

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'
  ;

编辑

正如我已经提到的:lexer规则以大写字母开头,而解析器规则以小写字母开头.词法分析器(有时称为标记器或扫描器)负责切断输入源.输入源仅作为字符流开始.然后这些字符由词法分析器组合在一起.因此,考虑到以下词法规则:

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
  ;

重要的是要记住,输入源首先由词法分析器记号化,只有重要的是经过这个过程中,语法规则发挥作用.