Embed Size (px)
Citation preview
1
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]
Site: http://www.alexandrecordel.com.br/fbv
Celular: (81) 9801-1878
3
Etapas da Compilação
Front-End(Análise)
Back-End(Síntese)
Análise Léxica
Análise Sintática
Analise Semântica
Geração de CódigoIntermediário
Geração de CódigoFinal
4
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...
5
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”
Gramáticas Livres de Contexto
7
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
8
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!
9
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)
10
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
11
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 + E T → x | i
12
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"
13
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"
14
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)
15
Gramáticas
A partir do símbolo inicial, podemos derivar (gerar) as cadeias (palavras) de terminais que são válidas na linguagem
16
Derivação
Seja a gramática BNF anterior• Derivar a cadeia “i+i+x”
• Consideremos que esta é uma derivação mais à esquerda
<expressao>Þ <termo> + <expressao>Þ i + <expressao>Þ i + <termo> + <expressao>Þ i + i + <expressao>Þ i + i + <termo>Þ i + i + x
17
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
18
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ão-terminal mais à esquerda• Derivação mais à direita: análogo
A derivação pára quando sobrarem apenas terminais e o resultado é a cadeia
19
Árvore de Derivação
A árvore dos exemplos anteriores
expressao
expressao
i
+
i
+
x
termo
termo expressao
a cadeia gerada pode ser percebida nas folhas, analisando-as da esquerda para a
direita
termo
20
Árvore de Derivação
A mesma árvore reorganizada
expressao
expressao
i + i + x
termo
termo expressao
a seqüência de terminais (cadeia) gerada
termo
21
Á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)
22
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...
23
Gramáticas Ambíguas
Exemplo
• Mostrar duas árvores de derivação para “i+i+x”
<expressao> ::= <expressao> "+" <expressao> | "x" | "i"
24
Exercício
As gramaticas a seguir são ambíguas?
E -> E + E | E * E | (E) | a
S -> if E then S | if E then S else S | s E -> e
25
Exercício É ambígua já que existem duas derivações mais à
esquerda para a cadeia a + a + a:A -> A + A | A − A | a
26
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
27
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?
Introdução à Análise Sintática
29
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
30
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
31
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"
32
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
33
Análise Top-down
O parser vai ter que escolher uma produção adequada para o símbolo inicial <expressao>
expressao
i + i + x
?
34
Análise Top-down
Sabe-se que ambas as produções iniciam com <termo>, variando o restante
i + i + x
expressao
termo ?
?
35
Análise Top-down
Ao ler o token “i”, o parser identifica que é gerado por <termo>, mas falta decidir o resto...
i + i + x
expressao
termo ?
36
Análise Top-down
A descoberta do “+” faz o parser decidir a produção adequada
expressao
expressao
i + i + x
termo
?
37
Análise Top-down
Processo similar acontece após a leitura dos dois tokens seguintes
expressao
expressao
i + i + x
termo
termo expressao
?
38
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
expressao
i + i + x
termo
termo expressao
termo
EOF
39
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ão-terminal do lado esquerdo da produção
40
Análise Bottom-up
Tenta crescer a árvore usando o corpo das produções, até chegar ao símbolo inicial
expressao
i + i + x
41
Análise Bottom-up
O token “i” é reduzido ao não-terminal <termo>, devido à produção <termo> ::= “i”
expressao
i + i + x
termo
42
Análise Bottom-up
O parser lê o token “+”, mas ainda não pode fazer uma redução
expressao
i + i + x
termo
43
Análise Bottom-up
Mais uma redução ao não-terminal <termo>
expressao
i + i + x
termo termo
44
Análise Bottom-up
Apenas continua a leitura
expressao
i + i + x
termo termo
45
Análise Bottom-up
Nova redução ao não-terminal <termo>
expressao
i + i + x
termo termo termo
46
Análise Bottom-up
Como acabaram-se os tokens, o último <termo> só pode ser gerado diretamente por <expressao>, então reduz
expressao
i + i + x
termo termo
expressao
termo
EOF
47
Análise Bottom-up
Agora, a subcadeia “<termo>+<expressao>” pode ser reduzida para <expressao>
expressao
i + i + x
termo
expressão
termo
expressão
termo
48
Análise Bottom-up
Outra redução, usando a mesma produção
expressao
i + i + x
termo
expressao
expressao
termotermo
49
Exercício
Realizar a análise bottom-up da seguinte gramática para a cadeia “a + a * a”:
E -> E + T E -> T T -> T * F T -> F F -> E F -> a
50
Resposta
51
Top-down x Bottom-up
A análise sintática top-down é mais fácil de entender e de implementar, porém a bottom-up é mais poderosa (aplicável em mais linguagens)
Uso principal das duas estratégias• Bottom-up: usada pelos melhores geradores
semi-automáticos de parsers• Top-down: melhor técnica para implementar
manualmente
52
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
53
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)
54
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
Conceitos
56
Conceitos
Veremos alguns conceitos adicionais ligados à fase de análise sintática
• Árvore sintática
• Sintaxe abstrata
• Precedência e associatividade
• Sintaxe concreta
57
Á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.
58
Árvore Sintática
Gramática para os exemplos a seguir
expressao ::= expressao + expressao | expressao - expressao | expressao * expressao | expressao / expressao | ( expressao ) | IDENTIFICADOR | INTEIRO_LITERAL
59
Árvore de Derivação
Árvore de derivação de “x*(i+i)”
expressao
expressao
x
*
i
+
i
expressao
expressao expressao
( )expressao
60
Árvore Sintática
Árvore sintática de “x*(i+i)”
produto
x
i i
var
soma
var
var
61
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
62
Sintaxe Abstrata
Um exemplo seria a gramática mostrada antes
É comum assumir associatividade à esquerda e precedência maior para a multiplicação
expressao ::= expressao + expressao | expressao * expressao | ( expressao ) | INTEIRO_LITERAL
63
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))))
64
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)
65
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
66
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
Tratando Ambiguidades
68
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
69
Tratando Ambiguidades
A seguinte de definição de comando apresenta ambigüidade
Exemplo: “if (x) if (x) outro else outro”
• A qual “if” está ligado o “else”?
cmd ::= if ( expr ) cmd else cmd | if ( expr ) cmd | outro
expr ::= x
70
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...
71
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 o
else
72
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
73
Tratando Ambiguidades
Como mostrado, a gramática abaixo é ambígua, mas essa ambiguidade pode ser resolvida com regras de precedência e associatividade
Como incluir essas regras na própria gramática?
expressao ::= expressao + expressao | expressao - expressao | expressao * expressao | expressao / expressao | expressao ^ expressao | ( expressao ) | INTEIRO_LITERAL
74
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
75
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)
76
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
77
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
78
Tratando Ambiguidades
Resultado
expressao ::= exprA
exprA ::= exprA + exprB | exprA - exprB | exprB
...
associativos à esquerda
79
Tratando Ambiguidades
Resultado (continuação)
exprB ::= exprB * exprC | exprB / exprC | exprC
exprC ::= exprD ^ exprC | exprD
exprD ::= ( expressao ) | INTEIRO_LITERAL
associativos à esquerda
associativo à direita
80
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)
