Tutorial 5

For a production of the form $A\rightarrow\alpha N\beta$ Add $\text{First}(\beta)-\{\epsilon\}\in\text{Follow}(N)$

Question 1

Consider the following grammar for possibly nested lists of numbers and identifiers enclosed in parentheses. The symbols NUM and ID are terminal symbols (lexical tokens) that matches numbers and identifiers, respectively.

1. Remove any left recursion in the grammar

   To remove the left recursion from: $A\rightarrow A\alpha|\beta$ Which matches a $\beta$ followed by one or more occurrences of $\alpha$, one can re-write the production as follows:

   $$A\rightarrow \beta A'\\A'\rightarrow \epsilon | \alpha A'$$

   • The left recursion in this grammar occurs in the production

     $\text{lexpseq}\rightarrow\text{lexpSeq lexp | lexp}$

     • We resolve this by introducing a new non-terminal symbol, say $\text{lexpNext}$, and a new production
     • Using the formula defined above, A = lexpseq, alpha=lexp, beta=lexp
     $$\text{lexpseq}\rightarrow\text{lexp lexpNext}\\ \text{lexpNext}\rightarrow\epsilon|\alpha \text{ lexpNext'}$$

   • Finally, the productions are:

     $$\begin{aligned} \text{lexp}&\rightarrow\text{atom | list}\\ \text{atom}&\rightarrow\bold{NUM\ |\ ID}\\ \text{list}&\rightarrow\text{'(' lexpSeq ')'}\\ \text{lexpseq}&\rightarrow\text{lexp lexpNext}\\ \text{lexpNext}&\rightarrow\epsilon|\text{lexp lexpNext'} \end{aligned}$$

2. Construct $\text{First}$ and $\text{Follow}$ sets for the non-terminals of the resulting grammar for the question above

   • The non-terminal symbols in the productions above are:
     $$\{\text{lexp, atom, list,lexpSeq, lexpNext}\}$$
   $$\def\first{\text{First}} \first(\bold{NUM})=$$

3. d

• FIrst column - add all of the terminal symbols in the production
• lexp can start with an atom, so we add the first set of an atom to lexp

d.

The following productions are given from before

We can convert to extended bnf form or some shit

lexpSeq → lexp {lexp}

Q2

Type → INT | Type’

Type’ → \epsilon | LBRACKET RBRACKET Type’

Convert to EBNF

Type → INT {LB RB}