Conteúdo da aula

1. Exemplos de Gramáticas
2. Propriedades: Ambíguas, sem ciclos, ε-livres,
Revisão de GLC e fatoradas à esquerda, recursivas à esquerda, simplificadas
3. Transformações: Eliminação de produções vazias, de
Analisadores Descendentes recursividade à esquerda (direta, indireta), fatoração

Marcelo Johann 4. Analisadores Descendentes

• Recursivos com Retrocesso
• Recursivos Preditivos
• Conjunto FIRST e Implementação

INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 2

Exemplos Exemplos
Gramática para Comandos Gramática para Expressões

cmd → if expr then cmd else cmd | print E → E OP E | “(“ E “)” | x

expr → ( bool ) | expr && expr | expr || expr OP → “*” | “/” | “+” | “-”
bool → true | false

INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 3 INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 4

Exemplos Ressaltando
Gramática para Listas • Convenções
– Símbolos que representam terminais em minúsculos:
S → a | “[“ L “]” • u, v, x, y, ...
– Símbolos que representam não-terminais em maiúsculos:
L → S “;” L | S • X, Y, TERM, S,...
– Símbolos que representam formas sentenciais (seqüências
de terminais e não-terminais): letras gregas ou
sublinhadas:
• α, β, ω, w, z

• Outras…

INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 5 INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 6

1
 Derivações Tipos e Características
• Derivação em um passo
• Gramáticas Ambíguas
A ⇒ xy
• Gramáticas sem ciclos
• Derivação em múltiplos passos
• Gramáticas ε-livres
Se A ⇒ w2 ⇒ w3 … ⇒ wn dizemos que
• Gramáticas fatoradas à esquerda
A ⇒* wn
• Gramáticas recursivas à esquerda
• Gramáticas simplificadas

INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 7 INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 8

Gramática Ambígua
E → E OP E | “(“ E “)” | x • Gramática sem ciclos:
OP → “*” | “/” | “+” | “-” – Uma gramática sem ciclos é uma GLC que não
possui derivações da forma
• Considere 5 – 3 * 2
A ⇒ + A para algum A ∈ N
E E

E - E E
E * E • Gramática ε-livre :
E - E 2
– GLC que não possui produções vazias do tipo
5 E * E
A→ε
3 2 5 3 exceto a produção S → ε (S é o símbolo inicial).

INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 9 INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 10

Transformações de GLCs
• Gramática fatorada à esquerda:
– GLC que não possui produções do tipo A → αβ1| αβ2 • (A) Eliminação de produções vazias
para alguma forma sentencial α.
• (B) Eliminação de recursividade à esquerda:
• Gramática recursiva à esquerda: – recursão direta
– GLC que permite a derivação – recursão indireta
A ⇒+ Aα para algum A ∈ N
O não terminal A deriva ele mesmo, de forma direta ou indireta, como
símbolo mais à esquerda de uma subpalavra gerada. • (C) Fatoração de uma gramática

INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 11 INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 12

2
Eliminação de Produções Vazias Eliminação de Produções Vazias

INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 13 INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 14

Eliminação de Produções Vazias (B) Eliminação de recursividade à esquerda

• Exemplo de GLC recursiva à esquerda:

A → Aa | b

• Gramáticas transformadas equivalentes:

Com a palavra vazia Sem a palavra vazia
A → bX A → b | bX
X → aX |ε X → a | aX

Obs: pode ainda haver recursão indireta!

INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 15 INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 16

(B) Outro exemplo de recursividade (C) Fatoração de uma gramática

• E -> E+T | T • Elimina a indecisão de qual produção

• T -> T*F | F aplicar quando duas ou mais produções
iniciam com a mesma forma sentencial
• F -> (E)| Id
A → αβ1 | αβ2
A regra E -> E+T | T se torna:
E -> TE’ Se torna:
E’ -> +TE’| ε
A → αX
A regra T- > T*F | F se torna:
T -> FT’ X → β1 |β2
T’-> *FT’ | ε

INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 17 INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 18

3
 (C) Exemplo de Fatoração a Esquerda Análise top-down e bottom-up

Cmd → if Expr then Cmd else Cmd

Cmd → if Expr then Cmd
Cmd → Outro

• Fatorando a esquerda:
Cmd → if Expr then Cmd ElseOpc
Cmd → Outro
ElseOpc → else Cmd | ε

INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 19 INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 20

Analisadores Descendentes Exemplo

• Também chamados recursivos ou top-down Gramática para Listas
• Recursivos com Retrocesso
Testam cada possível derivação S → a | “[“ L “]”
Exemplo L → S “;” L | S
• Recursivos Preditivos
Determinam produção pelo símbolo terminal atual Entrada: [ a ] $
Exemplo
• Conjunto FIRST e método de encontrá-lo
• Implementação

INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 21 INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 22

Observações sobre o método recursivo

Top-Down: Backtracking com retrocesso
S cbca tentar S→AB
S→AB AB cbca tentar A→c
• É fácil de implementar.
A→c|ε cB cbca casar c • É necessário:
B bca sem-saída, tentar A→ε
B → cbB | ca εB cbca tentar B→cbB
1. Que a gramática não seja recursiva à
cbB cbca casar c esquerda
bB bca casar b • A → Aa se tornará
B ca tentar B→cbB ReconheceA() { ReconheceA();... }
cbB ca casar c
• Gera bB a sem-saída, tentar B→ca
• Recursão infinita!
S ⇒* cbca? ca ca casar c
a a casar a -> Fim!

INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 23 INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 24

4
 Analisadores Descendentes Exemplo
• Também chamados recursivos ou top-down Gramática onde é fácil distinguir produções
• Recursivos com Retrocesso
Testam cada possível derivação CMD → “if” EXPR “then” CMD
Exemplo CMD → “while” EXPR “do” CMD
• Recursivos Preditivos CMD → “repeat” LISTA “until” EXPR
Determinam produção pelo símbolo terminal atual CMD → ID “:=“ EXPR
Exemplo
• Conjunto FIRST e método de encontrá-lo
• Implementação

INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 25 INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 26

Exemplo Exemplo
Mesma Gramática com mais Não-Terminais Outra Gramática

CMD: IF | ASS | WHILE | BL;

CMD → COND | ITER | ATRIB
BL: ´{´ CMDL ´}´;
COND → “if” EXPR “then” CMD
CMDL: CMD RESTO;
ITER → “while” EXPR “do” CMD | RESTO: ´;´ CMDL | epsilon;
“repeat” LISTA “until” EXPR IF: "if" E "then" CMD;
ATRIB → ID “:=“ EXPR WHILE: "while" E "do" CMD;
ASS: L ´=´ E;
L: ´*´ E | E;
E: NUM | ID;
INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 27 INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 28

Definição: Conjuntos “First” Condição para que se possa usar um

analisador preditivo
• Seja α qualquer seqüência de símbolos
• Informalmente: no caso que em os First() dos lados
– terminais ou não terminais
direitos das regras de produção sejam “simpáticos”, não
• First(α): terá retrocesso.
– Definição informal: • Formalmente: para qualquer produção
• conjunto de todos os terminais que começam A → α1 | α2 | ... | αn,
qualquer seqüência derivável de α. quer-se:
– Definição formal: First(α1 ) ∩ First(α2 ) ∩ ... ∩ First(αn) = Ø
• Se existe um t ∈ T e um β ∈ V* tal que α ⇒* t β
então t ∈ First(α)
• Se α ⇒* ε então ε ∈ First(α) A → B | C | D First(A)={b,c,d}
B→b First(B)={b}
C→c First(C)={c}
D→d First(D)={d}

INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 29 INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 30

5
 proc First(α: string of symbols) Observações sobre o método recursivo
preditivo
Repeat {
Para todas as produções α →
X1 X2 X3 … Xn do
• É fácil de implementar.
if X1 ∈T then // caso simples onde X1 é um terminal
First(α) := First(α) ∪ {X1 } • É necessário:
else { // caso menos simples: X1 é um não-terminal 1. Que a gramática não seja recursiva à esquerda
First(α) = First(α) ∪ First{X1} \ {ε}; • A → Aa se tornará
for (i=1 ; i<=n ; i++) { ReconheceA() { ReconheceA();... }
if ε is in First(X 1) and in First(X2) and in… First(Xi-1) • Recursão infinita!
First(α) := First(α) ∪ First(Xi) \ {ε} 2. Que a gramática seja fatorada à esquerda
• Senão, há ambigüidade na escolha da derivação.
}
} 3. Que os primeiros terminais deriváveis possibilitem a
if (α =>* ε) decisão de uma produção a aplicar!
then First(α) := First(α) ∪ {ε} • Não há retrocesso sobre não-terminais...
end do
} until no change in any First(α)
INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 31 INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 32

Implementação Etapas…
• CMD: IF | ASS | WHILE | BL;
• BL: '{' CMDL '}';
• CMDL: CMD RESTO;
• RESTO: ';' CMDL;
…voltando ao yacc
• IF: "if" E "then" CMD;
• WHILE: "while" E "do" CMD;
• ASS: L '=' E;
• L: '*' E | E;
• E: NUM | ID;
INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 33 INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 34

Leituras e Tarefas sugeridas

Ler e Reler o Livro

Implementar outra GLC
Ligar sua implementação com yylex
Ligar com autômato

INF01033 - Compiladores B - Marcelo Johann - 2012/1 Aula 07 : Slide 35