首页 文章

我们可以使用ANTLR定义非上下文语法吗？

提问于
浏览 次
2

我对ANTLR4很新，现在我正在尝试用它来定义哪种语法 .

据我所知，ANTLR中有两种规则： parser rules （小写单词）和 lexer rules （大写单词） . 例：

grammar Test;

init: prog(','prog)*;

prog: A
     | prog
     ;

A: [a-z]+;

从语法生成规则的立场出发，我会说解析器规则是NON-TERMINAL符号，可以用词法分析器规则定义的一系列令牌代替 .

因此，非常清楚语法是由the definition无上下文的 . 语法生成的语言的alpahbet包含由小写拉丁字母组成的所有单词 .

Question: 我们可以使用 ANTLR4 定义非上下文语法吗？

java parsing grammar antlr4

1 回答

  • 3

    YES. （咳） .

    我的理解是您可以在规则中添加代码 . 任意代码可以测试任意事物，所以答案是“是” . 一般来说，我认为你不能用ANTLR很好地做到这一点，但这对于许多有趣的特殊情况非常实用（例如，接受除素数之外的所有数字字符串） .

    NO.

    我想如果你坚持使用ANTLR允许的语法规范，答案就是“不” . 事实上，有一些无上下文的语法可以用ANTLR“指定”它无法正确处理，大多数解析器生成器也是如此 . （对于ANTLR，这包括具有间接左递归，歧义，任意前瞻等的语法 . ）我们甚至通过其“限制”的名称调用大多数这些解析器生成器，例如LL（1），LALR（k）等 . .

    Which ones can do full context free?

    一些解析器生成器可以处理完整的，无上下文的语法 . 我想到了Earley和CYK解析器，但它们并不是很快，所以人们往往会避免使用它们 . GLR解析器可以做到这一点（我们在我们的工具中使用它，因为它真的有助于为真实语言编写语法[参见我的生物]但是有一些语法使它们非常慢;你可以大多避免这些 . 显然GLL解析方案存在并且是也完全没有上下文;我希望它们在某些钝语法中也有性能问题，但在实践中也很有用 .

    我听说过唯一可以执行各种上下文相关语法的解析器生成器是MetaS . 我实际上并不是反对意见 .

    回复于

相关问题