哪些语法可以使用递归下降而无需回溯?

根据维基百科上的“递归下降语法分析器”, 采用不回溯的递归下降(也称为预测分析)仅适用于LL(k)语法。

而在其他地方,我读到Lua的实现使用了这样一个解析器。但该语言不是LL(k)。实际上,Lua本质上是不明确的:a = f(g)(h)[i] = 1是指a = f(g); (h)[i] = 1还是指a = f; (g)(h)[i] = 1? 此二义性由解析器中的贪婪解决(因此以上内容被解析为错误的a = f(g)(h)[i]; = 1)。

这个例子似乎表明,预测性解析器可以处理不是LL(k)的语法。他们可以处理比LL(k)更大的语法吗?如果是,是否有一种方法可以找出特定语法是否在此子集中?

换句话说,如果我正在设计一种想要使用预测分析器解析的语言,我需要将该语言限制为LL(k)吗?还是有一个更宽松的限制可以应用?

点赞