Algorítmos

Princípios de Um Compilador

binary-LanguageNeste artigo apresentarei um assunto muito relevante (e que a maioria dos desenvolvedores de software não dá a devida atenção), que são os compiladores e seu funcionamento. Falaremos sobre o funcionamento e aplicação dos compiladores, sobre a ótica da implementação e conceito, pois em sua forma mais geral, um compilador é um programa que aceita como entrada um texto de programa em uma certa linguagem e produz como saída um texto de programa em outra linguagem, enquanto preserva o significado desse texto.

Podemos entender da seguinte forma: que esse processo é chamado tradução como seria denominado se os textos estivessem em linguagens naturais. Quase todos os compiladores fazem a tradução de uma linguagem de entrada, a linguagem de origem ou linguagem-fonte, apenas para uma linguagem de saída, a linguagem de destino.

Este conceito acima pode ser extrapolado para outros tipos de sistemas além do próprio compilador, como por exemplo, sistemas de gestão de regras de negócio, quando se precisa escrever regras em linguagem de alto nível sem se ter o inconveniente de compilar o programa novamente. Normalmente, espera-se que a linguagem de origem e a linguagem de destino sejam bem diferentes: por exemplo, a linguagem de origem poderia ser C e a linguagem de destino poderia ser código de máquina para processador especificamente da série Pentium (não é comum, mas é possível ser feito).

O nome “compilador” é usado principalmente para os programas que traduzem o código fonte de uma linguagem de programação de alto nível para uma linguagem de programação de baixo nível (por exemplo, Assembly ou código de máquina).

Tenha em mente que a principal razão pela qual alguém desejaria tal tradução é o fato de haver hardware no qual seria possível “executar” o programa traduzido ou, mais corretamente falando, fazer o hardware executar as ações descritas pela semântica do programa. Este conceito é bastante importante quando se precisa manipular um hardware específico. O hardware é a única fonte real de poder de computação.

A execução de um programa traduzido muitas vezes envolve alimenta-lo com dados de entrada em algum formato, e isso provavelmente resultará em alguns dados de saída em algum outro formato. Os dados de entrada podem ser oriundos de diversas fontes: os exemplos são arquivos, sequências de teclas digitadas e pacotes de rede. Da mesma forma, a saída pode ir para diversos lugares; os exemplos são arquivos, telas de monitores e impressoras.

É importante observar que para obter o programa traduzido executamos um compilador, que é simplesmente outro programa cujos dados de entrada são constituídos por um arquivo com o formato de um texto de origem de programa e cujos dados de saída constituem um arquivo com o formato de código executável (para um determinado sistema operacional).

Observe que para obter o compilador, executamos outro compilador cuja entrada consiste em código-texto-fonte do compilador e que produzirá código executável correspondente a esse código-texto-fonte, como faria para o código-texto-fonte de qualquer programa.

Abaixo, segue uma imagem para ilustrar o que foi falado até o momento:

image

Perceba que um aspecto claro da compilação é que a entrada tem uma propriedade chamada semântica (seu ‘significado’), que deve ser preservado pelo processo e com frequência é menos claramente identificável em um programa de conversão de arquivos tradicional, por exemplo um programa que faça a conversão de EBCDIC em ASCII.

O Compilador consegue realizar suas tarefas devido a dois fatores:

  • A entrada está em uma linguagem e consequentemente tem uma estrutura, que é descrita no manual de referência da linguagem.
  • A semântica da entrada é descrita em termos dessa estrutura e está associada a ela.

Esses fatores permitem ao compilador ‘reconhecer’ o programa e coletar sua semântica em uma representação semântica.
Outro conceito importante é: A parte de um compilador que executa a análise do texto da linguagem-fonte é chamada front-end, e a parte que faz a síntese da linguagem de destino é o back-end.

image

Um ponto importante sobre a imagem acima (e que você pode estar se perguntando) é que a imagem acima sugere de imediato outro modo de operação para um compilador: se todos os dados de entrada exigidos estivessem disponíveis, o compilador poderia executar as ações especificadas pela representação semântica, em vez de expressa-las novamente em uma forma distinta. Certo? Sim. Mas nesta abordagem, o back-end de geração de código é então substituído por um back-end de interpretação, e assim, o programa inteiro é chamado interpretador e não compilador. Um ponto positivo para os interpretadores é que normalmente ele é escrito em uma linguagem de alto nível, e portanto funcionará na maioria dos tipos de máquinas, enquanto o código-objeto gerado só funcionará em máquinas do tipo de destino: em outras palavras, a portabilidade será aumentada. Outra razão é que a escrita de um interpretador é muito menos trabalhosa que a escrita de um back-end (sem a menor dúvida).

É importante observar que não há nenhuma diferença fundamental entre usar um compilador e usar um interpretador. Em ambos os casos, o texto do programa é processado em uma forma intermediária, a qual é então interpretada por algum mecanismo de interpretação.

Na compilação: O processamento de programas é considerável, a forma intermediária resultante, código binário executável específico da máquina, é de baixo nível e o mecanismo de interpretação é a CPU do hardware. A execução do programa é relativamente rápida.

Na interpretação: O processamento de programas é de mínimo a moderado, a forma intermediária resultante, alguma estrutura de dados específica do sistema, é de nível alto a médio, o mecanismo de interpretação é um programa (de software). A execução de programas é relativamente lenta.

Por Que Se Chama Compilador?

Então vamos aos conceitos: O significado original de compilar é selecionar material representativo e acrescenta-lo a uma coleção.  Em seu início, a conversão de linguagens de programação era vista do mesmo modo: por exemplo, quando a entrada continha ‘a + b’, um fragmento de código pré-fabricado ‘carregar a no registrador; adicionar b ao registrador’ era selecionado e adicionado à saída. Observe que um compilador compilava uma lista de fragmentos de código a serem adicionados ao programa traduzido. Os compiladores de hoje, em especial aqueles relacionados a paradigmas de programação não-imperativos, com frequência realizam transformações muito mais radicais sobre o programa de entrada.

Por Que Devo Estudar Compiladores?

Há uma série de razões objetivas pelas quais o estudo da construção de compiladores é uma boa ideia: A construção de compiladores é um ramo muito bem-sucedido da ciência da computação, e um dos primeiros a obter esse atributo. Dada sua relação próxima com a conversão de arquivos, ela tem uma aplicação mais ampla que os simples compiladores. Contém muitos algoritmos geralmente úteis em uma configuração realista. A principal razão subjetiva para estudar a construção de compiladores é, a pura curiosidade: é fascinante ver como os compiladores conseguem realizar tudo que fazem. E principalmente ganhar mais conhecimentos em algoritmos mais complexos.

A construção de compiladores é um ramo muito bem-sucedido da ciência da computação. Algumas razões para isso são a estruturação apropriada do problema, o uso criterioso de formalismos e o uso de ferramentas sempre que possível. Os compiladores analisam sua entrada, constroem uma representação semântica e sintetizam sua saída a partir dela. Esse paradigma de análise-síntese é muito eficiente e amplamente aplicável. Veja por exemplo, um programa para medir comprimentos de palavras em um texto poderia consistir em um front-end que analisasse o texto e construísse interiormente uma tabela de pares (comprimento, frequência) e um back-end que depois imprimisse essa tabela.

Outro fato importante de ser apresentado, é que, sem a separação estrita das fases e análise e síntese, as linguagens de programação e a construção de compiladores não seriam o que são hoje. Sem ela, cada nova linguagem exigiria um conjunto completamente novo de compiladores para todas as máquinas. Esse fato dificultaria muito todo o processo. Basta um novo front-end para essa linguagem, a ser combinado com os back-ends existentes para as máquinas atuais.

Veja conforme a imagem abaixo o que estamos falando:

image

Observe porém, que essa separação estrita não é completamente livre de trabalho. Se um front-end souber que está fazendo a análise para uma máquina com instruções de máquina especiais referentes a saltos de vários caminhos, é provável que ele analise instruções case/switch de modo que elas possam se beneficiar dessas instruções de máquina. De forma parecida, se um back-end souber que está gerando código para uma linguagem que não tem nenhuma declaração de rotinas aninhadas, ele poderá gerar um código mais simples para chamadas de rotinas. Entenda que muitos compiladores profissionais são compiladores integrados, destinados a uma linguagem de programação e uma arquitetura de máquina, utilizando uma representação semântica que deriva da linguagem-fonte e que já deve conter elementos da máquina de destino. De qualquer forma, a estruturação desempenhou e ainda desempenha um papel importante na introdução rápida de novas linguagens e novas máquinas.

Outro fato que deve ser sempre levado em conta é o uso criterioso de formalismos. Em algumas partes da construção de compiladores foram desenvolvidos excelentes formalismos padronizados, os quais reduzem bastante o esforço para produzir essas partes. Os melhores exemplos são expressões regulares e gramáticas livres de contexto, usadas em análise léxica e sintática. Não entraremos nesses detalhes aqui, pois demandaria um curso inteiro sobre o assunto. As gramáticas de atributos são um formalismo que pode ser usado para tratar o contexto, as relações de longa distância em um programa que vincula, por exemplo, o uso de uma variável à sua declaração. A geração de código-objeto para uma dada máquina envolve uma grande quantidade de programação complicada quando feita manualmente, mas o processo pode ser automatizado usando-se, por exemplo, técnicas de correspondência de padrões e programação dinâmica. Diversos formatos de formalismos foram projetados para a descrição de código de máquina tanto em nível “Assembly” quando em nível binário, todavia nenhum deles obteve ampla aceitação até hoje, e cada sistema de escrita de compiladores tem sua própria versão.

Teoricamente, assim que se tenha o formalismo apropriado no qual será descrito o que um determinado programa deve fazer, pode-se gerar um programa a partir desse formalismo, usando um gerador de programas.

Observe que para o ramo de compiladores, gerar programas em vez de escreve-los à mão tem várias vantagens:

  1. A entrada para um gerador de programas é de um nível de abstração muito mais alto do que seria o programa escrito à mão. O programador precisa especificar menos, e as ferramentas assumem a responsabilidade por grande parte das tarefas de administração interna propensas a erros. Isso aumenta as chances de que o programa esteja correto. Por exemplo, seria incômodo escrever tabelas de análise à mão.
  2. O uso de ferramentas de geração de programas oferece maior flexibilidade e facilidade de modificação. Por exemplo, se durante a fase de projeto de uma linguagem fosse considerada uma pequena mudança na sintaxe, um analisador escrito à mão seria um grande empecilho a qualquer mudança. Com um analisador gerado, bastaria alterar a descrição da sintaxe e gerar um novo analisador.
  3. Pode-se adicionar código pronto ou sob medida ao programa gerado, aumentando sua capacidade quase sem custo. Por exemplo, o tratamento de erros de entrada em geral é uma tarefa difícil em analisadores escritos à mão; um analisador gerado pode incluir código pronto de correção de erros sem qualquer esforço por parte do programador.
  4. Uma descrição formal às vezes pode ser usada para gerar mais de um tipo de programa. Por exemplo, depois de termos escrito uma gramática para uma linguagem com o propósito de gerar um analisador a partir dela, podemos usa-la para gerar um editor dirigido para a sintaxe, um editor de textos de programa de uso especial que oriente e forneça suporte para o usuário durante a edição de programas nessa linguagem.

Na teoria, os programas gerados podem ser ligeiramente mais ou menos eficientes que programas escritos à mão, mas gera-los é tão mais eficiente que escreve-los à mão que, sempre que existir essa possibilidade, quase sempre será preferível gerar um programa. Outras formas de programação podem ser consideradas construção de compiladores, mais do que se consideraria tradicionalmente. Os exemplos são a leitura de dados estruturados, a introdução rápida de novos formatos e os problemas gerais de conversão de arquivos.

A estrutura básica de qualquer compilador tem de conter pelo menos um analisador léxico, um analisador de sintaxe e um tratador de contexto, nessa ordem. Isso nos leva à estrutura do compilador/interpretador mostrado abaixo.

image

O back-end permite duas implementações intuitivamente diferentes: um gerador de código e um interpretador. Ambos usam o código intermediário, o primeiro para gerar código de máquina, e o segundo para executar de imediato as ações implícitas.

A imagem anterior mostra que, para descrever o compilador mínimo, tínhamos de decompor o front-end em três módulos e que o back-end poderia permanecer como um único modulo. E claro que isso não é suficiente para um compilador real. Apresento uma versão mais realista abaixo, no qual o fronr-end e o back-end consistem cada um em cinco módulos. Além desses módulos, compilador conterá módulos para o tratamento da tabela de símbolos e relatórios de erros; esses módulos serão chamados por quase todos os outros módulos.

image

Propriedades Para Bom Compilador

Não preciso nem dizer que a propriedade mais importante de um bom compilador é a de gerar código correto (mas já disse). Um compilador que ocasionalmente gera código incorreto é inútil; um compilador que gera código incorreto uma vez por ano pode parecer útil, mas talvez seja perigoso. Também é importante que um compilador obedeça completamente à especificação da linguagem. Ele pode estar tentando implementar um subconjunto, um superconjunto, ou até aquilo que às vezes é chamado sarcasticamente um ‘subconjunto’ estendido da linguagem, e os usuários podem até agradecer, mas esses mesmos usuários logo perceberão que programas desenvolvidos com um tal compilador são muito menos portáteis que programas escritos com o uso de um compilador completamente compatível. Outra propriedade de um bom compilador, negligenciada com frequência, é que ele deve ser capaz de manipular programas de tamanho essencialmente arbitrário, desde que a memória disponível o permita.

A velocidade de compilação é uma questão importante, mas não a principal, espera-se que programas pequenos sejam compilados dentro do intervalo de um segundo em máquinas mais potentes. O caráter amistoso de um compilador em relação ao usuário se mostra principalmente na qualidade de seus relatórios de erros. No mínimo, o usuário deve receber uma mensagem de erro clara que inclua a causa percebida do erro, o nome do arquivo de entrada e a posição nesse arquivo. A importância da velocidade e do tamanho do código gerado depende totalmente do propósito do compilador. Em geral, pode-se esperar que o usuário esteja mais interessado em alta velocidade que em tamanho pequeno (exceto o código para aplicações embarcadas utilizando  microcontroladores e etc).

No próximo artigo entrarei no assunto das gramáticas que é bem interessante e sem ela não existiria o formalismo da linguagem.

Qualquer dúvida entre em contato.


Teoria da Compactação de Dados

tar-gz1Uma das caracteísticas mais importantes da ciência da computação atualmente, é o estudo dos algorítmos para a compactação de dados que são trafegados através da internet para exibir filmes, mandar e-mail, enviar fotos e seja lá qual for a necessidade. Seria impossível termos as funcionalidade que temos hoje para internet, sem falar em compactação de dados. Por esse motivo, neste artigo apresentarei as bases da formação da compactação de dados.

Como este assunto é bastante complexo, vou me ater em compactação de arquivos simples, ou seja, arquivos de texto, entretanto as técnicas que vou apresentar aqui no artigo, são independente do tipo de arquivo.

Para armazenar um simples arquivo de texto em um computador, cada caractere é armazenado em um byte (8 bits). Obviamente, nem todos os 28 = 256 caracteres possíveis são usados. Pensou-se então em uma alternativa fácil para reduzir o tamanho do arquivo, que é verificar se menos de 2k caractéres são usados, usando apenas k bits neste caso, todavia essa técnica não compacta quase nada o arquivo. Pensou-se então em uma técnica mais inteligente que é considerar as frequências dos caracteres e codificar cada caractere com um número diferente de bits. Sem que esse conceito é um pouco abstrato, mas vou dar um exemplo:

Desejo compactar a palavra “cabana”. Facilmente identificamos que as frequências dos caracteres nesta palavra são f( c ) = f( b ) = f( n ) = 1/6 e f( a ) = 1/2. Temos 4 caracteres, então podemos usar 2 bits por caractere, totalizando 12 bits. Outra opção é usar os seguintes códigos:  c : 000, b : 001, n : 01, a : 1. Desta forma obtemos a palavra compactada 00010011011 com 11 bits. Não parece que ganhamos muito desta forma, mas este exemplo é bem pequeno e contém pouca redundância (tente algo semelhante com a palavra “aaaaabaaaaaabaaacaaacaaaaad”). Esta compactação é chamada de compactação de Huffman e sozinha não tem muita eficiência, entretanto ela está presente como parte importante de praticamente todos os melhores compactadores usados na atualidade.

É um ponto importante como podemos decodificar a mensagem. Primeiro, precisamos saber o código de cada caractere. Precisamos também, ter uma maneira de descobrir quando acaba um caractere e começa outro. Vejamos o exemplo anterior. Começamos lendo 0. Os caracteres iniciados por 0 são “c”, “b” e “n”. Lemos então outro 0. Agora sabemos que se trata ou de um “c” ou um “b”. Ao lermos 0 novamente, temos certeza que é um “c”. Isto é possível porque geramos um código de prefixo. Um código de prefixo é uma atribuição de uma sequência distinta de bits para cada caractere de modo que uma sequência não seja um prefixo da outra. Desta forma, um código ser de prefixo é uma condição suficiente para permitir que qualquer mensagem escrita com ele possa ser decodificada de modo único, mas não é uma condição necessária para isto.

Se estamos limitados a atribuir uma sequência de um número inteiros de bits para cada caractere, sempre existe código de prefixo que usa o mínimo de bits para codificar a mensagem dentre todos os códigos, que permitiriam que qualquer mensagem escrita com ele fosse decodificada de modo único. Desta forma, não estamos perdendo nada por nos limitarmos a códigos de prefixo.

SNAGHTML5aa9f67É importante ressaltar que existe uma relação direta entre árvores binárias e códigos de prefixo. A cada folha podemos associar um caractere. Cada bit indica se devemos seguir para a direita ou esquerda na árvore.

Esta árvore exibida ao lado corresponde a palavra “cabana”. Assim, chamamos de C = {c1, …, cn} o nosso conjunto de caracteres e de f( ci ) a frequência do caractere ci. Formalmente falando, queremos construir uma árvore binária “T” que tenha como conjunto de folhas o conjunto C e que minimize:

image

onde l(ci) é o nível da folha ci, definido como sua distência até a raiz, ou seja, l(ci) é o número de bits usados para codificar ci. Esta árvore é chamada de árvore de Huffman de C. Espero que não tenha parecido muito difícil o conceito, pois não é. São termos apenas formais da matemática. É importante notar que as frequências dos caracteres podem ser multiplicadas livremente por qualquer constante, por isso podemos usar frequências que somem 1 ou o número de aparições de cada caractere livremente.

Esta é apenas uma abordagem ao problema de compactação de dados e existem outro muito mais complexos e com poder de compactação maior, entretanto como dito antes, quase todos utilizam árvore de Huffman nas suas bases.

Para fechar este artigo, apresento o algorítmo para um dado conjunto de caractéres C com suas frequências:

Formalmente dizemos:

SNAGHTML5bba39c

Para que o descompactador decodifique um arquivo compactado com o código de Huffman ele precisa ter conhecimento da árvore. Daremos 4 alternativas para o problemas:

1) Usar uma árvore pré-estabelecida, baseada em frequências médias de cada caractere. Esta técnica sé é viável em arquivos de texto. Ainda assim, de um idioma para outro a frequência de cada caractere pode variar bastante.

2 ) Fornecer a árvore de Huffman, direta ou indiretamente, no início do arquivo. A árvore de Huffman para 256 caracteres pode ser descrita com 256 caracteres mais 511 bits usando percurso em árvore. Outra opção mais simples é informar a frequência de cada caractere e deixar que o descompactador construa a arvore. É necessário cuidado para garantir que a árvore do compactador e do descompactador sejam idênticas.

3) Fornecer a árvore de Huffman, direta ou indiretamente, para cada bloco do arquivo. Esta técnica divide o arquivo em blocos de um tamanho fixo e constrói árvores separadas para cada bloco. A vantagem é que se as frequências dos caracteres são diferentes ao longo do arquivo, pode-se obter maior compactação. A desvantagem é que várias árvores tem que ser fornecidas, gastando espaço e tempo de processamento.

4) Usar um código adaptativo. Inicia-se com uma árvore em que todo caractere tem a mesma frequência e, a cada caractere lido, incrementa-se a frequência deste caractere, atualizando a árvore. Neste caso não é necessário enviar nenhuma árvore, mas não há compactação significativa no início do arquivo.

 

Espero que tenham gostado do artigo. Qualquer dúvida, sugestão ou crítica, entre em contato.

Márcio Pulcinelli @ OminaVincit!