Due by Wednesday, 31st October, 10:15am sharp (right before the class).
We want to construct an LL(1) parser for the following grammar.
S -> ( L ) S -> a L -> L , S L -> S
a) Can the grammar be used with a LL(1) parser as is? If not, modify it accordingly.
b) Compute the First and Follow sets for S and L for the new grammar.
c) Finally, construct the parsing table.
A grammar has a cycle if there is a non-terminal such that ,
i.e. it is possible to derive the nonterminal A from A by a nonempty sequence of production rules.
a) Show that an LL(1) grammar is not allowed to have any cycles. Recall, that an LL(1) grammar is one for which a predictive parser needs just one look-ahead symbol.
b) Give an algorithm that eliminates cycles in a context-free grammar.
Show that the regular languages can be recognized with LL(1) parsers. Describe a process that, given a regular expression, constructs an LL(1) parser for it.
Put the following grammar into Chomsky normal form. Show your steps (i.e. don't just give the final grammar without explanation, or we won't be able/willing to check that it describes the same language).
S -> A ( S ) B | ε A -> S | S B | x | ε B -> S B | y
Assume a grammar in Chomsky normal form has non-terminals. Show that if the grammar can generate a word with a derivation having at least steps, then the recognized language should be infinite.