Revisão Compiladores – AP2
Prof. Alexandre Monteiro
Recife
‹#›
Contatos

Prof. Guilherme Alexandre Monteiro Reinaldo

Apelido: Alexandre Cordel

E-mail/gtalk: [email protected]
[email protected]

Site: http://www.alexandrecordel.com.br/fbv

Celular: (81) 9801-1878
Análise de Descida Recursiva


É uma análise sintática top-down ou
descendente
É um parser LL(1)
• Left-to-right – a ordem de leitura dos tokens é da
esquerda para a direita
• Leftmost derivation – segue a ordem típica de uma
derivação mais à esquerda
• Só olha 1 token por vez
3
Exemplo de Reconhecedor

Gramática:
Terminais = {a,b,c}
Não-terminais = {S, X}
Produções = {
SaXb
SbXa
Sc
a
b
c
S
aXb
bXa
c
X
a
bX
Error
XbX
Xa
}
Não-terminal inicial = S
4
Produção Única

Um não-terminal com apenas uma produção é
o caso mais simples de ser tratado
frase ::= sujeito predicado “.”

Ficará assim
void parseFrase() {
parseSujeito();
parsePredicado();
acceptToken(PONTO);
}
5
Múltiplas Produções


Porém, quando houver mais de uma produção,
é preciso usar um critério de escolha
Por exemplo:
sujeito ::= “Eu”
| “Um” substantivo
| “O” substantivo

Como escolher a produção certa (ou seja, a
que representa o código fonte) durante a
análise?
6
Múltiplas Produções

No exemplo anterior, basta olhar o token atual
void parseSujeito() {
TokenType tp = this.token.getType();
if (tp == TokenType.EU) {
acceptToken();
} else if (tp == TokenType.UM) {
acceptToken();
parseSubstantivo();
} else if (tp == TokenType.O) {
acceptToken();
parseSubstantivo();
} else {
<.. reportar erro ..>
}
}
7
Conjunto FIRST

Se α for a cadeia vazia (α = ε)
•FIRST(ε) = { ε }

Se for um terminal a qualquer
•FIRST(a) = { a }

Se for um não-terminal N com as produções N → α | β
•FIRST(N) = FIRST(α)  FIRST(β)
8
Conjunto FIRST

Se for uma cadeia de símbolos α = X1X2...Xk
• Depende de X1

Se X1 não pode gerar vazio
• FIRST (X1X2...Xk) = FIRST(X1)

Se X1 pode gerar vazio
• FIRST (X1X2...Xk) = FIRST(X1)  FIRST(X2...Xk)
• Calcula para X1 e continua o cálculo recursivamente
para o restante da cadeia
9
Fatoração à Esquerda



Alguns casos em que as produções têm seus
conjuntos FIRST idênticos podem ser tratados
Um deles é quando as produções têm prefixos
comuns
Exemplo
cmd ::= if exp then cmd else cmd
| if exp then cmd
| outro
10
Fatoração à Esquerda

A solução é parecida com a fatoração em
expressões matemáticas
• Colocar a parte comum em evidência
• A parte diferente pode se tornar outro não-terminal

Exemplo anterior
cmd ::= if exp then cmd restoCmd
| outro
restoCmd ::= else cmd
| ε
11
Fatoração à Esquerda

Caso geral
• Seja N com produções com prefixo comum α
N → α β1
| α β2
| Ф
• Colocando α em comum e criando um novo nãoterminal X
N → α X
| Ф
X → β1
| β2
12
Eliminação de Fatoração

Direta:

Xab
XYc
Yad
Xabc
Xade

Sem fatoração:
XaY
Ybc
Yde
Indireta

Elimina-se a indireção:
Xab
Xadc
Yad

Sem fatoração:
XaZ
Yad
Zb
Zdc
13
Exercícios
Resolver fatorações a esquerda:

Direta:
XacX
Xad

Indireta:
XaX
XYc
Xd
Yab
14
Recursão à Esquerda

Outra limitação (menos grave) da técnica, é se houver uma
produção recursiva à esquerda
exp ::= exp “+” NUM
| NUM

O que acontece se tentarmos criar o parser diretamente
desta gramática?
15
Recursão à Esquerda
void parseExp() {
if (token.getType() == NUM) {
recursão infiinita !
parseExp();
acceptToken(MAIS);
acceptToken(NUM);
} else if (token.getType() == NUM) {
acceptToken();
}

Qual o problema com esse código?
•Além dos conjuntos FIRST não serem
disjuntos, ele apresenta recursão infinita!
16
Recursão à Esquerda

Neste caso, é preciso alterar a gramática para
remover a recursão à esquerda
• É necessário haver outra produção sem a recursão

Como reescrever o exemplo anterior para
remover a recursão à esquerda?
exp ::= exp “+” NUM
| NUM
17
Recursão à Esquerda

O exemplo anterior reescrito
exp ::= NUM restoExpr
restoExpr ::= “+” NUM restoExpr
| ε
18
Recursão à Esquerda

Caso geral
• Seja a gramática
N →
|
|
|
N α1
N α2
β1
β2
Sejam α1, α2, β1 e β2
cadeias quaisquer
• Comentários
- A recursão à esquerda serve apenas para produzir
repetições de α1 ou α2 (à direita das recursões)
- A recursão só pára quando o N à esquerda for β1 ou β2
(produções sem recursão à esquerda)
19
Recursão à Esquerda

Caso geral (solução)
• Criar um novo não-terminal X para criar zero ou
mais repetições de α1 ou α2 com recursão à direita
• Fazer as produções sem recursão de N terminarem
com X
N →
|
|
|
N α1
N α2
β1
β2
N → β1 X
| β2 X
X → α1 X
| α2 X
| ε
20
Eliminação da Recursividade
Esquerda

Direta:

XXa
Xb

XYa
Xb
YXc
Yd
Sem recursão:
X’  ε
X’  a X’
X  b X’
Indireta:

Remove-se a indireção:
XXca
Xda
Xb
YXc
Yd

Resolve-se como no caso
anterior
21
Exercícios
Resolver recursividades a esquerda:

Direta:
XXa
Xb

Indireta:
XYa
Xb
YXc
Yd
22
Conjunto FOLLOW

FOLLOW (N)
• Aplicado a não-terminais N quaisquer

É o conjunto de terminais que podem aparecer à
direita do não-terminal N, em alguma cadeia derivada
pela gramática
• Se o símbolo inicial deriva uma cadeia “... N x ...” então x
faz parte de FOLLOW(A)
• O símbolo inicial tem $ no conjunto FOLLOW para indicar fim
da entrada (EOF)

Como calcular?
23
Conjunto FOLLOW

Se N for o símbolo inicial
• Colocar $ (EOF) no conjunto FOLLOW(N)

Para toda produção X → α N β , em que beta
não é vazio e não deriva vazio
• Adicionar tudo de FIRST(β) no FOLLOW(N)

Para toda produção X → α N β , em que beta
ou é vazio ou deriva vazio
• Adicionar todo o FOLLOW(X) no FOLLOW(N)
24
Analisador Sintática LR

Existem diversos tipos de analisadores LR(k)

O nome LR(k) indica
• Left-to-right – a ordem de leitura dos tokens é da
esquerda para a direita
• Rigthmost derivation – encontra uma derivação mais
à direita (porém, de trás para a frente)
• K token são olhados à frente (lookahead)
25
Relembrando as Tabelas

Tabela ACTION
•Diz qual ação será tomada, de acordo com o
estado atual e o próximo token

Tabela GOTO (usada após um reduce)
•Diz qual o próximo estado, de acordo com o
estado atual e o símbolo não-terminal que
foi reduzido
26
Funcionamento

A medida que lê os terminais (tokens), o parser poderá
realizar certas ações, de acordo com o estado atual
•SHIFT
•REDUCE
•ACCEPT
•ERROR
27
Exemplo (quadro)
0)
S:
stmt $
1)
stmt: ID ':=' expr
2)
expr: expr '+' ID
3)
expr: expr '-' ID
4)
expr: ID
28
Exemplo (autômato)
State 0
0)S:
. stmt $
1)stmt:
. ID ':=' expr
State 1
0)S:
State 3
1) stmt:
2) expr:
3) expr:
4) expr:
ID ':=' . expr
. expr '+' ID
. expr '-' ID
. ID
stmt . $
State 2
1)stmt:
ID . ':=' expr
29
Exemplo (autômato)
State 0
0) S: . stmt $
1) stmt: . ID ':=' expr
GOTO
2 on stmt
SHIFT 1 on ID
State 1
1) stmt: ID . ':=' expr
SHIFT 3 on ':='
4) expr: . ID
GOTO
6 on expr
SHIFT 5 on ID
State 7
2) expr: expr '+' . ID
SHIFT 9 on ID
State 4
0) S: stmt
State 8
3) expr: expr '-' . ID
SHIFT 10 on ID
$.
State 5
4) expr: ID .
State 2
0) S: stmt . $
SHIFT 4 on $
State 3
1) stmt: ID ':=' . expr
2) expr: . expr '+' ID
State 6
1) stmt: ID ':=' expr .
2) expr: expr . '+' ID
3) expr: expr . '-' ID
SHIFT 7 on '+'
SHIFT 8 on '-'
State 9
2) expr: expr '+' ID .
State 10
3) expr: expr '-' ID .
3) expr: . expr '-' ID
30
Exemplo (Tabelas)
0
1
2
3
4
5
6
7
8
9
10
Action Table
Goto Table
ID ':=' '+' '-'
$ stmt expr
s1
g2
s3
s4
s5
g6
acc acc acc acc acc
r4 r4 r4 r4 r4
r1 r1 s7 s8 r1
s9
s10
r2 r2 r2 r2 r2
r3 r3 r3 r3 r3
31
Exemplo: a:= b + c - d
Stack
0/S
0/S 1/a
0/S 1/a 3/:=
0/S 1/a 3/:= 5/b
0/S 1/a 3/:=
0/S 1/a 3/:= 6/expr
0/S 1/a 3/:= 6/expr 7/+
0/S 1/a 3/:= 6/expr 7/+ 9/c
0/S 1/a 3/:=
0/S 1/a 3/:= 6/expr
0/S 1/a 3/:= 6/expr 8/0/S 1/a 3/:= 6/expr 8/- 10/d
0/S 1/a 3/:=
0/S 1/a 3/:= 6/expr
0/S
0/S 2/stmt
0/S 2/stmt 4/$
Remaining Input
a:= b + c - d
:= b + c - d
b+c-d
+c-d
+c-d
+c-d
c-d
-d
-d
-d
d
$
$
$
$
$
Action
s1
s3
s5
r4
g6 on expr
s7
s9
r2
g6 on expr
s8
s10
r3
g6 on expr
r1
g2 on stmt
s4
32
accept
Análise Semântica

O que é?

Para que serve?

Qual a finalidade de uma tabela de símbolos (TS) no projeto
de um compilador?
33
Tradução em Parsers de Descida
Recursiva

...basta posicionar a ação semântica dentro do
bloco que trata a produção desejada
void parseLoopComand() {
if (token.getType() == WHILE) {
acceptToken();
System.out.println(“While!");
...
} else if (token.getType() == DO) {
acceptToken();
parseComand();
System.out.println(“Do-While!");
...
}
}
34
Código de Três Endereços

É uma linguagem de baixo nível (simples), porém independente
de máquina

Programas representados como uma simples lista de instruções

As instruções usam, no máximo, três operandos (endereços)
35
Tipos de Endereços

Um endereço pode ser:
• Um nome – representando uma variável, função, etc.
• Uma constante – valor literal de um número, uma
string, um caractere, etc.
• Um temporário – variável auxiliar criada pelo
compilador (t1, t2, etc.)
• Um rótulo – localização de uma instrução
36
Tipos de Instruções

Instruções de atribuição da forma
x = y op z

Onde op é um operador binário aritmético,
binário ou lógico
• Exemplo:
aux = t1 + temp
37
Tipos de Instruções

Instruções de atribuição da forma
x = op y

Onde op é um operador unário, como: negação
lógica, menos, conversão de tipo
• Exemplos:
t1 = (int) temp;
t1 = - temp;
38
Tipos de Instruções

Instruções de cópia
x = y


Usadas, em alguns casos, para facilitar a geração do código
intermediário
Numa fase posterior, de otimização, essa instrução pode
ser removida
39
Tipos de Instruções

Desvio incondicional
goto L

Desvia para o rótulo L : faz com que a próxima
instrução a ser executada seja a que tem o
rótulo L
• Exemplo:
label2:
aux = t + 1;
...
goto label2
40
Tipos de Instruções

Desvios condicionais
if x goto L
ifFalse x goto L

Desviam para o rótulo L dependendo do valor booleano de x
41
Tipos de Instruções

Desvios condicionais com operadores
relacionais (<, >, ==, !=, ...)
if x op_cond y goto L

Desvia para L se o resultado da operação
relacional for verdadeiro
• Exemplo:
label2:
aux = t + 1;
if aux < temp goto label2
42
Traduzindo Expressões

Uma expressão com várias operações...
myVar = aux + temp * 3

...é decomposta em expressões menores, com uma
operação cada
t1 = 3
t2 = temp * t1
t3 = aux + t2
myVar = t3
43
If-Else

Exemplo:
int x = 0;
if (x < 10) {
x = 20;
} else {
x = 10;
}
int y = x;
x = 0
t1 = x < 10
ifFalse t1 goto F1
x = 20
goto R1
F1:
x = 10
R1:
y = x
44
While

Exemplo:
x = 0;
while (x < 10) {
x = x + 1;
}
y = x;
x = 0
I1:
t1 = x < 10
ifFalse t1 goto R1
t2 = x + 1
x = t2
goto I1
R1:
y = x
45