Análise Sintática de Descida
Recursiva
Prof. Alexandre Monteiro
Baseado em material cedido pelo Prof. Euclides Arcoverde
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
Agenda

Introdução

Produção Única

Múltiplas Produções
• Conjuntos FIRST

Fatoração à Esquerda

Recursão à Esquerda

Recursão à Direita

Produção Vazia
• Conjunto FOLLOW

Produção de Substituição
3
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
4
Análise de Descida Recursiva


É útil para construir parsers manualmente, por ser
fácil de implementar
Princípio Básico
• Se eu quero produzir um não-terminal e sei qual o terminal
corrente eu devo saber que regra deve ser aplicada.

Porém, requer uma gramática muito bem ajustada
• Veremos os ajustes necessários

Mostraremos como usar a técnica, assumindo que o
parser final será uma classe Java
5
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
6
Classe Parser

Atributos típicos
• A classe Lexer (será o atributo “lexer”)
• O último token lido (será o atributo “token”)

Operação principal
• Método “parse()”

Métodos auxiliares
• Para aceitar os tokens, se estiverem corretos
• Para reconhecimento (parsing) de não-terminais
7
Métodos para Tokens


Serão dois métodos para aceitar tokens, ambos
serão chamados acceptToken()
Uma versão receberá o tipo do token que o
analisador espera
• Se o token não for do tipo esperado, reporta um
erro

A outra versão não receberá parâmetro
• Usado quando o tipo dele já é conhecido e é válido
8
Métodos para Tokens

Ambos os métodos acceptToken atualizam o
atributo token, lendo o próximo token
• A primeira versão (tipo como parâmetro) só lê se o
tipo do token anterior estiver correto

Assim, só esses dois métodos atualizam o
atributo token
• Portanto, só eles podem chamar o lexer
9
Métodos para Não-Terminais



Cada não-terminal N terá um método específico que
chamaremos parseN()
O objetivo desse método é reconhecer uma sequência de
símbolos que case com alguma das produções de N
É aqui que está a principal característica da análise de
descida recursiva...
10
Análise de Descida Recursiva

Portanto, cada método parseN() deverá:
• Identificar a produção adequada N  X1 X2 ...XK
• Em seguida, deverá chamar o método para
reconhecer cada símbolo Xi
- Se for um não-terminal, chama parseXi()
- Se for um terminal, chama acceptToken()
11
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);
}
12
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?
13
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 ..>
}
}
14
Múltiplas Produções

Como fazer no caso geral para escolher a produção?

Exemplo: reconhecer comando
comando ::= atribuição
| declaração
atribuição ::= IDENTIFICADOR = <expressao> ;
declaração ::= tipo IDENTIFICADOR ;
tipo ::= “int” | “char” | “float”
15
Conjunto FIRST

FIRST(α)
•Aplicado a cadeias α quaisquer

É o conjunto de terminais que podem iniciar a cadeia α
dada
•Se a cadeia derivar vazio, também inclui ε

Como calcular?
16
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(β)
17
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
18
Múltiplas Produções

Calculando o FIRST para as duas produções de comando ...
•comando ::= atribuição | declaração
FIRST(atribuição) = FIRST(IDENTIFICADOR = <expressao> ;)
= { IDENTIFICADOR }
FIRST(declaração) = FIRST(tipo IDENTIFICADOR ;)
= FIRST(tipo)
= { int , char, float }
19
Múltiplas Produções

A solução é comparar o token atual com o
FIRST de cada produção de comando...
void parseComando() {
TokenType token = this.token.getType();
if (token == IDENTIFICADOR) {
parseAtribuicao();
} else if (token == INT
|| token == CHAR
|| token == FLOAT ) {
parseDeclaracao();
} else {
throw new CompilerException(...);
}
}
20
Múltiplas Produções

No caso geral, para fazer o parsing de um nãoterminal N, com produções N  α | β
void parseN() {
if (token estiver em FIRST(α)) {
faz o parsing de α ...
} else if (token estiver em
faz o parsing de β ...
FIRST(β)) {
} else {
reportar/tratar erro
}
}
21
Análise de Descida Recursiva


Uma limitação dessa técnica é que as
produções de um mesmo não-terminal têm que
ter seus conjuntos FIRST disjuntos entre si
Ou seja, olhando apenas um terminal adiante
tem que ser possível escolher a produção da
gramática
• Uma gramática com essa propriedade é chamada
uma gramática LL(1)
• Assim como o parser é dito um parser LL(1)
22
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
23
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
| ε
24
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
25
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
26
Exercícios
Resolver fatorações a esquerda:

Direta:
XacX
Xad

Indireta:
XaX
XYc
Xd
Yab
27
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?
28
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!
29
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
30
Recursão à Esquerda

O exemplo anterior reescrito
exp ::= NUM restoExpr
restoExpr ::= “+” NUM restoExpr
| ε
31
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)
32
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
| ε
33
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
34
Exercícios
Resolver recursividades a esquerda:

Direta:
XXa
Xb

Indireta:
XYa
Xb
YXc
Yd
35
Recursão à Direita para Listas

As recursões servem para permitir repetições de algum tipo
de cadeia da gramática
•Listas/Seqüências de comandos
•Listas/Seqüências de declarações

A recursão à esquerda não pode ser usada, mas vamos ver
agora uma maneira de usar a recursão à direita
36
Recursão à Direita para Listas

Exemplo
listaComandos ::= comando listaComandos
| comando
comando

::= ID "=" expressao
Problemas com “listaComandos”
•Conjuntos FIRST das produções idênticos: { ID }
•Decidir quando parar de escolher a recursão
37
Recursão à Direita para Listas

Uma solução seria usar a fatoração à esquerda, explicada
antes
listaComandos ::= comando restoListaCmds
restoListaCmds ::= listaComandos
| 
comando

::= ID "=" expressao
Mas tem outra solução mais simples
38
Recursão à Direita para Listas

A recursão anterior pode ser reescrita assim:
listaComandos ::= comando {comando}*
comando


::= ID "=" expressao
Foi feita uma fatoração à esquerda sem
criação de um novo não-terminal
Isso foi possível com o operador regular *
• Zero ou mais repetições
39
Recursão à Direita para Listas

A parte do operador * pode ser resolvida
fazendo um loop
• Enquanto o token atual for elemento do FIRST de
comando, faz o parsing de mais um comando
void parseListaComandos() {
parseComando();
while (token.getType() == ID) {
parseComando();
}
}
40
Produção Vazia


Um tipo de produção que ainda não foi
abordada é a produção vazia
Um exemplo apareceu quando falamos de
fatoração à esquerda
• restoCmd
cmd ::= if exp then cmd restoCmd
| outro
restoCmd ::= else cmd
| ε
41
Produção Vazia

Uma solução simples é criar um else com corpo
vazio (não lançar erro), após verificar que o
token não casa com as outras produções
void parseRestoCmd() {
if (token.getType() == ELSE) {
...
} else {
/* do nothing! */
}
}
42
Produção Vazia

Um pequeno problema da abordagem anterior
é que erros sintáticos no código fonte só serão
identificados depois
• No método que for chamado após parseRestoCmd

Uma abordagem mais robusta para tratar a
produção vazia consiste em testar se o token é
um dos tipos esperados depois do não-terminal
43
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?
44
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)
45
Produção Vazia



Assim, a maneira mais correta de tratar a
produção vazia de um não-terminal N seria
testar, no último caso, se o token está no
conjunto FOLLOW(N)
Se não estiver, o caso else do parseN() já pode
reportar um erro imediatamente
Alterando o caso geral de “múltiplas
produções” mostrado antes...
46
Produção Vazia

Seja N um símbolo não-terminal N, com produções N ::= α |
β|ε
void parseN() {
if (token estiver em FIRST(α)) {
faz o parsing de α ...
} else if (token estiver em FIRST(β)) {
faz o parsing de β ...
} else if (token estiver em FOLLOW(N))
/* faz nada, produção vazia */
} else {
reportar/tratar erro...
}
}
47
Produção de Substituição

Uma produção de substituição de não-terminal
comando
::= cmdDecisão
cmdDecisão ::= if expressao...
| switch expressao ...

Este tipo de produção cria apenas uma
chamada de método a mais
void parseComando() {
parseCmdDecisao();
}
48
Produção de Substituição


Para melhorar a eficiência do parser, é melhor trocá-la
pelas produções do não-terminal referenciado
O exemplo anterior ficaria simplesmente
comando
::= if expressao...
| switch expressao ...
49
Exemplo

Linguagem XPR-0*
• Descrição
- É uma linguagem simples para reconhecer e calcular
expressões matemáticas de adição e multiplicação com
operandos de apenas um dígito. Os programas desta versão
são formados por um único comando, onde um comando
pode ser qualquer expressão terminada com ponto-evírgula. A semântica (significado) deste comando é a
avaliação da expressão seguida de sua impressão na saída
padrão
• Definir
- Sintaxe abstrata
- Sintaxe concreta
- Implementacao
* Continuação do código disponibilizado para o lexer “manual”
50
Exemplo

Sintaxe Abstrata
<program> ::= <command>
<command> ::= <expr> ";"
<expr>
::=
|
|
|
<expr> "+" <expr>
<expr> "*" <expr>
NUMERO
"(" <expr> ")"
51
Exemplo

Sintaxe Concreta
<program>
<command>
<expr>
<restExpr>
::=
::=
::=
::=
|
<term>
::=
<restTerm> ::=
|
<factor>
::=
|
<command>
<expr> ";"
<term> <restExpr>
"+" <term> <restExpr>
ε
<factor> <restTerm>
"*" <factor> <restTerm>
ε
NUMERO
"(" <expr> ")"
52
Exemplo

Implementar duas versões
• Classe ParserTemp
- Implementação “vazia” da análise sintática
- Apenas indica se a expressão está ou não correta
• Classe Parser
- Construído a partir do ParserTemp
- Calcula o resultado da expressão
- Funciona como um interpretador
53
Algoritmos FIRST e FOLLOW
Tabela LL(1)
Euclides Arcoverde
http://sites.google.com/site/euneto/
Algoritmo 1: Cálculo de FIRST

Calcular FIRST(A) para todos os não terminais
de uma gramática G
1. Inicialmente para todos os não terminais A da
gramática, todos os conjuntos FIRST(A) estão
vazios
2. Para cada regra A  B1 ... Bma tal que para todo
i = 1, ..., m, Bi  ε, acrescente a a FIRST(A)
3. Para cada regra A  B1 ... BmB tal que, para
todo i = 1, ..., m, Bi  ε, acrescente FIRST(B) a
FIRST(A)
4. Repita o passo 3 enquanto houver alteração no
valor de algum dos conjuntos FIRST
55
Resumo FIRST

FIRST() = {}

FIRST(t) = {t}

FIRST(XY) = FIRST(X)  FIRST(Y),
se X gera 

FIRST(XY) = FIRST(X), se X não gera 

FIRST(X|Y) = FIRST(X)  FIRST(Y)

FIRST(X*) = FIRST(X)
56
Algoritmo 1: Exemplo
Considere a seguinte gramática:

1.
2.
3.
4.
5.
6.
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> a

Passo 0: FIRST(E) = FIRST(T) = FIRST(F) = 

Passo 1:
•
•
(Regra 5) FIRST(F) = { ( }
(Regra 6) FIRST(F) = { a }
Passo 2:

•
•
(Regra 4) FIRST(T) = FIRST(F) = { (, a }
(Regra 2) FIRST(E) = FIRST(T) = FIRST(F) = { (, a }
57
Algoritmo 1: Exercício

Considere a seguinte gramática:
1.
2.
3.
4.
5.
6.
7.
8.
P -> A B C D
A -> ε
A -> a A
B -> ε
B -> B b
C -> c
C -> A B
D -> d
58
Algoritmo 2: Cálculo de FOLLOW

Calcular FOLLOW(A) para todos os não
terminais de uma gramática G
1. Inicialmente para todos os não terminais A da
gramática, todos os conjuntos FOLLOW(A) estão
vazios, exceto FOLLOW(S) = { $ }
2. Se há uma regra A  Ba e  = B1, ..., Bm  ε,
acrescente “a” a FOLLOW(B)
3. Se há uma regra A  BC e  = B1, ..., Bm  ε,
acrescente FIRST(C) a FOLLOW(B)
4. Se há uma regra A  B e  = B1, ..., Bm  ε,
acrescente FOLLOW(A) a FOLLOW(B)
5. Repita o passo 4 enquanto houver alteração no
valor de algum dos conjuntos
59
Algoritmo 2: Exemplo
Considere a seguinte gramática:

1.
2.
3.
4.
5.
6.
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> a

•
•
•
•

(Regra 1) FOLLOW(E) = { $, + }
(Regra 3) FOLLOW(T) = { * }
(Regra 5) FOLLOW(E) = { $, +, ) }
FOLLOW(F) = 
Passo 2:
• (Regra 2) FOLLOW(T) = FOLLOW(E) =
{ $, +, ), * }
• (Regra 4) FOLLOW(T) = FOLLOW(F) =
{ $, +, ), * }
FIRST(E) = FIRST(T) =

Passo 1:
FIRST(F) = { (, a }
Passo 0:

•
•
FOLLOW(E) = { $ }
FOLLOW(T) = FOLLOW(F) = 

Resultado final
• FOLLOW(E) = { $, +, ) }
• FOLLOW(T) = FOLLOW(F) = { $, +, ),
*}
60
Algoritmo 2: Exercício

Considere a seguinte gramática:
1.
2.
3.
4.
5.
6.
7.
8.
E -> T E’
T -> F T’
F -> ( E )
F -> a
E’ -> + T E’
E’ -> ε
T’ -> * F T’
T’ -> ε
FIRST(T) = FIRST(F) = { (, a }
FIRST(E’) = { + }
FIRST(T’) = { * }
61
Construção da Tabela LL(1)

Para cada produção A -> 
• Para cada terminal  em FIRST(A), inclua
A ->  em M[A, ]
• Se ε pertence a FOLLOW(), inclua A -> 
em M[A, b] para cada terminal b em
FOLLOW()
• Se ε pertence a FIRST() e $ pertence a
FOLLOW(A), acrescente também A ->  em
M[A, $]
62
Construção da Tabela LL(1)

Para toda regra: X -> A B C:
• Se A for um terminal:
-
Adicione “ABC” na posição (A,X) da tabela
• Se A for um não-terminal:
-

Adicione “ABC” na linha X somente nas colunas definidas pelos
FIRST(A)
Para toda regra: X ->
• Adicione “” na linha X e nas colunas vazias
(error)
63
Exemplo de Tabela LL(1)

X -> a X
Produções:
S -> a X b
X -> b
S -> b X a
Produções:
X
a
aX

b
b
S -> c
X -> b X
X -> a
a
b
c
S
aXb
bXa
c
X
a
bX
error
64
Exercícios

Produções 1
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> a

Produções 2
X > ab
X > Yb
X>b
Y > ca
Y > dZ
Z > ab

Produções 3
E -> T E’
T -> F T’
F -> ( E )
F -> a
E’ -> + T E’
E’ -> ε
T’ -> * F T’
T’ -> ε
65
Bibliografia

AHO, A., LAM, M. S., SETHI, R., ULLMAN, J. D.,
Compiladores: princípios, técnicas e ferramentas. Ed.
Addison Wesley. 2a Edição, 2008 (Capítulo 4)
66