recategorized by
2,411 views
6 votes
6 votes

Construct the $\text{LL(1)}$ table for the following grammar.

  1. $Expr \rightarrow \_Expr$
  2. $Expr \rightarrow (Expr)$
  3. $Expr \rightarrow Var\; ExprTail$
  4. $ExprTail \rightarrow \_Expr$
  5. $Expr \rightarrow \lambda$
  6. $Var \rightarrow Id\; VarTail$
  7. $VarTail \rightarrow (Expr)$
  8. $VarTail \rightarrow \lambda$
  9. $Goal \rightarrow Expr$$
recategorized by

2 Answers

Best answer
9 votes
9 votes

Non-Terminals$:\{Goal\ , Expr\ ,ExprTail\ ,Var\ , VarTail\ \}$

Terminals $: \{\_,(,),Id,\lambda \}$

Starting symbol $:\{Goal\}$ ($\because$ The end delimiter $\$ $ is at the end of it in RHS)

Rewriting the grammar

  1. $Goal \rightarrow Expr\$$
  2. $Expr \rightarrow \_Expr\mid  (Expr)\mid Var\; ExprTail\mid \lambda$
  3. $ExprTail \rightarrow \_Expr$
  4. $Var \rightarrow Id\; VarTail$
  5. $VarTail \rightarrow (Expr)\mid \lambda$

$$\begin{array}{|c|c|c|} \hline \textbf{Non-terminal} & \textbf{First}& \textbf{Follow} \\\hline \text{$Goal$} &  \{\_,(,Id,\lambda \}&  \{ \$ \}\\\hline Expr&  \{\_,(,Id,\lambda \} &\{ \$, )\ \} \\\hline \text{$ExprTail $}  & \{\_ \} & \{ \$, )\ \} \\\hline  \text{$Var$} & \{\ Id \} & \{\_ \} \\\hline \text{$VarTail $} & \{ (,\lambda \}  & \{\_ \} \\\hline \end{array}$$The $\text{LL(1)}$ table will be as follows:$$\small{\begin{array}{|c|c|c|c|c|c|c|} \hline& \textbf{_} & \textbf {(} &\textbf {)} & \textbf {Id} &  \textbf{$\lambda$} & \bf{$} \\\hline \textbf{Goal}& \text{$Goal \rightarrow Expr\$$} &\text{$Goal \rightarrow Expr\$$}  & & \text{$Goal \rightarrow Expr\$$} &\text{$Goal \rightarrow Expr\$$} & \\\hline \textbf{Expr} & \text{$Expr \rightarrow \_Expr$} & \text{$Expr \rightarrow \  (Expr)$} &  & \text{$Expr \rightarrow  Var\; ExprTail$}  & \text{$Expr \rightarrow \lambda$} & \\\hline  \textbf{ExprTail}& \text{$ExprTail \rightarrow \_Expr$} &  \\\hline \textbf{Var} & & &  & \text{$Var \rightarrow Id\; VarTail$} \\\hline \textbf{VarTail} & & \text{$VarTail \rightarrow(Expr)$} & &   & \text{$VarTail \rightarrow \lambda$} \\\hline \end{array}}$$

edited by
0 votes
0 votes
the grammar is

\[ \begin{aligned} 1. & \ \text{Expr} \rightarrow \_ \text{Expr} \\ 2. & \ \text{Expr} \rightarrow (\text{Expr}) \\ 3. & \ \text{Expr} \rightarrow \text{Var Expr Tail} \\ 4. & \ \text{ExprTail} \rightarrow \_ \text{Expr} \\ 5. & \ \text{ExprTail} \rightarrow \lambda \\ 6. & \ \text{Var} \rightarrow \text{Id Var Tail} \\ 7. & \ \text{VarTail} \rightarrow (\text{Expr}) \\ 8. & \ \text{VarTail} \rightarrow \lambda \\ 9. & \ \text{Goal} \rightarrow \text{Expr}\$ \end{aligned} \]

the first and follow sets are

 \[ \begin{aligned} & \text{First(Expr)} &&= \{ \_, (, \text{Id} \} \\ & \text{First(ExprTail)} &&= \{ \_, \lambda \} \\ & \text{First(Var)} &&= \{ \text{Id} \} \\ & \text{First(VarTail)} &&= \{ (, \lambda \} \\ & \text{First(Goal)} &&= \{ \_, (, \text{Id} \} \end{aligned} \]

 \[ \begin{aligned} & \text{Follow(Expr)} &&= \{ \$, ), \_ \} \\ & \text{Follow(ExprTail)} &&= \{ \$, ), \_ \} \\ & \text{Follow(Var)} &&= \{ \_, (, ), \text{Id} \} \\ & \text{Follow(VarTail)} &&= \{ \$, ), \_ \} \\ & \text{Follow(Goal)} &&= \{ \$ \} \end{aligned} \]

fill in the LL(1) parsing table:

Related questions

23 votes
23 votes
4 answers
1
Kathleen asked Oct 8, 2014
6,564 views
Translate the arithmetic expression $a^\ast -(b+c)$ into syntax tree.A grammar is said to have cycles if it is the case that $A \overset{+}{\Rightarrow} A$ Show that no g...
44 votes
44 votes
1 answer
3
38 votes
38 votes
3 answers
4