INF1018 - Software Básico (2017.1)
Segundo Trabalho

Um compilador muito simples

O objetivo deste trabalho é desenvolver, em C, uma função compila que implementa um pequeno gerador de código (um "micro-compilador") para uma linguagem de programação muito simples, chamada Simples.

A função compila deverá ler um arquivo texto contendo o código fonte de uma função escrita em Simples e retornar um ponteiro para o início da região de memória que contém o código de máquina que corresponde à tradução da função contida no arquivo.

A região de memória que armazena o código gerado deve ser alocada dinamicamente.

Instruções Gerais

---

Leia com atenção o enunciado do trabalho e as instruções para a entrega. Em caso de dúvidas, não invente. Pergunte!

---

O trabalho deve ser entregue até meia-noite (23:59) do dia 19 de junho.

Trabalhos entregues com atraso perderão um ponto por dia de atraso.

Trabalhos que não compilem não serão considerados (ou seja, receberão grau zero).

Os trabalhos devem preferencialmente ser feitos em grupos de dois alunos

Alguns grupos poderão ser chamados para apresentações orais / demonstrações dos trabalhos entregues.

---

A Linguagem Simples

Funções na linguagem Simples contém atribuições, operações aritméticas, instruções de desvio e de retorno.

• Uma atribuição tem a forma

  varp '=' expr
  

  onde varp é uma variável local ou um parâmetro e expr é uma operação aritmética.

• Uma operação aritmética tem a forma

  varpc op varpc
  

  onde varpc é uma variável local, um parâmetro ou uma constante inteira e op é um dos operadores: + - *

• A instrução de desvio tem a forma

  'if' varp num
  

  onde varp é uma variável local ou um parâmetro e num é o número da linha no código fonte para a qual o controle deve ser desviado caso o valor de varp seja diferente de zero.

• Finalmente, a instrução de retorno tem a forma

  'ret' 
  

  Neste caso, a função deverá retornar, e seu valor de retorno é o valor da variável local v1.

Na linguagem Simples, as variáveis locais são da forma vi, sendo o índice i utilizado para identificar a variável (ex. v1, v2, etc...). A linguagem permite o uso de no máximo 4 variáveis locais.

Da mesma forma, os parâmetros são denotados por pi, e podem ser usados no máximo 2 parâmetros (p1 e p2).

Constantes são escritas na forma $i, onde i é um valor inteiro, com um sinal opcional. Por exemplo, $10 representa o valor 10 e $-10 representa o valor -10.

A sintaxe da linguagem Simples pode ser definida formalmente como abaixo. Note que as cadeias entre ' ' são símbolos terminais da linguagem: os caracteres ' não aparecem nos comandos!

---

Alguns Exemplos

Veja a seguir alguns exemplos de funções Simples.

Note que os comentários não fazem parte da linguagem! Eles estão incluidos nos exemplos abaixo apenas para facilitar seu entendimento.

• O exemplo abaixo implementa uma função f(x) = x + 1

  v1 = p1 + $1          // 1: i = x + 1
  ret                   // 2: retorna i
  

• O próximo exemplo implementa uma função f(x,y) = (x+y) * (x-y):

  v1 = p1 + p2          // 1: i = x + y
  p1 = p1 - p2          // 2: x = x - y
  v1 = v1 * p1          // 3: i = i + x
  ret                   // 4: retorna i
  

• O próximo exemplo é uma função fatorial fat(n):

  v1 = $0 + $1          // 1: f = 1
  if p1 4               // 2: if (n != 0) desvia para linha 4
  ret                   // 3: retorna f
  v1 = v1 * p1          // 4: f = f * n
  p1 = p1 - $1          // 5: n = n - 1
  if p1 4               // 6: if (n != 0) desvia para linha 4
  ret                   // 7: retorna f
  

• Finalmente, uma função squad(x) que calcula a soma dos quadrados de 1 a x:

  v1 = $0 + $0          // 1: sum = 0
  v2 = $1 + $0          // 2: i = 1
  p1 = p1 + $1          // 3: x = x + 1
  v3 = p1 - v2          // 4: aux = x - i  (será zero se x == i)
  if v3 7               // 5: if (aux != 0) desvia para linha 7
  ret                   // 6: retorna sum
  v3 = v2 * v2          // 7: aux = i * i
  v1 = v1 + v3          // 8: sum = sum + aux
  v2 = v2 + $1          // 9: i = i + 1
  if v2 4               // 10: if (i != 0) desvia para linha 4 (sempre desviará)
  

---

Implementação e Execução

O que fazer

Você deve desenvolver em C uma função chamada compila, que leia um arquivo de entrada contendo o código fonte uma função na linguagem Simples, gere o código de máquina correspondente, e retorne o endereço da região de memória que contém o código gerado (um bloco de memória alocado dinamicamente).

O arquivo de entrada terá no máximo 50 linhas, com um comando Simples por linha.

O protótipo de compila é o seguinte:

typedef int (*funcp) ();
funcp compila (FILE *f);

O parâmetro f é o descritor de um arquivo texto, já aberto para leitura, de onde deve ser lido o código fonte da função escrita em Simples.

Implementação

A função compila deve alocar um bloco de memória onde armazenará o código gerado (lembre-se que as instruções de máquina ocupam um número variável de bytes na memória!). O endereço retornado por compila será o endereço do início da memória alocada.

Para cada instrução Simples imagine qual uma tradução possível para assembly. Além disso, lembre-se que a tradução de uma função Simples deve começar com o prólogo usual (preparação do registro de ativação, incluindo o espaço para variáveis locais) e terminar com a finalização padrão (liberação do registro de ativação antes do retorno da função).

O código gerado deverá seguir as convenções de C/Linux quanto à passagem de parâmetros, valor de retorno e salvamento de registradores (se for o caso). As variáveis locais deverão ser alocadas na pilha de execução.

Para ler e interpretar cada linha da linguagem Simples, teste se a linha contém cada um dos formatos possíveis.

Não é necessário fazer tratamento de erros no arquivo de entrada, você pode supor que o código fonte Simples desse arquivo está correto. Vale a pena colocar alguns testes para facilitar a própria depuração do seu código, mas as entradas usadas como testes na correção do trabalho sempre estarão corretas.

Veja um esboço de código C para fazer a interpretação de código aqui. Lembre-se que você terá que fazer adaptações pois, dentre outros detalhes, essa interpretação não será feita na main!

O código gerado por compila deverá ser um código de máquina x86-64, e não um código fonte assembly. Ou seja, você deverá descobrir o código de máquina que corresponde às instruções de assembly que implementam a tradução das instruções da linguagem Simples. Para isso, você pode usar o programa objdump e, se necessário, uma documentação das instruções da Intel.

Por exemplo, para descobrir o código gerado por movl %eax, %ecx, você pode criar um arquivo meuteste.s contendo apenas essa instrução, traduzi-lo com o gcc (usando a opção -c) para gerar um arquivo objeto meuteste.o, e usar o comando

objdump -d meuteste.o

para ver o código de máquina gerado.

Estratégia de Implementação

Implemente sua solução passo a passo, testando separadamente cada passo implementado!

Por exemplo:

1. Compile um arquivo assembly contendo uma função bem simples usando:

   minhamaquina> gcc -c code.s
   

   (para apenas compilar e não gerar o executável) e depois veja o código de máquina gerado usando:

   minhamaquina> objdump -d code.o
   

   Construa uma versão inicial da função compila, que aloque uma área de memória, coloque lá esse código, bem conhecido, e retorne o endereço da área alocada como os dois retornos de compila (os retornos são iguais pois só há uma função no código).

   Crie uma função main e teste essa versão inicial da função (leia o próximo item para ver como fazê-lo).

2. Implemente e teste a tradução de uma função bem simples, como o exemplo a seguir (repare que neste caso precisamos apenas de uma atribuição e uma operação de soma de constantes):

   v1 = $0 + $1 // 1: i = 1
   ret          // 2: retorna i
   

   Pense em que informações você precisa extrair para poder traduzir as instruções (quais são os operandos, qual é a operação, onde armazenar o resultado da operação).

   Continue sua implementação, implementando e testando uma operação por vez. Experimente usar constantes, parâmetros, variáveis locais, e combinações desses tipos como operandos.

   Lembre-se que é necessário alocar espaço (na pilha) para as variáveis locais!

3. Deixe para implementar a instrução de desvio apenas quando todo o resto estiver funcionando!

   Pense em que informações você precisa guardar para traduzir essas instruções (note que você precisa saber qual o endereço da instrução correspondente à linha para onde o controle deve ser desviado...)

Testando o gerador de código

Você deve criar um arquivo contendo apenas a função compila (e funções auxiliares) e outro arquivo com uma função main para testá-la.

Sua função main deverá abrir um arquivo texto que contém um "programa fonte" na linguagem Simples (i.e, uma função Simples) e chamar compila, passando o arquivo aberto como argumento.

Em seguida, sua main deverá chamar a função retornada por compila, passando os parâmetros apropriados, e imprimir o valor de retorno dessa função (um valor inteiro).

Não esqueça de compilar seu programa com

gcc -Wall -Wa,--execstack -o seuprograma seuprograma.c

para permitir a execução do código de máquina criado por compila!

Uma sugestão para testar a chamada de uma função Simples com diferentes argumentos, é sua função main receber argumentos passados na linha de comando. Para ter acesso a esses argumentos (representados por strings), a sua função main deve ser declarada como

int main(int argc, char *argv[])

sendo argc o número de argumentos fornecidos na linha de comando e argv um array de ponteiros para strings (os argumentos).

Note que o primeiro argumento para main (argv[0]) é sempre o nome do seu executável. Os parâmetros que deverão ser passados para a função criada por compila serão os argumentos de 1 em diante, convertidos para um valor inteiro (você pode usar a função atoi para fazer essa conversão).

---

Entrega

Deverão ser entregues via Moodle dois arquivos:

1. Um arquivo fonte chamado compila.c , contendo as função compila (e funções auxiliares, se for o caso).
   • Esse arquivo não deve conter a função main.
   • Coloque no início do arquivo, como comentário, os nomes dos integrantes do grupo da seguinte forma:

     /* Nome_do_Aluno1 Matricula Turma */
     /* Nome_do_Aluno2 Matricula Turma */
     

2. Um arquivo texto, chamado relatorio.txt, contendo um pequeno relatório.
   • O relatório deverá explicar o que está funcionando e o que não está funcionando. Não é necessário documentar sua função no relatório. Seu código deverá ser claro o suficiente para que isso não seja necessário.
   • O relatório deverá conter também alguns exemplos de funções da linguagem Simples que você usou para testar o seu trabalho. Mostre tanto as funções Simples traduzidas e executadas com sucesso como as que resultaram em erros (se for o caso).
   • Coloque também no relatório o nome dos integrantes do grupo

Indique na área de texto da tarefa do Moodle o nome dos integrantes do grupo. Apenas uma entrega é necessária (usando o login de um dos integrantes do grupo) se os dois integrantes pertencerem à mesma turma.