Ete*_*ght 1 grammar parsing ll-grammar lr-grammar
对于一种不是LL(1)or 的语言LR(1)，如何尝试找出某个数字是否n存在使得语法可以是LL(n)or 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的最小可能值，并且不能保证搜索将终止。
Although the problem is hard (or impossible) in the general case, it can often be answered for specific grammars, by considering the possible valid successors of a grammar state which exhibits conflicts.
In most real-world grammars, there will only be a few conflicts, so manual examination of conflicting states is possible. In general terms, one needs to figure out the path which led to the conflicting state, and the possible continuations. In many cases it will be clear that the parsing conflict could be resolved with slightly more lookahead.
A large class of grammars where this will fail is the set of ambiguous grammars. An ambiguous grammar cannot be LR(k) (or LL(k)) for any k. Again, the question of whether a grammar is ambiguous is not decidable but effective heuristics exist, some of which are included in commercial products.
Again, it is often easy to find ambiguities in real-world grammars, either by visual inspection (as above), or by feeding a lot of valid texts into a GLR parser (such as the one produced by bison) until an ambiguity is reported. (Alternatively, you can enumerate valid texts from the grammar with a straight-forward algorithm, and see if a text appears twice in the enumeration.)
Here are a couple of possibly relevant SO questions illustrating analysis techniques. I'm sure there are more.
A yacc shift/reduce conflict on an unambiguous grammar
yacc shift-reduce for ambiguous lambda syntax
How to understand and fix conflicts in PLY