java - 我们可以用 ANTLR 定义一个非上下文无关文法吗？

Question

我是 ANTLR4 的新手，现在我正在尝试了解我们可以用它定义哪种语法。

据我所知，ANTLR 中有两种规则:解析器规则(小写单词)和词法分析器规则(大写单词)。示例:

grammar Test;

init: prog(','prog)*;

prog: A
     | prog
     ;

A: [a-z]+;

从语法产生规则的角度来看，我会说解析器规则是非终端符号，可以用词法分析器规则定义的一系列标记替换。

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

问题:我们可以使用 ANTLR4 定义非上下文无关文法吗？

Answer 1

是的。(咳嗽)。

据我了解，您可以向规则中添加代码。任意代码可以测试任意事物，所以答案是"is"。一般来说，我不认为你可以用 ANTLR 做到这一点，但这对于许多有趣的特殊情况非常实用(例如，接受除素数之外的所有数字字符串)。

没有。

我认为如果您坚持 ANTLR 允许的语法规范，答案是否定的。事实上，您可以使用 ANTLR“指定”它无法正确处理的上下文无关语法，这对于大多数解析器生成器都是如此。 (对于 ANTLR，这包括具有间接左递归、歧义、任意先行等的语法)我们甚至通过它们的“限制”名称来调用这些解析器生成器中的大多数，例如 LL(1)、LALR(k) 等.

哪些可以做full context free？

一些解析器生成器可以处理完整的、上下文无关的语法。想到 Earley 和 CYK 解析器，但它们不是很快，因此人们倾向于避免使用它们。 GLR 解析器可以做到这一点(我们在我们的工具中使用它，因为它确实有助于为真实语言编写语法 [请参阅我的简历] 但有些语法会使它们非常慢；你基本上可以避免这些。显然 GLL 解析方案存在并且是也是完全上下文无关的；我希望他们也会遇到一些钝语法的性能问题，但在实践中也很有用。

我听说过的唯一可以执行各种上下文相关语法的解析器生成器是 MetaS .我从未使用过它，但它背后的理论令人印象深刻。声称它可以执行任意上下文相关的语法；对于任意讨厌的语法，它会产生极高的成本，但这实际上并不是一个反对意见。