CompiladoresProf. Srgio de Barros Pinto
ltima atualizao: 10/09/2010
1
Compiladores - Tpicos-Linguagens e suas representaes -
Linguagens; - Gramticas; - Representao BNF; -Grafos sintticos; e -
rvores de anlise sinttica (rvores de derivao) - Arvores sintticas
(rvores reduzidas de anlise sinttica) -Compiladores - Traduo de
linguagens de programao - Analise lxica; - Analise sinttica; -
Traduo dirigida por sintaxe; - Gerao de cdigo intermedirio; -
Otimizao de cdigo; - Gerncia de memria; 2 - Gerao de cdigo
objeto;
Linguagens e Suas Representaes
3
O Problema da Torre de Babel
4
Torre de Babela) Cdigo de Mquina do Processador Motorola MC
68000 23FC 0000 0CB9 0000 6E0C 06B9 0000 06E8 0001 0000 0040 000A
0000 0040 0001 0000 0040
b) Linguagem de Montador (Assembly) do Processador MC 68000
#0X1,N COMPARE:CMPL #0XA,N BGT END_OF_LOOP ADDL #0X1,N BRA COMPARE
END_OF_LOOP: MOVL
5
Torre de Babelc) Linguagem FORTRAN 2 DO 2 N=1,10 CONTINUE
d) Linguagem COBOL MOVE 1 TO N. AGAIN. IF N IS EQUAL TO 10 GOTO
END_DEMO. ADD 1 TO N. END_DEMO.6
Torre de Babele) Linguagem C For (N=1; N ::= alfa | beta | gama
onde ::= significa definido como | significa ou < >
identifica os smbolos no-terminais da linguagem16
Estrutura Sinttica de Uma Linguagem Formalismo de Backus Naur
(BNF)Exemplo: < atribuio > ::= < identificador > = <
expresso > ; < expresso > ::= < termo > | <
expresso > + < termo > < termo > ::= <
identificador > | < termo > * < identificador > <
identificador> ::= A | B | C | D As sentenas geradas a partir
desse conjunto de produes uma sentena vlida da linguagem.
17
Estrutura Sinttica de Uma Linguagem Formalismo de Backus Naur
(BNF)Exemplo de obteno de sentenas vlidas: < identificador >
= < expresso > ; A = < expresso > ; A = < expresso
> + < termo > ; A = < termo > + < termo > ; A
= < termo > + < termo > + < identificador >; A =
< termo > + < termo > + D; A = < identificador >
+ < termo > + D ; A = B + < termo > + D ; A = B + <
identificador > + D ; A = B+ C + D; Portanto: A = B + C + D ,
uma sentena da linguagem.18
Exerccios
Dada a gramtica: G1 = (V1, 1, P1, S1) V1 = { A, B, 0, 1} 1 = {0,
1} P1 = { A 0A, A B, B 1B, B } S1 = A Provar que as sentenas abaixo
so sentenas vlidas da gramtica: a) 111001 b) 011111 c) 000001 d)
00011
19
Exerccios - Resultadosa) 111001 Obteno da Sentena : A B
aplicando B 1B A 1B B 1B A 11B B 1B A 111B Como no existe produo
que partindo de B nos permita obter o valor zero, a sentena no
vlida para a gramtica em questo. b) 011111 Obteno da Sentena : A 0A
aplicando A 1B A 01B B 1B A 011B B 1B A 0111B B 1B A 01111B B 1B A
011111B B A 011111 c.q.d.
20
c) 000001 Obteno da Sentena : A 0A aplicando A 0A A 00A A 0A A
000A A 0A A 0000A A 0A A 00000A A B A 00000B B 1B A 000001B B A
000001 c.q.d. d) 00011 Obteno da Sentena : A 0A aplicando A 0A A
00A A 0A A 000A A B A 000B B 1B A 0001B B 1B A 00011B B A 00011
c.q.d.
Exerccios - Resultados
21
ExerccioVerifique se a sentena begin A:= B + C ; B := C end
pertence linguagem definida pela gramtica abaixo: < programa
> ::= begin < lista de declaraes > end < lista de
declaraes > ::= < declarao > | < declarao > ; <
lista de declaraes > < declarao > ::= < varivel > :=
< expresso > < varivel > ::= A | B | C < expresso
> ::= < varivel > + < varivel > | < varivel >
- < varivel > | < varivel >22
Exerccio - ResultadoVerifique se a sentena begin A:= B + C ; B
:= C end ::= begin < lista de declaraes > end begin <
lista de declaraes > end begin < declarao > ; < lista
de declaraes > end begin < varivel > := < expresso >
; < lista de declaraes > end begin A := < expresso > ;
< lista de declaraes > end begin A := < varivel > +
< varivel > ; < lista de declaraes > end begin A := B +
< varivel > ; < lista de declaraes > end begin A := B +
C ; < lista de declaraes > end begin A := B + C ; <
declarao > end begin A := B + C ; < varivel > := <
expresso > end begin A := B + C ; B := < expresso > end
begin A := B + C ; B := < varivel > end begin A := B + C ; B
:= C end c.q.d 23
Notao BNF Estendida (EBNF)Notao BNF normal < expresso >
::= < varivel > + < expresso > | < varivel > -
< expresso > | < varivel > Notao BNF estendida <
expresso > ::= < varivel > { [+, - ] < varivel > }*
onde [ ] indica que os smbolos internos so opcionais; e { }* indica
um fechamento transitivo de concatenao24
Grafo Sinttico uma maneira grfica de representar as regras
sintticas de uma linguagem na forma EBNF. < programa > ::=
begin < lista de declaraes > end begin lista de declarao
end
< lista de declaraes > ::= < declarao > | <
declarao > ; < lista de declaraes > < lista de
declaraes > declarao ;25
Grafo Sinttico
< declarao > ::= < varivel > := < expresso >
< declarao > varivel := expresso
< varivel > ::= A | B | C < varivel > A B C26
Grafo Sinttico
< expresso > ::= < varivel > + < varivel > |
< varivel > - < varivel > | < varivel > <
expresso > varivel varivel varivel27
+ -
varivel varivel
Regras de Construo do Grafo Sinttico
28
Regras de Construo do Grafo Sinttico - Exerccio Dada a gramtica
abaixo, desenhar o grafo sinttico correspondente: < programa
> ::= program < declarao >* end < declarao > ::=
< atribuio > | < lao > < atribuio > ::= <
identificador > := < expresso > ; < lao > ::= while
< expresso lgica > do < declarao >+ done < expresso
> ::= < valor > | < valor > + < valor > | <
valor > - < valor > | < valor > * < valor > |
< valor > / < valor > < expresso lgica > ::= <
valor > = < valor > | < valor > > < valor >
| < valor > < < valor > < valor > ::= <
identificador > | < nmeros > < identificador > ::= {
a,b,c,..., z }+ < nmeros > ::= { 0,1,2,..., 9 }+29
- Exerccio ( Soluo ) -
30
- Exerccio ( Soluo ) -
31
- Exerccio ( Soluo ) -
32
- Exerccio ( Soluo ) -
33
rvore de Anlise Sinttica ( Parse Tree)Mostra a hierarquia da
estrutura sinttica das sentenas. rvore de anlise sinttica da
sentena A:= B * ( A + C )
Gramtica < atribuio > ::= < id > := < expr >
< id > ::= A|B|C < expr > ::= < id > + < expr
> | < id > * < expr > | ( < expr > ) | < id
>34
Gramtica Ambgua a gramtica que permite mais de uma rvore de
anlise sinttica para uma mesma sentena. Gramtica ::= := ::= A|B|C
::= + | * | ( ) |
Sentena A:= B + C * A
35
rvore de Anlise Sinttica - ExerccioDada a gramtica abaixo,
construir as rvores de anlise sinttica p/ as sentenas A:= B + C * A
Gramtica ::= := ::= A|B|C ::= + | ::= * | ::= ( ) | OBS: Esta uma
gramtica no ambgua para atribuies.36
e
A:= (B + C) * A
rvore de Anlise Sinttica - Soluo do Exerccio
A:= B + C * A
37
rvore de Anlise Sinttica - Soluo do Exerccio
A:= ( B + C ) * A
38
rvore de Anlise Sinttica - ExerccioDada a gramtica G1 = (V1, 1,
P1, S1) V1 = { A, B, 0, 1} 1 = {0, 1} P1 = { A 0A, A B, B 1B, B }
S1 = A Criar as rvores de anlise sinttica para as sentenas abaixo:
01111 00111 00011 00001 00000 11111 1010139
rvore de Anlise Sinttica Exerccio (continuao)01111 00111
40
rvore de Anlise Sinttica - Exerccio (continuao)00011 00001
41
rvore de Anlise Sinttica Exerccio (continuao)00000 11111
42
rvore de Anlise Sinttica Exerccio (continuao)10101
Como no existe produo que partindo de B implique na obteno de um
0, a sentena no pode ser obtida e portanto ela no uma sentena da
gramtica.
43
rvore de Anlise Sinttica ExerccioDada a gramtica abaixo,
verificar, usando rvore de anlise sinttica, se a sentena: int alfa,
beta[100]; uma sentena vlida. OBSERVAO: Uma sentena vlida quando as
folhas da rvore de anlise sinttica s contm terminadores da
gramtica. ::= ; | ; ::= | , ::= | [] ::= int | float | char <
identificador > ::= { a,b,c,..., z }+ < nmero > ::= {
0,1,2,..., 9 }+
44
rvore de Anlise Sinttica Exerccio (continuao...)
Portanto a sentena: int alfa, beta[100]; uma sentena
vlida.45
Autmatos de Estados FinitosAutmatos de estados finitos so
mquinas abstratas (modelos matemticos) capazes de reconhecer
estruturas de linguagens. Um autmato finito AF, sobre um alfabeto
A, representado por: AF = (E,e0, Ef, A, G) Onde: E um conjunto
finito denominado conjunto de estados. O conjunto E deve conter
pelo menos 1 estado. e0 o estado inicial do autmato. e0 pertence a
E. Ef o conjunto de estados finais, no vazio. Ef est contido em E.
A um conjunto finito, denominado alfabeto de entrada. G: E x A S,
denomina-se aplicao de transio e representa o mapeamento das
transies E x A. Obs: G(E, A) no precisa estar definida pra todos os
pares E, A 46 (estado, smbolo de entrada).
Autmatos de Estados FinitosUm autmato pode ser representado
atravs de grafos (ou diagramas) de estado ou de tabelas de transio
de estados. Um diagrama de estado usa a seguinte simbologia:
A mudana de um estado Sn-1 para um estado Sn, ocasionada por uma
entrada e, representada por:
47
Autmatos de Estados FinitosExemplo: Dado o autmato AF =
({S0,S1}, S0, {S1}, {0, 1}, G) Com as seguintes transies de estado
definidas em: g(S0, 0)=S0; g(S0, 1)=S1; g(S1, 0) = S0; g(S1, 1)=S1;
Ento o diagrama de estados correspondente dado por:
48
Autmatos de Estados FinitosUma tabela de transio de estados tem
a seguinte representao g(S0, 0)=S0; g(S0, 1)=S1; g(S1, 0) = S0;
g(S1, 1)=S1; Ento o diagrama de estados correspondente dado
por:
O primeiro estado na coluna de estados e o estado inicial.
49
Autmatos de Estados FinitosTabela de transio de estados para o
autmato do exemplo anterior:
Onde: S0 o estado inicial (primeira posio na coluna de estados);
S1 o estado final (valor 1 na coluna de indicao de estados final e
no-final) A leitura da tabela se d da seguinte forma: Na linha 1:
estando o autmato no estado S0: ao receber uma entrada 0 ele
continua no estado S0; ao receber uma entrada 1 ele passa ao estado
S1. Na linha 2: estando o autmato no estado S1: ao receber uma
entrada 0 ele passa ao estado S0; ao receber uma entrada 1 ele
continua no estado S .
50
Autmatos de Estados FinitosExemplo: Criar um autmato para
representar uma moeda sobre a mesa. Considere que a moeda
inicialmente exibe o lado cara. O autmato : AF = ({cara,coroa},
cara, {cara, coroa}, {virar}, G) Com as seguintes transies de
estado definidas em G: g(cara, virar) = coroa; g(coroa, virar) =
cara; Diagrama de estados:
Tabela de transio de estados:51
Autmatos de Estados FinitosExemplo: Representar a soma de n com
os nmeros -1, 0 e 1, indicando se aps a soma o nmero resultante par
ou impar. Considere que inicialmente n = 0. O autmato AF =
({par,impar}, par, {par, impar}, {-1, 0, 1}, G) Com as seguintes
transies de estado definidas em G: g(par, -1) = impar; g(par, 0) =
par; g(par, 1) = impar; g(impar, -1) = par; g(impar, 0) = impar;
g(impar, 1) = par;
Tabela de transio de estados Diagrama de estados52
Autmatos de Estados FinitosDizemos que uma cadeia de smbolos k =
k1k2...kn, com n 0, reconhecida por um autmato finito AF, quando a
execuo do algoritmo abaixo deixa o autmato em um estado
final:Incio_Algoritmo e = estado_Inicial; i = 1; Enquanto no chegar
ao final da cadeia k Ler o smbolo k[i] da cadeia k; e = Aplicar a
Transio (e, k[i])); i = i + 1; Fim_Enquanto Se e for um
estado_Final A cadeia foi reconhecida; Seno A cadeia no foi
reconhecida; Fim_Se Fim_Algoritmo
53
Autmatos de Estados FinitosExemplo: Dado o autmato
A)O mesmo reconhece as cadeias de zeros e uns terminadas em 1
como 11001011:
B) O mesmo no reconhece as cadeias de zeros e uns terminadas em
0 como 11001010:54
Autmatos de Estados FinitosExemplo: Dado o autmato AF = ({S0,
S1, S2, S3}, S0, {S0}, {0,1}, G) com G: g(S0,0) = S2 g(S1,0) = S3
g(S2,0) = S0 g(S3,0) = S1 g(S0,1) = S1 g(S1,1) = S0 g(S2,1) = S3
g(S3,1) = S2 Este autmato reconhece cadeias cadeias com quantidades
pares de zeros e uns como: 0011 000011 101000 0101010001
1110001055
Autmatos como Reconhecedores de SentenasDada a gramtica abaixo,
::= ; | ; ::= | , ::= | [] ::= int | float | char <
identificador > ::= { a,b,c,..., z }+ < nmero > ::= {
0,1,2,..., 9 }+ Desenhar uma mquina de estado (autmato) para
reconhecer sentenas do tipo: int alfa, beta, gama; char letra,
palavra[10]; float delta[20], omega;56
Autmatos como Reconhecedores de Sentenas1: Crie a lista de
cdigos de tokens Token Cdigo ; 1 , 2 [ 3 ] 4 int 5 float 6 char 7
id 8 (identificador) num 9 (nmero) 2: Considerando cada cdigo como
sendo um estado, defina os estados finais. Os estados finais so os
elementos finalizadores de uma sentena vlida. Neste caso, ; e
portanto o estado final 1
57
Autmatos como Reconhecedores de Sentenas3: Com base na gramtica
e nos estados identifique as transies.
Transies: g(0, int) = 5 g(5, id) = 8 g(8, ,) = 2 g(8, [) = 3
g(4, ,) = 2
g(0, float) = 6 g(0, char) = 7 g(6, id) = 8g(7, id) = 8 g(2, id)
= 8 g(8, ;) = 1 g(3, num) = 9 g(9, ]) = 4 g(4, ;) = 1
58
Autmatos como Reconhecedores de Sentenas4: Com base nas
transies, crie a tabela de transio de estados: g(0, int) = 5 g(0,
float) = 6 g(0, char) = 7 g(5, id) = 8 g(6, id) = 8 g(7, id) = 8
g(8, ,) = 2 g(2, id) = 8 g(8, ;) = 1 g(8, [) = 3 g(3, num) = 9 g(9,
]) = 4 g(4, ,) = 2 g(4, ;) = 1
Observao: Transies no previstas levam a um estado de erro.
59
Autmatos como Reconhecedores de Sentenas5: Otimize a tabela de
transio de estados: Os estados 2, 5, 6 e 7 sofrem uma transio para
8 na presena de id e transio para E na presena dos demais smbolos
da gramtica.
60
Autmatos como Reconhecedores de SentenasPortanto, a tabela de
transio de estados poderia ser simplificada para:
E as novas transies seriam: g(0, int) = x g(0, float) = x g(0,
char) = x g(8, ,) = x g(x, id) = 8g(8, ;) = 1 g(8, [) = 3 g(3, num)
= 9 g(9, ]) = 4 g(4, ,) = x g(4, ;) = 1
g(x, id) = 8
61
Autmatos como Reconhecedores de Sentenas6: Construir o
autmato:
As transies para o estado de erro no esto desenhadas
62
Autmatos Como Reconhecedores de SentenasDizemos que uma sentena
S, formada pelas palavras (smbolos) da gramtica (ou linguagem) L,
reconhecida por um autmato finito AF, quando a execuo do algoritmo
abaixo deixa o autmato em um estado final:Incio_Algoritmo e =
estado Inicial; Posicionar ponteiro de leitura no incio da primeira
palavra; Enquanto no chegar ao final da sentena S Ler a palavra p
da sentena S; e = Aplicar a Transio (e, p); Posicionar ponteiro de
leitura no incio da prxima palavra; Fim_Enquanto Se e for um
estado_Final A sentena foi reconhecida; Seno A sentena no foi
reconhecida; Fim_Se Fim_Algoritmo
63
Compiladores - IntroduoO compilador um software de sistema cujo
papel traduzir programas em linguagens de alto nvel (programa
fonte), para linguagens de mquina (programa objeto).
O processo de traduo envolve duas tarefas bsicas: Anlise: o
texto de na linguagem fonte avaliado e os erros so identificados, e
Sntese: em que a sada em linguagem objeto gerado.64
Compiladores - IntroduoA tarefa de anlise dependente da
linguagem fonte a ser traduzida (C, Pascal, C++, etc). A tarefa de
sntese tem uma ligao estreita c/ o hardware e dependente da
linguagem de mquina. Para manter uma independncia entre as duas
fases, um cdigo intermedirio gerado pela tarefa de anlise.
65
Compiladores - FasesAs tarefas de anlise e sntese podem ser
subdivididas nas seguintes fases: Anlise lxica Anlise sinttica
Anlise Anlise semntica Gerao de cdigo intermedirio Otimizao de
cdigo Sntese Gerao de cdigo objeto E o compilador pode ser visto
como sendo formado por um conjunto de componentes, de modo que cada
fase seja executada por um componente.
66
Compiladores - ComponentesPortanto, um compilador seria
constitudo pelos seguintes componentes: Analisador lxico Analisador
sinttico Analisador semntico Gerador de cdigo intermedirio
Otimizador de cdigo Gerador de cdigo objeto Alm dos componentes
acima, o compilador tambm possui um gerenciador da tabela de
smbolos. A tabela de smbolos uma estrutura de dados contendo um
registro para cada nome de varivel, com campos para os atributos
desse nome, como por exemplo: tipo, escopo, 67 endereo.
Anlise LxicaA anlise lxica, tambm chamada de varredura, feita
pelo analisador lxico. O analisador l cada caractere que compe o
programa fonte agrupando-os em sequncias chamadas lexemas ou marcas
(tokens, em ingls). Cada lexema representa uma unidade de informao
do programa fonte. So exemplos de lexemas: Palavras reservadas: if,
for, while, else, char. Identificadores: nomes de variveis e de
constantes. Smbolos especiais: + - * / Valores numricos: 100 5.67
-76 A anlise lxica usa autmatos finitos para reconhecer os
lexemas.68
Anlise Lxica (continuao...)A anlise lxica ocorre por demanda do
analisador sinttico. O analisador sinttico solicita, ao analisador
lxico, a leitura do prximo lexema atravs da chamada de uma funo do
tipo: tipoToken GetNextToken(); Os lexemas podem ser declarados
como um tipo enumerado: typedef enum { IF, ELSE, WHILE, FOR, ....}
tipoToken; A funo GetNextToken() deve retornar o tipo do prximo
lexema de uma linha de cdigo, como por exemplo: Os tipos retornados
poderiam ser: TIPO, ID, VG, ID, ACOL, NUM, FCOL, PTVG Durante a
anlise lxica, alm do tipo do lexema, alguns analisadores tambm
retornam a sua posio na linha. 69
A Linguagem C- (SEMENOS) ::= ::= | ::= | ::= ID; | ID [ NUM ];
::= int | ::= int | void ::= ID () ::= | void ::= , | ::= ID | ID [
] ::= { } ::= | ::= | 70
A Linguagem C- (SEMENOS) (Continuao) ::= | | | ::= ; | ; ::= if
(
