Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Note: we will use $\epsilon$ (epsilon) to denote the empty string.

Problem 1

The following grammar is not LL(1), because of the common prefix problem. Rewrite as an LL(1) grammar defining the same language.
$S \rightarrow c\ |\ aT\ |\ abT$
$T \rightarrow ba\ |\ ca\ |\ ac$

Problem 2

The grammar below is not LL(1) due to left recursion in the rules. Rewrite as an LL(1) grammar defining the same language.
$S \rightarrow a X b S \ |\ \epsilon$
$X \rightarrow Xc\ |\ c$

Problem 3

Consider the following grammar that defines the language of scheme expressions with symbols ($s$) and numbers ($n$). So the terminals/tokens are: $(, ), s, n$. Draw a parse tree for the string $(s (n n))$.
$E \rightarrow (\ L \ )\ |\ A$
$L \rightarrow E L\ |\ \epsilon$
$A \rightarrow n\ |\ s$

Problem 4

The problem 3 grammar is:
$E \rightarrow (\ L \ )\ |\ A$
$L \rightarrow E L\ |\ \epsilon$
$A \rightarrow n\ |\ s$
This is LL(1), so we should be able to put together a top down parser for it. Consider the input
( s ( n n ) ). Trace through the process of top-down parsing this input, and
  1. Write down the input remaining and stack contents at the first point at which you needed to decide whether to apply the rule $L \rightarrow EL$ or the rule $L \rightarrow \epsilon$ and chose $L \rightarrow EL$. 
    
input remaining: _______________________      ________________________||stack
  2. Write down the input remaining and stack contents at the first point at which you needed to decide whether to apply the rule $L \rightarrow EL$ or the rule $L \rightarrow \epsilon$ and chose $L \rightarrow \epsilon$. 
    
input remaining: _______________________      ________________________||stack
  3. What's the rule for how you decide between the two?