INF1018 - Software Básico (2018.1)
Segundo Trabalho

Outro compilador muito simples

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

A função geracod deverá ler um arquivo texto contendo o código fonte de uma função escrita em SB 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. Também deve ser implementada uma função chamada liberacod, que é responsável por liberar a memória alocada para armazenar o códido de máquina gerado.

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 29 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 podem ser feitos em grupos de dois alunos.

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

A Linguagem SB

Na linguagem SB, 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.

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

Uma atribuição tem a forma varp ':=' varpc
onde var é uma variável local ou um parâmetro e varpc é uma variável local, um parâmetro ou uma constante inteira.
Como exemplo, se temos
```
v1 := p1
v2 := $1
```
o valor do parâmetro p1 será armazenado na variável local v1 e o valor inteiro 1 será armazenado na variável local v2.
Uma operação aritmética tem a forma varp op varpc
onde varp é uma variável local ou um parâmetro, varpc é uma variável local, um parâmetro ou uma constante inteira, e op é um dos operadores '+' '-' '*' seguido de '='.
Como exemplo, se temos
```
v1 *= p1 
p1 += $1
```
o resultado da operação v1 * p1 será armazenado na variável local v1 e o valor do parâmetro p1 será incrementado.
A instrução de desvio condicional tem a forma 'if' varp n1 n2
onde varp é uma variável local ou um parâmetro, e n1 e n2 são números de linhas no código fonte. A semântica dessa instrução é a seguinte:
- se o valor da variável local ou parâmetro é menor que 0, será executado um desvio para a instrução que está na linha n1;
- se o valor da variável local ou parâmetro é igual a 0, será executado um desvio para a instrução que está na linha n2;
- se o valor da variável local ou parâmetro é maior que 0, não há desvio e a execução segue normalmente para a instrução da linha seguinte.
A instrução de desvio incondicional tem a forma 'go' n
onde n é o número da linha no código fonte para onde o controle deverá ser desviado.
Finalmente, a instrução de retorno tem a forma 'ret' varpc
Neste caso, a função deverá retornar, e seu valor de retorno é o valor da variável local, parâmetro ou constante inteira indicada.

A sintaxe da linguagem SB 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!

func	::=	cmd '\n' \| cmd '\n' func
cmd	::=	att \| expr \| dif \| dgo \| ret
att	::=	varp ':=' varpc
expr	::=	varp op varpc
varp	::=	'v' num \| 'p' num
varpc	::=	varp \| '$' snum
op	::=	'+=' \| '-=' \| '*='
ret	::=	'ret' varpc
dif	::=	'if' varp num num
dgo	::=	'go' num
num	::=	digito \| digito num
snum	::=	[-] num
digito	::=	0' \| '1' \| '2' \| '3' \| '4' \| '5' \| '6' \| '7'\| '8' \| '9'

Alguns Exemplos

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

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

O primeiro exemplo implementa uma função f(x) = x + 1 p1 += $1 // 1: x = x + 1 ret p1 // 2: retorna x

O exemplo a seguir implementa uma função que avalia se seu parâmetro é negativo if p1 3 2 // 1: if (p1 < 0) desvia para linha 3 ret $0 // 2: retorna 0 (false) ret $1 // 3: retorna 1 (true)

O próximo exemplo implementa uma função f(x,y) = (x+y) * (x-y) v1 := p1 // 1: i = x v1 += p2 // 2: i = x + y p1 -= p2 // 3: x = x - y v1 *= p1 // 4: i = i * x ret v1 // 5: retorna i

A seguir, a função fatorial fat(n): v1 := $1 // 1: f = 1 if p1 6 6 // 2: if (n ≤ 0) desvia para linha 6 v1 *= p1 // 3: f = f * n p1 -= $1 // 4: n = n - 1 go 2 // 5: desvia para linha 2 ret v1 // 6: retorna f

Finalmente, uma função squad(x) que calcula a soma dos quadrados de 1 a x: v1 := $0 // 1: sum = 0 if p1 8 8 // 2: if (x ≤ 0) desvia para linha 8 v2 := p1 // 3: aux = x v2 *= v2 // 4: aux = x * x v1 += v2 // 5: sum = sum + (x * x) p1 -= $1 // 6: x = x - 1 go 2 // 7: desvia para linha 2 ret v1 // 8: retorna sum

Implementação e Execução

O que fazer

Você deve desenvolver em C uma função chamada geracod, que leia um arquivo de entrada contendo o código fonte uma função na linguagem SB, 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 20 linhas, com um comando SB por linha.

O protótipo de geracod é o seguinte:

typedef int (*funcp) ();
funcp geracod (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 SB. Você também deve implementar uma função chamada liberacod, responsável por liberar a memória alocada para armazenamento do código de máquina. Seu protótipo é

void liberacod (void *pf);

Esses protótipos estão definidos no arquivo geracod.h, disponível aqui.

Implementação

A função geracod 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 geracod será o endereço do início da memória alocada.

Para cada instrução SB imagine qual uma tradução possível para assembly. Além disso, lembre-se que a tradução de uma função SB 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 e valor de retorno. As variáveis locais deverão ser alocadas na pilha de execução.

Para ler e interpretar cada linha da linguagem SB, teste se a linha contém cada um dos formatos possíveis. Veja um esboço de código C para fazer essa interpretação aqui. Lembre-se que você terá que fazer adaptações pois, dentre outros detalhes, essa interpretação não será feita na main!

Não é necessário fazer tratamento de erros no arquivo de entrada, você pode supor que o código fonte SB desse arquivo sempre estará correto.

O código gerado por geracod 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 SB. 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 cada passo implementado!

Por exemplo:

Compile um arquivo assembly contendo uma função bem simples (por exemplo, uma função que retorne o valor do seu parâmetro) usando:
```
minhamaquina> gcc -c code.s
```
e depois veja o código de máquina gerado usando:
```
minhamaquina> objdump -d code.o
```
Construa uma versão inicial da função geracod, que aloque uma área de memória, coloque lá esse código, bem conhecido, e retorne o endereço da área alocada.
Crie uma função main e teste esse primeiro passo.
Implemente e teste a tradução da função SB equivalente: ret p1
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 instruçã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!
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 as funções geracod e liberacod (e funções auxiliares, se for o caso)) e outro arquivo com uma função main para testá-las.

Sua função main deverá abrir um arquivo texto que contém um "programa fonte" na linguagem SB (i.e, uma função SB) e chamar geracod, passando o arquivo aberto como argumento. Em seguida, sua main deverá chamar a função retornada por geracod, passando os parâmetros apropriados.

Por exemplo:

#include "geracod.h"

int main(int argc, char *argv[]) {
  FILE *myfp;
  funcp funcaoSB;
  int res;

  /* Abre o arquivo fonte */
  if ((myfp = fopen("programa", "r")) == NULL) {
    perror("Falha na abertura do arquivo fonte");
    exit(1);
  }
  /* compila a função SB */
  funcaoSB = geracod(myfp);
  fclose(myfp);

  /* chama a função */
  res = (*funcaoSB) (....);  /* passando parâmetro apropriados */
  ...
  liberacod(funcaoSB);
  ...
}

Não esqueça de compilar seu programa com

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

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

Uma sugestão para testar a chamada de uma função SB 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 geracod 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:

Um arquivo fonte chamado geracod.c , contendo as funções geracod e liberacod (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 */
```
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 SB que você usou para testar o seu trabalho. Mostre tanto as funções SB 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.

INF1018 - Software Básico (2018.1) Segundo Trabalho