5. 文法的变换¶
5.1. 文法的变换¶
编程语言开发者经常使用文法来表示编程语言的语法。 当然，与实现一种编程语言（或对文法的任何其他使用）相关的关键问题是： 给定的程序在语法上是否正确？ 这完全等同于问：这个串是否在该文法定义的语言中（成员问题）。
我们已经看到，如果能把一个 CFG 变换为等价的、 没有 \(\lambda\)-产生式、也没有类似 \(A \rightarrow B\) 规则的 CFG， 那么我们就可以在 \(2|w|\) 轮推导内确定串 \(w\) 是否在 \(L(G)\) 中， 其中每一步都会增加一个终结符，或者增加当前推导的句式的长度。 这样做可行，但速度不快！ 至少它避免了陷入无限循环的可能性。
我们将研究一些变换文法的方法。 有时我们这样做是为了创建一个更容易处理的文法版本。 有时我们只是想知道我们 能够 把文法变换到某种给定形式， 因为假设文法处于那种形式会让它在证明中更容易使用。
在本模块中我们要回答的问题：
是否存在某种变换（限制）CFG 的方法，使得：
1) 我们能够高效地处理它们？
2) 同时又不会限制 CFG 的能力？
