Upload
internet
View
104
Download
0
Embed Size (px)
Citation preview
Construção de compiladores i
Linguagem de Prog. e Programas
• Em qualquer ling. de programação, é necessário conhecer: – estruturas de dados permitidas– como mexer com partes do programa, sem alterar
todo o resto;– os elementos de controle que identificam as
estruturas, tais como: loop etc;– como implementar subrotinas.
Construção de compiladores i
Linguagens e o Compilador
Lf = ling. fonte; Lm= ling. máquina; L0 = Ling. objeto.
Construção de compiladores i
No compilador: 3 linguagens:
- linguagem fonte;
- linguagem objeto;
- linguagem na qual o compilador foi escrito.
Linguagens e o Compilador
Cxy
z
- escrito para a linguagem x;
- escrito na linguagem z
- código objeto na linguagem y
Construção de compiladores i
Linguagens e o Compilador
CCCla
a
sa
a
la
s
CCClb
a
la
a
lb
a
Construção de compiladores i
Em geral, Lf é uma linguagem de alto nível como ALGOL, COBOL, PASCAL, etc. Lo não é necessariamente uma linguagem de máquina, podendo ser uma Linguagem de Montagem ("Assembler") La.
Nesse caso, é necessário ter-se mais uma fase de tradução de La para a linguagem de máquina Lm do computador a ser utilizado
para processar o programa objeto:
Linguagens e o Compilador
Construção de compiladores i
Est. Hierárquica de uma L.P.
Construção de compiladores i
Análise Léxica
Analisador Léxico:Analisador Léxico:1ª fase de um compiladorlê os caracteres de entrada e produz uma sequência de
símbolos léxicos válidos (tokens)pode ser implementado como uma subrotina do parser ou
uma co-rotina do parser;executa tarefas secundárias, como:
remover comentários; remover espaços em branco controlar posição dos elementos, visando mensagens de
erros ao programador
Construção de compiladores i
Análise Léxica
TokensTokens::Elementos dados: elementos básicos de qualquer ling. de
programação:numéricos: inteiros, reais, complexos etclógicos: true, falsecaracteres: “C”, “a”, “casa”ponteiros
Identificadores / nomes: variáveis dos procedimentos,
associadas a um dado nome:
Nomevalor
atributo
Construção de compiladores i
Análise Léxica
TokensTokens::Estruturas de dados
arraysrecordlistaspilhas
Operadores aritméticos:Unários:
pré-fixadospós-fixados
Binários
Construção de compiladores i
Reconhecimento de TokensDiagramas de Transição:Diagramas de Transição:
- passo intermediário;- apresentam ações executadas pelo Analisador Léxico;- controla as informações a respeito de caracteres que são examinados, com a leitura do arquivo fonte.
Elementos dos Diagramas: Elementos dos Diagramas: - estados: posições no diagrama;- lados: setas que conectam os estados;- rótulos: indicam os caracteres de entrada que podem aparecer após atingir-se um dado estado;
ObsObs: Chamamos o diagrama de determinístico quando o mesmo símbolo não figura como rótulo de lados diferentes que deixem um mesmo estado.
Construção de compiladores i
Diagramas de TransiçãoSupondo a que um número real possa ser dado por:
<sinal><parte_inteira>.<parte_fracionária>E<expoente>
Construção de compiladores i
Diagramas de Transição
Para reconhecimento de identificadores:
Construção de compiladores i
Autômatos FinitosOs símbolos que deverão ser reconhecidos na análise léxica são representáveis por expressões regulares (ou equivalentemente por gramáticas regulares).
Há uma correspondência unívoca entre expressões (ou gramáticas) regulares e autômatos finitos.
Autômatos FinitosAutômatos Finitos: máquinas que podem ser utilizadas para reconhecer strings de uma dada linguagem. Autômatos Finitos são compostos por:
um conjunto de estados, alguns dos quais são denominados estados finais. À medida que caracteres da string de entrada são lidos, o controle da máquina passa de um estado a outro;
um conjunto de regras de transição entre os estados.
Construção de compiladores i
Autômatos FinitosFormalmente, um autômato é descrito por cinco características:Formalmente, um autômato é descrito por cinco características:
- um conjunto finito de estados;
- um alfabeto de entrada finito;
- um conjunto de transições;
- um estado inicial;
- um conjunto de estados finais.
Quando, partindo de um estado inicial, varrendo a sentença dada (de acordo com as regras de transições), consegue-se atingir um estado final, a sentença dada é parte da linguagem.
Construção de compiladores i
Autômatos Finitos
Forma Gráfica de Representação de um Autômato Finito:
Construção de compiladores i
Autômatos Finitos
a b c
A B B C
B C B -
C A - D
D - - -
Forma Tabular de Representação do mesmo Autômato Finito:
Construção de compiladores i
Autômatos Finitos não-determínisticos
Um Autômato de Estados Finito não-deterministico é:
- aquele em que pode ocorrer a transição vazia (aquela em que o
autômato pode passar de um estado a outro sem que ocorra a
entrada de um caracter do string);
- aquele onde podem ocorrer indeterminações na ação, isto é,
determinados estados podem ter mais do que uma transição
possível para um dado caracter.
Construção de compiladores i
Autômatos Finitos não-determínisticosExemplo: Reconhecimento da linguagem (a|b)*abb:
Estado Símbolo de Entrada
a b
0 {0,1} {0}
1 {2}
2 {3}