INF1018 - Software Básico - 2011.1

Segundo Trabalho: Mini-Compilador

O objetivo deste trabalho é desenvolver um compilador (i.e., uma função de compilação) para uma linguagem de programação bastante simples, chamada SB. A função de compilação deverá ler um arquivo texto contendo o código fonte de uma função escrita em SB e retornar um ponteiro para uma função (gerada pelo compilador) que contém o código que executa a função SB.

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

Leia com atenção o enunciado do trabalho e as intruções para a entrega!

A Linguagem SB

A linguagem SB contém apenas três tipos de instruções: atribuição, desvio e retorno.

Uma atribuição tem a forma

var '=' var op var

onde var pode ser uma variável local, um parâmetro da função ou uma constante inteira (não negativa), e op é um dos operadores: +, -, *.

As variáveis locais são da forma v[i], sendo o índice i utilizado para identificar uma variável (ex. v[0], v[1], etc...). Da mesma forma, os parâmetros são da forma p[i], sendo p[0] o primeiro parâmetro, p[1] o segundo, e assim sucessivamente. A linguagem permite o uso de no máximo 20 variáveis locais e 5 parâmetros.

Na linguagem SB as constantes numéricas são escritas como c[i], onde c[i] equivale à constante i. Por exemplo, a constante c[10] representa o valor 10.

Um desvio tem a forma:

'jcond' var1 var2 num

onde var1 e var2 são variáveis locais, parâmetros ou constantes. Um desvio faz com que o controle seja passado à instrução da linha de número num se o valor de var1 for igual ao de var2.

Finalmente, um retorno tem a forma:

'ret' var

Neste caso, a função deverá retornar e o valor de retorno é o valor de var.

Formalmente, a sintaxe da linguagem SB é dada por:

func ::   cmd '\n' | cmd '\n' func 
cmd  ::    att | desvio | ret
att  ::    var '=' var op var 
var  ::    'v' '[' num ']' | 'p' '[' num ']' | 'c' '[' num ']'
op   ::    '+' | '-' | '*'
num  ::    digito | num digito
digito :: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7'|  '8' |  '9'
desvio :: 'jcond' var var num
ret  ::    'ret' var

Exemplos

O exemplo a seguir mostra a implementação da função f(a,b,c) = a * (b + c) na linguagem SB (os comentários não fazem parte da linguagem). v[0] = p[1] + p[2] //1: i = b + c v[0] = p[0] * v[0] //2: i = a * i ret v[0] //3: retorna i
O próximo exemplo mostra a implementação da função fatorial fat(n): v[0] = c[0] + c[1] //1: i = 0 + 1 jcond p[0] c[0] 6 //2: if (n == 0) goto linha 6 v[0] = v[0] * p[0] //3: i = i * n p[0] = p[0] - c[1] //4: n = n - 1 jcond c[0] c[0] 2 //5: goto linha2 ret v[0] //6: retorna i

O que fazer

Desenvolva, em C, uma função chamada Compila que leia um arquivo de entrada contendo o código fonte de uma função na linguagem SB, gere o código de máquina IA32 correspondente, e retorne um ponteiro para função (será um ponteiro para uma área de memória contendo o código gerado). O protótipo de Compila deve ser o seguinte:

typedef int (*funcp) ();

funcp Compila (FILE *f);

Compila recebe como argumento um descritor de arquivo (já aberto para leitura) de onde deve ser lido o código fonte.

Execução

Você deve criar um arquivo contendo a função Compila e outro arquivo com uma função main para testá-la.

O arquivo texto contendo a função SB a ser compilada deve ter sempre o nome "SB".

Sua função main deverá abrir esse arquivo e chamar a função Compila, passando o arquivo aberto como argumento. Em seguida, sua função main deverá chamar a função retornada por Compila e imprimir o valor de retorno dessa função (isto é, o valor do inteiro retornado), usando "%d\n" como controle de formatação.

A função criada por Compila é a tradução da função lida do arquivo de entrada.

Os argumentos do seu programa (de um a cinco inteiros) devem ser passados na linha de comando, e representam os parâmetros a serem passados para a função criada por Compila. 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 para a função criada por Compila são do argumento 1 em diante.

Implementação

A função Compila deve alocar um bloco de memória para escrever o código gerado. O valor de retorno de Compila será um ponteiro para essa área. (Para simplificar, você pode considerar o número máximo de linhas de arquivo na hora de alocar o bloco de memória para código.)

O código gerado por Compila deverá ser um código de máquina IA-32, 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 cada uma das instruções de nossa linguagem, por exemplo, usando o programa objdump.

Lembre-se que as instruções assembly ocupam um número variável de bytes na memória.

Recomendamos fortemente que você inicialmente faça apenas a geração de código para atribuições e retorno, e somente depois inclua o tratamento da instrução de desvio.

Não é necessário fazer o tratamento de erros do arquivo de entrada, você pode supor que o código nele estará sempre correto. Vale a pena colocar alguns testes (ver programa exemplo abaixo) só 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.

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 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 deve ser feita na main!!)

IMPORTANTE: Esse trabalho é razovelmente complexo. Tente construir seu programa em passos pequenos para poder testar cada parte separadamente. Por exemplo, compile um arquivo C contendo uma função simples usando:

minhamaquina> gcc -m32 -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 um programa inicial que aloque espaço e coloque esse código "colado" do compilador, bem conhecido, para testar um esqueleto inicial.

E assim por diante...

Prazo

O trabalho deve ser entregue até meia-noite do dia 20 de junho por mensagem eletrônica.

Leia com atenção as intruções para entrega a seguir.

Entrega

Deverão ser entregues três arquivos:
1. Um arquivo fonte chamado compila.c, contendo a função Compila. Esse arquivo não deve conter a função main.
2. Um arquivo fonte chamado testa.c contendo sua função main.
3. Um arquivo texto, chamado relatorio.txt contendo um pequeno relatório descrevendo os testes realizados. Esse relatório, além de explicar o que está funcionando e o que não está funcionando, deverá necessariamente conter os progamas SB que você usou para testar o seu trabalho. Mostre tanto os programas SB compilados e executados com sucesso como os que resultaram em erros (se for o caso).
Coloque no início do arquivo fonte, como comentário, os nomes dos integrantes do grupo da seguinte forma:
```
/* Nome_do_Aluno1 Matricula Turma */
/* Nome_do_Aluno2 Matricula Turma */
```
Coloque também no relatorio o nome dos integrantes do grupo
O trabalho deve ser enviado por email para o professor da turma, com subject/assunto "Trabalho 2 - Software Basico". Indique claramente os integrantes do grupo no corpo do email e inclua, como anexo, os arquivo "compila.c" e "relatorio.txt".

Observações

Os trabalhos podem ser feitos em grupos de até dois alunos. Caso alunos de turmas diferentes queiram formar um grupo, isso deve ser avisado aos dois professores com antecedência de pelo menos uma semana de entrega dos trabalhos. O trabalho deverá ser entregue aos dois professores.
O prazo de entrega é dia 20/06. Os trabalhos perderão um ponto por cada dia de atraso.
muito importante: Em caso de dúvidas, não invente. Pergunte!