Análise Sintática
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
Etapas da Compilação
Análise Léxica
Análise Sintática
Front-End
(Análise)
Analise Semântica
Geração de Código
Intermediário
Geração de Código
Final
Back-End
(Síntese)
3
Análise Sintática

Alguns autores consideram que a análise sintática envolve
tudo que diz respeito à verificação do formato do código
fonte
•Inclui a análise léxica como subfase
•Visão mais coerente, porém o livro texto
que usamos tem outra visão...
4
Análise Sintática

Entenderemos análise sintática como sendo
apenas a segunda fase dessa verificação de
formato:
• “É a fase que analisa os tokens para descobrir a
estrutura gramatical do código fonte”
• Também chamada “Reconhecimento” (Parsing)
• Porém, um nome melhor seria “Análise Gramatical”
5
Gramáticas Livres de Contexto
Gramáticas


São usadas para organizar os tokens em “frases” de sentido
lógico
Definem regras de formação recursivas
expressão → CTE_INT
| ID
| expressão + expressão
7
Gramáticas

As gramáticas livres de contexto possuem quatro
elementos:
•Símbolos terminais
•Símbolos não-terminais
•Símbolo inicial
•Produções! ou Regras de Produção!
8
Gramáticas

Elementos das gramáticas livres de contexto:
•Símbolos terminais:
- Símbolos assumidos como atômicos, indivisíveis
- Em compiladores, são os tokens (int, +, -, /, identificador, valores
literais, etc)
•Símbolos não-terminais:
- Usados para organizar os tokens em “frases”
- Representam elementos abstratos do programa (expressões, termos,
etc)
9
Gramáticas

Elementos das gramáticas livres de contexto:
• Símbolo inicial:
- Não-terminal a partir do qual são derivadas “cadeias” de
símbolos terminais
- Geralmente é um não-terminal chamado programa
• Produções:
- São as regras de formação
- Definem as “frases” de terminais válidas na linguagem
10
Notações

Notação formal típica
•Símbolo não-terminal: letras maiúscula (E, T)
•Símbolo terminal: letras minúsculas, sinais,
etc. (x,i)
E
→
|
T →
|
T
T + E
x
i
11
Notações

Notação da Gramática BNF (Backus Naur Form)
•Símbolo não-terminal delimitado por “<“ e “>”
<expressao> ::= <termo>
| <termo> "+" <expressao>
<termo> ::= "x"
| "i"
12
Notações

Notações EBNF (existem várias versões)
•Não-terminais sem delimitadores
•BNF + operadores de expressões regulares
expressao = termo {"+" termo}*
termo = "x"
| "i"
13
Notações

Notações que usaremos
• Formal: para mostrar conceitos mais teóricos
• BNF e EBNF: para os exemplos práticos
- Tokens aparecerão literalmente se forem simples
- Ex.: sinais: “(”, “+”, “;” - palavras-chave: “int”, “for”,
“public”, etc.
- Tokens com várias opções de casamento aparecerão em
maiúscula (ex.: identificadores, valores literais)
14
Gramáticas

A partir do símbolo inicial, podemos derivar (gerar) as
cadeias (palavras) de terminais que são válidas na
linguagem
15
Derivação

Seja a gramática BNF anterior
• Derivar a cadeia “i+i+x”
<expressao>
 <termo> + <expressao>
 i
+ <expressao>
 i
+ <termo> + <expressao>
 i
+ i
+ <expressao>
 i
+ i
+ <termo>
 i
+ i
+ x
• Consideremos que esta é uma derivação mais à
esquerda
16
Derivação

Seja a gramática BNF mostrada antes
•Agora a Derivação mais à direita da cadeia
“i+i+x”
<expressao>
 <termo> + <expressao>
 <termo> + <termo> + <expressao>
 <termo> + <termo> + <termo>
 <termo> + <termo> + x
 <termo> + i
+ x
 i
+ i
+ x
17
Derivação

O processo de derivação consiste em substituir
cada ocorrência de um não-terminal pelo lado
direito (corpo) de alguma de suas produções
• Derivação mais à esquerda: substituir sempre o nãoterminal mais à esquerda
• Derivação mais à direita: análogo

A derivação pára quando sobrarem apenas
terminais e o resultado é a cadeia
18
Árvore de Derivação

A árvore dos exemplos anteriores
expressao
termo
i
+
expressao
termo
+
expressao
i
termo
a cadeia gerada pode ser percebida nas
folhas, analisando-as da esquerda para a
direita
19
x
Árvore de Derivação

A mesma árvore reorganizada
expressao
termo
expressao
termo
expressao
termo
i
+
i
+
a seqüência de terminais (cadeia) gerada
x
20
Árvore de Derivação

Mostra de maneira estática as produções
aplicadas
• Não diferencia se foi uma derivação mais à
esquerda ou mais à direita que gerou a cadeia

Forma
• Tem o símbolo inicial como raiz:
- (expressão)
• Não-terminais formam nós intermediários:
- (expressões e termos)
• As folhas são os terminais (tokens) da cadeia:
- (i, +, x)
21
Gramáticas Ambíguas


Uma gramática é dita ambígua se ela puder gerar duas
árvores de derivação distintas para uma mesma cadeia
Veremos uma gramática equivalente à anterior, porém
ambígua...
22
Gramáticas Ambíguas

Exemplo
<expressao> ::= <expressao> "+" <expressao>
| "x"
| "i"
•Mostrar duas árvores de derivação para
“i+i+x”
23
Exercício

As gramaticas a seguir são ambíguas?
E ->
|
|
|
E + E
E * E
(E)
a
S ->
|
|
E ->
if E then S
if E then S else S
s
e
24
Exercício

É ambígua já que existem duas derivações mais à esquerda
para a cadeia a + a + a:
A -> A + A
| A − A
| a
25
Gramáticas Ambíguas

Gramáticas ambíguas são, em geral, inadequadas para uso
em compiladores
•Dificultam a construção do analisador
sintático

Em alguns casos, são usadas gramáticas ambíguas junto com
restrições adicionais
•Exemplo: precedência e associatividade
26
Análise Sintática



Vimos que gramáticas são formalismos que geram cadeias
Em compiladores, não vamos gerar uma cadeia, mas já
temos a cadeia de terminais (ou seja, de tokens) pronta...
Diante disso, qual seria a função do analisador sintático?
27
Introdução à Análise Sintática
Análise Sintática

O objetivo
•Descobrir como uma sequência de tokens
pode ser gerada pela gramática da
linguagem

Em outras palavras
•Entrada: sequência de tokens
•Saída: árvore
29
Análise Sintática

O módulo de software responsável por essa etapa pode ser
chamado de
•Analisador sintático ou parser
(reconhecedor)

Existem duas estratégias algorítmicas que podem ser
adotadas
•Bottom-up / ascendente
•Top-down / descendente
30
Análise Sintática

Usaremos a seguinte gramática não-ambígua para ilustrar, a
seguir, as duas estratégias de análise sintática
<expressao> ::= <termo>
| <termo> "+" <expressao>
<termo> ::= "x"
| "i"
31
Análise Top-down



Parte da raiz (símbolo inicial) e tenta criar a
árvore de cima para baixo
Recursivamente testa se a cadeia de tokens
(lida da esquerda para a direita) pode ser
gerada pelas produções de cada não-terminal
O processo de construção da árvore lembra
uma derivação mais à esquerda da cadeia
32
Análise Top-down

O parser vai ter que escolher uma produção
adequada para o símbolo inicial <expressao>
expressao
?
i
+
i
+
33
x
Análise Top-down

Sabe-se que ambas as produções iniciam com
<termo>, variando o restante
expressao
?
termo
?
i
+
i
+
34
x
Análise Top-down

Ao ler o token “i”, o parser identifica que é
gerado por <termo>, mas falta decidir o
resto...
expressao
?
termo
i
+
i
+
35
x
Análise Top-down

A descoberta do “+” faz o parser decidir a
produção adequada
expressao
termo
expressao
?
i
+
i
+
36
x
Análise Top-down

Processo similar acontece após a leitura dos
dois tokens seguintes
expressao
termo
expressao
termo
expressao
?
i
+
i
+
37
x
Análise Top-down

Porém, no último token, <expressão> vai ter
apenas <termo> e o parser encerra no EOF (fim de
arquivo)
expressao
termo
expressao
termo
expressao
termo
i
+
i
+
38
x
EOF
Análise Bottom-up



Parte das folhas (tokens) e tenta crescer a
árvore até a raiz (símbolo inicial)
Para isso, compara a sequência de símbolos do
lado direito (ou corpo) das produções para
tentar criar um ramo da árvore
Diz-se que a sequência é “reduzida” ao nãoterminal do lado esquerdo da produção39
Análise Bottom-up

Tenta crescer a árvore usando o corpo das
produções, até chegar ao símbolo inicial
expressao
i
+
i
+
40
x
Análise Bottom-up

O token “i” é reduzido ao não-terminal
<termo>, devido à produção <termo> ::= “i”
expressao
termo
i
+
i
+
41
x
Análise Bottom-up

O parser lê o token “+”, mas ainda não pode
fazer uma redução
expressao
termo
i
+
i
+
42
x
Análise Bottom-up

Mais uma redução ao não-terminal <termo>
expressao
termo
i
termo
+
i
+
43
x
Análise Bottom-up

Apenas continua a leitura
expressao
termo
i
termo
+
i
+
44
x
Análise Bottom-up

Nova redução ao não-terminal <termo>
expressao
termo
i
termo
+
i
termo
+
45
x
Análise Bottom-up

Como acabaram-se os tokens, o último <termo> só
pode ser gerado diretamente por <expressao>,
então reduz
expressao
expressao
termo
i
termo
+
i
termo
+
46
x
EOF
Análise Bottom-up

Agora, a subcadeia “<termo>+<expressao>”
pode ser reduzida para <expressao>
expressao
expressão
expressão
termo
i
termo
+
i
termo
+
47
x
Análise Bottom-up

Outra redução, usando a mesma produção
expressao
expressao
expressao
termo
i
termo
+
i
termo
+
48
x
Exercício

Realizar a análise bottom-up da seguinte gramática para a
cadeia “a + a * a”:
E
E
T
T
F
F
->
->
->
->
->
->
E + T
T
T * F
F
E
a
49
Resposta
50
Top-down x Bottom-up


A análise sintática top-down é mais fácil de
entender e de implementar, porém a bottomup é mais poderosa (aplicável em mais
linguagens)
Uso principal das duas estratégias
• Bottom-up: usada pelos melhores geradores semiautomáticos de parsers
• Top-down: melhor técnica para implementar
manualmente
51
Top-down x Bottom-up


Chama-se gramática LL àquela que permite a construção
de um parser top-down (descendente) para reconhecê-la
Chama-se gramática LR àquela que permite a construção
de um parser bottom-up (ascendente) para reconhecê-la
52
Análise Sintática

Além de construir a árvore, outras atribuições importantes
do analisador sintático são:
•Reportar erros, o que deve ser feito de
maneira clara para permitir ao usuário
corrigir o problema
•Recuperar-se de erros automaticamente
(pouco uso em compiladores comerciais)
53
Análise Sintática



Na verdade, a análise sintática não precisa
construir a árvore durante o reconhecimento
Só é necessário construir a árvore se a análise
sintática for separada das etapas seguintes
Em todo caso, o parser vai funcionar como se
estivesse descobrindo a árvore que seria
gerada pela gramática para os tokens dados
54
Conceitos
Conceitos

Veremos alguns conceitos adicionais ligados à
fase de análise sintática
• Árvore sintática
• Sintaxe abstrata
• Precedência e associatividade
• Sintaxe concreta
56
Árvore Sintática



É quase igual à árvore de derivação, porém é
organizada de maneira mais “racional”
Cada nó interior é uma construção da
linguagem ou um operador
Cada nó filho é uma parte significativa da
construção ou um operando
• São descartados: pontuação, parênteses, etc.
57
Árvore Sintática

Gramática para os exemplos a seguir
expressao ::=
|
|
|
|
|
|
expressao + expressao
expressao - expressao
expressao * expressao
expressao / expressao
( expressao )
IDENTIFICADOR
INTEIRO_LITERAL
58
Árvore de Derivação

Árvore de derivação de “x*(i+i)”
expressao
expressao
x
*
expressao
(
expressao
expressao
+
)
expressao
i
i
59
Árvore Sintática

Árvore sintática de “x*(i+i)”
produto
var
x
soma
var
var
i
i
60
Sintaxe Abstrata

É comum uma linguagem ser especificada por meio de uma
gramática de sintaxe abstrata
•Em geral, é ambígua
•Porém, mais simples de entender

Para resolver as ambiguidades, a especificação precisa
definir restrições adicionais
61
Sintaxe Abstrata

Um exemplo seria a gramática mostrada antes
expressao ::=
|
|
|

expressao + expressao
expressao * expressao
( expressao )
INTEIRO_LITERAL
É comum assumir associatividade à esquerda e precedência
maior para a multiplicação
62
Associatividade

Associatividade diz como será aplicada uma
mesma operação binária quando há vários
operandos
• Exemplo: como interpretar a + b + c + d + e ?
• Se o operador for associativo à esquerda:
((((a + b) + c) + d) + e)
• Se o operador for associativo à direita:
(a + (b + (c + (d + e))))
63
Precedência

Precedência diz qual operação binária será
aplicada primeiro houver operadores
diferentes
• Exemplo: como interpretar a + b * c + d * e ?
• Se o operador * tiver maior precedência:
((a + (b * c)) + (d * e))
• Se o operador + tiver maior precedência:
(((a + b) * (c + d)) * e)
64
Sintaxe Concreta

Por outro lado, a gramática tal como ela foi usada para
implementar o parser é chamada de sintaxe concreta
•Geralmente não tem ambigüidades
•Mais fácil de implementar

Específica da implementação
•Cada compilador (de uma mesma linguagem)
pode criar uma implementação diferente
65
Sintaxe Concreta

Exemplo de sintaxe concreta correspondente à gramática
de expressões anterior
expressao ::= termo + expressao
| termo
termo ::= fator * termo
| fator
fator ::= ( expressao )
| INTEIRO_LITERAL
66
Tratando Ambiguidades
Tratando Ambiguidades


Veremos como tratar gramáticas ambíguas (sintaxe
abstrata), de modo a prepará-la para ser usada em um
parser (sintaxe concreta)
Veremos como tratar dois tipos de ambiguidades:
•Ambiguidade do “else”
•Ambiguidade de expressões
68
Tratando Ambiguidades

A seguinte de definição de comando apresenta ambigüidade
cmd ::= if ( expr ) cmd else cmd
| if ( expr ) cmd
| outro
expr ::= x

Exemplo: “if (x) if (x) outro else outro”
•A qual “if” está ligado o “else”?
69
Tratando Ambiguidades



O mais comum é considerar que o “else” casa
com o “if” aberto mais próximo
Geralmente, a definição anterior funciona bem
com as técnicas que vamos aprender
Mas, caso seja desejado, é possível remover
essa ambiguidade...
70
Tratando Ambiguidades


A estratégia é classificar os comandos em
comandos incompletos (ou abertos) e
completos
Comandos completos (matched)
• if-else
• todos os outros

Comandos incompletos ou abertos (open)
• if (sem else)
• if-else com um comando incompleto após o71else
Tratando Ambiguidades

Solução
cmd ::= matched-cmd
| open-cmd
matched-cmd ::=
| if ( expr ) matched-cmd else matched-cmd
| outro
open-cmd ::=
| if ( expr ) cmd
| if ( expr ) matched-cmd else open-cmd
72
Tratando Ambiguidades

Como mostrado, a gramática abaixo é ambígua, mas
essa ambiguidade pode ser resolvida com regras de
precedência e associatividade
expressao ::=
|
|
|
|
|
|

expressao + expressao
expressao - expressao
expressao * expressao
expressao / expressao
expressao ^ expressao
( expressao )
INTEIRO_LITERAL
Como incluir essas regras na própria gramática?
73
Tratando Ambiguidades

Criar um não-terminal para cada nível de precedência
•Chamaremos de: exprA, exprB, exprC...

No último nível (máxima precedência) ficam apenas
expressões não binárias
74
Tratando Ambiguidades


O não-terminal de cada nível tem uma produção para cada
operador do nível
Os operandos serão
•o não-terminal do nível atual, para outras
operações do mesmo nível
•e o não-terminal do próximo nível (nível de
maior precedência)
75
Tratando Ambiguidades

Na produção para os operadores, a posição do
não-terminal do nível atual indica o tipo de
associatividade do operador
• Se estiver à esquerda: associativo à esquerda
• Se estiver à direita: associativo à direita

Para tratar o caso de não haver nenhuma
operação do nível, deve haver uma produção
de substituição para o próximo nível
76
Tratando Ambiguidades

No exemplo anterior, vamos assumir três níveis
para os operadores binários
• As demais expressões formam um quarto nível

Ordenados da menor para a maior
precedência:
• adição e subtração, associativos à esquerda
- exprA
• multiplicação e divisão, assoc. à esquerda
- exprB
• exponenciação, assoc. à direita
- exprC
77
Tratando Ambiguidades

Resultado
expressao ::= exprA
exprA ::= exprA + exprB
| exprA - exprB
| exprB
associativos à esquerda
...
78
Tratando Ambiguidades

Resultado (continuação)
exprB ::= exprB * exprC
| exprB / exprC
| exprC
associativos à esquerda
exprC ::= exprD ^ exprC
| exprD
associativo à direita
exprD ::= ( expressao )
| INTEIRO_LITERAL
79
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)
80