Preliminares

Computadores, diferente de seres humanos, são capazes de executar apenas instruções em linguagem de máquina. No caso da esmagadora maioria dos computadore contemporâneos, as instruções do código de máquina são binárias, o que leva muitos a dizer que computadores compreendem apenas "zeros e ums". Entretanto, ao dizer isso estamos, na verdade, abstraindo a ideia de que somos capazes de distringuir apenas entre estados complementares. Por exemplo, se estamos falando de RAM, 1 e 0 se referirão, respectivamente, a DDP mais alta e mais baixa. Em um HD, por outro lado, a estados magnéticos distintos e assim por diante.

Apesar disso, ao utlizarmos uma linguagem de programação, não precisamos nos procupar com questões tão elementares sobre o funcionamento de um computador. Este é o caso, porque o código que escrevemos enquanto programadores, código fonte, é traduzido em código de máquina antes da sua execução. Este processo pode ser feito de mais duas maneiras: via compiladores e interpretadores. É importante notar que, embora o caso clássico tenha a ver com a conversão de código fonte para código de máquina, outros tipos de sistemas também podem ser considerados compliladores e interpretadores. Por exemplo, um um programa de composição (typesetting) que produz PostScript pode ser considerado um compilador.Ele recebe como entrada uma especificação de como o documento deverá ser impresso em uma página e produz como saída um arquivo PostScript (uma linguagem para descrever imagens). O código por sua vez que transforma PostScript em pixels costuma ser interpretado.

É o caso, pois, que o presente artigo artigo buscará prover uma visão geral sobre o que são compiladores e como são implementados.

Compiladores

Para entender as tarefas envolvidas no processo de compilação considere que desejamos gerar código executável a partir da seguinte expressão:

Vamos acompanhar a expressão pelo processo de compilação:

Compreendendo o programa de entrada

Precisamos, antes de mais nada, determinar se

é uma epxressão gramatical da nossa linguagem de programção. Isto é, um compilador precisa ser capaz de determinar se a entrada é bemm formada com respeito a linguagem fonte. Se sim, o compilador dará prosseguimento ao processo de tradução, otmização e geração de código. Caso contrário, o compilador deve retornar um erro ao usuário que , na medida do possível, isola o problema com a sentença de código problemática.

Para fazer essa checagem sintática, conhecida como análise sintática, é necessário que o compilador tenha acesso a:

1. Uma definição formal da linguagem
2. Um teste eficiente para o pertencimento à linguagem fonte
3. Um plano para lidar com entradas ilegais

Linguagens naturais, como o português, inglês e japonês, não podem ser compiladas perfeitamente, já que não existe critério bem específicado de pertencimento à linguagem. Por outro lado, linguagens artificiais, como o cálculo lambda, a lógica de primeira ordem, C++ e Rust, não estão sujeitas a estes mesmos problemas. Para ilustrar bem o tipo de procedimento que deve ser executado por um compilador, tomaremos um exemplo extremamente simples: o fragmento proposicional da lógica de primeira ordem.

Perceba que se queremos que a linguagem seja completamente especificável, precisamos que as definições sejam indutivas. O procedimento é simples, basta começar com o menor conjunto de fórmulas, fórmulas aqui significando as expressões legais da nossa linguagem, que não podem ser decompostas em fórmulas menores. Em seguida, devemos descrever como fórmulas complexas são construídas a partir daquelas já dadas, as atômicas.

Dessa forma podemos dizer que o alfabeto da linguagem da lógica proposicional é constituída por:

1. Símbolos de proposição: $\{p_n |n\in \mathbb{N}\}$
2. Operadores: $\wedge , \vee , \rightarrow , \neg , \leftrightarrow , \bot$
3. Símbolos de desambiguação: ( , )

Os símbolos de proposição e $\bot$ são nossas fórmulas indecomponíveis, chamadas de atômicas.

Perceba que dada a nossa definição o Conjunto das Fórmulas, $\Gamma$, é o menor cojunto satisfazendo:

$(1) \; p_n \in \Gamma(n \in \mathbb{N}), \bot \in \Gamma$

$(2) \; \varphi , \psi \in \Gamma \Rightarrow (\varphi \wedge \psi), (\varphi \vee \psi), (\varphi \rightarrow \psi), (\varphi \leftrightarrow \psi) \in \Gamma$

$(3) \; \varphi \in \Gamma \Rightarrow (\neg \varphi) \in \Gamma$

Essas cláusulas descrevem todas as formas de construir proposições. Para simplificar a clásula 2, podemos escrever $\varphi , \psi \in \Gamma \Rightarrow (\varphi \square \psi) \in \Gamma$

Uma nota importante é que fizemos uso das letras gregas $\varphi$ e $\psi$ nas definições, mas elas não são fórmulas, já que não fazem parte do alfabeto da linguagem. Assim como faríamos o uso de classes gramaticais em linguagens naturais para abstrair de frases particulares e utilizamos variáveis numéricas em aritmética para abstrair dos números $\varphi$ e $\psi$ são variáveis para proposições, também chamadas de meta-variáveis . O ponto é, já que a linguagem foi formalmente definida de maneira adequada é fácil obter um procedimento para testar se uma expreção da linguagem pertence ao conjunto $\Gamma$ das expressões legais, considere os exemplos:

Verificar $(i)$ é fácil, basta aplicar os passos de construção que definimos anteriormeente. Por outro lado, o processo de mostrar, por exemplo que

não pertence a $\Gamma$ é um pouco mais complicado, vejamos:

Suponha que $\neg \neg \bot \in \Gamma$ e que $\Gamma$ satisfaz as propriedades (1), (2) (3). Dizemos então que

e que $\Delta$ também satisfaz (1), (2) e (3). Como $\bot , p_n \in \Gamma$, também deve ser o caso que $\bot , p_n \in \Delta$. Se $\varphi \psi \in \Delta$, então $\varphi , \psi \in Gamma$. Como $\Gamma$ satisfaz (2) $(\varphi \square \psi) \in \Gamma$. Olhando a forma das expressões fica claro que $(\varphi \square \psi) \neq \neg \neg \bot$, portanto $(\varphi \square \psi) \in \Gamma - \{\neg \neg \bot \}$, que é $\Delta$. Da mesma forma podemos mostrar que $\Delta$ satisfaz (3). Como $\Delta$ é menor do que $\Gamma$, pela exclusão de $\neg \neg \bot$ e o conjunto das fórmulas é o menor conjunto satisfazendo (1), (2) e (3), $\neg \neg \bot$ não pertence ao Conjunto das Fórmulas.

É este tipo de procedimento que deve ser executado por um compilador para checar se o código fonte está sintaticamente adequado e caso não esteja, idealmente a implementação do compilador deve avisar o usuário sobre o problema.

Significado

Antes de prosseguir para a tradução, entretanto, o programa deve checar se as expressões a serem computadas possuem significados bem definidos, o que requer atenção, na nossa analogia coma lógica proposicional, aos valores de verdade das proposições e não apenas sua estrutura sintática. Essa análise é chamda de análise semântica e análise sensível ao contexto. Um programa de computador bem formado especifica computações a serem cumpridas quando o programa for executado e há diversas formas pelas quais a nossa expressão:

pode ser mal formada além daquelas puramente sintáticas. Por exemplo, um ou mais nomes podem não estar definidos. A variável $x$ pode não ter valor quando a expressão é executada. As variáveis $y$ e $z$ podem ser de tipos diferentes, os quais não podem ser multiplicados. Antes que o compilador possa traduzir a expressão, ele precisa estar certo de que o programa tem Significado bem definido, no sentido de que segue algumas regras extra-gramaticais.

Criando e mantendo o ambiente de execução (runtime environment)

O artigo até aqui mostra concisamente como linguagens de programação permitem que os seus usuários lidem com abstrações que simplificam o processo de programar. Uma linguagem tem associada a si um conjunto de facilidades com respeito à expressão de computações, e o programador escreve código que implicitamente segue o modelo definido pela linguagem. Isso é visível mesmo em algoritmos simples, como um FizzBuzz.

FizzBuzz em JavaScript:

for (let i = 1; i <= 100; i++) {
    let out = '';
    if (i % 3 === 0) out += 'Fizz';
    if (i % 5 === 0) out += 'Buzz';
    console.log(out || i);
}

FizzBuzz em Scheme:

(define (fizzbuzz x y)
  (println
    (cond (( = (modulo x 15) 0 ) "FizzBuzz")
          (( = (modulo x 3) 0 ) "Fizz")
          (( = (modulo x 5) 0 ) "Buzz")
          (else x)))
 
    (if (< x y) (fizzbuzz (+ x 1) y)))
 
(fizzbuzz 1 100)

O papel dessas abstrações é isolar o programador dos detalhes de baixo nível dos sistemas utilizados, assim sendo, parte do papel do compilador é criar mecânismos eficientes em manter esta ilusão. Um bom exeplo são as linguagem assembly, que permite que escrevamos expressões mnemônicas ao invés de códigos numéricos para operações. Esta ilusão especifica, de que o computador é capaz de compreender nomes alfabéticos ao invés de números binário, é facilmente mantida por uma tabela de consulta (lookup table).

Este exemplo mostra uma abstração importante: nomes simbólicos. O nosso exemplo faz referência a valores de nomes $w$, $x, y$ e $z$. Estes nomes não são simplesmente valores, um único nome pode ter vários valores que um programa executa. Por exemplo, já que $w$ está sendo utilizado do lado direito e esquerdo, ele provavelmente tem atribuições de valores distintos antes e depois da execução da expressão. Portanto $w$ se refere ao valor que está guardado em alguma parte nomeada da memória, ao invés de ter um valor específico, como 20.

Memórias de computadores contemporâneos são organizadas por meio de endereços numéricos, e não nomes textuais. Dentro do espaço de endereçamento de um programa em execução, estes endereços correspondem a partes únicas da memória. Apesar disso, é comum que, como programadores, nós possamos criar várias variáveis distintas com o mesmo nome. $i, j$ e $k$, por exemplo, por serem usualmente usadas como índex de laços costumam ser encontradas em diferentes partes de um programa complexo. Logo, faz parte do papel do compilador mapear cada instância de uso desses símbolos ao endereço de memória correto. Computadores não possuem este tipo de esquema de nomes para endereçamento de memória, essa é uma abstração criada pelo design da linguagem e mantida pelo código gerado pelo compilador e seu ambiente de execução.

Voltando ao nosso exemplo: $w \longleftarrow w \times 2 \times x \times y \times z$, para traduzir, o compilador precisa atribuir algum local de armazenamento para cada nome. Para simplicidade do exemplo assumiremos que a constante 2 não precisa de alocação na memória, já que é um inteiro pequeno e provavelmente pode ser obtido utilizando uma instrução de endereçamento imediato. Isso pode ser feito na memória da seguinte maneira:

0 | w | x | y | z |  

testando

Referências:

1. Cooper, Keith e Linda, Torczon. Engineering a Compiler. Morgan Kaufmann 2011.
2. Dalen, van Dirk. Logic and structure Springer 1994.
3. https://softwareengineering.stackexchange.com/questions/236415/is-machine-language-always-binary