Parsers- LL(1)

Frank Coelho de Alcantara -2021    

Exercício LL(1)

Considere o alfabeto $\Sigma = \{n, +, *, (, )\}$, o seguinte conjunto de Regras de produção e a Tabela D a seguir:

  1. $S \rightarrow TR$
  2. $R \rightarrow \varepsilon$
  3. $R \rightarrow +S$
  4. $T \rightarrow FG$
  5. $G \rightarrow \varepsilon$
  6. $G \rightarrow *T$
  7. $F \rightarrow n$
  8. $F \rightarrow (S)$
$n$ $+$ $*$ $($ $)$ $\$$
$S$ $1$ $ $ $ $ $1$ $ $ $ $
$R$ $ $ $3$ $2$ $ $ $2$ $2$
$T$ $4$ $ $ $ $ $4$ $ $ $ $
$G$ $ $ $5$ $6$ $ $ $5$ $5$
$F$ $7$ $ $ $ $ $8$ $ $ $ $

use para gerar a árvore sintática abstrata da string "n+n*n" sem as aspas.

Exercício LL(1) - Solução

  1. $S \rightarrow TR$
  2. $R \rightarrow \varepsilon$
  3. $R \rightarrow +S$
  4. $T \rightarrow FG$
  5. $G \rightarrow \varepsilon$
  6. $G \rightarrow *T$
  7. $F \rightarrow n$
  8. $F \rightarrow (S)$
$n$ $+$ $*$ $($ $)$ $\$$
$S$ $1$ $ $ $ $ $1$ $ $ $ $
$R$ $ $ $3$ $2$ $ $ $2$ $2$
$T$ $4$ $ $ $ $ $4$ $ $ $ $
$G$ $ $ $5$ $6$ $ $ $5$ $5$
$F$ $7$ $ $ $ $ $8$ $ $ $ $
Localizado Pilha Buffer Ação
   S $ n + n * n$ Reduce S → T R
   T R $ n + n * n $ Reduce T → F G
   F G R $ n + n * n $ Reduce F → n
   n G R $ n + n * n $ Encontrei n
n G R $ + n * n $ Reduce G → ε
n R $ + n * n $ Reduce R → + S
n + S $ + n * n $ Encontrei +
n + S $ n * n $ Reduce S → T R
n + T R $ n * n $ Reduce T → F G
n + F G R $ n * n $ Reduce F → n
n + n G R $ n * n $ Encontrei n
n + n G R $ * n $ Reduce G → * T
n + n *T R $ * n $ Encontrei *
n + n * T R $ n $ Reduce T → F G
n + n * F G R $ n $ Reduce F → n
n + n * n G R $ n $ Encontre n
n + n * n G R $ $ Reduce G → ε
n + n * n R $ $ Reduce R → ε
n + n * n $ $ Fim

First

Considere a seguinte gramática:

  1. $E \rightarrow TE'$
  2. $E' \rightarrow +TE' | \varepsilon$
  3. $T' \rightarrow FT'$
  4. $T \rightarrow *FT'\space | \space \varepsilon $
  5. $F \rightarrow (E) \space | \space id$
Símbolo First()
$E$ $First(E)=\{\}$
$E'$ $First(E')=\{+,\varepsilon\}$
$T$ $First(T)=\{\}$
$T'$ $First(T')=\{*, \varepsilon\}$
$F$ $First(F)=\{(,id\}$
First()
$First(E)=\{(,id)\}$
$First(E')=\{+,\varepsilon\}$
$First(T)=\{(,id\}$
$First(T')=\{*, \varepsilon\}$
$First(F)=\{(,id\}$

Regras para Follow

Considerando que $N={A,B}$ e que $\alpha, \beta$ representam conjuntos de símbolos terminais, não terminais ou uma combinação de ambos, temos as seguintes regras para encontrar as funções $Follow()$ :

  1. se $A$ é o símbolo inicial, então $Follow(A)=\{\$\}$
  2. regras de produção na forma $B \rightarrow \alpha A \beta$ então: $Follow(A) = First(\beta)$
  3. regras de produção na forma $B \rightarrow \alpha A$ ou $B \rightarrow \alpha A \beta$ onde $\beta = \varepsilon$ então $Follow(A) = Follow(B)$
  4. $\varepsilon \notin Follow(A)$

Follow()

  1. $E \rightarrow TE'$
  2. $E' \rightarrow +TE' | \varepsilon$
  3. $T' \rightarrow FT'$
  4. $T \rightarrow *FT'\space | \space \varepsilon $
  5. $F \rightarrow (E) \space | \space id$
Símbolo First()
$E$ $First(E)=\{(,id)\}$
$E'$ $First(E')=\{+,\varepsilon\}$
$T$ $First(T)=\{(,id\}$
$T'$ $First(T')=\{*, \varepsilon\}$
$F$ $First(F)=\{(,id\}$
Símbolo Follow()
$E$ $Follow(E)=\{\$\} \cup \{)\} = \{\$,)\}$
$E'$ $Follow(E')=Follow(E) = \{\$, )\}$
$T$ $Follow(T)=\{+\} \cup Follow(E') = \{+, \$, )\}$
$T'$ $Follow(T')=Follow(T) = \{+, \$, )\}$
$F$ $Follow(F)=\{*\} \cup Follow(T') = \{*, +, \$, )\}$

Exercício First-Follow

Considerando a gramática a seguir, compute as funções $First()$ e $Follow()$:

  1. $S \rightarrow (A) | \varepsilon$
  2. $A \rightarrow TE$
  3. $E \rightarrow \&TE | \varepsilon$
  4. $T \rightarrow (A) | a|b|c$
Símbolo First()
$S$ $\{(, \varepsilon \}$
$A$ $\{(, a, b, c\}$
$E$ $\{\&,\varepsilon\}$
$T$ $\{(, a, b, c\}$
Símbolo Follow()
$S$ $Follow(S)=\{\$\} = \{\$\}$
$A$ $Follow(A)=\{)\}$
$E$ $Follow(E)= Follow(A) = \{)\}$
$T$ $Follow(T)=\{\&\} \cup Follow(E) = \{\&, )\}$

Exemplo Tabela

  1. $E \rightarrow TE'$
  2. $E' \rightarrow +TE' | \varepsilon$
  3. $T \rightarrow FT'$
  4. $T' \rightarrow *FT'\space | \space \varepsilon $
  5. $F \rightarrow (E) \space | \space id$
First()
$First(E)=\{(,id)\}$
$First(E')=\{+,\varepsilon\}$
$First(T)=\{(,id\}$
$First(T')=\{*, \varepsilon\}$
$First(F)=\{(,id\}$
Follow()
$Follow(E)= \{\$,)\}$
$Follow(E')= \{\$, )\}$
$Follow(T)== \{+, \$, )\}$
$Follow(T')= \{+, \$, )\}$
$Follow(F)= \{*, +, \$, )\}$
$id$$+$$*$$($$)$$\$$
$E$$E \rightarrow TE'$$E \rightarrow TE'$
$E'$$E' \rightarrow +TE'$$E' \rightarrow \varepsilon$$E' \rightarrow \varepsilon$
$T$$T \rightarrow FT'$$T \rightarrow FT'$
$T'$$T' \rightarrow \varepsilon$$T' \rightarrow *FT'$$T' \rightarrow \varepsilon$$T' \rightarrow \varepsilon$
$F$$F \rightarrow id$$F \rightarrow (E)$

Exercício

Considerando os dados apresentados no Exercício First-Follow, crie a tabela referente ao seguinte conjunto de regras de produção.

  1. $S \rightarrow (A) | \varepsilon$
  2. $A \rightarrow TE$
  3. $E \rightarrow \&TE | \varepsilon$
  4. $T \rightarrow (A) | a|b|c$