Linguagens de Programação

Enunciado do Trabalho Prático

Departamento de Informática
Universidade de Évora

2006/2007

Versão 1.01

Objectivo

O objectivo deste trabalho é a criação de uma implementação, em C, da máquina XISC. Esta implementação deverá ler um programa XISC na sua entrada padrão (stdin), executá-lo e terminar quando o programa terminar.

A Máquina XISC

A máquina XISC (iniciais de Xtrange Instruction Set Computer) é uma máquina abstracta simples, preparada para a execução de programas escritos em linguagens estruturadas em blocos, com ligação estática de nomes (lexical scope) e que permitem a definição de funções e procedimentos dentro de funções ou procedimentos.

A memória da máquina XISC divide-se em três zonas distintas:

a memória de instruções, onde são guardadas as instruções do programa a executar, e cujo formato não é especificado;
a pilha de avaliação, que é usada na avaliação de expressões, para a transferência de dados e para guardar o valor devolvido por uma função; e
a memória de execução, onde se encontram os registos de activação dos blocos do programa cuja execução ainda não terminou.

Além daquelas zonas da memória, a máquina XISC possui dois registos: o registo EP, que contém o environment pointer; e o registo PC, com o program counter.

Caso seja considerado útil ou necessário, uma implementação poderá acrescentar outros registos que ajudem a controlar o funcionamento da máquina (como, por exemplo, um registo RA para guardar o endereço de retorno de uma função). Estes registos não poderão conter dados manipulados pelo programa.

A Linguagem Pseudo-C

O Pseudo-C é uma variante da linguagem C que permite a definição de funções locais a uma função. Esta linguagem só permite manipular inteiros e todas as variáveis são globais no corpo da função em que são declaradas, i.e., a definição de uma função tem a forma:

        tipo nome(argumentos formais)
        {
          declarações (de variáveis ou funções)

          instruções
        }

em que as instruções não incluem qualquer declaração de variável ou função.

Outra característica do Pseudo-C é todo o código de um programa constituir a definição da função void main(), como é exemplificado pelo programa seguinte, que calcula e escreve no terminal o valor do factorial de 12:

        void main()
        {
          int fact(int n)
          {
            int i, f = 1;

            for (i = 1; i <= n; ++i)
              f = f * i;

            return f;
          }

          println(fact(12));
        }

Os programas em Pseudo-C são compilados para sequências de instruções XISC, que são, posteriormente, executadas por uma implementação da máquina abstracta. Para o programa anterior, um compilador poderia gerar o seguinte código XISC:

        main:   locals 0 0
                push_int 12
                set_arg 1
                call -1 fact    # calcula fact(12)
                put             # e imprime
                put_nl
                ret

        fact:   locals 1 2
                push_int 1
                store_var 0 2   # f = 1
                push_int 1
                store_var 0 1   # i = 1
        L1:     push_arg 0 1
                push_var 0 1
                jlt L2          # n < i
                push_var 0 2
                push_var 0 1
                mult
                store_var 0 2   # f = f * i
                push_var 0 1
                push_int 1
                add
                store_var 0 1   # i = i + 1
                jump L1
        L2:     push_var 0 2
                ret             # return f

(Nos ficheiros factorial.pc e factorial.xisc encontram-se as duas versões do programa.)

Blocos em Pseudo-C

O corpo de uma função em Pseudo-C constitui um bloco de código.

A profundidade de um bloco é dada pelo número de blocos que o envolvem no texto do programa Pseudo-C. A função main é o único bloco com profundidade 0. No exemplo acima, o outro bloco lá presente, correspondente à função fact, tem profundidade 1.

Não há qualquer restrição quanto à profundidade máxima que um bloco pode ter.

As Instruções XISC

O conjunto de instruções XISC é constituído pelas instruções descritas abaixo. Um programa XISC é uma sequência de instruções XISC, onde cada instrução pode ser identificada por uma etiqueta, no formato:

<etiqueta>: <instrução>

A instruções de um programa XISC são executadas pela ordem em que aparecem no texto do programa, a partir da primeira instrução da função main, identificada pela etiqueta main. A ordem normal de execução das instruções poderá, no entanto, ser alterada devido à execução das instruções de salto ou de alguma das instruções call e ret.

Instruções aritméticas

Estas instruções executam as operações aritméticas da máquina XISC. São instruções que não possuem argumentos, operando sobre o conteúdo da pilha de avaliação.

add: Adição.
sub: Subtracção.
mult: Multiplicação.
div: Divisão (inteira).

O funcionamento destas instruções consiste em quatro passos: 1) o 2º operando é desempilhado da pilha de avaliação; 2) o 1º operando é desempilhado da pilha de avaliação; 3) a operação é efectuada; 4) o resultado é empilhado na pilha de avaliação.

Instruções de salto

Existem duas instruções de salto condicionais e uma incondicional.

jump <etiqueta>: A instrução executada a seguir a esta instrução será a instrução identificada por <etiqueta>. A instrução jump não tem qualquer outro efeito sobre o estado da máquina.
jeq <etiqueta>: Se os dois valores nas duas posições no topo da pilha de avaliação forem iguais, a instrução executada a seguir será a identificada por <etiqueta>; senão, a próxima instrução a executar será a que se segue a jeq na ordem do programa.; Em ambos os casos, os dois valores no topo da pilha de avaliação são desempilhados.
jlt <etiqueta>: Sejam A o valor no topo da pilha de avaliação e B o valor na posição imediatamente abaixo. Se B for menor que A, a instrução executada a seguir será a identificada por <etiqueta>; senão, a próxima instrução a executar será a que se segue a jlt na ordem do programa.; Em ambos os casos, os dois valores no topo da pilha de avaliação são desempilhados.

Instruções de manipulação de inteiros

push_int <inteiro>: Esta instrução empilha o seu argumento, uma constante inteira, na pilha de avaliação.

Instruções de acesso a variáveis

As operações de leitura e de escrita do valor de uma variável são efectuadas através das instruções deste grupo. As variáveis são declaradas no início dos blocos que constituem a definição das funções e não incluem os argumentos das funções.

push_var <inteiro> <inteiro>: Sejam P0 a profundidade do bloco em que uma determinada variável foi declarada, e P1 a profundidade do bloco em que ela está a ser acedida. O 1º argumento de push_var é a diferença entre P1 e P0, ou seja, a distância entre o bloco corrente e aquele em que a variável foi declarada: se a variável é local à função corrente, esse valor é 0; se a variável foi declarada na função dentro da qual a função corrente está definida, esse valor é 1; e assim sucessivamente.; O 2º argumento de push_var é o número da variável no bloco em que foi declarada. O número de uma variável pode ser qualquer, desde que, em cada bloco, todas as variáveis tenham números distintos e consecutivos, começando em 1. Nestas condições, um número de uma variável identifica-a univocamente dentro do seu bloco.; O efeito desta instrução é empilhar, na pilha de avaliação, o valor da variável com número número do bloco cuja profundidade dista distância da do bloco corrente.
store_var <inteiro> <inteiro>: Os dois argumentos desta instrução são como na instrução anterior.; Esta instrução desempilha o valor no topo da pilha de avaliação e atribui-o à variável com número número do bloco cuja profundidade dista distância da do bloco corrente.

Instruções de acesso a argumentos

O papel das instruções XISC deste grupo é o mesmo que o das do grupo anterior, mas em relação aos argumentos das funções.

Em ambas as instruções, o 1º argumento é a distância entre a profundidade da função a que o argumento pertence e a da função que lhe acede, e o 2º é o número de ordem do argumento na lista de argumentos formais da função, cabendo ao primeiro destes o número 1.

push_arg <inteiro> <inteiro>: Empilha, na pilha de avaliação, o valor do argumento com número número da função cuja profundidade dista distância da profundidade da função corrente.
store_arg <inteiro> <inteiro>: Desempilha o valor no topo da pilha de avaliação e atribui-o ao argumento com número número da função cuja profundidade dista distância da profundidade da função corrente.

Instruções para a chamada de funções

As instruções deste grupo processam a chamada de funções, o início e o fim da sua execução, através da manipulação dos registos de activação.

set_arg <inteiro>: Esta instrução desempilha, da pilha de avaliação, o valor de um argumento da função que vai ser chamada, e põe-o numa localização em que esta lhe poderá aceder.; O argumento da instrução indica o número do argumento da função.
call <inteiro> <etiqueta>: Esta instrução efectua a chamada da função cujo nome é dado por <etiqueta>, provocando a transferência da execução para a primeira instrução dessa função. Antes de poder ser utilizada, a instrução set_arg terá de ter sido utilizada, tantas vezes quantos os argumentos da função, para que estes estejam prontos quando a chamada ocorre.; O 1º argumento de call é a distância entre a profundidade da função chamadora e a da função chamada: seja f a função em cujo corpo é chamada a função g: se g está definida nas declarações de f, a distância será -1; se g e f estão definidas dentro da mesma função, a distância será 0; se f está definida nas declarações de g, a distância será 1; e assim sucessivamente.
locals <inteiro> <inteiro>: É a primeira instrução do corpo de uma função e indica quantos argumentos a função tem (o 1º argumento da instrução) e quantas variáveis locais declara (o 2º argumento da instrução).
ret: Termina a execução do corpo de uma função, provocando o retomar da execução da função que a chamou.; Se a função devolver algum valor, este é devolvido através da pilha de avaliação, e já lá deverá ter sido colocado antes de ret ser executada.

Instruções de saída

Através das instruções deste grupo é possível, a um programa, enviar informação para o écrã.

put: Desempilha o valor no topo da pilha de avaliação e escreve-o, como um inteiro, no écrã.
put_str <string>: Escreve a <string> no écrã.
put_nl: Termina a linha corrente na saída do programa. O resultado da execução da próxima instrução de saída aparecerá na linha seguinte do écrã.

Características da Implementação

Linguagem

A implementação da máquina XISC deverá ser feita em C, recorrendo ao gerador de analisadores lexicais flex e ao gerador de analisadores sintácticos bison.

São fornecidos os seguintes ficheiros:

regact.lex: definição do analisador lexical;
regact.y: definição do analisador sintáctico;
Makefile.

O conteúdo destes ficheiros pode ser alterado, excepto no que diz respeito às definições dos símbolos terminais (tokens) e à gramática, a não ser para a introdução de acções semânticas.

As regras contidas no ficheiro Makefile deverão ser tais que os comandos make e make all provocarão a construção de um executável chamado xisc.

Memória da máquina

A memória de instruções terá a estrutura considerada a mais adequada e a pilha de avaliação será uma pilha de valores inteiros. A memória de execução deverá ser encarada como uma sequência de valores não estruturados e deverá ser implementada num vector (de inteiros, de caracteres, ...).

Poderão existir outras estruturas de dados, somente para o controlo do funcionamento da máquina. Estas estruturas não poderão, no entanto, ser usadas durante a execução do programa XISC para manipular os dados com que este trabalha.

Registos de activação

Faz parte da realização do trabalho o desenho dos registos de activação.

Entrada e saída de dados

A implementação da máquina XISC lerá o programa da sua entrada padrão (stdin) e não escreverá nada no écrã, excepto o resultado das instruções de saída incluídas no programa XISC em execução, que deverá ser enviado para a saída padrão da máquina (stdout).

Compilação de código Pseudo-C

Não faz parte do trabalho fazer um compilador de Pseudo-C para código XISC.

Exemplos

A seguir, apresentam-se exemplos de programas em Pseudo-C e, para cada um, uma possível tradução para código XISC.

factorial.pc, factorial.xisc: programa que calcula iterativamente o factorial de 12.
factorial_rec.pc, factorial_rec.xisc: versão recursiva do programa anterior.
factorial_tail.pc, factorial_tail.xisc: versão recursiva terminal do programa anterior.
mdc.pc, mdc.xisc: cálculo do maior divisor comum a dois inteiros.
fibonacci.pc, fibonacci.xisc: implementação recursiva do cálculo dos números de Fibonacci.
dia.pc, dia.xisc: programa que calcula o número de ordem, no ano, do dia correspondente a uma data.
sethi.pc, sethi.xisc: exemplo do uso de variáveis e funções locais.
mixtura.pc, mixtura.xisc: outro exemplo do uso de variáveis e funções locais.
funcfunc.pc, funcfunc.xisc: uma aplicação a uma aplicação.

Relatório

O relatório a entregar deverá incluir:

O desenho dos registos de activação adoptado e a justificação das escolhas feitas.
A descrição da estrutura da implementação da máquina e das estruturas de dados usadas.
A descrição, através de pseudo-código, do funcionamento de cada instrução XISC, tal como implementada no trabalho.
Por exemplo, o pseudo-código para a instrução sub poderia ser:
```
        sub:
          o2 = desempilha()
          o1 = desempilha()
          empilha(o1 - o2)
	  PC = PC + 1
  
```
(considerando que empilha e desempilha são duas primitivas da pilha de avaliação).
Para a instrução jump, poderíamos ter:
```
        jump etiqueta:
	  PC = @etiqueta
  
```
onde @ é um operador unário que devolve o endereço do operando.
(O livro Warren's Abstract Machine: A Tutorial Reconstruction, de Hassan Aït-Kaci, poderá servir de inspiração neste aspecto (ver, por exemplo, as páginas 14 e 30).)
Indicação dos elementos consultados (livros, URI's, ...).

Entrega e Avaliação

O trabalho será realizado por grupos de até dois elementos.

O trabalho será classificado de 0 a 20 valores.

Os elementos a entregar serão:

os ficheiros com o código fonte da implementação da máquina, incluindo os ficheiros com as definições dos analisadores lexical e sintáctico;
uma Makefile com os comandos para a construção da implementação da máquina;
o relatório.

O código entregue deverá ser compilável e funcionar na máquina alunos.di.uevora.pt.

O relatório poderá ser entregue em formato electrónico ou impresso. Se for entregue em formato electrónico, o relatório deverá estar em formato texto, HTML ou PDF (não serão aceites relatórios em formato DOC).

Os ficheiros a entregar deverão ser incluídos num arquivo .tar.gz ou .zip. O arquivo deverá ter nome nnnnn-mmmmm.tar.gz (ou .zip), onde nnnnn e mmmmm deverão ser substituídos pelos números dos elementos do grupo. No caso dos trabalhos individuais, o nome do arquivo deverá ser nnnnn.tar.gz (ou .zip). É da responsabilidade de cada grupo certificar-se de que o arquivo entregue contém exactamente o que pretendiam entregar.

A entrega deverá ser feita, através do moodle, até às 19 horas do dia 3 de Julho de 2007. (Para evitar problemas com entregas em cima da hora limite, a entrega estará aberta até às 23:55.)

Serão avaliadas: a correcção e a eficiência da solução apresentada; a relevância e a completude do relatório; a qualidade, a documentação e a apresentação do código (cada linha não deverá ter mais de 80 caracteres).

O trabalho deverá ser realizado somente por quem o entrega. A detecção de qualquer tentativa de subverter este princípio terá como consequência, para todos os envolvidos, a impossibilidade de obter aprovação à disciplina este ano lectivo.

Os docentes da cadeira agradecem que qualquer erro detectado no enunciado do trabalho lhes seja comunicado.

Bom trabalho.