6.5. Transforming Grammars¶
6.5.1. Transforming Grammars¶
Programming language developers often use grammars to represent the syntax for a programming language. Of course, a key question related to implementing a programming language (or any other use of a grammer) is this: Is a given program syntactically correct? This is exactly the same as asking if the string is in the language defined by that grammar (the membership problem).
We have seen that if we could transform a CFG into an equivalent CFG with no \(\lambda\)-productions, and no rules like \(A \rightarrow B\), then we can determine if string \(w\) is in or not in \(L(G)\) in \(2|w|\) derivation rounds, where each step adds a terminal or increases the length of the sentential form of the current derivation. This works, but it is not fast! At least it avoids the possibility of getting into an infinite loop.
We will look at some methods for transforming grammars. Sometimes we do this to create a version of the grammar that is easier to work with. Sometimes we just want to know that we can do a transformation to a given form because assuming that the grammar is in that form makes it easier to use in a proof.
