Task:

Write a program that does the following:

1. take a simple input CFG without lambda-productions

2. compute and print out all Unit-productions, both explicit and implicit, and

3. compute and print out all necessary productions to be added the set of the original Non-Unit productions of the input CFG.

4. print out all productions of the resulting equivalent grammar

(See the example "EXAMPLE 6.6" on pages 166 and 167)

Two input grammars:

Use these two grammars to test your program:

1. Grammar of EXAMPLE 6.6 on page 166 that has three variables and three terminals, a, b, c.

2. Second grammar:

S ---> E

E ---> E + T

E ---> T

T ---> F ^ T

T ---> F

F ---> a

F ---> b

F ---> c

F ---> ( E )

Note that above grammar has three explicit Unit-productions: S--->E, E--->T and T--->F.

Now, because of the first two of these three, we have S--->T, which is implicit. We also have

S--->F, implicit. So, in general, we will get many implicit ones in addition to explicit ones.

They both must be accounted for in removing all Unit-productions.

Some simplification Assumptions:

You may make following assumptions for the sake of simplifying your programming task:

1. Every uppercase letter is a variable and any character other than an uppercase letter is each a terminal.

2. S is the Start Variable.