首页 文章

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

提问于
浏览 次
1

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

我正在尝试编写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 trying to match token within longer token并制作了与之相对应的语法：

parse
:   
  identifier 'keyword'
;

identifier
:   
  (HIGHCHAR | LOWCHAR)+
;

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

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

parsing antlr antlr3 antlr4 lexer

1 回答

  • 7

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

    identifier : IDENTIFIER+;
IDENTIFIER : HIGHCHAR | LOWCHAR;

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

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

    Edit: 您在ANTLR 3中收到消息"The following alternatives can never be matched..."的原因是静态分析已确定规则 IDENTIFIER 中的正结束永远不会匹配多于1个字符，因为规则将始终成功，只有1个字符 .

    回复于

相关问题