如何识别一个文法是LR(n), LL(n)
How to identify whether a grammar is LR(n), LL(n)
对于一种不是 LL(1) 或 LR(1) 的语言，如何尝试找出是否存在某个数字 n 使得语法可以是 LL(n) 或LR(n)?
您可以通过查看 LR(0) 项的规范集合来检查语法是否 LR(0)。然后，假设它不是 LR(0)，您可以通过引入前瞻符号来检查它是否是 LR(1)。我的简单推理告诉我，要检查它是否为 LR(2)，您可能必须让前瞻包含接下来的两个符号而不是一个。对于 LR(3) 你必须考虑三个符号等等
即使是这种情况，尽管我对此表示怀疑，但我仍在努力思考如何尝试识别（甚至得到暗示）一个 n，或者不存在其中，特定语法可以是 LR(n) and/or LL(n) 而无需从任意 LR(m) 向上递增检查。
如果语言是LR(k)对于某些k>1，则为LR(1)。 （当然，对于文法而言，情况并非如此。）也就是说，如果您有一种语言的 LR(k) 文法，那么您可以机械地构造一个 LR(1) 文法，它允许您恢复原始解析树。这不是 LL(k); LL(k) 语言是 LL(k+1) 语言的严格子集。
你提出的测试确实会让你决定一个 grammar 是否是 LR(k) 对于一些给定的k（或 LL(k)）。不幸的是，除了您建议的连续搜索之外，没有办法计算出 k 的最小可能值，并且不能保证搜索将永远终止。
虽然这个问题在一般情况下很难（或不可能），但通常可以通过考虑表现出冲突的语法状态的可能有效后继来解决特定语法问题。
在大多数 real-world 语法中，只会有少数冲突，因此可以手动检查冲突状态。一般来说，需要弄清楚导致冲突状态的路径，以及可能的延续。在许多情况下，很明显可以通过稍微向前看来解决解析冲突。
大量 class 语法将失败，这是一组不明确的语法。对于任何 k，歧义文法不能是 LR(k)（或 LL(k)）。同样，语法是否有歧义的问题无法确定，但存在有效的启发式方法，其中一些包含在商业产品中。
同样，通常很容易在 real-world 语法中发现歧义，可以通过视觉检查（如上所述），也可以通过将大量有效文本输入 GLR 解析器（例如由bison) 直到出现歧义。 （或者，您可以使用 straight-forward 算法从语法中枚举有效文本，并查看一个文本是否在枚举中出现两次。）
这里有几个可能相关的 SO 问题说明了分析技术。我确定还有更多。
A yacc shift/reduce conflict on an unambiguous grammar
Bison reduce/reduce situation
对于一种不是 LL(1) 或 LR(1) 的语言，如何尝试找出是否存在某个数字 n 使得语法可以是 LL(n) 或LR(n)?
您可以通过查看 LR(0) 项的规范集合来检查语法是否 LR(0)。然后，假设它不是 LR(0)，您可以通过引入前瞻符号来检查它是否是 LR(1)。我的简单推理告诉我，要检查它是否为 LR(2)，您可能必须让前瞻包含接下来的两个符号而不是一个。对于 LR(3) 你必须考虑三个符号等等
即使是这种情况，尽管我对此表示怀疑，但我仍在努力思考如何尝试识别（甚至得到暗示）一个 n，或者不存在其中，特定语法可以是 LR(n) and/or LL(n) 而无需从任意 LR(m) 向上递增检查。
如果语言是LR(k)对于某些k>1，则为LR(1)。 （当然，对于文法而言，情况并非如此。）也就是说，如果您有一种语言的 LR(k) 文法，那么您可以机械地构造一个 LR(1) 文法，它允许您恢复原始解析树。这不是 LL(k); LL(k) 语言是 LL(k+1) 语言的严格子集。
你提出的测试确实会让你决定一个 grammar 是否是 LR(k) 对于一些给定的k（或 LL(k)）。不幸的是，除了您建议的连续搜索之外，没有办法计算出 k 的最小可能值，并且不能保证搜索将永远终止。
虽然这个问题在一般情况下很难（或不可能），但通常可以通过考虑表现出冲突的语法状态的可能有效后继来解决特定语法问题。
在大多数 real-world 语法中，只会有少数冲突，因此可以手动检查冲突状态。一般来说，需要弄清楚导致冲突状态的路径，以及可能的延续。在许多情况下，很明显可以通过稍微向前看来解决解析冲突。
大量 class 语法将失败，这是一组不明确的语法。对于任何 k，歧义文法不能是 LR(k)（或 LL(k)）。同样，语法是否有歧义的问题无法确定，但存在有效的启发式方法，其中一些包含在商业产品中。
同样，通常很容易在 real-world 语法中发现歧义，可以通过视觉检查（如上所述），也可以通过将大量有效文本输入 GLR 解析器（例如由bison) 直到出现歧义。 （或者，您可以使用 straight-forward 算法从语法中枚举有效文本，并查看一个文本是否在枚举中出现两次。）
这里有几个可能相关的 SO 问题说明了分析技术。我确定还有更多。
A yacc shift/reduce conflict on an unambiguous grammar
Bison reduce/reduce situation