Compiler Construction

The grammar G given below describes a language of nested lists like {x, (x,x), x} and (((x))). Every list must have at least one element, and can use both parentheses () and braces {} provided they always match.

term braces | parens braces {list} parens (list) list term rest list x rest rest ,list |

Answer the following questions, each on a separate sheet of paper, scan and submit.

Write down the FIRST set of the grammar (2 marks) Write down the FOLLOW set of the grammar (2 marks) Construct the parse table for the grammar (4 marks) Show the top down predictive parse (include columns matched, stack, input and action) of the expression { x, x } (2 marks)

\begin{tabular}{|l|l|} \hline The set of non-terminals is listed below. & The set of terminals is listed below. Make sure that you don't confuse them with the notation you use to write down the sets. \\ 1. term (start symbol) & 1. \{ \\ 2. braces & 2. } \\ 3. parens & 3. \\ 4. list & 4. \\ 5. rest & 5. x \\ & 6. , \\ \hline \end{tabular}