COSC3302 Program-4 Due: 4/11/2011 CF Grammar Reduction Task: 1. Mandatory Requirement: Write a program that will reduce an input CF grammar by identifying and eliminating all useless symbols and clearly show the resulting grammar (in terms of its production rules). 2. Bonus Points (Up to 10 bonus points) Additionally, your program can identify all nullable nonterminals and eliminate all those nullable nonterminals and clearly show the resulting new (yet equivalent) grammar. Your program will output the following: a. The input grammar rules. b. All useless symbols found. c. The resulting grammar after all useless symbols have been eliminated. d. All nullable nonterminals. (Bonus points) e. The final reduced grammar after eliminating all empty-production rules and making adjustments for each nullable nonterminal. (Bonus points) Input grammar: Program --> Block Program --> Block More Block --> begin Body end More --> More Extra More --> More Body Extra --> Extra Body Extra --> Body Another Another --> Another , SS Another --> Another , SR Another --> SR More Body --> S Body Body --> S S --> Block S --> var = Exp S --> Print ExpList S --> SS SR S --> Empty-string S --> If Exp then SS endif S --> If Exp then S else S endif Others --> Read IdList IdList --> id , IdList IdList --> id SS --> S , More SS --> Empty-string SR --> SS : SR ExpList --> Exp ExpList --> Exp , ExpList Exp --> var Exp --> Empty-string