Construção de Compiladores
Analise Sintática II
Universidade Federal da Paraíba
Departamento de Informática
Adaptando a Gramática
• Requerimento de Linguagem Recursiva
 Na indisponibilidade de uma linguagem recursiva,
podemos utilizar o analisador de gramáticas LL(k))
 No LL(k) ("Left-to-right Left-mostderivation") basta olharmos no
máximo k símbolos à frente na sentença para decidir que regra
de produção aplicar
Universidade Federal da Paraíba
Departamento de Informática
Método Top-down
• Analisador de Gramáticas LL(1)
Universidade Federal da Paraíba
Departamento de Informática
Método Top-down
• LL(1) – Funcionamento
 Sendo X o símbolo do topo da pilha, e PS o atual
símbolo de entrada, as ações podem ser:
 Se X é um terminal = PS = $, o analisador encerra sua
atividade e comunica fim da análise sintática com sucesso
 Se X é um terminal = PS ≠ $, o analisador elimina X do topo
da pilha e avança para o próximo símbolo de entrada
 Se X é um terminal ≠ PS, o analisador acusa um erro de
sintaxe (ativa rotina de tratamento de erros)
Universidade Federal da Paraíba
Departamento de Informática
Método Top-down
• LL(1) – Funcionamento (continuação)
 Se X é um não-terminal, o analisador consulta M[X, PS].
– Se a resposta for uma regra de produção X ::= MVU, o
analisador desempilha X do topo da pilha e empilha
UVM (com M no topo da pilha). Para a saída é enviada a
regra de produção usada
– Se M[X, PS] = ERRO, o analisador acusa um erro de
sintaxe (ativa rotina de tratamento de erros)
Universidade Federal da Paraíba
Departamento de Informática
Método Top-down
•
LL(1) – Exemplo
(1) S ::= aAS
(2) S ::= b
(3) A ::= a
(4) A ::= bSA
 w = abbab$
Universidade Federal da Paraíba
Departamento de Informática
Construção da Tabela
• Considerando um não terminal A, três tipos de
informação são importantes para a construção da
tabela:
 Se A gera ou não cadeia vazia 
 Quais são os símbolos terminais iniciadores de A
 Se A * , que terminais podem aparecer como primeiro
símbolo de 
 Quais são os símbolos terminais seguidores de A
 Se S * A, que terminais podem aparecer como primeiro
símbolo de 
Universidade Federal da Paraíba
Departamento de Informática
Cadeia Vazia 
•
Algoritmo: identificação dos não-terminais que derivam 
1.
A lista L contém, inicialmente, todas as regras de G
2.
Retire de L as regras que possuem um terminal
3.
Se existe um não-terminal A sem regras, marcar A como NÃO
4.
Se existe um A  , retirar todas as regras que tem A do lado esquerdo,
remover A do lado direito das regras restantes e marcar A como SIM
5.
Se uma regra tem do lado direito um não-terminal marcado NÃO, o
símbolo esquerdo também é marcado como não e a regra removida
(Repetir 3, 4 e 5 enquanto houver regras)
Universidade Federal da Paraíba
Departamento de Informática
Cadeia Vazia  - exemplo
•
L:
1. P  A B C D
2. A  
3. A  a A
4. B  
5. B  B b
6. C  
7. C  A B
8. D  d
Gera 
:
Não gera  :
Universidade Federal da Paraíba
Departamento de Informática
- Preencher L com todos as regras da
gramática
Cadeia Vazia  - exemplo
•
L:
1. P  A B C D
2. A  
3. A  a A
4. B  
5. B  B b
6. C  
7. C  A B
8. D  d
Gera 
:
Não gera  :
Universidade Federal da Paraíba
Departamento de Informática
- Retirar da lista L as regras que possuem terminais do lado
direito
- D não tem regras, então é marcado com NÃO
- A tem uma regra com lado direito  então é marcado SIM e
remove a regra 2
- As ocorrências de A nas regras 1 e 7 são removidas
- B tem uma regra com lado direito  então é marcado SIM e
remove a regra 4
- As ocorrências de B nas regras 1 e 7 são removidas
- C tem uma regra com lado direito  então é marcado SIM e
remove a regra 6 e 7
- A ocorrência de C na regra 1 é removida e Como D está
marcado não, P também é marcado não
Cadeia Vazia  - exemplo
•
L:
1. P  A B C D
2. A  
3. A  a A
4. B  
5. B  B b
6. C  
7. C  A B
8. D  d
Gera 
:
Não gera  : D
Universidade Federal da Paraíba
Departamento de Informática
- Preencher a lista L com as regras que não possuem
terminais do lado direito
- D não tem regras, então é marcado com NÃO
- A tem uma regra com lado direito  então é marcado SIM e
remove a regra 2
- As ocorrências de A nas regras 1 e 7 são removidas
- B tem uma regra com lado direito  então é marcado SIM e
remove a regra 4
- As ocorrências de B nas regras 1 e 7 são removidas
- C tem uma regra com lado direito  então é marcado SIM e
remove a regra 6 e 7
- A ocorrência de C na regra 1 é removida e Como D está
marcado não, P também é marcado não
Cadeia Vazia  - exemplo
•
L:
1. P  A B C D
2. A  
3. A  a A
4. B  
5. B  B b
6. C  
7. C  A B
8. D  d
Gera 
:A
Não gera  : D
Universidade Federal da Paraíba
Departamento de Informática
- Preencher a lista L com as regras que não possuem
terminais do lado direito
- D não tem regras, então é marcado com NÃO
- A tem uma regra com lado direito  então é marcado SIM e
remove a regra 2
- As ocorrências de A nas regras 1 e 7 são removidas
- B tem uma regra com lado direito  então é marcado SIM e
remove a regra 4
- As ocorrências de B nas regras 1 e 7 são removidas
- C tem uma regra com lado direito  então é marcado SIM e
remove a regra 6 e 7
- A ocorrência de C na regra 1 é removida e Como D está
marcado não, P também é marcado não
Cadeia Vazia  - exemplo
•
L:
1. P  A B C D
2. A  
3. A  a A
4. B  
5. B  B b
6. C  
7. C  A B
8. D  d
Gera 
:A
Não gera  : D
Universidade Federal da Paraíba
Departamento de Informática
- Preencher a lista L com as regras que não possuem
terminais do lado direito
- D não tem regras, então é marcado com NÃO
- A tem uma regra com lado direito  então é marcado SIM e
remove a regra 2
- As ocorrências de A nas regras 1 e 7 são removidas
- B tem uma regra com lado direito  então é marcado SIM e
remove a regra 4
- As ocorrências de B nas regras 1 e 7 são removidas
- C tem uma regra com lado direito  então é marcado SIM e
remove a regra 6 e 7
- A ocorrência de C na regra 1 é removida e Como D está
marcado não, P também é marcado não
Cadeia Vazia  - exemplo
•
L:
1. P  A B C D
2. A  
3. A  a A
4. B  
5. B  B b
6. C  
7. C  A B
8. D  d
Gera 
:AB
Não gera  : D
Universidade Federal da Paraíba
Departamento de Informática
- Preencher a lista L com as regras que não possuem
terminais do lado direito
- D não tem regras, então é marcado com NÃO
- A tem uma regra com lado direito  então é marcado SIM e
remove a regra 2
- As ocorrências de A nas regras 1 e 7 são removidas
- B tem uma regra com lado direito  então é marcado SIM e
remove a regra 4
- As ocorrências de B nas regras 1 e 7 são removidas
- C tem uma regra com lado direito  então é marcado SIM e
remove a regra 6 e 7
- A ocorrência de C na regra 1 é removida e Como D está
marcado não, P também é marcado não
Cadeia Vazia  - exemplo
•
L:
1. P  A B C D
2. A  
3. A  a A
4. B  
5. B  B b
6. C  
7. C  A B
8. D  d
Gera 
:AB
Não gera  : D
Universidade Federal da Paraíba
Departamento de Informática
- Preencher a lista L com as regras que não possuem
terminais do lado direito
- D não tem regras, então é marcado com NÃO
- A tem uma regra com lado direito  então é marcado SIM e
remove a regra 2
- As ocorrências de A nas regras 1 e 7 são removidas
- B tem uma regra com lado direito  então é marcado SIM e
remove a regra 4
- As ocorrências de B nas regras 1 e 7 são removidas
- C tem uma regra com lado direito  então é marcado SIM e
remove a regra 6 e 7
- A ocorrência de C na regra 1 é removida e Como D está
marcado não, P também é marcado não
Cadeia Vazia  - exemplo
•
L:
1. P  A B C D
2. A  
3. A  a A
4. B  
5. B  B b
6. C  
7. C  A B
8. D  d
Gera 
:AB
Não gera  : D
Universidade Federal da Paraíba
Departamento de Informática
- Preencher a lista L com as regras que não possuem
terminais do lado direito
- D não tem regras, então é marcado com NÃO
- A tem uma regra com lado direito  então é marcado SIM e
remove a regra 2
- As ocorrências de A nas regras 1 e 7 são removidas
- B tem uma regra com lado direito  então é marcado SIM e
remove a regra 4
- As ocorrências de B nas regras 1 e 7 são removidas
- C tem uma regra com lado direito  então é marcado SIM e
remove a regra 6 e 7
- A ocorrência de C na regra 1 é removida e Como D está
marcado não, P também é marcado não
Cadeia Vazia  - exemplo
•
L:
1. P  A B C D
2. A  
3. A  a A
4. B  
5. B  B b
6. C  
7. C  A B
8. D  d
Gera 
:AB C
Não gera  : D
Universidade Federal da Paraíba
Departamento de Informática
- Preencher a lista L com as regras que não possuem
terminais do lado direito
- D não tem regras, então é marcado com NÃO
- A tem uma regra com lado direito  então é marcado SIM e
remove a regra 2
- As ocorrências de A nas regras 1 e 7 são removidas
- B tem uma regra com lado direito  então é marcado SIM e
remove a regra 4
- As ocorrências de B nas regras 1 e 7 são removidas
- C tem uma regra com lado direito  então é marcado SIM e
remove a regra 6 e 7
- A ocorrência de C na regra 1 é removida e Como D está
marcado não, P também é marcado não
Cadeia Vazia  - exemplo
•
L:
1. P  A B C D
2. A  
3. A  a A
4. B  
5. B  B b
6. C  
7. C  A B
8. D  d
Gera 
:AB C
Não gera  : D P
Universidade Federal da Paraíba
Departamento de Informática
- Preencher a lista L com as regras que não possuem
terminais do lado direito
- D não tem regras, então é marcado com NÃO
- A tem uma regra com lado direito  então é marcado SIM e
remove a regra 2
- As ocorrências de A nas regras 1 e 7 são removidas
- B tem uma regra com lado direito  então é marcado SIM e
remove a regra 4
- As ocorrências de B nas regras 1 e 7 são removidas
- C tem uma regra com lado direito  então é marcado SIM e
remove a regra 6 e 7
- A ocorrência de C na regra 1 é removida e como D está
marcado não, P também é marcado não e a regra removida
Conjunto Primeiro (First)
•
É o conjunto de símbolos terminais que iniciam uma sequência de
símbolos, de acordo com as seguintes regras:

Se =, Primeiro() = Primeiro() = {}

Se  é um terminal a, Primeiro() = Primeiro(a) = {a}

Se  é uma cadeia a, cujo primeiro símbolo é um terminal a,
Primeiro() = Primeiro(a) = {a}

Se  é um não-terminal A, Primeiro(A) é calculado via algoritmo

Se  é uma cadeia A, e o primeiro símbolo é um não não-terminal A,
que deriva , Primeiro() = Primeiro(A) = Primeiro(A)  Primeiro()

Se  é uma cadeia A, e o primeiro símbolo é um não não-terminal A,
que não deriva , Primeiro() = Primeiro(A) = Primeiro(A)
Universidade Federal da Paraíba
Departamento de Informática
Conjunto Primeiro (First)
•
Algoritmo
1.
Inicialmente para todo não-terminal A da gramática, todos Primeiro
(A) estão vazios
2.
Se um não terminal A gera , acrescentar  a Primeiro(A)
3.
Para cada regra A → B1...Bma, tal que para todo i=1,...,m; Bi →* ,
acrescentar “a” a Primeiro(A)
4.
Para cada regra A → B1...Bm, tal que para todo i=1,...,m; Bi →* ,
acrescentar Primeiro() a Primeiro(A)
(Repetir 4 enquanto houver alteração no valor de algum Primeiro)
Universidade Federal da Paraíba
Departamento de Informática
Conjunto Primeiro (First)
•
Exemplo
1. E → E + T
Nenhum dos não-terminais produz 
2. E → T
Primeiro(E) = Primeiro(T) = Primeiro(F) = { }
3. T → T * F
Pela regra 5, adiciona-se “(“ a Primeiro(F)
Pela regra 6, adiciona-se “a“ a Primeiro(F)
4. T → F
Pela regra 4, adiciona-se Primeiro(F) a Primeiro(T)
5. F → ( E )
Pela regra 2, adiciona-se Primeiro(T) a Primeiro(E)
6. F → a
Primeiro(E) : ( a
Primeiro(T) : ( a
Primeiro(F) : ( a
Universidade Federal da Paraíba
Departamento de Informática
Conjunto Seguidor (Follow)
•
Seguidor(A) é o conjunto de símbolos terminais que
seguem o não-terminal A
•
Se o não-terminal aparece no fim da cadeia não há
um seguidor, neste caso usamos o $ para indicar o
final da cadeia (eof)
•
$ sempre será seguidor de S (símbolo inicial da
gramática)
Universidade Federal da Paraíba
Departamento de Informática
Conjunto Seguidor (Follow)
•
Algoritmo
1. Todos os não terminais A da gramática, inicialmente, terão
Seguidor(A) = { }, exceto S que terá Seguidor(S) = {$}
2. Se há uma regra A → Ba, e =B1...Bm →* , acrescentar “a” a
Seguidor(B)
3. Se há uma regra A → BC, e =B1...Bm →* , acrescentar
Primeiro(C) a Seguidor(B)
4. Se há uma regra A → B, e =B1...Bm →* , acrescentar
Seguidor(A) a Seguidor(B)
5. Repetir passo 4 sempre que houver modificações nos conjuntos
Universidade Federal da Paraíba
Departamento de Informática
Conjunto Seguidor (Follow)
•
Exemplo
1. E → E + T
Nenhum dos não-terminais produz 
2. E → T
Inicialmente tem-se Seguidor(E) = {$} e demais vazios
3. T → T * F
Pela regra 1, acrescentamos “+” a Seguidor(E)
Pela regra 3, acrescentamos “*” a Seguidor(T)
4. T → F
Pela regra 5, acrescentamos “)” a Seguidor(E)
5. F → ( E )
Pela regra 2, adiciona-se Seguidor(E) a Seguidor(T)
6. F → a
Pela regra 4, adiciona-se Seguidor(T) a Seguidor(F)
Primeiro(E) : ( a
Primeiro(T) : ( a
Primeiro(F) : ( a
Universidade Federal da Paraíba
Departamento de Informática
Seguidor(E) : $ + )
Seguidor(T) : * $ +
Seguidor(F) : * $ +
)
)
Construção da Tabela
•
Algoritmo: considere uma matriz M[X,y], onde as linhas
são os não-terminais e as colunas terminais
1. Para cada produção A→  de G, executar os passos 2 e 3
(criação da linha A da tabela)
2. Para cada terminal a de Primeiro(), adicionar a produção A → 
a M[A,a]
3. Se Primeiro() inclui , então adicione A→  a M[A,b] para cada
b em Seguidor(A)
Se houver mais de uma produção para M[X,y] a gramática é ambígua
Universidade Federal da Paraíba
Departamento de Informática
Construção da Tabela
•
Regras
1.
E→E+T
2.
E→T
3.
T→T*F
4.
T→F
5.
F→(E)
6.
F→a
Primeiro(E) : ( a
Primeiro(T) : ( a
Primeiro(F) : ( a
a
E
Gera  :
Não gera  : F T E
Universidade Federal da Paraíba
Departamento de Informática
T
F
1 2
3 4
6
+
Seguidor(E) : $ + )
Seguidor(T) : * $ +
Seguidor(F) : * $ +
*
(
1 2
3 4
5
)
$
)
)
Construção da Tabela
•
Regras
1.
E→E+T
2.
E→T
3.
T→T*F
4.
T→F
5.
F→(E)
6.
F→a
Considere a existência desse
símbolo vazio. Note que regras
são acrescidas na tabela.
Primeiro(E) : ( a 
Primeiro(T) : ( a
Primeiro(F) : ( a
E
Gera  :
Não gera  : F T E
Universidade Federal da Paraíba
Departamento de Informática
T
F
a
+
1 2
1
3 4
6
Seguidor(E) : $ + )
Seguidor(T) : * $ +
Seguidor(F) : * $ +
*
(
)
$
1 2
1
1
3 4
5
)
)