**This is an old revision of the document!**

- Understand how some grammars require back-tracking to parse because it isn't possible to predict perfectly which production should be used.
- Understand how to do parsing using table-driven parsing and recursive descent parsing for LL(1) grammars

- Recursive descent parsing
- Backtracking and the use of a stack in parsing
- LL(1) grammars
- FIRST and FOLLOW sets
- Constructing a table for table-driven parsing with and without FIRST and FOLLOW sets
- Using the call stack via recursive function calls in recursive-descent parsing

- (4 points) Show the recursive descent parse for the input
*int / int*when trying the rules in order (*int*is an integer literal).

<E> ::= <T> - <E> | <T></p>

<T> ::= ( <E> ) | int | int / <T> - (2 points) Compute the FIRST sets for the following. Compute FOLLOW sets as well for extra credit.

<A> ::= <A><A>'+' | <A><A>'*' | a - (6 points) For each of the following grammars, devise predictive parsers and show the parsing tables. You may left-factor and/or eliminate left-recursion form your grammars first if needed:
- S –> 0 S 1 | 0 1
- S –> + S S | * S S | a
- S –> S ( S ) S | epsilon

- (8 points) Build the parse table for the following grammar with start symbol X. You may left-factor or remove left-recursion if needed.

<X> ::= (<P>)

<X> ::= <Z><P> | <Z>

<X> ::= 0 | 1 - (4 points) The following is a grammar for regular expressions over symbols
*a*and*b*only, using + in place of | for union, to avoid conflict with the use of vertical bar as a meta-symbol in grammars:

<rexpr> ::= <rexpr> '+' <rterm> | <rterm>

<rterm> ::= <rterm> <rfactor> | <rfactor>

<rfactor> ::= <rfactor> '*' | <rprimary>

<rprimary> ::= 'a' | 'b'- Is the grammar ready for LL(1) parsing? If yes, then justify your answer. If no, then modify the grammar so it is LL(1).