是否有一个解析器生成器能够生成一个解析器,可以解析它: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'.