6.4. Transforming Grammars¶
6.4.1. Transforming Grammars¶
Programming language developers often use grammars to represent a 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 then 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 lots of methods for transforming grammars. Some will be forms that are easier to work with, some are easier to use in proofs.
