Compiladores da teoria à prática

Visualizações: 257
Classificação: (0)

Compiladores da teoria à prática é voltado para estudantes de nível universitário e profissional, desenvolvedores de software, programadores e usuários em geral que necessitem compreender como o compilador converte em códigos executáveis programas descritos por linguagens de alto nível. Apresenta o compilador como ferramenta determinante no desempenho das aplicações e explica a interligação entre linguagens, processadores, arquiteturas e sistemas operacionais.
O livro aborda os diferentes passos do desenvolvimento de um compilador, como a análise determinista linear com autômatos finitos, para linguagens regulares, e autômatos de pilha, para uma análise ascendente e descendente; a realização de verificações semânticas e a construção da árvore sintática do programa analisado; e a linearização das instruções para a geração de código direto para máquinas de pilha. Trata, também, da seleção e do escalonamento das instruções, bem como da reserva de registros, para máquinas de registros uniformes, além da otimização do código resultante com base na análise do fluxo de controle e de dados.
Desse modo, de forma didática e objetiva, a obra revela os desafios das linguagens e das arquiteturas atuais, preparando o leitor para enfrentar, nessa área de atuação, novos obstáculos que, inevitavelmente, surgirão no futuro.

FORMATOS DISPONíVEIS

eBook

Disponível no modelo assinatura da Minha Biblioteca

15 capítulos

Formato Comprar item avulso Adicionar à Pasta

1 - Introdução

PDF Criptografado

1

Introdução

Um compilador é uma aplicação complexa, sem privilégios, que traduz uma descrição em determinada linguagem fonte para uma descrição equivalente em determinada linguagem de destino. Em sua forma mais complexa, um compilador traduz um programa em uma linguagem de programação, em um progra‑ ma executável em linguagem de máquina para uma arquitetura de destino. Uma vez que a maior parte do software é compilado, é imperativo que o compilador garanta a correção do resultado. Assim, os princí‑ pios fundamentais da compilação consistem em preservar o significado do programa fonte e melhorar o resultado produzido de forma significativa. O compilador deve ser eficiente, para que a tradução não seja exageradamente lenta. O código produzido deve ser eficiente para que seja rápido quando executado.

Para tanto, a construção de compiladores reúne diversas disciplinas da ciência da computação em uma só aplicação. Os compiladores representam a ponte entre as aplicações e os sistemas. O compilador é um microcosmo da engenharia de software, que usa estruturas de dados e algoritmos complexos. Como parte do processo de tradução, o compilador precisa analisar o programa fonte para determinar se é uma descrição válida e converter o programa em um conjunto finito de recursos na arquitetura de destino. Para que o resultado seja eficiente, é preciso explorar alternativas utilizando, por exemplo, heurísticas ou mé‑ tricas estatísticas. Atualmente, é a própria tecnologia dos compiladores que determina as características que devem ser acrescentadas ao novo hardware, bem como quais as novas características das lingua‑ gens necessárias ao desenvolvimento do software. A própria tecnologia dos compiladores tem evoluído significativamente nos últimos anos com a automatização das técnicas de análise, a compilação parcial, o compilador JIT (Just‑in‑time) e as novas técnicas de otimização para processadores RISC.

 

2 - ANÁLISE LÉXICA

PDF Criptografado

2

ANÁLISE LÉXICA

As linguagens regulares, denominadas tipo‑3 na hierarquia de Chomsky (ver seção 1.6.2, no Capítulo 1), são linguagens muito simples. Assim, a maioria das linguagens utilizadas em computação não são re‑ gulares, ou seja, não podem ser completamente descritas por gramáticas regulares [20]. No entanto, como o seu processamento é simples e eficazes, as gramáticas regulares são frequentemente utiliza‑ das para processar partes, por vezes significativas, de linguagens mais complexas. Desta separação do processamento da linguagem por uma gramática regular e por outra gramática, em geral livre de contexto, resulta em uma maior eficiência em termos de espaço ocupado pelo analisador e do tempo gasto na análise das descrições. Resulta, ainda, em uma simplificação da gramática livre de contexto, facilitando a sua descrição, realização e execução.

O processamento da parte regular de uma linguagem denomina‑se análise léxica. A análise léxica tem a vantagem de ser um processo que, podendo ser formalmente descrito através de expressões regula‑ res, pode produzir uma rotina que realiza essa análise. Essa rotina modela um autômato finito derivado matematicamente das expressões regulares especificadas [49].

 

3 - Gramáticas Livres de Contexto

PDF Criptografado

3

Gramáticas Livres de Contexto

Gramáticas genéricas livres de contexto são processáveis por meio de algoritmos genéricos, por exemplo, o algoritmo de Earley. No entanto, esses algoritmos apresentam, no pior dos casos, um pro‑ cessamento cuja complexidade é O(n3), em que n é o número de símbolos da sequência de entrada.

Contudo, existem subconjuntos de gramáticas que podem ser processadas de modo mais eficiente.

Essas formas mais simples são ainda suficientemente genéricas em relação a quase todas as lingua‑ gens concebidas para o processamento informático. Entre essas, salientam‑se as gramáticas LL(1) e

LR(1). As gramáticas LL(1) são mais restritivas que as LR(1), embora sejam mais fáceis de pôr em prá‑ tica, mais eficientes e exigem menos memória [54].

As gramáticas constituem a ferramenta preferida para a descrição de linguagens, pois apresentam

­várias vantagens:

■■

Uma gramática dá uma descrição precisa e fácil para o entendimento da sintaxe de uma linguagem;

 

4 - Análise sintática descendente

PDF Criptografado

4

Análise sintática descendente

Este capítulo descreve os analisadores sintáticos descendentes. Esta abordagem consiste em procurar uma sequência de derivações que permite, a partir do símbolo inicial da gra­má­tica, obter a sequência de símbolos terminais a ser analisada.

Nesta família de algoritmos, o mais usado é o analisador preditivo não recursivo (ver seção 4.3). Permi‑ te analisar as gramáticas LL(1) que constituem um conjunto mais restrito do que as linguagens LALR(1)

(ver Capítulo 5).

O presente capítulo começa por descrever os analisadores descendentes recursivos que ilus­tram a técnica de análise. Em seguida, são descritos algoritmos que permitem trans­for­mar uma gramática li‑ vre de contexto em gramática LL(1). As seções 4.3 até 4.7 são dedi­cadas ao analisador preditivo recur‑ sivo e à sua implementação. O capítulo termina com uma família de analisadores descendentes mais abrangente, porém mais complexa – os analisa­dores LL(k).

4.1

 

5 - Análise sintática ascendente por tabela

PDF Criptografado

5

Análise sintática ascendente por tabela

Um analisador ascendente constrói a árvore sintática das folhas para a raiz. Ao contrário da análise des‑ cendente, que demanda a previsão da regra a ser utilizada, a análise ascendente atrasa a escolha da regra até ter lido todos os símbolos que constituem a derivação (lado direito de uma produção), mais os símbolos de antevisão necessários. A principal decisão de um analisador ascendente consiste em determinar quando uma sequência de símbolos corresponde a alguma das regras da gramática. Essa tarefa não é trivial, pois pode haver mais de uma regra com a mesma derivação e casos em que, ape‑ sar da semelhança, não se trata de derivações possíveis.

Como os analisadores ascendentes substituem uma derivação de uma regra pelo símbolo não terminal que a origina, são globalmente denominados LR(k). A análise LR(k) é efetuada pela leitura da sequência de entrada da esquerda para a direita (Left to right), emparelhando as derivações das regras da direita para esquerda (Right to left), usando, no máximo, k símbolos de antevisão. Esses analisadores são os mais uti‑ lizados, pois são menos restritivos do que os correspondentes analisadores preditivos descendentes LL.

 

6 - gramáticas atributivas

PDF Criptografado

6 gramáticas atributivas

Os algoritmos descritos nos Capítulos 4 e 5 permitem realizar a análise sintática de uma linguagem, porém não chegam a construir as estruturas de dados necessárias às fases posteriores da compilação.

As técnicas descritas neste capítulo permitem associar ações às produções da gramática. Essas ações podem servir a vários objetivos conforme o tipo de aplicação que queremos desenvolver. No contexto de um interpretador, as ações associadas às regras podem servir para avaliar expressões. No caso de um compilador, duas tarefas principais podem ser realizadas:

■■

Verificação semântica: é necessário verificar que os tipos das variáveis e expressões são compa‑ tíveis (nas atribuições, chamadas às funções etc.);

■■

Geração de uma representação intermediária para as instruções do programa: o código interme‑ diário é geralmente representado por uma árvore ou por uma sequência de pseudoinstruções.

Falaremos, portanto, de «regras semânticas» ou de «ações semânticas» associadas às produções da gramática. As verificações semânticas são guiadas pela estrutura sintática, por isso essas técnicas são chamadas de tradução orientada pela sintaxe (syntax‑directed translation).

 

7 - ANÁLISE SEMÂNTICA

PDF Criptografado

7

ANÁLISE SEMÂNTICA

Nos capítulos anteriores foram descritos algoritmos que permitem a análise léxica e sintática das lin‑ guagens. O Capítulo 6 mostrou um conjunto de técnicas para acrescentar processamentos à análise sintática por meio de atributos. Geralmente, as ações associadas ao cálculo dos atributos têm como objetivo produzir uma representação interna do programa e efetuar verificações semânticas. Idealmen‑ te, o processamento dos atributos é realizado sem produzir efeitos colaterais. Na prática, muitas veri‑ ficações semânticas devem ser efetuadas sobre elementos presentes em vários pontos do programa, possivelmente distantes. Uma referência a um tipo, a um método ou a uma variável pode estar distan‑ te da sua definição e, eventualmente, aparecer em um arquivo diferente. Para resolver este problema

é usado um repositório central em que fica armazenada toda a informação relativa aos símbolos (iden‑ tificadores de variáveis, tipos, funções, métodos, classes etc.): a tabela dos símbolos. Os detalhes de implementação da tabela de símbolos serão abordados no Capítulo 8.

 

8 - Projeto de análise

PDF Criptografado

8

Projeto de análise

As linguagens usadas em computação, sejam de programação ou não, foram concebidas para não se‑ rem ambíguas; portanto, podem ser processadas pelos métodos de análise anteriormente apresen‑ tados. Além disso, a maior parte dessas linguagens foi projetada levando em conta as limitações dos analisadores disponíveis, e podem ser facilmente descritas por gramáticas LALR(1) ou mesmo LL(1).

Agora que já conhecemos as técnicas de análise em tempo linear, ou seja, O(N), torna‑se necessário compreender como se constrói um analisador. Abordaremos várias ferramentas [29, 52, 112] que, em‑ bora sigam invariavelmente o mesmo processo, diferem em diversas opções. Optamos por usar como exemplo uma linguagem de programação, pois essas são em geral mais complexas, além de servir de base à Parte II do livro. Contudo, poderíamos tomar como exemplo qualquer linguagem utilizada em computação, como HTML, XML, SQL etc.

8.1 Um analisador para uma linguagem regular

 

9 - ambiente de execução de programas

PDF Criptografado

9 ambiente de execução de programas

Antes de iniciar a geração de código, é necessário compreender os formatos de dados e código utiliza‑ dos pelo processador e pelo sistema operacional. Só assim saberemos o que devemos efetivamente conseguir que o compilador gere. Este capítulo oferece uma introdução aos formatos para a geração de código necessária aos capítulos seguintes. Primeiramente, trataremos a representação de valores, desde os tipos elementares, como o inteiro, aos compostos, como o vetor ou a estrutura. O formato das funções é abordado separadamente, sem incluir ainda as instruções que executam as operações, mas sim a forma como os dados são passados e os resultados recolhidos. Finalmente, para que o pro‑ grama possa ser executado, os dados e as funções são integrados em um arquivo executável que é parcialmente carregado para a memória no momento em que o programa é invocado.

9.1 Representação de valores

Para que os computadores processem os números de maneira eficiente é necessário que os números tenham uma dimensão finita e que sejam representados em numeração binária. A numeração biná‑ ria simplifica significativamente as operações a serem realizadas, por exemplo, a tabuada resume‑se a 0 3 0 5 0, 0 3 1 5 0, 1 3 0 5 0 e 1 3 1 5 1, o que pode ser feito por uma porta lógica AND. Por

 

10 - representação de código intermediário

PDF Criptografado

10 representação de código intermediário

O principal objetivo de um compilador é gerar código para processadores, reais ou virtuais. Para tanto é necessário: conhecer os diversos tipos de processadores; ver os diversos tipos de representações in­ termediárias possíveis; e definir uma arquitetura que permita gerar, de forma simples e direta, o código não otimizado. A maioria dos compiladores recorre a uma representação intermediária de código, com instruções semelhantes a um processador final mas sem as limitações desse último. Essa representa­

ção de código intermediário pode, posteriormente, como veremos nos próximos capítulos, ser manipu­ lada de modo a gerar instruções mais eficientes para um processador específico.

10.1 Arquiteturas de processadores

A geração de código para um processador específico deve levar em conta as suas características parti­ culares. No entanto, os processadores podem ser agrupados em conjuntos com características seme­ lhantes. Os dois primeiros grupos, stack machines e accumulator machines, permitem a execução do código intermediário de pilha abordado no capítulo anterior, podendo as accumulator machines optar pela colocação do topo da pilha no acumulador. Os dois grupos seguintes, load‑store machines e m

 

11 - geração de código intermediário

PDF Criptografado

11 geração de código intermediário

O processo de linearização de código consiste em gerar uma sequência linear de instruções inter‑ mediárias a partir da estrutura sintática do programa a ser compilado. A linearização de dados globais e de instruções permite sua disposição e armazenamento sequencial na memória. Essa linearização pode ter por base uma árvore sintática ou qualquer outro tipo de representação intermediária. Alterna‑ tivamente, pode ser dirigida pela sintaxe, ou seja, efetuada diretamente a partir das ações semânticas do analisador sintático. No entanto, nesse último caso, só linguagens simples podem ser lineariza‑ das utilizando exclusivamente as ações semânticas, sem recorrer a estruturas auxiliares, mesmo que

­temporárias.

11.1 Geração de dados

A geração de dados baseia‑se em um conjunto de diretivas assembly que o assembler vai utilizar para colocar os valores na memória e registrar as suas posições para posterior referência pelas instruções.

 

12 - geração de código final para máquinas de pilha

PDF Criptografado

12 geração de código final para máquinas de pilha

O código intermediário para registros (ver seção 10.5.3, no Capítulo 10) gera código que utiliza um nú‑ mero indeterminado de registros. Como processadores reais têm um número limitado de registros, é sempre possível que alguma sequência de entrada necessite de mais registros do que os disponíveis no processador [37, 17]. Desta forma, o código intermediário para registros necessita de processamento adicional para ser executado por um processador real, conforme abordaremos nos capítulos seguintes.

Por outro lado, o código intermediário de pilha assume que não existem registros de dados para preser‑ var valores entre as instruções. Como não há registros de dados, também não existe necessidade de efetuar reserva de registros ou de otimizar a sua utilização. A seleção de instruções também pode ser ignorada por meio da disponibilização de uma só instrução possível para cada operação. Assim, nessas condições particulares, o código intermediário pós‑fixado torna‑se código final para uma arquitetura em que as instruções não contêm argumentos (zero‑address architecture) [71]. O código pós‑fixado pode ser entendido simultaneamente como intermediário e final, pois podemos ignorar os registros de um processador real ou usá‑los de maneira implícita. Consequentemente, podemos dispor de um compi‑ lador funcional com pouco esforço porém sem aproveitar as características específicas do processador subjacente. O código resultante será bastante ineficiente, em especial se o processador contiver mui‑ tos registros.

 

13 - SELEÇÃO E ESCALONAMENTO DE INSTRUÇÕES

PDF Criptografado

13

SELEÇÃO E ESCALONAMENTO

DE INSTRUÇÕES

A otimização, mesmo em compiladores, não é mais que uma busca pela perfeição e, como na vida, é inatingível. O objetivo é otimizar o desempenho do código gerado, preservando o significado do pro‑ grama original. Em média, a execução do código gerado pelo compilador deve melhorar visivelmente o tempo de execução, o uso da memória ou o espaço ocupado pelo programa. Claro que isso só é pos‑ sível com o aumento da complexidade do próprio compilador: aumentando o tempo de execução e o espaço por esse ocupado durante o processo de compilação.

Para otimizar, ou seja, melhorar a qualidade do código gerado, uma enorme variedade de técnicas tem sido criada. O compilador ideal usa todas as técnicas, sempre que possível. No entanto, algumas po‑ dem estar inacessíveis em certos casos, por exemplo, as otimizações interprocedimentais quando al‑ gumas rotinas não estão acessíveis devido à compilação separada. Outras podem não se justificar, por exigir um grande esforço do compilador para ganhos reduzidos na qualidade do código gerado, como otimizações globais em processadores com poucos registros. A regra, em geral, consiste em restringir o compilador para utilizar apenas as otimizações que oferecem maiores ganhos, em termos de tempo de execução do programa compilado, com menores custos em termos de tempo de compilação e com‑ plexidade do compilador. Só em casos específicos, e normalmente sob o controle do programador, é que as otimizações mais agressivas são ativadas, caso o compilador em questão as disponibilize.

 

14 - Reserva de registros

PDF Criptografado

14

Reserva de registros

A reserva de registros tem por missão fazer corresponder registros físicos às instruções já geradas e, possivelmente, escalonadas. Como a reserva de registros é um problema NP‑completo, existem diver‑ sos métodos de atribuição de registros. Entre esses métodos podemos mencionar: algoritmos greedy, top‑down, ordenação de subárvores, próximo uso, pesquisa linear ou coloração de grafos. A comple‑ xidade crescente permite obter, em geral, melhores resultados por conta de maiores tempos de exe‑ cução. Excetua‑se o algoritmo de ordenação de subárvore, que é um algoritmo localmente ideal que, pode no entanto, ser aplicado apenas a uma única expressão.

O problema da reserva de registros consiste em minimizar a utilização de registros, uma vez que os processadores dispõem de um número limitado de registros. No entanto, sempre que o número de registros é insuficiente, a reserva de registros pode necessitar introduzir instruções que movimentem os valores entre registros, por exemplo, no caso de arquiteturas de registros não uniformes e entre re‑ gistros e memória.

 

15 - Análise de Fluxo

PDF Criptografado

15

Análise de Fluxo

A análise de fluxo procura identificar otimizações passíveis de serem executadas tendo por base a se‑ quência de execução produzida pelo código gerado [90, 66]. A análise de fluxo divide‑se em análise de fluxo de controle e análise de fluxo de dados. A análise de fluxo de controle investiga o código em termos de loops e alternativas, baseando‑se nas instruções de salto geradas para esse efeito. A análi‑ se de fluxo de dados acompanha a evolução das variáveis e das expressões calculadas a partir dessas, quer no interior de cada bloco de código, quer entre os diversos blocos de código. Finalmente, são identificadas as diversas otimizações disponibilizadas por um compilador, bem como a forma como se relacionam com os processos de geração de código e análise de fluxo tratados.

15.1 Análise de fluxo de controle

A análise de fluxo de controle procura compreender o comportamento de cada rotina do ponto de vis‑ ta de repetições e alternativas de conjuntos de instruções [109]. O paralelo com as linguagens de alto nível pode ser realizado caso se considere como uma só instrução cada bloco de código entre chaves, em C ou Java, por exemplo. Este tipo de análise parte do princípio de que o valor dos registros não pode ser garantido quando a instrução é alvo de uma ou mais instruções de salto. Para tanto, o código

 

Detalhes do Produto

Livro Impresso
Book
Capítulos

Formato
PDF
Criptografado
Sim
SKU
BPP0000261264
ISBN
9788521635154
Tamanho do arquivo
15 MB
Impressão
Desabilitada
Cópia
Desabilitada
Vocalização de texto
Não
Formato
PDF
Criptografado
Sim
Impressão
Desabilitada
Cópia
Desabilitada
Vocalização de texto
Não
SKU
Em metadados
ISBN
Em metadados
Tamanho do arquivo
Em metadados