L7 : Simplifying Context-Free Grammar

Simplifying Context-Free Grammars.
We found already in the last section on CFGs and Parsing, that parsing can be pretty time- and space-consuming. In order to construct good and efficient parsing algorithms, we consider now transformations of grammars, essentially simplifications of the form of productions, which lead to certain normal forms for grammars. These normal forms are better to deal with, and they allow more efficient parsing algorithms.
Methods for Transforming Grammars .
? Substitution Rule
? Removing useless productions
? Removing ?-productions
? Removing unit productions

1-Substitution Rule
If a grammar contains a production
A ? x1 B x2 with A, B ? V and A ? B
and
B ? y1 | y2 | ... | yn (alternatives)
then we can construct a new grammar G with a modified set of productions P , in which we replace the rules for A and B above with one set of rules:
A ? x1 y1 x2 | x1 y2 x2 | ... | x1 yn x2
G and G are equivalent, i.e. the generate the same language.





2-Removing useless productions
Definition Useful Variable
A variable A is called useful if there is at least one w?L(G) such that
S?*xAy ?* w with x, y ? (V ? T)*
Otherwise, it is called useless.
A production is useless, if it involves a useless variable.
Note that the concept of useless variable includes the case that the variable does not lead to a terminal string, and the case that the variable cannot be reached from the start symbol. The elimination of useless variables and productions from a grammar (or the selection of those variables and productions, which are useful) proceeds in two phases:
A. Determine and select those variables, which can lead to a terminal string, and subsequently determine and select the related productions.
B. Determine and select those variables, which can be reached from the start symbol, and select related productions.
Algorithm - find useful variables and productions leading to w?T*
1. Set V1 = ?
2. Repeat until closure:
For every A?V with a production
A ? x1 x2 ... xn and xi ? (V1 ? T)
add A to V1.
3. Set P1 as the subset of productions from P, which contain only symbols from (V1 ? T).
4. This defines a new grammar G1 = (V1, T, S, P1)
Algorithm - eliminate unreachable variables and related productions
Draw a Dependency Graph for G1, above. The dependency graph is a graph with vertices labelled with variables and arcs going from vertex A to a vertex B, if the grammar contains a production A ? x1 B x2.
Eliminate from G1 all variables and related productions, which cannot be reached from the start symbol. This gives the new grammar G , which does not contain useless variables or productions.