1

我正在尝试为以下语法创建一个 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)？

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

提前致谢。

4

1 回答 1

3

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' 满足 1 ≤ k' < k，它都有一个 LALR(k') 文法。

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

不过，有一种简单的方法可以消除特定的班次减少冲突，而且这种技术通常很有效。考虑两个相互冲突的规则：

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
于 2013-08-29T03:40:31.393 回答