Compiler Construction
Assign 3: Due 26/3

Top-Down Parsing

Develop an iterative algorithm that decides if a non terminal, X is nullable, i.e., X => empty-string
Extend the algorithm to determine if a sequence of grammar symbols is nullable
Use the above algorithm to construct an LL(1) parsing table for the following grammar:
- E -> -E | (E) | V E'
- E' -> -E | empty-string
- V -> id V'
- V' -> (E) | empty-string
Sketch a run of the parser from previous exercise for the input -id(-id)-id
Consider the following grammar:
- G -> P
- G -> P G
- P -> id : R
- R -> empty-string
- R -> id R
Left factor the grammar
Show that the resulting grammar is LL(2) but not LL(1)
Update the advance function to allow two symbols look-a-head and show the parser program for this grammar

Show that the following left-factored simplified if-then-else grammar is not LL(1)

S -> i c t S'
S -> a
S' -> e S
S' -> empty-string

Investigate the two possibilities to patch the parsing table in the above grammar, and their consequences

Bottom-Down Parsing

Construct an SLR(1) parsing table for the following grammar:

E -> T + E | T
T -> F * T | F
F -> id | (E)

Sketch a run of the parser from previous exercise for the input id + id + id. What kind of conclusion can you draw on the impact of right-recursion in LR parsing?

Show that the following grammar is LL(1) but not SLR(1)

S -> A a A b | B b B a
A -> empty-string
B -> empty-string

Explain how to resolve conflicts in the following grammar using precedence directives, grammar transformations, and both. Use CUP in your investigations if you like:

E -> id | E B E
B -> + | - | * | /

Give a non-ambiguous grammar that CUP will not be able to parse due to a shift/reduce conflict. Show a particular valid input in the grammar that will not be recognized.