6.3. Transforming Grammars¶
6.3.1. Transforming Grammars¶
We use grammars to represent a programming language. Want to know: Is a given string (or program \(x\)) valid (syntactically correct)? Same as asking if it is in the language (the membership problem).
Last time we showed that if we could transform a CFG into a CFG with no \(\lambda\)-productions, and no rules like \(A \rightarrow B\), then we could determine if \(w\) is in or not in \(L(G)\) in \(2|w|\) rounds, each step adding a terminal or increasing in length.
This works, but it is not fast, that is, not linear!
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.
Key question: Are there ways to transform (restrict) CFGs such that
1) We can process efficiently
2) without restricting the power of CFGs
