O objetivo deste trabalho é desenvolver um compilador 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 uma ou mais funções escritas em SB e retornar um ponteiro para uma função C gerada pelo compilador, que contém o código que executa a última função lida.
O arquivo de entrada terá no máximo 100 linhas, com um comando por linha (ver sintaxe).
A linguagem a ser interpretada é simples e contém três tipo de instruções: atribuições, chamadas e retornos condicionais. Além disso, há marcas de início e final de funções.
Uma atribuição tem sempre a forma
var'='var op varsem brancos entre os símbolos, onde
val é uma variável (var) ou uma
constante inteira não negativa,
e op um dos operadores: +, -, *, /.
Todas as variáveis são da forma v[i] ou p[i].
As constantes numéricas são escritas como c[i] para facilitar
a sintaxe.
Uma chamada tem sempre a forma:
'call' num varsem brancos entre os símbolos. O seu significado é que a função de número
num deve
ser chamada com a variável var como parâmetro.
O retorno será sempre armazenado em v[1].
Um retorno condicional tem sempre a forma:
'ret?' varsem brancos entre os símbolos. O seu significado é que, se a variável
var tiver valor igual a
zero, a função deve retornar.
(atenção: Essa variável não contém o valor a ser retornado pela
função, apenas o valor que indica se a função deve retornar ou não!
O valor de retorno vai sempre em v[0].)
Mais formalmente, a sintaxe de nossa mini linguagem é dada por:
func: functionheader cmds endf functionheader: 'function\n' endf: 'end\n' cmds : cmd '\n' | cmd '\n' cmds cmd : att | ret | call 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' call: 'call' num var ret: 'ret?' var
O arquivo de entrada pode conter uma ou mais funções. A primeira função será a de número 0, a segunda a de número 1, e assim por diante, sequencialmente. Esses números são usados em chamadas de funções.
Uma função só pode chamar funções que apareçam antes dela no arquivo de entrada. A última função do arquivo de entrada é a que será chamada pelo programa principal (ver abaixo).
Os nomes p[0] .. p[n] representam
os argumentos recebidos pela última função do arquivo.
Como visto na sintaxe da linguagem, as demais funções recebem
sempre exatamente um parâmetro. A última função do arquivo poderá receber até três argumentos.
Os nomes v[0] .. v[m]
representam variáveis locais.
Cada função usará no máximo 20 variáveis locais.
Cada função usará no máximo 20 variáveis locais.
Os nomes c[0] .. c[m]
representam constantes com o valor do índice.
Cada função gerada irá sempre retornar o valor final em v[0].
O exemplo a seguir ilustra como uma função para o cálculo do fatorial de um número poderia ser implementada nessa linguagem:
function v[0]=c[1]+c[0] ret?p[0] v[1]=p[0]-c[1] call0v[1] v[0]=p[0]*v[1] v[1]=c[0]+c[0] ret?v[1] end
Compila que leia
um arquivo de entrada contendo o código fonte de uma ou mais funções
na linguagem SB, gere o código de máquina IA32 correspondente, e
retorne um ponteiro para função (será um ponteiro para área contendo o código
gerado).
O protótipo de Compila deve ser o seguinte:
typedef int (*funcpointer) (); funcpointer Compila (FILE *f);
Compila recebe como argumento um descritor de arquivo (já aberto para
leitura) de onde deve ser lido o código fonte.
O arquivo ascii contendo os comandos a serem compilados deve ter sempre o nome "programa".
Crie uma main que abra esse arquivo, chame a
função Compila, passando o arquivo aberto como argumento,
em seguida chame a função retornada por Compila e
imprima o retorno dessa função.
Seu programa deve imprimir apenas o valor do inteiro,
nada mais, usando "%d\n" como controle.
A função (ponteiro) retornada por Compila é a tradução da última função lida do arquivo de entrada. Ela pode, por sua vez, chamar as funções anteriores.
Ao chamar a main de seu programa,
ela deve receber como argumentos (na linha de comando,
ou seja, através de argv e argc) entre
um e três inteiros, que devem ser passados para a função criada
por Compila.
A função Compila deve alocar um bloco de memória para escrever
o código gerado.
O que será retornado será um ponteiro para essa área.
(Considere 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 deverá ser o código de máquina, e não
assembly. Ou seja, você deverá descobrir o código de máquina que
corresponde às instruções de assembly que implementam cada uma das duas
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 as atribuições, e somente depois inclua o tratamento das demais instruções.
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 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 essa interpretação não deve ser feita na main!!)
IMPORTANTE: Esse trabalho é bastante grande e 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 -O2 -c code.c(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.oConstrua 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...