首页 文章

来自ANTLR4中列表的令牌的非贪婪匹配

提问于
浏览 次
0

在a previous question with a simple grammar中，我学会了处理可以包含关键字列表中的关键字的ID . 我的实际语法稍微复杂一些：在不同类型的句子中有几个关键词列表 . 这是我尝试一种讲述故事的简单语法：

grammar Hello;

file     : ( fixedSentence )* EOF ;
sentence : KEYWORD1 ID+ KEYWORD2 ID+ PERIOD
         | KEYWORD3 ID+ KEYWORD4 ID+ PERIOD;

KEYWORD1 : 'hello' | 'howdy' | 'hi' ;
KEYWORD2 : 'bye' | 'goodbye' | 'adios' ;
KEYWORD3 : 'dear' | 'dearest' ;
KEYWORD4 : 'love' | 'yours' ;
PERIOD  : '.' ;
ID      : [a-z]+ ;
WS      : [ \t\r\n]+ -> skip ;

所以我想要匹配的句子是，例如：

hello snickers bar goodbye mars bar.
dear peter this is fun yours james.

这很有效 . 但我还想匹配包含不希望终止ID块的关键字的句子 . 例如

hello hello kitty goodbye my dearest raggedy ann and andy.

hello 拳头显示为 KEYWORD1 ，然后仅作为第一个ID的一部分 . 按照上述链接问题的示例，我可以像这样解决：

// ugly solution:
fixedSentence : KEYWORD1 a=(ID|KEYWORD1|KEYWORD3|KEYWORD4)+ KEYWORD2 b=(ID|KEYWORD1|KEYWORD2|KEYWORD3|KEYWORD4)+ PERIOD
              | KEYWORD3 a=(ID|KEYWORD1|KEYWORD2|KEYWORD3)+ KEYWORD4 b=(ID|KEYWORD1|KEYWORD2|KEYWORD3|KEYWORD4)+ PERIOD;

这工作，并完全符合我的要求 . 在我的真实语言中，我有数百个关键字列表，用于不同类型的句子，所以如果我尝试这种方法，我肯定会犯这样的错误，当我用我的语言创建新结构时，我必须回去编辑所有其他人 .

根据ANTLR4书中的评论示例，从列表中进行非贪婪匹配会更好 . 所以我尝试了这个

// non-greedy matching concept:
KEYWORD : KEYWORD1 | KEYWORD2 | KEYWORD3 | KEYWORD4 ;
niceID : ( ID | KEYWORD ) ;
niceSentence : KEYWORD1 niceID+? KEYWORD2 niceID+? PERIOD
             | KEYWORD2 niceID+? KEYWORD3 niceID+? PERIOD;

我认为遵循评论模型（例如，在本书的第81页给出）：

COMMENT : '/*' .*? '*/' -> skip ;

通过使用 ? 建议非贪婪 . （虽然这个例子是词法规则，这会改变这里的含义吗？） fixedSentence 有效，但 niceSentence 是失败的 . 我从哪里开始？

具体来说，解析上面的hello kitty测试句中报告的错误是，

测试规则 sentence ：

line 1:6 extraneous input 'hello' expecting ID
line 1:29 extraneous input 'dearest' expecting {'.', ID}

测试规则 fixedSentence ：没有错误 .

测试规则 niceSentence ：

line 1:6 extraneous input 'hello' expecting {ID, KEYWORD}
line 1:29 extraneous input 'dearest' expecting {KEYWORD2, ID, KEYWORD}
line 1:57 extraneous input '.' expecting {KEYWORD2, ID, KEYWORD}

如果它有助于查看解析树，here they are .

antlr4

1 回答

  • 1

    认识到解析器非常适合处理语法，即结构，而不是语义区别 . 关键字在一个上下文中是否为 ID 终止符而在另一个上下文中是否在语法上是等价的，本质上是语义的 .

    处理语义模糊的典型ANTLR方法是创建一个尽可能多地识别多个结构区别的解析树，然后走树分析每个节点相对于周围节点（在这种情况下）以解决模糊 .

    如果这解析为你的解析器

    sentences : ( ID+ PERIOD )* EOF ;

    那么你的句子基本上是自由形式的 . 更合适的工具可能是NLP库 - 斯坦福有一个很好的工具 .

    Additional

    如果将词法规则定义为

    KEYWORD1 : 'hello' | 'howdy' | 'hi' ;
KEYWORD2 : 'bye' | 'goodbye' | 'adios' ;
KEYWORD3 : 'dear' | 'dearest' ;
KEYWORD4 : 'love' | 'yours' ;
. . . .
KEYWORD : KEYWORD1 | KEYWORD2 | KEYWORD3 | KEYWORD4 ;

    词法分析器将永远不会发出 KEYWORD 令牌 - 'hello'被消耗并作为KEYWORD1发出，并且永远不会评估 KEYWORD 规则 . 由于解析树无法识别令牌的类型（显然），因此它不是很有启发性 . 转储令牌流以查看词法分析器实际执行的操作

    hello    hello    kitty goodbye  my dearest  ...
KEYWORD1 KEYWORD1 ID    KEYWORD2 ID KEYWORD3 ...

    如果将 KEYWORD 规则放在其他规则之前，则词法分析器将仅发出 KEYWORD 标记 .

    更改为解析器规则

    niceID : ( ID | keyword ) ;
keyword : KEYWORD1 | KEYWORD2 | KEYWORD3 | KEYWORD4 ;

    将允许这个非常有限的例子工作 .

    回复于

相关问题