Tutoriais - Compiladores
Tutoriais
Compiladores

1. Ybadoo
2. Tutoriais
3. Compiladores
4. Análise Sintática
5. Exercício 03.65

Exercício 03.65

Apresente a Análise Preditiva Tabular, com recuperação de erros em modo pânico, da entrada r1: se a_zero então r4 senão vá_para r2;r2:faça vá_para r3;r3:faça adicionar_b vá_para sobre a gramática a seguir.

G = ({S, C, D, I, A, N, G}, {:, ;, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, r, faça, subtrair_a, adicionar_b, vá_para, se, a_zero, então, senão}, P, S)
P = { S → C | S C
      C → A : D ; | A : I ;
      D → faça subtrair_a vá_para A | faça adicionar_b vá_para A
      I → se a_zero então vá_para A senão vá_para A
      A → r N
      N → G | N G
      G → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 }

Solução do Exercício

1. Eliminação da recursividade à esquerda:

1.1. Simplificação da gramática livre de contexto:

G = ({S, C, D, I, A, N, G}, {:, ;, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, r, faça, subtrair_a, adicionar_b, vá_para, se, a_zero, então, senão}, P, S)
P = { S → A : D ; | A : I ; | S C
      C → A : D ; | A : I ;
      D → faça subtrair_a vá_para A | faça adicionar_b vá_para A
      I → se a_zero então vá_para A senão vá_para A
      A → r N
      N → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | N G
      G → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 }

1.2. Renomeação das variáveis em uma ordem crescente qualquer:

G = ({A, B, C, D, E, F, G}, {:, ;, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, r, faça, subtrair_a, adicionar_b, vá_para, se, a_zero, então, senão}, P, A)
P = { A → E : C ; | E : D ; | A B
      B → E : C ; | E : D ;
      C → faça subtrair_a vá_para E | faça adicionar_b vá_para E
      D → se a_zero então vá_para E senão vá_para E
      E → r F
      F → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | F G
      G → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 }

1.3. Transformação das produções da forma A_r → A_sα, onde r ≤ s:

G = ({A, B, C, D, E, F, G}, {:, ;, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, r, faça, subtrair_a, adicionar_b, vá_para, se, a_zero, então, senão}, P, A)
P = { A → E : C ; | E : D ; | A B
      B → E : C ; | E : D ;
      C → faça subtrair_a vá_para E | faça adicionar_b vá_para E
      D → se a_zero então vá_para E senão vá_para E
      E → r F
      F → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | F G
      G → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 }

1.4. Exclusão das recursões da forma A_r → A_rα:

G = ({A, A1, B, C, D, E, F, F1, G}, {:, ;, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, r, faça, subtrair_a, adicionar_b, vá_para, se, a_zero, então, senão}, P, A)
P = { A  → E : C ; A1 | E : D ; A1
      A1 → B A1 | ε
      B  → E : C ; | E : D ;
      C  → faça subtrair_a vá_para E | faça adicionar_b vá_para E
      D  → se a_zero então vá_para E senão vá_para E
      E  → r F
      F  → 0 F1 | 1 F1 | 2 F1 | 3 F1 | 4 F1 | 5 F1 | 6 F1 | 7 F1 | 8 F1 | 9 F1
      F1 → G F1 | ε
      G  → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 }

2. Fatoração a esquerda da gramática livre de contexto:

G = ({A, A1, A2, B, B1, C, C1, D, E, F, F1, G}, {:, ;, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, r, faça, subtrair_a, adicionar_b, vá_para, se, a_zero, então, senão}, P, A)
P = { A  → E : A2
      A1 → B A1 | ε
      A2 → C ; A1 | D ; A1
      B  → E : B1
      B1 → C ; | D ;
      C  → faça C1
      C1 → subtrair_a vá_para E | adicionar_b vá_para E
      D  → se a_zero então vá_para E senão vá_para E
      E  → r F
      F  → 0 F1 | 1 F1 | 2 F1 | 3 F1 | 4 F1 | 5 F1 | 6 F1 | 7 F1 | 8 F1 | 9 F1
      F1 → G F1 | ε
      G  → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 }

3. Conjuntos FIRST(α) e FOLLOW(A):

FIRST(A)  = {r}
FIRST(A1) = {r, ε}
FIRST(A2) = {faça, se}
FIRST(B)  = {r}
FIRST(B1) = {faça, se}
FIRST(C)  = {faça}
FIRST(C1) = {subtrair_a, adicionar_b}
FIRST(D)  = {se}
FIRST(E)  = {r}
FIRST(F)  = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
FIRST(F1) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ε}
FIRST(G)  = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

FOLLOW(A)  = {$}
FOLLOW(A1) = {$}
FOLLOW(A2) = {$}
FOLLOW(B)  = {r, $}
FOLLOW(B1) = {r, $}
FOLLOW(C)  = {;}
FOLLOW(C1) = {;}
FOLLOW(D)  = {;}
FOLLOW(E)  = {:, ;, senão}
FOLLOW(F)  = {:, ;, senão}
FOLLOW(F1) = {:, ;, senão}
FOLLOW(G)  = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, :, ;, senão}

4. Tabela de Análise Preditiva:

5. Analisador Preditivo Tabular:

Apenas o uso do FOLLOW(A) como conjunto de sincronização para A pode não ser suficiente para a recuperação de erro. Por exemplo, se os ponto e vírgulas terminarem os comandos, como em C, então as palavras-chave que iniciam os comandos podem não aparecer no conjunto FOLLOW do não-terminal representando expressões. A ausência de um ponto e vírgula após uma atribuição pode, portanto, fazer com que a palavra-chave que inicia o próximo comando seja ignorada. Frequentemente, existe uma estrutura hierárquica nas construções de uma linguagem de programação; por exemplo, as expressões aparecem dentro de comandos, que aparecem dentro de blocos, e assim por diante. Podemos então acrescentar ao conjunto de sincronização de uma construção de nível inferior os símbolos que iniciam construções de nível superior. Por exemplo, poderíamos adicionar palavras-chave que iniciam os comandos da linguagem aos conjuntos de sincronização para os não-terminais que geram expressões (Aho, 2008).

4. Tabela de Análise Preditiva Adaptada:

5. Analisador Preditivo Tabular Adaptado: