algorithm - 有没有一种通用的方法可以将明确的上下文无关文法转换为 LALR(1) 文法？

Question

我正在尝试为以下语法创建一个 LALR(1) 解析器并发现一些移位/归约冲突。

S := expr
expr := lval | ID '[' expr ']' OF expr
lval := ID | lval '[' expr ']'

所以解析器无法正确解析字符串“ID[ID]”。我的问题是，

1. 是否有任何通用方法可以将此类非 LALR(1) 文法转换为 LALR(1) 文法？
2. 如果两个文法生成完全相同的语言，并且我们知道一个不是 LALR(1)，那么我们能否知道另一个是否是 LALR(1)？

上面提到的语法只是一个例子，我真正想知道的是解决这些语法问题的一般方法。欢迎任何建议或阅读建议。

提前致谢。

Answer 1

1 . Are there any general ways to convert such non-LALR(1) grammars into LALR(1) grammars?

没有。将任意上下文无关文法 (CFG) 转换为 LALR(1) 文法可能可行，也可能不可行。此外，如果你有一个 CFG 和一个 LALR(1) 文法，你无法判断它们是否识别相同的语言。 (更糟糕的是，没有算法甚至可以告诉您任意 CFG 是否识别其字母表的每个可能字符串。)

2 . If two grammars generate exactly the same languages and we know that one is not LALR(1), can we know if the other is LALR(1)?

同样，不。如上所述，没有算法可以验证两个文法生成相同的语言，但即使假设您知道两个文法生成相同的语言，其中一个不是 LALR(1) 这一事实也不会告诉您关于另一个的任何信息一个。

但是，有一个有用的结果。如果你有一个有限 k > 1 的 LALR(k) 文法，那么你可以生成一个 LALR(1) 文法。换句话说，对于 k > 1，不存在 LALR(k) 语言；如果一种语言具有 LALR(k) 文法，则对于满足 1 ≤ k' < k 的任何 k'，它都具有 LALR(k') 文法。

但是，这对您的语法没有帮助，因为无法通过增加对任何有限值的前瞻性来消除冲突。

不过，有一种简单的方法可以消除这种特定的 shift-reduce 冲突，而且这种方法经常有效。考虑两个相互冲突的规则:

lval := lval '[' expr ']'
expr := ID   '[' expr ']' OF expr

问题是在第一种情况下，ID 必须立即缩减为 lval(或者至少，在以下 expr 被缩减之前)减少)，但在第二种情况下，它可能不会减少到 lval。但是在我们减少 expr 并遇到(或没有)OF 之前，我们无法判断我们处于哪种情况。

如果我们可以在不进行内部 lval 缩减的情况下完成 lval 的产生，那么我们就不会有问题，因为实际的缩减会在 token 跟随时发生] 可见。

这可能有一个技术术语，但我不知道。我一直把它描述为“递减延迟”，在很多情况下它并不是很难:

lval' := ID `[` expr `]`
      |  lval' `[` expr `]`
lval  := ID
      |  lval'
expr  := lval
      |  ID '[' expr ']' OF expr