Assignment 3

Write a program that takes two arguments: the name of an input file of context-free grammar rules and the name of an non-existing output file that your program will fill with the CNF (Chomsky Normal Form) conversion of the input context-free grammar. The input file will be an ascii text file of context-free grammar rules in the form:

S -> NP VP
S -> Aux NP VP
S -> VP
NP -> Pronoun
NP -> Proper-Noun

Where each grammar rule is on its own line (you can choose UNIX, Mac or Windows type line ending markers) and the separator between the right-hand-side and left-hand-side of the rule is a space followed by a dash followed by a greater-than sign followed by a space and the separator between symbols is a single space. Your program's output will also be a text file with one rule per line. Note that this is equivalent to exercises 12.11 and 13.1 from your textbook. The solution to 12.11 (the conversion algorithm) is actually given in your textbook on pages 437-438. You can also find pseudo-code online on Wikipedia and other sites.

Test your program on the L1 grammar (Figure 13.8 in your textbook). Turn in to Laulima a zip file with your program code, your test file of the L1 grammar, the program output to your test file, and a README file describing how to compile and run your program.