Construção de compiladores
34 pág.

Construção de compiladores


DisciplinaConstrução de Compilares3 materiais14 seguidores
Pré-visualização10 páginas
PDF gerado usando o pacote de ferramentas em código aberto mwlib. Veja http://code.pediapress.com/ para mais informações.
PDF generated at: Fri, 06 Dec 2013 10:27:13 UTC
Construção de compiladores
Conteúdo
Páginas
Capa 1
O que é um compilador 1
Fases de um compilador 2
Teoria das linguagens formais 2
Linguagens regulares e autômatos finitos 3
Linguagens livres de contexto 4
Análise léxica 6
Análise sintática 10
Tradução dirigida por sintaxe 18
Análise semântica 19
Geração de código intermediário 21
Otimização de código 26
Nomes dos colaboradores 29
Referências
Fontes e Editores da Página 30
Fontes, Licenças e Editores da Imagem 31
Licenças das páginas
Licença 32
Capa 1
Capa
. . Construção de compiladores
Ir para o índice
O que é um compilador
Um compilador é um tipo de tradutor que lê um programa escrito numa linguagem, a linguagem fonte, e
transforma-o em um outro programa equivalente escrito em outra linguagem, a linguagem objeto.
Existem outros tipos de tradutores sendo um deles o interpretador que, obtém um programa escrito em alguma
linguagem e o converte para código executável. A principal diferença entre um compilador e um interpretador é que
os compiladores geram códigos que podem ser executados diretamente pelo computador, enquanto que, no
interpretador o programa fonte precisa ser traduzido toda vez que for executado. Linguagem como Pascal, COBOL,
C e C++ são compiladas enquanto que linguagens como PHP, Perl, Javascript e Python são interpretadas.
Abaixo um exemplo de um programa em linguagem de alto nível e seu equivalente em linguagem de baixo nível, ou
seja, depois do processo de compilação.
Linguagem de alto nível
c = a + b;
Linguagem de baixo nível
mov ax, $a
add ax, $b
mov $c, ax
É importante notar que o programa fonte e o programa objeto são completamente diferentes, porém possuem o
mesmo significado. Além da tradução é importante destacar a tarefa do compilador na detecção de erros feitos pelo
programador, caso isso ocorra o programa objeto não é gerado e uma ou mais mensagens de erro são exibidas.
Fases de um compilador 2
Fases de um compilador
Um compilador possui várias fases que podem ser divididas em dois grupos, análise e síntese.
A análise é constituída geralmente de três fases que são, análise léxica, análise sintática e análise semântica,
enquanto que a fase de síntese é composta por módulos de geração e otimização de código.
Esta página é um esboço de informática. Ampliando-a você ajudará a melhorar o Wikilivros.
Teoria das linguagens formais
Teoria das Linguagens Formais e dos autômatos é o estudo de modelos matemáticos que possibilitam a
especificação e o reconhecimento de linguagens (no sentido amplo da palavra), suas classificações, estruturas,
propriedades, características e inter-relacionamentos.
Uma linguagem formal é um conjunto de palavras,isto é, um conjunto finito de letras ou símbolos com um conjunto
de regras para combinar estes elementos. O inventário destas letras é chamado de alfabeto na qual esta linguagem é
definida. O modo formal como uma linguagem é definida é chamada de gramática formal.
Assim, podemos dizer que "Linguagens formais" são mecanismos formais para representação e especificação de
linguagens, baseados na chamada "Teoria da Computação". As representações podem ser feitas por reconhecedores e
geradores. Os reconhecedores são dispositivos formais que servem para verificar se uma sentença pertence ou não à
determinada linguagem. São os autômatos: autômatos finitos, autômatos de pilha e Máquina de Turing. Os sistemas
geradores são dispositivos formais que permitem a geração sistemática de todas as sentenças de uma linguagem. Os
principais sistemas geradores disponíveis são as gramáticas, onde se destacam as gramáticas de Chomsky. Então,
linguagens formais podem ser representadas de maneira finita e precisa através de sistemas com sustentação
matemática.
Importância na Computação
A importância dessa teoria na Ciência da Computação é dupla: ela tanto apóia outros aspectos teóricos da Ciência da
Computação (Decibilidade, computabilidade, complexidade computacional, por exemplo), como fundamenta
diversas aplicações computacionais tais como processamento de linguagens, reconhecimento de padrões, modelagem
de sistemas.
Linguagens regulares e autômatos finitos 3
Linguagens regulares e autômatos finitos
A linguagem regular pode ser descrita por [1][2][3]:
\u2022\u2022 Autômatos finitos
\u2022\u2022 Gramáticas regulares
\u2022\u2022 Expressões regulares
Autômatos Finitos
Paradigma reconhecedor. Descrevem uma expressão regular. Podem ser classificados em:
Autômato Finito Determinístico: Representado pela quintupla ( ,Q, ,q,F) que consite em:
\u2022 : Alfabeto - Conjunto finito de símbolos de entrada
\u2022 Q: Conjunto finito de estados
\u2022 : Função de transição ( : Q x Q)
\u2022 q: Estado inicial
\u2022 F: Conjunto de estados finais
Um autômato finito determinístico aceita uma cadeia de símbolos se após um estado inicial, mudando de estados por
meio da função (que determina precisamente o próximo estado), consegue chegar à um estado final.
Regras:
\u2022\u2022 Todo estado deve conter uma e somente uma transição para cada símbolo do alfabeto.
Autômato Finito Não-Determinístico: Representado pela quintupla ( ,Q, ,q,F), onde a função de transição 
pode conduzir à múltiplos estados ou até mesmo nenhum.
Regras:
\u2022\u2022 Não é necessário uma transição para cada símbolo do alfabeto;
\u2022\u2022 Podem haver várias transições partindo de um mesmo estado na leitura de um mesmo símbolo;
\u2022\u2022 Não é necessário mapear todas as possibilidades, mas, somente o que valida a cadeia.
Gramáticas Regulares
Conhecida também como Tipo 3 da Hierarquia de Chomsky. Pode ser definida como gramática linear.
As gramáticas regulares caracterizam as linguagens regulares:
\u2022\u2022 Toda linguagem gerada por uma gramática regular é regular.
\u2022\u2022 Toda linguagem regular pode ser caracterizada por uma gramática linear a direita, e por uma gramática linear a
esquerda.
Teorema 1: Se a linguagem L pode ser gerada por uma gramática regular, então L é regular.
Teorema 2: Se a linguagem L é regular, então L pode ser gerada por uma gramática linear a esquerda e por uma
gramática linear a direita.
Linguagens regulares e autômatos finitos 4
Expressões Regulares
Definição:
Trata-se de um paradigma gerador. Um modelo que denota qualquer linguagem regular de forma mais simples,
verificando o conjunto de cadeias de símbolos permitidos na linguagem.
Aplicação:
\u2022\u2022 Sistemas de pesquisa de texto, geradores de analisadores léxicos.
\u2022\u2022 Algoritmos de reconhecimento de pouca complexidade, grande eficiência e de fácil implementação.
\u2022\u2022 Sistemas operacionais, protocolos, editores, compiladores.
Referências
[1] Roberto Claudino da Silva - http:/ / www. claudino. unifei. edu. br/
[2] José Lucas Rangel - http:/ / www. inf. puc-rio. br/ ~inf1302/
[3] http:/ / teia. inf. ufrgs. br/ cgi-bin/ moore. pl?curso=LivroAnimado& estado=281
Linguagens livres de contexto
Na teoria de linguagens formais, uma linguagem livre de contexto é uma linguagem gerada por alguma gramática
livre de contexto. O conjunto de todas as linguagens livres de contexto é idêntico ao conjunto de linguagens aceitas
por um autômato de pilha. De acordo com a Hierarquia de Chomsky, linguagens livres de contexto são Tipo-2.
As gramáticas livres de contexto são da seguinte forma:
V -> w
de modo que V é um símbolo não-terminal e w é uma cadeia composta de terminais e/ou de não-terminais. O termo
'livre de contexto' vem da idéia de que um não-terminal V sempre pode ser trocado por w, sem precisar entender seu
contexto.
Um exemplo que facilita a compreensão do que são linguagens livres de contexto é a frase:
\u2022\u2022 1. "Fui à biblioteca hoje."
a palavra "biblioteca" independente da frase indica todo espaço (concreto, virtual ou híbrido) destinado a uma
coleção de informações de quaisquer tipos, sejam