对于一种不LL(1)
或LR(1)
的语言,如何尝试找出是否存在一些数字n
,以便语法可以LL(n)
或LR(n)
?
您可以通过查看LR(0)
项的规范集合来检查语法是否LR(0)
。然后,假设它没有LR(0)
,您可以通过引入前瞻符号来检查它是否LR(1)
。我的简单推理告诉我,要检查它是否LR(2)
,您可能必须使前瞻包含接下来的两个符号,而不仅仅是一个符号。对于LR(3)
,您必须考虑三个符号等。
即使情况是这样,即使我对此表示怀疑,我也在努力思考如何尝试识别(甚至暗示)一个n
,或者它不存在,一个特定的语法可以LR(n)
和/或LL(n)
,而不从任意LR(m)
向上逐步检查。
-
如果一种语言对于某些k>1 是 LR(k),那么它是 LR(1)。(当然,对于语法来说并非如此。也就是说,如果你有一个语言的 LR(k) 语法,那么你可以机械地构造一个 LR(1) 语法,它允许你恢复原始解析树。LL(k)则不然;LL(k) 语言是 LL(k+1) 语言的严格子集。
-
你提出的测试确实会让你决定语法是否是某个给定的k(或LL(k))的LR(k)。不幸的是,除了您提出的连续搜索之外,没有办法找出k的最小可能值,并且不能保证搜索会终止。
-
尽管这个问题在一般情况下很难(或不可能),但通常可以通过考虑表现出冲突的语法状态的可能有效继承者来回答特定的语法。
在大多数现实世界的语法中,只会有少量冲突,因此可以手动检查冲突状态。一般而言,人们需要找出导致冲突状态的路径,以及可能的延续。在许多情况下,很明显,解析冲突可以通过稍微多一点的展望来解决。
这将失败的一大类语法是一组不明确的语法。对于任何 k,歧义语法不能是 LR(k)(或 LL(k))。同样,语法是否模棱两可的问题不是可判定的,但存在有效的启发式方法,其中一些包含在商业产品中。
同样,通常很容易在现实世界的语法中发现歧义,无论是通过目视检查(如上所述),还是通过将大量有效文本输入 GLR 解析器(例如 bisson 生成的文本)直到报告歧义。(或者,您可以使用直接算法从语法中枚举有效文本,并查看文本是否在枚举中出现两次。
以下是几个可能相关的SO问题,说明了分析技术。我相信还有更多。
关于明确语法的 yacc 转移/减少冲突
野牛减少/减少情况
YACC 移位-归约,用于不明确的 lambda 语法
如何理解和修复 PLY 中的冲突