2

首先，我检查了类似的问题，但没有一个包含我所寻求的信息。

我想知道，给定上下文无关的语法，是否有可能：

  • 知道是否存在等效的 LL(1) 语法。等效于它应该生成相同的语言。
  • 将上下文无关文法转换为等效的 LL(1) 文法，前提是它存在。如果存在等效的 LL(1) 语法，则转换应该成功。如果不存在等价物，它不终止也没关系。

如果这些问题的答案是肯定的，那么这些算法或工具是否在某处可用？我自己的研究没有结果。

另一个答案提到 Dragon Book 有一种算法可以消除左递归并留下上下文无关语法。我可以访问这本书并检查了它，但我不清楚语法是否保证为 LL(1)。对上下文无关语法（没有空产生和没有循环）施加的限制对我来说是可以接受的。

4

1 回答 1

2

从我参加的大学编译器课程中，我记得 LL(1) 语法是上下文无关语法，但上下文无关语法比 LL(1) 大得多。没有通用算法（意味着不是 NP 难）来检查和从上下文无关（可以转换为 LL(1)）转换为 LL(1)。

当您想要集成一个函数时，应用诸如移除左递归、移除首尾冲突、左因子分解等技巧的袋子类似于数学变换......您需要的经验有时非常接近一门艺术。这些变换通常是彼此相反的。

LR 类型文法现在大量用于生成的解析器的一个原因是，它们比 LL(1) 涵盖了更广泛的上下文无关文法。

顺便提一句。例如，C 语法可以表示为 LL(1)，但 C# 不能（例如x -> x + 1想到 lambda 函数，您无法确定您看到的是 lambda 参数还是已知变量）。

于 2012-05-16T10:38:39.397 回答