<- previous index next ->
Greibach Normal Form of a CFG has all productions of the form
A ->aV Where 'A' is a variable, 'a' is exactly one terminal and
'V' is a string of none or more variables.
Every CFG can be rewritten in Greibach Normal Form.
This is step 5 in the sequence of "simplification" steps for CFG's.
Greibach Normal Form will be used to construct a PushDown Automata
that recognizes the language generated by a Context Free Grammar.
Starting with a grammar: G = ( V, T, P, S)
1a) Eliminate useless variables that can not become terminals
1b) Eliminate useless variables that can not be reached
2) Eliminate epsilon productions
3) Eliminate unit productions
4) Convert productions to Chomsky Normal Form
5) Convert productions to Greibach Normal Form using algorithm below:
Re-label all variables such that the names are A1, A2, ... , Am .
The notation A(j) refers to the variable named Aj .
New variables may be created with names B1, B2, ... referred to as B(j) .
Productions may be created and/or removed (a mechanical implementation
may use coloring to track processed, added and deleted productions.)
Step 1 (repeat until no productions are added, m-1 times at most)
begin (m is the number of variables, can change on each repeat)
for k := 1 to m do
begin
for j := 1 to k-1 do
for each production of the form A(k) -> A(j) alpha do
begin
for all productions A(j) -> beta do
add production A(k) -> beta alpha
remove production A(k) -> A(j) alpha
end;
end;
for each production of form A(k) -> A(k) alpha do
begin
add production b(k) -> alpha and B(k) -> alpha B(k)
remove production A(k) -> A(k) alpha
end;
for each production A(k) -> beta where beta does not begin A(K) do
add production A(k) -> beta B(k)
end;
Step 2 (sort productions and delete any duplicates )
Remove A -> A beta by creating B -> alpha B
Substitute so all reules become Greibach with starting terminal.
For neatness, sort productions and delete any duplicates
see book: 2nd Ed. page 271, section 7.1, Exercise 7.1.11 construction
Example (in file format, input given to program cykp,
output file greibach.pda)
// g1.g a test grammar
// G = (V, T, P, S) V={S,A} T={a,b} S=S
//
start S
terminal a b ;
verbose 7 // causes every step of ever loop to be printed
// runs a very long time !
S -> a A S ;
S -> a ;
A -> S b A ;
A -> S S ;
A -> b a ;
enddef
abaa
// greibach.pda , edited, from cykp < g1.g > g1_cykp.out
start S
terminal a ;
terminal b ;
variable A ;
variable C_AS ;
variable C_T_bA ;
variable S ;
variable T_a ;
A -> a C_AS C_T_bA ;
A -> a C_AS S ;
A -> a C_T_bA ;
A -> a S ;
A -> b T_a ;
C_AS -> a C_AS C_T_bA S ;
C_AS -> a C_AS S S ;
C_AS -> a C_T_bA S ;
C_AS -> a S S ;
C_AS -> b T_a S ;
C_T_bA -> b A ;
S -> a C_AS ;
S -> a ;
T_a -> a ;
enddef
Note that an optional optimization could delete the last rule,
and replace T_a by S.
<- previous index next ->