我们可以用ANTLR定义一个非上下文无关的语法吗?

Question

我对ANTLR4很陌生，现在我正在尝试理解我们可以用它定义哪种语法。

据我所知，ANTLR中有两种规则：解析器规则（小写单词）和词法分析器规则（大写单词）。例：

grammar Test;
init: prog(','prog)*;
prog: A
     | prog
     ;
A: [a-z]+;

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

因此，很明显

，根据定义，语法是与上下文无关的。由语法生成的语言的alpahbet由由小写拉丁字母组成的所有单词组成。

问题：我们可以使用ANTLR4定义一个非上下文无关的语法吗？

Answer 1

是的。 （咳）。

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

不。

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

哪些可以做到完全上下文免费？

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

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