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

Question

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

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

grammar Test;

init: prog(','prog)*;

prog: A
     | prog
     ;

A: [a-z]+;

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

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

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

Answer 1

是的。（咳嗽）。

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

没有.

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

哪些可以做full context free？

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

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

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

Can we define a non context-free grammar with ANTLR?

java

grammar

parsing

antlr4