Lexer的前瞻如何与ANTLR3和ANTLR4中的贪婪和非贪婪匹配一起工作？

Question

如果有人能够从前瞻性关系背后的混淆中清除我的想法,那就是涉及格雷斯/非贪婪匹配的令牌化,我会非常高兴.这是一个稍长的帖子,因为它跟随我的思考过程.

我正在尝试编写antlr3语法,允许我匹配输入,如:

"identifierkeyword"

我在Antlr 3.4中提出了类似的语法:

KEYWORD: 'keyword' ;

IDENTIFIER
: 
  (options {greedy=false;}: (LOWCHAR|HIGHCHAR))+ 
;

/** lowercase letters */
fragment LOWCHAR
:   'a'..'z';
/** uppercase letters */
fragment HIGHCHAR
:   'A'..'Z';

parse: IDENTIFIER KEYWORD EOF;

然而,它抱怨它永远不会匹配IDENTIFIER这种方式,我真的不明白.(以下替代方案永远不能匹配:1)

基本上我试图指定试图匹配(LOWCHAR | HIGHCHAR)非贪婪方式的词法分析器,因此它停在KEYWORD前瞻.到目前为止我读到的关于ANTLR词法分析器的内容应该是词法规则的某种优先权.如果我首先在词法分析器语法中指定KEYWORD词法分析器规则,那么之后的任何词法分析器规则都不应该与消耗的字符匹配.

经过一些搜索后我明白这里的问题是它无法以正确的方式对输入进行标记,因为例如输入:"identifierkeyword"首先出现"标识符"部分,因此当没有KEYWORD时它决定开始匹配IDENTIFIER规则令牌匹配了.

然后我尝试在ANTLR 4中编写相同的语法,以测试新的预装功能是否可以匹配我想要的,它看起来像这样:

KEYWORD: 'keyword' ;

/** lowercase letters */
fragment LOWCHAR
:   'a'..'z';
/** uppercase letters */
fragment HIGHCHAR
:   'A'..'Z';

IDENTIFIER
: 
  (LOWCHAR|HIGHCHAR)+?
;

parse: IDENTIFIER KEYWORD EOF;

对于输入:"identifierkeyword"它会产生此错误:第1行:1不匹配的输入'd'期待'关键字'

它将字符'i'(第一个字符)与IDENTIFIER标记匹配,然后解析器需要一个KEYWORD标记,他不会这样做.

对于词法分析器的非贪婪匹配是不是应该匹配,直到前瞻中有任何其他可能性？难道它不应该期待IDENTIFIER可以包含KEYWORD并以这种方式匹配吗？

我真的对此感到困惑,我看过Terence Parr介绍ANTLR4的新功能的视频,他谈到了在实际匹配规则的同时监视所有"正确"解决方案的预先运行的线程.我认为它也适用于Lexer规则,其中用于标记输入"identifierkeyword"的可能正确解决方案匹配IDENTIFIER:"identifier"并匹配KEYWORD:"keyword"

我觉得我脑子里有很多关于非贪婪/贪婪匹配的错误.有人可以解释一下它是如何工作的吗？

在这之后我在这里发现了一个类似的问题:ANTLR尝试在更长的令牌中匹配令牌,并制作了与之对应的语法:

parse
:   
  identifier 'keyword'
;

identifier
:   
  (HIGHCHAR | LOWCHAR)+
;

/** lowercase letters */
LOWCHAR
:   'a'..'z';
/** uppercase letters */
HIGHCHAR
:   'A'..'Z';

这就是我现在想要的,但是我不明白为什么我不能将标识符规则更改为Lexer规则而将LOWCHAR和HIGHCHAR更改为片段.Lexer不知道"关键字"中的字母可以作为标识符匹配吗？或相反亦然？或者可能是规则只定义为内部有一个先行,而不是所有可能的匹配语法？

Answer 1

在ANTLR 3和ANTLR 4中解决此问题的最简单方法是仅允许IDENTIFIER匹配单个输入字符,然后创建解析器规则来处理这些字符的序列.

identifier : IDENTIFIER+;
IDENTIFIER : HIGHCHAR | LOWCHAR;

这将导致词法分析器将输入跳过identifier10个单独的字符,然后keyword作为单个KEYWORD标记读取.

您在ANTLR 4中使用非贪婪运算符观察到的行为+?与此类似.该运算符表示" (HIGHCHAR|LOWCHAR)在创建IDENTIFIER令牌的同时匹配尽可能少的块".显然,创建令牌的最少数量是一个,因此这实际上是一种非常低效的写入方式IDENTIFIER来匹配单个字符.parse规则无法处理此问题的原因是它只允许在IDENTIFIER令牌之前出现单个KEYWORD令牌.通过创建identifier如上所示的解析器规则,解析器将能够将IDENTIFIER令牌序列(每个都是单个字符)视为单个标识符.

编辑:你的消息的原因在ANTLR 3"有以下两个选项不能匹配......"是静态分析已经确定了规则中的正关闭IDENTIFIER永远比不上更超过1个字符,因为该规则永远是成功的与正好 1个字符.