parsing - 是否有解析器生成器能够生成可以解析此: S → 'x' S 'x' | 'x' 的解析器

Question

有一段时间，我对 ANTLR 无法解析以下上下文无关语法规则这一事实感到好奇:S → 'x' S 'x' | “x”。

对我来说，这似乎并不那么复杂。

据我所知，ANTLR 是可用的最强大的 LL 解析器。是否有任何其他类型的解析器生成器(LR 或其他)能够为此生成解析器？

gr，

科恩

Answer 1

我不认为你的语法对于任何 n 都是 LL(n) 或 LALR(n) 或 LR(n) 。证明:修复任意n。您的输入流以 n x 个字符开头，后跟另一个字符。 此时，没有任何进一步的预测，您需要向上还是向下？

由于标准解析器生成器仅适用于这些类别之一的语言(许多类别仅适用于较小的 n 值)，因此您找不到能够处理您的输入的解析器生成器也就不足为奇了。您可能需要重新考虑您的语法是否真的需要看起来像现在这样；对于您给出的简化示例，您也可以 S → 'x' 'x' S |例如“x”。