Tabela de Smbolos
Tabela de Smbolos Funes:
- Armazenar as informaes sobre os nomes declarados num programa podendo ser:
o Variveiso Constanteso Procedimentoso Funeso Mtodoso Classeso Entre outros
o Em alguns casos so registrados tambm inicio e fim de laos, selees, etc..
Tabela de Smbolos - Usada, pelo analisador semntico, para
verificar se uma varivel foi declarada, naverificao de compatibilidade de tipos, entre outras consultas que forem necessrias.
- Pode ser usada para armazenar os valores das variveis durante a execuo do programa
- Utilizado no ambiente de debug
Por ser muito utilizada em consultas, importante que a estrutura de dados tenha uma performance considervel.
Tambm necessrio o crescimento dinmico de tal estrutura de dados
- Por isso uma boa escolha a tabela hashing Devem ser guardados quais endereos de
memria sero associados as variveis- Pode ser utilizada o atributo referncia na classe
Simbolo para essa utilidade
Tabela de Smbolos
Escopo: Um programa pode ter vrias tabelas de smbolos
dando assim o escopo para os smbolos. Alguns exemplos:
o Tabela de Smbolos globais (externos)o Tabela de Smbolos globais (internos ao mdulo)o Tabela de Smbolos de uma funo
Cada funo tem a sua prpria tabela de smbolos
Tabela de Smbolos
Tabela de SmbolosUtilizando a Tabela de Smbolos:
- As informaes armazenadas para cada smbolo podem variar de acordo com o tipo/uso - Cada entrada na tabela pode ser implementada como um registro contendo campos (nome, tipo, classe, tamanho, escopo, etc.) sobre o smbolo.- Cria-se a classe Smbolo.- Cria-se a classe Tabela (Tabela de Smbolos).- A interao se dar por aes semnticas inseridas no analisador sinttico, na classe principal do compilador.
Tabela de Smbolos
A tabela se smbolos interage com quase todas as fases do compilador: varredura, anlise sinttica e anlise semntica.
- Elas podem fornecer identificadores a tabela-O analisador semntico interage com os tipos de
dados e outras informaes -As fases de otimizao e gerao de cdigo utilizam
a informao da tabela para efetuar escolhas apropriadas
Ex. Tabela de Smbolos
Tabela de Smbolos
Exerccio Definir a Estrutura da Tabela da sua linguagem
Apresentar na Prxima Aula em Slide Considerar Variveis, funes, Mtodos,
Classes e Mtodos etc... Escopo para 0 programa principal, 1 funes,
Mtodos, Classes e Mtodos etc..., 2 outras funes, Mtodos, Classes e Mtodos etc.. Uma Dentro da outra
Linha de declarao, linhas de utilizao e
Compilador Preparao
Programa que l um programa escrito emuma linguagem (fonte) e o traduz para umaoutra linguagem (destino), reportando errosquando eles ocorrem.
Linguagens
Linguagem fonte: C, Pascal, Java, Fortran, etc.
Linguagem destino: linguagem de mquina(assembler) de um processador, de umamquina virtual (e.g. Java ou .NET), ouqualquer outra linguagem (e.g. C).
Compilador
Programa fonte
Programa destino
Processadores de Linguagens: Compilador
Programadestinoentrada sada
Execuo de um programa
InterpretadorPrograma fonte
sada
Processadores de Linguagens: Interpretador
entrada
MquinaVirtual
Programa intermediriosada
Compilador Hbrido
entrada
Tradutor
Programa fonte
compilador
preprocessador assembler
Linker /Loader
Programa fonte
Programa fontemodificado
Programa em assembler
Cdigo objeto (relocvel)
Cdigo objeto (executvel)
Bibliotecas /cdigo objeto
Sistema de processamentode uma linguagem
Programas auxiliares do processode compilao
Preprocessadores: processam macros, incluem de arquivos, suportam compilaocondicional e extenso de linguagens.
Assemblers: servem como uma pequenaabstrao da arquitetura da mquina-destino. So na realidade um tradutor/compilador simples, de dois passos, quegera cdigo relocvel.
Programas auxiliares do processode compilao (cont.)
Carregadores (loaders) e linkeditores(linkers) Ajustam o cdigo relocvel, resolvem
referncias externas.
Compilao: Anlise e Sntese
Anlise: quebra o cdigo fonte em suaspartes, e cria uma representaointermediria do programa.Verifica erros e constri tabela de smbolos.
Sntese: Constroi o programa-destino a partir da representao intermediria.
Fases de um compilador
Analisador lxico
stream de caracteres
Cdigo de mquina
Analisador sinttico
Analisador semntico
Ger. de cdigo intermedirio
Otimizador de cdigo
Gerador de cdigo
stream de tokens
rvore sinttica
rvore sinttica
representao intermediria
representao intermediria
Anlise: front-end do compilador(at gerao de cdigo intermedirio)
Sntese: back-end do compilador
Anlise do programa fonte
Anlise lxica l a seqencia de caracteres e a organiza como tokens sequencias de caracterescom algum significado
Anlise sinttica agrupa caracteres ou tokens emuma estrutura hierrquica com algum significado
Anlise semntica verifica se os componentes de um programa se encaixam de forma a ter um significado adequado.
Programas baseados em anlise
Editores de programa dirigidos sintaxe(comuns nos IDEs, como no Eclipse e Visual Studio)
Pretty-printers Interpretadores
Anlise lxica ou Scanning
L os caracteres de entrada e agrupa-os emsequencias chamadas lexemas.
Para cada lexema o analisador lxico produz comosada um token da forma
que passado para a fase seguinte.
Exemplo
position = initial + rate * 60
Tabela de Smbolos
identificador tipo
1 position
2 initial
3 rate
Anlise sinttica ou parsing
A partir dos tokens cria uma estrutura emrvore (rvore sinttica) que representa a estrutura gramatical do programa.
rvore Sinttica position = initial + rate * 60
*
+
=
60
Anlise semntica
Verifica o programa em relao a possveiserros semnticos e guarda informaesadicionais
Exemplo: verificao de tipos
A expresso
x = x + 3.0
est sintaticamente correta, mas pode estarsemanticamente certa ou errada, dependendo do tipo de x.
Anlise Semntica
*
+
=
60
inttofloat
Cdigo intermedirio
Idealmente deve ser fcil de produzir e tambm de traduzir para a linguagem-destino.
Na prtica, se est gerando cdigo para umamquina abstrata.
Por exemplo, Three-address-code: usa trsoperandos por instruo, cada um como se fosse um registrador.
Cdigo intermedirio - exemplo
t1 = inttofloat(60)t2 = id3 * t1t3 = id2 + t2id1 = t3
Otimizao de cdigo
Realiza transformaes no cdigo visandomelhorar sua performance em aspectos de tempo de execuo, uso de memria, tamanho do cdigo executvel etc.
Otimizao de cdigo - exemplo
t1 = inttofloat(60)t2 = id3 * t1t3 = id2 + t2id1 = t3
t2 = id3 * 60.0id1 = id2 + t2
Gerao de cdigo
Realiza a alocao de registradores (se necessria) e a traduo do cdigointermedirio para a linguagem-destino.
Gerao de cdigo
LDF R2, id3MULF R2, R2, #60.0LDF R1, id2ADDF R1, R1, R2STF id1, R1
Tabela de Smbolos
Estrutura de dados usada para guardaridentificadores e informaes sobre eles: alocao de memria, tipo do identificador, escopo (onde vlido no programa) se for um procedimento ou funo: nmero e
tipo dos argumentos, forma de passagem dos parmetros e tipo do resultado.
Tabela de Smbolos
identificador tipo
1 position
2 initial
3 rate
Organizando fases em passos
Fases: viso lgica de um compilador Em uma implementao as fases podem ser
agrupadas em um ou mais passos Passos: nmero de vezes em que se passa
pelo mesmo cdigo. Por exemplo, em um assembler so
necessrios pelo menos dois passos.
Cx86
Front-end
Separao entre front-end e back-end para criao de mltiplos compiladores
cdigointermedirio
cdigointermedirio
Back-end
Front-endFront-end
Front-end
C#Pascal Fortran
Pascal
x86
Front-end
ARM
Separao entre front-end e back-end para criao de mltiplos compiladores
cdigointermedirio
cdigointermedirio
MIPS
.NET
Back-end Back-end
Back-end Back-end
Cx86
Front-end
ARM
Separao entre front-end e back-end para criao de mltiplos compiladores
cdigointermedirio
cdigointermedirio
MIPS
.NET
Back-end Back-end
Back-end Back-end
Front-endFront-end
Front-end
C#Pascal Fortran
Ferramentas auxiliares para a construo de compiladores
Scanner generators, baseados em expressesregulares. Exemplo: lex
Parser generators, baseados em gramticas livresde contexto. Exemplo: yacc
Engenhos de traduo dirigida por sintaxe, geramrotinas para navegar na parse tree e gerar cdigointermedirio
Geradores de geradores de cdigo (template matching)
Toolkits de construo de compiladores
Contexto Histrico
Demanda por linguagens de mais alto nvel quelinguagem de mquina e assembler.
Nos anos 1950, compiladores eram programasnotadamente difceis de se escrever.
Avano terico e de tcnicas e ferramentas de implementao tornaram possvel implementarcompiladores muito mais facilmente.
Classificaes: Geraes
Linguagens de mquina Linguagens de montagem (Assembly languages) Fortran, Cobol, Lisp, C, C++, C#, Java
(Linguagens de Proposito Geral) SQL, Postscript (Domain Specific Languages)
First Program Mark 1 (Computation)
000 CI = S001 A = A - S010 A = - S011 If A < 0, CI = CI + 1100 CI = CI + S101 A = A S110 S = A111 HALT
Classificaes: Paradigma Imperativo
como = programador diz o que vai ser executado Conceito de estado e comandos que mudam o
estado = computaes que alteram variveis! C, C++, C#, Java
Declarativo o qu = Insere Regras, Dados e faz Consultas ML, Haskell, Prolog
Classificaes - Evolues
Von Neumann(1940s): C, Fortran, Pascal (Define variveis e faz transformaes em seus valores emunico programa com chamada de subprogramas, salvaapenas os dados, execuo local)
Orientadas a Objetos(1960s): Simula 67, Smalltalk, C++, C#, Java, Ruby (instnciar objetos e mant-los ativos, salvando dados e programas=classes, instalao local e execuo pode ser distribuida)
Scripting Languages(1980s): Awk, JavaScript, Perl, PHP, Python, Ruby, Tcl (regras de execuo a sereminterpretadas, conceito de execuo distribuda)
Fundamentos de Linguagens de Programao
Esttico x Dinmico: Esttico: em tempo de compilao (Cobol,
Clipper..) Dinmico: em tempo de execuo (Basic,) Java = Esttico at o Bytecode e Dinmico na
execuo do Bytecode.
Fundamentos de Linguagens de Programao
Ambientes e Estados
nomes locais(variveis)
ambiente estado
valores
Fundamentos de Linguagens de Programao
Escopo esttico e estrutura de Blocos
Controle de Acesso Explcito public, private, protected
Fundamentos de Linguagens de Programao
Escopo Dinmico Exemplo: macros em C
#define a (x+1)int x = 2;void b() {int x = 1; printf(%d\n, a); }void c() {printf(%d\n, a); }void main() { b(); c(); }
Fundamentos de Linguagens de Programao
Mecanismos de passagem de parmetro Por valor (call by value) Por referncia (call by reference) Por nome (call by name) Por necessidade (call by need)
Fundamentos de Linguagens de Programao
Sinnimos (Aliasing) Outros Mecanismos especficos do Projeto de cada
Linguagem de Programao