Tópicos em Compiladores
Cristiano Damiani Vasconcellos
[email protected]
Bibliografia Recomendada
COMPILADORES Princípios, Técnicas e Ferramentas;
Sethi, Ravi; Aho, Alfred V.; Ullman, Jeffrey D. LTC, 1995.
Projeto Moderno de Compiladores;
Bal, Henri E.; Grune, Dick; Langendoen, Koen. CAMPUS, 2001.
Introdução A Teoria dos Autômatos, Linguagens e Computação;
Hopcroft, John E.; Ullman, Jeffrey D.; Motwani, Rajeev. CAMPUS,
2002.
Introdução
Pré-processador
Analisador Léxico
Analisador Sintático
front-end
Analisador Semântico
Gerador de Código
(intermediário)
Otimizador
back-end
Gerador de Código
Introdução
final = (nota1 + nota2) / 2;
Analisador Léxico
Id1 = (Id2 + Id3) / 2
Analisador Sintático
=
Id1
Tabela de Símbolos
/
2
+
Id2
Id3
Id1
final
double
...
Id2
nota1
double
...
Id3
nota2
double
...
...
Introdução
Analisador Semântico
=
Id1
/
intToDouble(2)
+
Id2
Id3
Gerador de Código
(intermediário)
Tabela de Símbolos
Id1
final
double
...
Id2
nota1
double
...
temp2 = temp1 / 2.0
Id3
nota2
double
...
Id1 = temp2
...
temp1 = Id2 + Id3
Análise Léxica
•
•
•
•
•
•
O Analisador Léxico (scanner) examina o
programa fonte caractere por caractere
agrupando-os em conjuntos com um significado
coletivo (tokens):
palavras chave (if, else, while, int, etc),
operadores (+, -, *, /, ^, &&, etc),
constantes (1, 1.0, ‘a’, 1.0f, etc),
literais (“Projeto Mono”),
símbolos de pontuação (; , {, }),
labels.
Análise Léxica
constanteInt
 digito digito*
constanteDouble  digito digito*. digito*
digito  {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
X* Representa uma seqüência de zero ou mais X.
Análise Sintática
Verifica se as frases obedecem as regras
sintáticas da linguagem:
Por exemplo, uma expressão pode ser definida
como:
expressão + expressão
expressão – expressão
(expressão)
constante
Gramáticas
Um conjunto de regras de produção, é um
símbolo de partida. Uma regra de produção
tem o formato   , onde  representa o
nome da construção sintática e  representa
uma forma possível dessa construção:
<expressão>  <expressão> + <expressão>
Gramáticas
<expr>  <expr> + <expr>
| <expr> – <expr>
| (<expr>)
| <const>
<const>  <const><const>
|0|1|2|3|4|5|6|7|9
Derivação
A verificar se uma frase faz parte da linguagem
gerada pela gramática, envolve sucessivas
substituições da cadeia de símbolos que ocorre
do lado esquerdo da produção pela sua
construção sintática correspondente, partindo
do símbolo inicial.
Essa substituição é chamada derivação sendo
normalmente denotada pelo símbolo .
Derivação
<expressão>
 <expr> + <expr>
 (<expr>) + <expr>
 (<expr> - <expr>) + <expr>
 (<const> - <expr>) + <expr>
 (<const><const> - <expr>) + <expr>
 (1<const> - <expr>) + <expr>
 (10 - <expr>) + <expr>
 (10 - <const>) + <expr>
...
 (10 - 2) + 3
Árvore Sintática
(10 – 2) + 3
<expr>
<expr>
+
(<expr>)
<expr>
<const>
<expr> - <expr>
<const>
<const>
10
2
3
Gramáticas Ambíguas
10 – 2 + 3
<expr>
<expr>
<expr>
-
<expr>
<expr>
<expr> + <expr>
10
2
3
+
<expr>
<expr> - <expr>
10
2
3
Gramáticas
<expr>  <expr> + <termo>
| <expr> - <termo>
| <termo>
<termo>  (<expr>)
| <const>
<expr>
<expr>
+
<termo>
<expr> - <termo>
<expr>
10
 <expr> + <termo>
 <expr> - <termo> + <termo>
 <termo> - <termo> + <termo>
 10 – 2 + 3
2
3
Gramáticas
<expr> 
<termo> 
<fator> 
<expr> + <termo>
| <expr> - <termo>
| <termo>
<termo> * <fator>
| <termo> / <fator>
| <fator>
(<expr>)
| <const>
1+2*3
<expr>
<expr>
+
<termo>
<termo> * <fator>
3
2
3
Gramáticas
<expr> 
<termo> 
<fator> 
<expr> + <termo>
| <expr> - <termo>
| <termo>
<termo> * <fator>
| <termo> / <fator>
| <fator>
(<expr>)
| <const>
1+2*3
<expr>
<termo>
<termo> * <fator>
Tradução Dirigida pela Sintaxe
Programa Fonte
Analisador Léxico
Tabela de Símbolos
token
Solicita token
...
Analisador Sintático
Analisador Semântico
Código Intermediário
Gramáticas - Exercícios
1.
2.
3.
4.
Considerando a gramática apresentada anteriormente
derive as expressões e apresente a árvore sintática
correspondente:
(1 + 2) * 3
(1 – 2) + 3 * 4
Altere a gramática para incluir o operador unário -, esse
operador deve ter precedência maior que os outros
operadores.
Altere a gramática para que os operadores de adição,
subtração, multiplicação e divisão tenham associatividade
da direita para a esquerda.
Defina uma gramática para expressões aritméticas
(operadores +, -, *, /) pós fixadas .
Gramáticas
Dados 2 conjuntos independentes de símbolos:
• Vt – Símbolos terminais
• Vn – Símbolos não terminais.
Uma gramática é definida como a quádrupla:
{Vn, Vt, S, P}
Onde,
S  Vn é o símbolo inicial da gramática.
P é um conjunto de regras de reescrita na forma:
  , sendo:   (Vn  Vt)* Vn (Vn  Vt)*
  (Vn  Vt)*
Classificação de Gramáticas
• Irrestritas – nenhuma restrição é imposta
• Sensíveis ao Contexto - ||  ||
• Livres de Contexto -
  Vn
  (Vn  Vt)+
• Regulares -
  Vn
 tem a forma a ou aB, onde
a  Vt e B  Vn
Gramáticas Regulares
C0|1|2|3|4|5|6|7|9
| 0C | 1C | 2C | 3C | 4C | 5C | 7C | 8C | 9C
C  CC | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9
C
 digito digito*
digito  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Especificação
• Análise Léxica – expressões regulares
• Análise Sintática – gramáticas livre de contexto.
• Análise Semântica – sistema de tipos (regras de
inferência), semântica denotacional, semântica
operacional, semântica de ações.
• Geração/Otimização de Código – linguagens
para descrição de arquiteturas.
Linguagens Regulares
• Gerada a partir de uma gramática regular.
• Pode ser representada através de uma
expressão regular.
• Pode ser reconhecida por um Autômato Finito.
• Considerando linguagens compostas por
símbolos 0 e 1 podemos afirmar:
a linguagem L01 ={0n1n| n  1} não é regular;
a linguagem L01 ={0n1m | n  1, m  1} é regular;
Expressões Regulares
Maneira compacta de representar linguagens
regulares. É composta de 3 operações, sendo e1 e
e2 expressões geradas por duas linguagens
regulares L1 e L2 respectivamente
• Concatenação: e1e2 = { xy | x  L1 e y  L2}
• Alternação:
e1|e2 = { x | x  L1 ou x  L2}
• Fechamento: e1* = zero ou mais ocorrências de e1.
É definida a precedência desses operadores como sendo: fechamento,
concatenação, alternação (da maior precedência para a menor).
Expressões Regulares
Exemplos:
identificador  (letra | _) (letra | digito | _)*
letra  a | b | ... | A | B | ...
digito  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
constInt  digito digito*
constDouble  digito digito*.digito* | . digito digito*
Autômato Finito
A linguagem gerada por uma gramática regular
pode ser reconhecida por um autômato finito.
Um autômato finito consiste em:
1. Um conjunto finito de estados.
2. Um conjunto finito de símbolos de entrada (alfabeto).
3. Uma função de transição que tem como argumentos um
estado e um símbolo de entrada e retorna a um estado.
4. Um estado inicial.
5. Um conjunto de estados finais também chamados
estados de aceitação.
Autômato Finito
letra | digito | _
letra | _
letra | digito | _
letra | _
.
digito
digito
digito
digito
.
Autômato Finito
letra | digito | _
letra | _
AFN – Autômato Finito Não Determinista
f
r
o
letra | digito | _
letra | _
ld
AFD – Autômato Finito Determinista
ld
ld
f
o
r
Onde ld representa letra | digito | _
(com exceção da letra que faz a
transição para outro estado).
Autômato Finito
Implementação
letra | digito | _
letra | _
0
digito
digito
2
1
Geradores de Analisadores
Léxicos
delim
[ \t]
ws
{delim}+
letra
[A-Za-z]
digito [0-9]
id
{letra}({letra}|{digito})*
int
{digito}+
real
{digito}+\.{digito}*(E[+-]?{digito}+)?
char
'{letra}'
string '({letra}|{digito}|[ \t\\:])*'
%%
{char} {yylval.ptr=insereTab(&TabSimb[0], yytext);return TCCHARACTER;}
{string} {yylval.ptr=insereTab(&TabSimb[0], yytext);return TCSTRING;}
\n
{num_linhas++;}
FUNCTION {return TFUNCTION;}
INTEGER {return TINTEGER;}
ARRAY
{return TARRAY;}
IF
{return TIF;}
{id}
{yylval.ptr=instalar(yytext); return TID;}
"<"
{return TMENOR;}
Análise Léxica - Exercícios
1. Escreva uma gramática, expressão regular e AFD
que defina os números binários terminados em
zero.
2. Mostre uma expressão regular e o AFD
correspondente a gramática abaixo:
S  aS
B  bC C  aC
| aB
|a
3. Escreva uma expressão regular para as constantes
double da linguagem C.
Dica pode-se usar o símbolo  para indicar uma
“cadeia” vazia.