我试图为下面的语法创建一个lalr（1）解析器，并找到一些移位/减少冲突。
S := expr
expr := lval | ID '[' expr ']' OF expr
lval := ID | lval '[' expr ']'
因此解析器无法正确分析字符串“id[id]”。
我的问题是，
有没有什么通用的方法可以把这些非lalr（1）文法转换成lalr（1）文法？
如果两个文法生成完全相同的语言，并且我们知道一个不是lalr（1），那么我们能知道另一个是lalr（1）吗？
上面提到的语法只是一个例子，我真正想知道的是解决这些语法问题的一般方法。欢迎任何建议或阅读建议。
提前谢谢。
最佳答案
一。有没有什么通用的方法可以把这些非lalr（1）文法转换成lalr（1）文法？
不可以。可以将任意上下文无关语法（cfg）转换为lalr（1）语法，也可以不转换。没有通用的算法可以做到这一点，即使你知道这是可能的此外，如果你有一个cfg和一个lalr（1）语法，你就不能判断它们是否识别同一种语言。（更糟糕的是，没有任何算法可以告诉您任意CFG是否可以识别其字母表中的每个可能字符串。）
2.如果两个文法生成完全相同的语言，并且我们知道一个不是lalr（1），那么我们能知道另一个是lalr（1）吗？
同样，没有。如上所述，没有算法可以验证两个文法生成同一种语言，但即使假设您知道两个文法生成同一种语言，其中一个文法不是lalr（1）也不会告诉您关于另一个文法的任何信息。
然而，有一个有用的结果如果有一个有限k>1的lalr（k）文法，那么可以生成一个lalr（1）文法。换言之，k>1不存在lalr（k）语言；如果一种语言有lalr（k）语法，那么它有任何k'的lalr（k'）语法，使得1≤k'但是，这对语法没有帮助，因为增加lookahead到任何有限值都无法消除冲突。
不过，有一种简单的方法可以消除这种特定的转变，减少冲突，而且这是一种经常奏效的技术。考虑两个相互冲突的规则：
lval := lval '[' expr ']'
expr := ID '[' expr ']' OF expr
问题是，在第一种情况下，
ID必须立即减少到lval（或者至少在以下expr减少之前），但在第二种情况下，它可能不会减少到lval但是，在我们减少expr并遇到OF（或不遇到）之前，我们无法判断我们属于哪种情况。如果我们可以在不进行内部
lval缩减的情况下完成lval生产，那么我们就不会有问题，因为当]后面的标记可见时，实际的缩减就会发生。这可能有个技术术语，但我不知道。我一直把它描述为“减少延迟”，在许多情况下，这并不难：
lval' := ID `[` expr `]`
| lval' `[` expr `]`
lval := ID
| lval'
expr := lval
| ID '[' expr ']' OF expr