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

Question

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

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

grammar Test;

init: prog(','prog)*;

prog: A
     | prog
     ;

A: [a-z]+;

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

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

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

Answer 1

是的。（咳嗽）。

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

不。

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

哪些可以完全无上下文？

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

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