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

Question

我对ANTLR4还是很陌生，现在我想了解我们可能会用它定义哪种语法。

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

grammar Test;

init: prog(','prog)*;

prog: A
     | prog
     ;

A: [a-z]+;

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

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

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

Answer 1

是。 （咳嗽）。

据我了解，您可以将代码添加到规则中。任意代码可以测试任意事物，因此答案为“是”。总的来说，我认为您无法使用ANTLR做到这一点，但这对于许多有趣的特殊情况（例如，接受除质数之外的所有数字字符串）来说非常实用。

没有。

我认为，如果您遵守ANTLR允许的语法规范，答案是“否”。实际上，您可以使用ANTLR“指定”上下文无关的语法来说明它不能正确处理，这对于大多数解析器生成器都是如此。（对于ANTLR，这包括具有间接左递归，歧义，任意超前等的语法。）我们甚至甚至将大多数此类解析器生成器称为其“限制”，例如LL（1），LALR（k）等。
。

哪些可以完全释放上下文？

一些解析器生成器可以处理完全上下文无关的语法。Earley和CYK解析器浮现在脑海，但它们的速度不是很快，因此人们倾向于避免使用它们。GLR解析器可以做到这一点（我们在工具中使用了它，因为它确实有助于编写真实语言的语法（请参见我的简历），但是有些语法会使它们变得非常慢；您可以避免这些语法。显然，GLL解析方案存在并且也完全没有上下文；我希望它们也会因使用一些过时的语法而出现性能问题，而且在实践中也非常有用。

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