Here's a CFG for declaration of struct in a language simliar to C.

strt STRUCT ID LCURLY members RCURLY SEMICOLON

members decllist | epsilon

declList declList decl | decl

decl TYPE ID SEMICOLON | TYPE ID ASSIGN INTLIT SEMICOLON

a. Although the CFG given above is not LL(1), some correct struct declaration can be parsed by a predictive parser. This is because those inputs never cause the parser to look at a table entry that contains two or more CFG rules. However, some declaration cannot be parsed by predictive parser because the CFG is not LL(1).

1. Give a struct declaration that is the language of the CFG and can be parsed by a predictive parser.

2. Give the shortest struct declaration that is the language of the CFG but cannot be parsed by a predictive parser.

b. What is the earliest point in the course at which the parser broke? (i.e., a sequence of tokens that is a prefix of a valid input, but for which the parser would not know how to continue to build the parse tree top-down because it looks at a table entry that contains two or more CFG rules)? To answer this question, give all of the following:

1. The sequence of tokens (a prefix of a valid input).

2. The CFG rules that the predictive parser can't choose between to continue to grow the parse tree.

c. One problem with the CFG is that it has not been left factored. Find the CFG rules with a common prefix and transform them by doing left factoring.

d. Another problem with the CFG is that is has immediate left recursion. Find the CFG rules that cause this and transform them to remove the left recursion.