0% acharam este documento útil (0 voto)

31 visualizações68 páginas

Aula 4

A aula aborda conceitos fundamentais sobre gramáticas, incluindo definições de alfabeto, cadeias e linguagens, além de métodos de representação de linguagens. Também discute a estrutura das gramáticas, suas classes conforme a Hierarquia de Chomsky e relações como Cabeça, Último, Primeiro e Seguinte. Exemplos práticos são apresentados para ilustrar a linguagem gerada por diferentes gramáticas.

Enviado por

Fre Dy

Direitos autorais

Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.

Formatos disponíveis

Baixe no formato PDF, TXT ou leia on-line no Scribd

0% acharam este documento útil (0 voto)

31 visualizações68 páginas

Aula 4

Enviado por

Fre Dy

Direitos autorais

Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.

Formatos disponíveis

Baixe no formato PDF, TXT ou leia on-line no Scribd

Compiladores

Aula 4

Celso Olivete Júnior

olivete@[Link]
Na aula de hoje...

 Revisão: gramáticas

 Relações em uma gramática: Cabeça, Último,

Primeiro (First) e Seguinte (Follow)
 Capítulo 4 (seção 4.4.2) do livro Compiladores : Princípios,
técnicas e ferramentas

Compiladores 2
Definições

 Alfabeto ou vocabulário: Conjunto finito não vazio de símbolos.

Símbolo é um elemento qualquer de um alfabeto.
 Ex:
 {a,b}
 {0,1,2,3,4,5,6,7,8,9}

 Cadeia: Concatenação de símbolos de um alfabeto. Define-se como

cadeia vazia ou nula uma cadeia que não contém nenhum símbolo.
 Ex:
 aab
 123094
 λ − cadeia nula

Compiladores 3
Definições

 Comprimento de cadeia: Número de símbolos de uma cadeia. Ex:

 |aab| = 3

 |123094|=6

 |λ|=0

Compiladores 4
Definições

 Linguagem é uma coleção de cadeias de

símbolos, de comprimento finito. Estas cadeias
são denominadas sentenças da linguagem, e são
formadas pela justaposição de elementos
individuais, que são os símbolos ou átomos
da linguagem.

Compiladores 5
Definições

 Métodos de Representação de Linguagens

1) Enumeração (especificação) das cadeias de símbolos
que formam as suas sentenças (somente linguagens
finitas podem ser representadas por este método)
2) Através de um conjunto de leis de formação das
cadeias (Gramática)
3) Através de regras de aceitação de cadeias (às regras de
aceitação dá-se o nome de Reconhecedor -
autômatos)

Compiladores 6
Gramáticas

2) Leis de Formação
 Através de um conjunto de leis de formação das
cadeias (ao conjunto de leis de formação dá-se o
nome de Gramática)
 dada uma cadeia de símbolos, só é possível afirmar que tal
cadeia pertence à linguagem se for possível, aplicando-se as
leis de formação que compõem a gramática da linguagem,
derivar (sintetizar) a cadeia em questão.
 Ao processo de obtenção de uma sentença a partir da
gramática dá-se o nome de derivação da sentença.

Compiladores 7
Gramáticas

Gramáticas
 Formalmente as gramáticas, são caracterizadas como
quádruplas ordenadas

G = ( Vn, Vt, P, S)
 onde:
 Vn representa o vocabulário não terminal (variáveis) da
gramática. Este vocabulário corresponde ao conjunto de todos os
símbolos dos quais a gramática se vale para definir as leis de
formação das sentenças da linguagem.

Compiladores 8
Gramáticas

Gramáticas
 Formalmente as gramáticas, são caracterizadas como
quádruplas ordenadas

G = ( Vn, Vt, P, S)
 onde:
 Vt é o vocabulário terminal, contendo os símbolos que
constituem as sentenças da linguagem. Dá-se o nome de
terminais aos elementos de Vt.

Compiladores 9
Gramáticas

 Gramáticas
 Formalmente as gramáticas, são caracterizadas como quádruplas
ordenadas

G = ( Vn, Vt, P, S)

 onde:
 P são as regras de produção, que definem o conjunto de todas as leis
de formação utilizadas pela gramática para definir a linguagem. Para
tanto, cada construção parcial, representada por um não-terminal, é
definida como um conjunto de regras de formação relativas à definição do
não-terminal a ela referente. A cada uma destas regras de formação que
compõem o conjunto P dá-se o nome de produção da gramática

Compiladores 10
Gramáticas

 Gramáticas Símbolos Símbolos

que terminais
derivam

 Exemplo: G = ( Vn, Vt, P, S)

G = ({S, A, B}, {a, b}, P, S) Início da
derivação
P:
S  AB
Regras de
Aa
produção
B  bB|b

1. Qual a linguagem produzida por esta gramática?

2. Faça a árvore de derivação para a cadeia abbbbb

Compiladores 11
Gramáticas

 Gramáticas Símbolos Símbolos

que terminais
derivam

 Exemplo: G = ( Vn, Vt, P, S)

G = ({S, A, B}, {a, b}, P, S) Início da
derivação
P:
S  AB
Regras de
Aa
produção
B  bB|b
1. Qual a linguagem produzida por esta gramática?
Linguagem que começa com um símbolo a seguido de n símbolos b’s (n≥1).
Expressão regular que representa a linguagem  abb*
2. Faça a árvore de derivação para a cadeia abbbbb
Compiladores 12
Gramáticas

 Árvore de derivação
 a raiz tem como rótulo o símbolo inicial S da
gramática.
 a cada nó rotulado por um não-terminal A
corresponde uma regra de A. Se a regra for A 
X1X2 ... Xm, os filhos do nó são rotulados, da
esquerda para a direita, por X1, X2, ..., Xm. (cada
um dos Xi pode ser um terminal ou um não-
terminal.)
 um nó rotulado por um terminal é sempre uma
folha da árvore, e não tem filhos.

Compiladores 13
Gramáticas

 Árvore de derivação para a gramática e cadeia

abbbbb G = ({S, A, B}, {a, b}, P, S)
P:{
S  AB
Aa
B  bB|b
}

Compiladores 14
Gramáticas

1. Duas gramáticas G1 e G2 são equivalentes se produzem

a mesma linguagem
L(G1) = L(G2)

2. Uma sentença é ambígua se existem duas ou mais

sequências de derivação que a define.

3. Uma gramática é ambígua se possui alguma sentença

ambígua.

G: S  AB
É ambígua  permite
A  AA | B | a
derivação mais à direita
B  Bcd | A e mais à esquerda
– Verifique se x= aaacd é ambígua.

Compiladores 15
Classes Gramaticais

 Conforme as restrições impostas ao formato das produções de uma gramática, a

classe de linguagens que tal gramática gera varia correspondentemente.

 A teoria mostra que há quatro classes de gramáticas capazes de gerar quatro

classes correspondentes de linguagens, de acordo com a denominada Hierarquia
de Chomsky.
a. Gramáticas com Estrutura de Frase ou Tipo 0

b. Gramáticas Sensíveis ao Contexto ou Tipo 1

c. Gramáticas Livres de Contexto ou Tipo 2

d. Gramáticas Regulares ou Tipo 3

Compiladores 16
Classes Gramaticais

a. Gramáticas com Estrutura de Frase ou Tipo 0

 São aquelas às quais nenhuma restrição é imposta.
 Exemplo de reconhecedor: Máquina de Turing com fita de entrada infinita

 Produções da forma
α β
Onde: α ∈ (Vn ∪ Vt)+ G = ( Vn, Vt, P, S)
β ∈ (Vn ∪ Vt)*

 Lado esquerdo da regra de produção pode conter N símbolos (terminais ou não

terminais);
 Lado direito da regra de produção pode conter N símbolos (terminais ou não terminais ou
vazio);

Compiladores 17
Classes Gramaticais

a. Gramáticas com Estrutura de Frase ou Tipo 0

 Exemplo de GEF:
G = ({A, B, C}, {a, b}, P, A)
P: A  BC
BC  CB
B b
C a
 Qual a linguagem gerada?
 L(G) = ?

Compiladores 18
Classes Gramaticais

a. Gramáticas com Estrutura de Frase ou Tipo 0

 Exemplo de GEF:
G = ({A, B, C}, {a, b}, P, A)
P: A  BC
BC  CB
B b
C a
 Qual a linguagem gerada?
 L(G) = {ba, ab}

Compiladores 19
Classes Gramaticais

b. Gramáticas Sensíveis ao Contexto ou Tipo 1

 Restrição: nenhuma substituição pode reduzir o

comprimento da forma sentencial à qual a substituição
é aplicada.
 Produções da forma
α β
Onde: α ∈ (Vn ∪ Vt)+
β ∈ (Vn ∪ Vt)+
|α| ≤ |β|

Compiladores 20
Classes Gramaticais

b. Gramáticas Sensíveis ao Contexto ou Tipo 1

α β
 Exemplo de GSC: Onde: α ∈ (Vn ∪ Vt)+
G = ({S, B, C}, {a, b, c}, P, S) β ∈ (Vn ∪ Vt)+
|α| ≤ |β|
P : S  aSBC | aBC
CB  HB
HB  HC
HC  BC
aB  ab
bB  bb
bC  bc Faça a derivação (mais
cC  cc à esquerda ou mais à
direita)
 Qual a linguagem gerada?
 L(G) = {anbncn|n≥1}

Compiladores 21
Classes Gramaticais

c. Gramáticas Livres de Contexto ou Tipo 2

 As Gramáticas Livres de Contexto (GLC) ou do

Tipo 2 são aquelas que no lado esquerdo da regra
há apenas um símbolo não-terminal.

Compiladores 22
Classes Gramaticais

c. Gramáticas Livres de Contexto ou Tipo 2

 Qual a linguagem gerada para:

G = ({S,A,B},{a,b},P,S)
P: S  AB
A  aA | a
B  bB | b

L(G)={anbm| n, m ≥ 1}
Compiladores 23
Classes Gramaticais

d. Gramáticas Regulares ou Tipo 3

 Aplicando-se mais uma restrição sobre a forma das
produções, pode-se criar uma nova classe de gramáticas,
as Gramáticas Regulares (GR), de grande importância no
estudo dos compiladores por possuírem propriedades
adequadas para a obtenção de reconhecedores simples.
Nas GRs, as produções são restritas às formas seguintes:
A  aB ou A  Ba
Aa no lado esquerdo da regra há
Aε apenas um símbolo não-
onde A,B ∈ Vn e a ∈ Vt terminal

Compiladores 24
Classes Gramaticais

d. Gramáticas Regulares ou Tipo 3

 Exemplo GR em EBNF:
G = ( {<Dig>, <Int>}, {+, -, 0, ..., 9}, P, <Int>)
P: <Int> ::= +<Dig> | -<Dig>
<Dig> ::= 0<Dig> | 1<Dig>|...| 9<Dig> | 0 | 1 | 2 |...|9

 Qual linguagem gerada?

 L(G) = conj. números inteiros com sinal ±[0..9]

Compiladores 25
Na aula de hoje...

 Revisão: gramáticas

 Relações em uma gramática: Cabeça, Último,

Primeiro (First) e Seguinte (Follow)
 Capítulo 4 (seção 4.4.2) do livro Compiladores :
Princípios, técnicas e ferramentas

Compiladores 26
Relações em uma Gramática

 A construção de analisadores sintáticos é facilitada através de

algumas funções associadas a gramática: CABEÇA, ÚLTIMO,
PRIMEIRO(First) e Seguinte (Follow).
 Ideia: permitem escolher qual produção aplicar com base no próximo
símbolo lido.

Analisador léxico
retornou o token if Partes das regras em EBNF
<comando condicional 1> ::=
Trecho de código
if <expressão> then <comando>
... [else <comando>]
if (a<1) then <comando repetitivo 1> ::=
a:=12 while <expressão> do <comando>
...
Compiladores 27
Cabeça

 É uma das mais simples de identificar

 um de seus elementos é a cabeça do lado direito de uma regra

 Dada uma produção na forma Exemplo

α  βγ P: S AB
A aA | a
Onde: α ∈ Vn B bB | b
β ∈ (Vn ∪ Vt)
Cabeça (S) = ?
γ ∈ (Vn ∪ Vt)* Cabeça (A) = ?
Cabeça (B) = ?
 Cabeça (α) = β

Compiladores 28
Cabeça

 É uma das mais simples de identificar

 um de seus elementos (terminal ou não-terminal) é a cabeça
do lado direito de uma regra Exemplo
 Dada uma produção na forma P: S AB
A aA | a
α  βγ B bB | b
Onde: α ∈ Vn
Cabeça (S) = {A}
β ∈ (Vn ∪ Vt) Cabeça (A) = {a}
Cabeça (B) = {b}
γ ∈ (Vn ∪ Vt)*

 Cabeça (α) = β

Compiladores 29
Último

 Relaciona um dado não terminal, existente do lado

esquerdo de uma certa regra, com o último elemento
que aparece do lado direito desta regra
Exemplo
 Dada uma produção na forma
P: S AB
α  γβ A aA | a
Onde: α ∈ Vn B bB | b

β ∈ (Vn ∪ Vt) Último (S) = ?

Último (A) = ?
γ ∈ (Vn ∪ Vt)* Último (B) = ?
 Último (α) = β

Compiladores 30
Último

 Relaciona um dado não terminal, existente do lado esquerdo de

uma certa regra, com o último elemento (terminal ou não-
terminal) que aparece do lado direito desta regra
 Dada uma produção na forma Exemplo
α  γβ
P: S AB
Onde: α ∈ Vn A aA | a
B bB | b
β ∈ (Vn ∪ Vt)

γ ∈ (Vn ∪ Vt)* Último (S) = {B}

Último (A) = {A,a}
 Último (α) = β Último (B) = {B,b}

Compiladores 31
Primeiro (First)

 Relação próxima a relação cabeça; entretanto, deve conter

somente terminais

 Primeiro(A) = x, onde A produz x como seu símbolo mais à

esquerda com n derivações, sendo A ∈ Vn e x ∈ Vt*
 x pode ser a cadeia vazia Exemplo
P: S AB
A aA | a
B bB | b

Primeiro (S) = {a}

Primeiro (A) = {a}
Primeiro (B) = {b}

Compiladores 32
Primeiro (First)

 Para determinar PRIMEIRO(X):

1. Se x é um terminal, então PRIMEIRO (x) = {x}

2. Se X é não-terminal e X aα é uma produção, então se acrescenta a ao

conjunto PRIMEIRO de x

3. Se X  ε é uma produção ε deve ser adicionado ao conjunto PRIMEIRO de x

4. Se XY1Y2...Yk é uma produção, então todo i tal que todos Y1...Yi-1 são não-

terminais e PRIMEIRO(Yj) contém ε, onde j=1,2...i-1. acrescente todo

símbolo diferente de ε de PRIMEIRO(Yj) a PRIMEIRO(X). Se ε ∈

PRIMEIRO(X), para todo i=1,2..k. então acrescente ε a PRIMEIRO(X).

Compiladores 33
Primeiro (First)

 Exemplo

Primeiro (E) = {?}

E → TE’ Primeiro (E’) = {?}
E’ → +TE’ | ε Primeiro (T) = {?}
Primeiro (T’) = {?}
T → FT’
Primeiro (F) = {?}
T’ → *FT’ | ε
F → (E) | id

Compiladores 34
Primeiro (First)

 Exemplo

Primeiro (E) = Primeiro(T) = Primeiro(F) ={(, id}

E → TE’ Primeiro (E’) = {+, ε}
E’ → +TE’ | ε Primeiro (T) = Primeiro(F) = {(, id}
Primeiro (T’) = {*, ε}
T → FT’
Primeiro (F) = {(, id}
T’ → *FT’ | ε
F → (E) | id

F deriva em ε?
R: Não, então primeiro(T) = primeiro(F) = {(, id}
Se F derivasse em ε era preciso incluir o
primeiro(T’) em primeiro(T)

Compiladores 35
Primeiro (First)

 Exemplo 2

E → TE’
E’ → +TE’ | ε Primeiro (H) = {?}
T → FT’
H → E’T
T’ → *FT’ | ε
F → (E) | id

Se fosse incluída esta regra na

gramática como ficaria o primeiro(H)?

Compiladores 36
Primeiro (First)

 Exemplo 2

E → TE’
E’ → +TE’ | ε Primeiro (H) = Primeiro(E’)∪Primeiro(T)
T → FT’ = {+, (, id }
H → E’T
T’ → *FT’ | ε
F → (E) | id

E’ deriva em ε?
R: Sim, então incluir o primeiro(T) em primeiro(H).
Regra 4 Se primeiro(T) e primeiro(E’) contem ε então incluir
slide 33 ε em primeiro(H), caso contrário remover ε do
primeiro(H)

Compiladores 37
Seguinte (Follow)

 Se A é um não-terminal, Seguinte(A) é o conjunto de

terminais que podem figurar imediatamente à direita

de A em alguma forma sentencial

 Seguinte(A)=x para a regra SαAβ e primeiro(β)=x

Onde: A ∈ Vn
x ∈ Vt*
α e β ∈ (Vn ∪ Vt)*

Compiladores 38
Seguinte (Follow)

 Para determinar Seguinte(A):

1. Colocar $ em Seguinte(S) se S é o símbolo de partida - $ é o

marcador de fim de entrada durante a análise sintática

2. Se existe uma produção A→ αBβ e β ∉ ε então tudo que estiver em

PRIMEIRO(β), exceto ε, deve ser adicionado em Seguinte(B)

3. Se existe uma produção A→ αB ou A→ αBβ onde PRIMEIRO(β)

contem ε (β  ε), então tudo que está em Seguinte(A) está em

Seguinte(B)
Compiladores 39
Seguinte (Follow)
Seguinte(A)=x para a regra SαAβ e primeiro(β)=x

Primeiro (E) = Primeiro(T) = Primeiro(F) =

E → TE’ {(, id}
E’ → +TE’ | ε Primeiro (E’) = {+, ε}
T → FT’ Primeiro (T) = Primeiro(F) = {(, id}
Primeiro (T’) = {*, ε}
T’ → *FT’ | ε
Primeiro (F) = {(, id}
F → (E) | id Regra 2 e Regra 1

1. Colocar
Seguinte(E) = {), $}
1. Colocar  em Seguinte(S)
$ em Seguinte(S) se
se S
S éé o
o símbolo
símbolo de
de
Seguinte(E’) = Seguinte(E) = {), $}
partida -  é o marcador de fim de entrada
partida Seguinte(T) = Primeiro(E’) = {+} U
2. Se existe uma produção A→ αBβ e β é diferente
2. Se existe uma produção A→ αBβ e β é diferente Seguinte(E) U Seguinte(E’) = {+, ), $}
de ε então tudo que estiver em PRIMEIRO(β),
de ε então tudo que estiver em PRIMEIRO(β), Seguinte(T’) = Seguinte(T)= {+, ), $}
exceto ε, deve ser adicionado em Seguinte(B) Seguinte(F) = primeiro(T') = {*} U
exceto ε, deve ser adicionado em Seguinte(B)
3.
3.
Se existe uma produção A→ αB ou A→ αBβ
Se existe uma produção A→ αB ou A→ αBβ Seguinte(T) U Seguinte(T’) = {*,+,), $}
onde PRIMEIRO(β) contêm ε (β  ε), então tudo
onde PRIMEIRO(β) contêm ε (β  ε), então tudo
que está em Seguinte(A) está em Seguinte(B)
que está em Seguinte(A) está em Seguinte(B)

Compiladores 40
Seguinte (Follow)
Seguinte(A)=x para a regra SαAβ e primeiro(β)=x

Primeiro (E) = Primeiro(T) = Primeiro(F) =

E → TE’ {(, id}
E’ → +TE’ | ε Primeiro (E’) = {+, ε}
T → FT’ Primeiro (T) = Primeiro(F) = {(, id}
Primeiro (T’) = {*, ε}
T’ → *FT’ | ε
Primeiro (F) = {(, id}
F → (E) | id
Regra 3
1. Colocar
Seguinte(E) = {), $}
1. Colocar  em Seguinte(S)
$ em Seguinte(S) se
se S
S éé o
o símbolo
símbolo de
de
Seguinte(E’) = Seguinte(E) = {), $}
partida -  é o marcador de fim de entrada
partida Seguinte(T) = Primeiro(E’) = {+} U
2. Se existe uma produção A→ αBβ e β é diferente
2. Se existe uma produção A→ αBβ e β é diferente Seguinte(E) U Seguinte(E’) = {+, ), $}
de ε então tudo que estiver em PRIMEIRO(β),
de ε então tudo que estiver em PRIMEIRO(β), Seguinte(T’) = Seguinte(T)= {+, ), $}
exceto ε, deve ser adicionado em Seguinte(B) Seguinte(F) = primeiro(T') = {*} U
exceto ε, deve ser adicionado em Seguinte(B)
3.
3.
Se existe uma produção A→ αB ou A→ αBβ
Se existe uma produção A→ αB ou A→ αBβ Seguinte(T) U Seguinte(T’) = {*,+,), $}
onde PRIMEIRO(β) contêm ε (β  ε), então tudo
onde PRIMEIRO(β) contêm ε (β  ε), então tudo
que está em Seguinte(A) está em Seguinte(B)
que está em Seguinte(A) está em Seguinte(B)

Compiladores 41
Seguinte (Follow)
Seguinte(A)=x para a regra SαAβ e primeiro(β)=x

Primeiro (E) = Primeiro(T) = Primeiro(F) =

E → TE’ {(, id}
E’ → +TE’ | ε Primeiro (E’) = {+, ε}
T → FT’ Primeiro (T) = Primeiro(F) = {(, id}
Primeiro (T’) = {*, ε}
T’ → *FT’ | ε
Primeiro (F) = {(, id}
F → (E) | id
Regras 2 e 3
Seguinte(E) = {), $}
1. Colocar $ em Seguinte(S) se S é o símbolo de
Seguinte(E’) = Seguinte(E) = {), $}
partida Seguinte(T) = Primeiro(E’) = {+} U
2. Se existe uma produção A→ αBβ e β é diferente Seguinte(E) U Seguinte(E’) = {+, ), $}
de ε então tudo que estiver em PRIMEIRO(β), Seguinte(T’) = Seguinte(T)= {+, ), $}
exceto ε, deve ser adicionado em Seguinte(B) Seguinte(F) = primeiro(T') = {*} U
3. Se existe uma produção A→ αB ou A→ αBβ Seguinte(T) U Seguinte(T’) = {*,+,), $}
onde PRIMEIRO(β) contêm ε (β  ε), então tudo
que está em Seguinte(A) está em Seguinte(B)

Compiladores 42
Seguinte (Follow)
Seguinte(A)=x para a regra SαAβ e primeiro(β)=x

Primeiro (E) = Primeiro(T) = Primeiro(F) =

E → TE’ {(, id}
E’ → +TE’ | ε Primeiro (E’) = {+, ε}
T → FT’ Primeiro (T) = Primeiro(F) = {(, id}
Primeiro (T’) = {*, ε}
T’ → *FT’ | ε
Primeiro (F) = {(, id}
F → (E) | id
Regra 3
Seguinte(E) = {), $}
1. Colocar $ em Seguinte(S) se S é o símbolo de
Seguinte(E’) = Seguinte(E) = {), $}
partida - $ é o marcador de fim de entrada
Seguinte(T) = Primeiro(E’) = {+} U
2. Se existe uma produção A→ αBβ e β é diferente Seguinte(E) U Seguinte(E’) = {+, ), $}
de ε então tudo que estiver em PRIMEIRO(β), Seguinte(T’) = Seguinte(T)= {+, ), $}
exceto ε, deve ser adicionado em Seguinte(B) Seguinte(F) = primeiro(T') = {*} U
3. Se existe uma produção A→ αB ou A→ αBβ Seguinte(T) U Seguinte(T’) = {*,+,), $}
onde PRIMEIRO(β) contêm ε (β  ε), então tudo
que está em Seguinte(A) está em Seguinte(B)

Compiladores 43
Seguinte (Follow)
Seguinte(A)=x para a regra SαAβ e primeiro(β)=x

Primeiro (E) = Primeiro(T) = Primeiro(F) =

E → TE’ {(, id}
E’ → +TE’ | ε Primeiro (E’) = {+, ε}
T → FT’ Primeiro (T) = Primeiro(F) = {(, id}
Primeiro (T’) = {*, ε}
T’ → *FT’ | ε
Primeiro (F) = {(, id}
F → (E) | id
Regras 2 e 3
Seguinte(E) = {), $}
1. Colocar $ em Seguinte(S) se S é o símbolo de
Seguinte(E’) = Seguinte(E) = {), $}
partida - $ é o marcador de fim de entrada
Seguinte(T) = Primeiro(E’) = {+} U
2. Se existe uma produção A→ αBβ e β é diferente Seguinte(E) U Seguinte(E’) = {+, ), $}
de ε então tudo que estiver em PRIMEIRO(β), Seguinte(T’) = Seguinte(T)= {+, ), $}
exceto ε, deve ser adicionado em Seguinte(B) Seguinte(F) = primeiro(T') = {*} U
3. Se existe uma produção A→ αB ou A→ αBβ Seguinte(T) U Seguinte(T’) = {*,+,), $}
onde PRIMEIRO(β) contêm ε (β  ε), então tudo
que está em Seguinte(A) está em Seguinte(B)

b) S → ABd
A → aA | ε
B → bB | cA | AC
C → cB | ε

c) S → A | BC Quando tem uma regra do tipo A  BCD, o ε só

A → aAS | D
B → bB | fAC | ε
entra no Primeiro(A) se ele puder ser gerado por
C → cC B, C e D também.
D → gD | C | ε
d) S → aA | bB
A → aAS | BD
B → bB | fAC | ε
C → cC | Dd
D → gD | C | ε
Compiladores 45
Exercícios
Encontre os conjuntos Primeiro(First) para as gramáticas
abaixo
a) S → A | B
A → aAS | BD a) Primeiro(S)= {Primeiro(A) U Primeiro(B)}
B → bB | fAC | ε Primeiro(A)=
C → cC | BD Primeiro(B)=
D → gD | C | ε Primeiro(C)=
Primeiro(D)=

Quando tem uma regra do tipo A  BCD, o ε só

entra no Primeiro(A) se ele puder ser gerado por
B, C e D também.
Compiladores 46
Exercícios
Encontre os conjuntos Primeiro(First) para as gramáticas
abaixo
a) S → A | B
A → aAS | BD a) Primeiro(S)= {Primeiro(A) U Primeiro(B)}
B → bB | fAC | ε Primeiro(A)= {a U Primeiro(B) U ε U Primeiro(D)}
C → cC | BD Primeiro(B)= Primeiro(B)
D → gD | C | ε Primeiro(C)= gera ε,
Primeiro(D)= então
Primeiro(D)
entra em
Primeiro(A)

Quando tem uma regra do tipo A  BCD, o ε só

entra no Primeiro(A) se ele puder ser gerado por
B, C e D também.
Compiladores 47
Exercícios
Encontre os conjuntos Primeiro(First) para as gramáticas
abaixo
a) S → A | B
A → aAS | BD a) Primeiro(S)= {Primeiro(A) U Primeiro(B)}
B → bB | fAC | ε Primeiro(A)= {a U Primeiro(B) U ε U Primeiro(D)}
C → cC | BD Primeiro(B)= {b,f, ε} Primeiro(B)
D → gD | C | ε Primeiro(C)= gera ε,
Primeiro(D)= então
Primeiro(D)
entra em
Primeiro(A)

Quando tem uma regra do tipo A  BCD, o ε só

entra no Primeiro(A) se ele puder ser gerado por
B, C e D também.
Compiladores 48
Exercícios
Encontre os conjuntos Primeiro(First) para as gramáticas
abaixo
a) S → A | B
A → aAS | BD a) Primeiro(S)= {Primeiro(A) U Primeiro(B)}
B → bB | fAC | ε Primeiro(A)= {a U Primeiro(B) U ε U Primeiro(D)}
C → cC | BD Primeiro(B)= {b,f, ε} Primeiro(B)
D → gD | C | ε Primeiro(C)= {c U Primeiro(B) U ε} gera ε,
Primeiro(D)= então
Primeiro(D)
entra em
Primeiro(A)

Primeiro(B)
gera ε,
então
Primeiro(D)
entra em
Primeiro(C)

Quando tem uma regra do tipo A  BCD, o ε só

entra no Primeiro(A) se ele puder ser gerado por
B, C e D também.
Compiladores 49
Exercícios
Encontre os conjuntos Primeiro(First) para as gramáticas
abaixo
a) S → A | B
A → aAS | BD a) Primeiro(S)= {Primeiro(A) U Primeiro(B)}
B → bB | fAC | ε Primeiro(A)= {a U Primeiro(B) U ε U Primeiro(D)}
C → cC | BD Primeiro(B)= {b,f, ε} Primeiro(B)
D → gD | C | ε Primeiro(C)= {c U Primeiro(B) U ε} gera ε,
então
Primeiro(D)= {g U Primeiro(C) U ε}
Primeiro(D)
entra em
Primeiro(A)

Primeiro(B)
gera ε,
então
Primeiro(D)
entra em
Primeiro(C)

Quando tem uma regra do tipo A  BCD, o ε só

entra no Primeiro(A) se ele puder ser gerado por
B, C e D também.
Compiladores 50
Exercícios
Encontre os conjuntos Primeiro(First) para as gramáticas
abaixo
a) S → A | B
A → aAS | BD a) Primeiro(S)= {Primeiro(A) U Primeiro(B)} = {a, b, f, g, c, ε}
B → bB | fAC | ε Primeiro(A)= {a U Primeiro(B) U ε U Primeiro(D)} = {a, b, f, g, c, ε}
C → cC | BD Primeiro(B)= {b,f, ε}
D → gD | C | ε Primeiro(C)= {c U Primeiro(B) U ε} = {c, b, f, g, ε}
Primeiro(D)= {g U Primeiro(C) U ε} = {g,c,b,f, ε}