Trabalho Prático II
Programação Imperativa (PI2008)
José Carlos Ramalho
Alberto Simões
2008-05-26
Revisão: foram feitas várias correcções de modo a tornar o enunciado mais coincidente com o
da disciplina de "Sistemas de Computação".
2008-04-05
Revisão: foi introduzida a definição da linguagem MSP.
2008-03-21
Revisão: foram introduzidas melhorias ao enunciada da primeira
fase.
2008-03-06
Criada a primeira versão.
Palavras-chave: Programação Imperativa, Trabalho Prático, C
Este documento descreve o único tema disponível para a realização do trabalho
prático que os alunos a fazer a disciplina em epígrafe têm de realizar de forma a
obter uma avaliação prática à disciplina.
Ao longo de várias semanas, irá evoluindo e sofrendo alterações. Esteja atento às
datas de revisões e aos comentários sobre as alterações introduzidas.
1. Objectivos de formação e resultados de aprendizagem
Este projecto tem como objectivos principais a formação genérica e específica de
estudantes em fundamentos de computação na área da programação imperativa.
Os objectivos de formação genérica incluem: (i) a pesquisa, análise e selecção de
informação, (ii) o treino na resolução de problemas, (iii) o desenvolvimento da
capacidade de análise, e (iv) o desenvolvimento da capacidade de comunicação escrita
e oral.
Os objectivos de formação específica incluem: (i) a análise da especificação e do
problema, (ii) o desenvolvimento de algoritmos e consequente programação numa
linguagem imperativa, (iii) a execução e realização de testes de conformidade.
A avaliação dos resultados esperados de aprendizagem irão verificar se as/os
estudantes conseguem demonstrar ter adquirido o seguinte conjunto de competências
genéricas e específicas:
- competências genéricas
- a capacidade de comunicação escrita e oral na apresentação e discussão
dos processos usados e resultados obtidos;
- a capacidade de utilização de utilitários genéricos de informática em
ambiente Linux e de elaboração de documentos anotados
- competências específicas de Programação Imperativa
- a capacidade de desenvolver algoritmos para resolver problemas, de
forma criativa, criteriosa e crítica, e inserida/o num grupo de trabalho
- o conhecimento e a capacidade de codificar algoritmos e estruturas de
dados segundo os princípios da programação estruturada
- a capacidade e aptidões práticas para gerar, executar e testar
programas codificados em C, usando um conjunto adequado de utilitários
(GNU)
- o conhecimento e as aptidões de desenvolver e aplicar testes de
conformidade e de analisar situações de fronteira na execução de
programas
- capacidade e aptidões na produção de documentação adequada à
manutenção por terceiros dos programas desenvolvidos
2. Tema: "Mais Simples Possível (MSP)"
O tema escolhido para este projecto foi o da criação de uma máquina de
stack
virtual e do respectivo ambiente de edição e execução.
A máquina virtual será programada em
Assembly
numa linguagem muito simples
definida para este contexto, o MSP.
O MSP é uma linguagem simples, com um número de instruções reduzido e com uma
sintaxe e uma semântica bastante acessíveis. O MSP destina-se a programar uma
Máquina de
Stack
Virtual. Como se verá mais à frente, é recorrendo a uma
stack
que a máquina efectua os seus cálculos. A designação de virtual
surge do facto de que tal máquina não tem existência real, sendo, neste caso, da
vossa responsabilidade a criação da ilusão de que ela existe.
Este trabalho será dividido em duas fases. Na primeira fase serás responsável pela
criação da interface da máquina: edição de programas, carregamento, armazenamento e
execução. Na segunda fase, terás de criar a máquina de stack e de executar nela os
programas entretanto criados.
Os objectivos a atingir para a primeira fase aparecem descritos no capítulo
3. Enquanto que os objectivos a atingir na segunda fase, uma
vez que são mais complexos, encontram-se descritos nos capítulos seguintes.
Resumindo, podemos enumerar na seguinte lista os objectivos a atingir na primeira
fase:
- Especificação do modelo de dados para suportar o ambiente de edição,
manipulação e execução de programas: programa (linhas de código), historial de
comandos, ...
- Especificação e implementação das funcionalidades descritas no capítulo 3.
- Elaboração do respectivo relatório em LaTeX.
A seu tempo colocaremos aaqui os objectivos a atingir na segunda fase.
3. Ambiente de programação: "Vamos voltar aos anos 80"
O ambiente de programação que se pretende criar é muito semelhante ao que existia
para as máquinas pessoais tipo
ZX Spectrum
nos anos 80.
Basicamente, um utilizador tem um monitor de caracteres à frente com uma área de
trabalho útil de 25 linhas, em que cada linha tem 80 colunas. Por baixo dessas 25
linhas, existe uma linha especial que é a
prompt
de interacção. É nesta linha
que o utilizador introduz os comandos do ambiente que levarão à criação e execução
de programas.
Na figura
1 podemos ver o aspecto geral do ambiente.
No início, se o sistema fôr invocado sem nenhum programa:
$msp
O sistema deverá aparecer com o aspecto da figura
1.
No entanto, se o sistema fôr invocado com um programa:
$msp prog1.msp
O ambiente deverá apresentar as primeiras 25 linhas do programa (se este tiver mais
de 25) e reflectir na linha de status a informação relativa ao programa que foi
carregado (como se pode ver na figura
2).
Pode encarar este ambiente como um editor de texto parecido com o
vi
que
acompanha normalmente o sistema operativo Linux.
O ambiente tem no topo uma linha de status para dar alguma informação ao
utilizador: qual o ficheiro que está a ser editado, quantas linhas contem esse
ficheiro,... Em baixo tem uma linha especial que será o ponto de entrada de comandos
por parte do utilizador. Será nesta linha que o utiizador introduzirá comandos aos
quais o ambiente deverá reagir.
Também à semelhança do
vi
o ambiente terá dois tipos de comandos:
- um primeiro tipo correspondente ao carregamento de programas, armazenamento,
execução de um programa, listagem de um programa,...
- um segundo tipo correspondente aos comandos de edição de um programa:
acrescentar uma linha, apagar linhas, posicionar em determinada linha,
...
Quando tiver tempo, poderá sofisticar a interface do sistema fazendo com que esta
aceite abreviaturas dos comandos.
Estes dois tipos de comandos enumeram-se e descrevem-se nas subsecções seguintes.
3.1. Comandos de Operação
Nesta secção apresentam-se os comandos operacionais que o seu sistema deverá
suportar. Tome as descrições seguintes como guias e não se deixe limitar por
elas.
Use a imaginação...
O sistema deverá aceitar os seguintes comandos operacionais:
- load <ficheiro>
- Carregamento de programas: se o ficheiro existir na directoria corrente o
ambiente deverá carregá-lo exibindo depois um écran semelhante ao mostrado
na figura 2. O ambiente deverá reagir com uma mensagem de
erro à inexistência do ficheiro na directoria corrente. No caso deste
comando ser dado com um programa já a ser editado, o utilizador deverá ser
consultado quanto ao armazenamento do programa que estava a ser editado
antes do novo ser carregado.
- save <ficheiro>
- Armazenamento de programas: o ambiente deverá gravar o programa corrente no
ficheiro designado. Se o nome do ficheiro fornecido diferir do ficheiro que
estava a ser editado, o sistema deverá assumir este como o ficheiro actual
para edição e deverá actualizar a linha de status.
- history
- Historial de comandos: à semelhança de um sistema Unix este comando permite
listar todos os comandos introduzidos pelo utilizador até ao momento. Como
resultado deste comando o écran deverá exibir os útimos 25 comandos dados
pelo utilizador numerados de 1 a 25. Depois da listagem, a introdução de um
'\n'
na linha de comando fará regressar o sistema ao estado
anterior.
- com <n>
- Execução de comandos anteriores: o
n
corresponde ao número de ordem
de um comando anterior (dado pelo número de linha do editor); como resultado
o sistema deverá voltar a executar esse comando.
- hsave <ficheiro>
- Armazenamento do historial num ficheiro: o ambiente deverá o historial no
ficheiro designado (mais tarde poderá ser interessante olhar para a
descrição da interacção ocorrida numa sessão).
- clear
- Reset do sistema: após este comando o sistema volta ao seu estado inical
descartando tudo o que está a ser feito (programa que se está a editar e a
memória de todos os comandos dados até ao momento; eventualmente, poderá ser
pedido ao utilizador que confirme a execução deste comando.
- run
- Execução do programa que está no editor.
- help
- Lista os comandos disponíveis.
- exit
- Saída e abondono do sistema: todos os recursos alocados em tempo de execução
deverão ser libertados.
3.2. Comandos de Edição
Estes comandos estão relacionados com a introdução/criação/alteração dos
programas no sistema e têm uma estrutura diferente: começam todos por número de
linha, a seguir têm o nome do comando seguido de opções caso as haja.
- <int> go
- Posicionamento da janela de visualização: após este comando a primeira linha
da janela deverá corresponder à linha com número:
<int>
.
- <int> insert <comando msp>
- Inserção de uma linha nova: a nova linha deverá ser inserida imediatamente
antes da linha com número
<int>
e o seu conteúdo será
<comando msp>
.
- <int> append <comando msp>
- Acrescento de uma linha: a nova linha deverá ser acrescentada imediatamente
a seguir à linha com número
<int>
e o seu conteúdo será
<comando msp>
.
- <int> delete
- Apagar uma linha: a linha com número <int> deverá ser apagada.
- <int> replace <comando msp>
- Substituir uma linha: a linha com número <int> é substituída
pelo novo <comando msp> introduzido pelo utilizador.
4. Máquina Virtual de Stack
Numa Máquina de
Stack
, podem-se identificar os seguintes blocos:
- Memória
- Área lógica para armazenamento de instruções e valores. Divide-se em 3 blocos
independentes com funcionalidades distintas:
- Memória de Programa (ou abreviadamnte MProg);
- Memória de Dados (ou MDados);
- Memória de Trabalho (Stack).
- Descodificador
- Unidade encarregue de interpretar e mandar executar cada instrução;
- Unidade Lógica e Aritmética
- Unidade que tem a responsabilidade de efectuar as operações lógicas e aritméticas (na nossa máquina será materializada
num conjunto de funções que efectuarão as operações referidas);
- Input e Output
- São duas posições de memória especiais, com endereços fixos e bem conhecidos:
input
e
output
; Têm a
característica especial de estarem ligadas ao exterior, permitindo a entrada de valores para a máquina (
input
)
e a saída de valores da máquina (
output
); em concreto, estas células de memória estão ligadas ao teclado (
input
)
e ao monitor (
output
).
- Bus Interno
- É o "corredor" lógico qu liga as várias unidades permitindo a circulação e comunicação de instruções e valores (na
nossa máquina implementada em C não terá uma materialização concreta).
- Instruction Pointer (IP) e Stack Pointer (SP)
- São os únicos registos da nossa máquina. O IP contem sempre, num dado instante, o endereço da próxima instrução que
deve ser executada (endereço de MProg). O SP contem o endereço da última posição ocupada na
Stack
(ou seja, a posição
do valor no
topo
da
Stack
).
A figura
3 apresenta a arquitectura da Máquina de Stack de acordo com os blocos funcionais descritos
anteriormente.
Cada célula de memória (
MProg
,
MDados
ou
Stack
) tem capacidade para armazenar 2
bytes
(sequência de 16
bits
) e está associada a um enedereço que a identifica univocamente.
Um endereço é um número inteiro que tem o valor 0 para a primeira posição de memória e sofre
incrementos de 1 para as posições seguintes até à última célula. Nesta máquina virtual definiu-se o
valor 65536 como o número total de células de memória. Portanto, a gama de endereços possíveis na
nossa máquina virtual é dada pelo seguinte intervalo: [0, 65535].
O valor que é armazenado em determinada célula de memória pode representar uma instrução, um
argumento de uma instrução, um valor inteiro (como veremos mais à frente num dos intervalos: [0, 65536]
ou [-32767, +32767]), um carácter ou um componente de um endereço.
A interpretação do significado de cada valor é da responsabilidade da máquina e baseia-se no tipo
de memória à qual se está a aceder em determinado instante:
- Memória de Programa (MProg)
- Armazena as instruções que vão ser executadas pela máquina. Um
programa
é uma
sequência de instruções
armazenadas na MProg. Uma célula da MProg pode conter o
código de uma instrução ou o argumento de uma instrução. A maioria das instruções da linguagem
MSP não contem argumentos. Os argumentos, se existirem, localizam-se nas posições seguintes à
do código da instrução.
- Memória de Dados (MDados)
- Armazena valores. Esses valores correspondem aos dados do problema ou aos resultados
calculados pelo programa. Cada valor ocupa dois
bytes
, podendo representar grandezas
numéricas no intervalo [-32768,32767], ou caracteres (pelo seu código ASCII respectivo), ou
ainda
endereços de células da MDados.
- Stack
- Memória de trabalho semelhante no conteúdo à MDados. Contudo, é acedida e usada segundo uma
filosofia LIFO ("Last In First Out"): os valores que se vão introduzindo na
Stack
ficam
empilhados uns por cima dos outros, de tal forma que apenas se pode aceder (ler, consultar) o
valor que está no cimo (topo) da
Stack
, e que corresponde ao último valor que lá foi
armazenado. Assim, apenas é necessário conhecer um único endereço: o da última posição, ou topo
da
Stack
. Considera-se que o topo é o endereço da
Stack
relativo ao último valor
armazenado. O próximo valor a guardar na
Stack
será armazenado no endereço a seguir ao
topo, e o primeiro valor a sair será sempre o do topo. A Máquina de
Stack
foi desenhada
de tal forma que todas as operações esperam ter os seus operandos armazenados em posições
consecutivas a partir do topo, retiram-nos de lá e, em sua substituição, coloca-se no topo o
resultado da sua computação. Na Máquina de
Stack
, o topo "cresce do fim para o
princípio", ou seja, do último endereço disponível (65535) em direcção ao primeiro (0).
5. Funcionamento
Para um programa ser executado o IP é carregado com o endereço de MProg onde está a primeira
instrução a ser executada (como no nosso caso estamos a interpretar linha a linha o programa, bas
ta a indicação do número de linha onde está a primeira instrução).
A partir daqui o funcionamento é sistemático: descodifica-se a instrução, dão-se as ordens
necessárias para a executar, e coloca-se no IP a indicação da próxima instrução a executar
(atenção que na maior parte dos casos esta será a instrução seguinte mas no caso de haver saltos
poderá ser outra qualquer).
Este processo continua até que seja executada a instrução que manda parar a execução do
programa.
Como exemplo de acções a realizar para executar uma dada instrução podemos apresentar entre
outras as seguintes:
- transferência de dados entre o topo da Stack e uma das células especiais
input
ou
output
;
- realização de uma operação aritmética (adição, subtracção, multiplicação ou divisão) ou
lógica (conjunção, disjunção ou negação);
- alteração da sequência normal de execução do programa forçando o IP a tomar um valor que
não é o da linha seguinte.
6. Linguagem MSP
Relativamente à linguagem MSP, e quando se estiver a analisar a linguagem, convem estar
atento aos seguintes pormenores:
- em cada linha da Zona de Dados (limitada por
MEMORIA DE DADOS
e
por
CODIGO
)
e da Zona de Código (limitada por
CODIGO
e estendendo-se até à última
linha do texto do programa) não é permitida mais do que uma declaração de variável e de
label
respectivamente; também não é permitida mais de uma instrução em cada linha da
Zona de Código;
- são permitidas linhas vazias ou de comentário em qualquer parte da Zona de Dados e de
Código;
- os identificadoes de variáveis ou
labels
devem começar por letra podendo
seguir-se-lhe mais letras, digitos ou o carácter
underscore
;
- a presença dos delimitadores das Zonas de Dados e Código (
MEMORIA DE
DADOS
e
CODIGO
) é obrigatória mesmo que estas
estejam vazias;
- um comentário começa pelo carácter ';' ao qual pode seguir-se qualquer sequência de
caracteres que não inclua o fim de linha, que termina o comentário;
- em números positivos o sinal '+' é opcional; nos números negativos o sinal '-' é
obrigatório.
6.1. Sintaxe e Semântica
6.1.1. Zona de Dados: declaração de variáveis
A Zona de Dados é iniciada pelas palavras reservadas
MEMORIA de
DADOS
e prolonga-se até ao início da Zona de Código, iniciada pela palavra
reservada
CODIGO
.
É na Zona de Dados que se declaram e podem inicializar as variáveis que irão ser
utilizadas pelo programa.
A declaração de uma variável tem a seguinte forma:
identificador-variável endereço TAM tamanho VAL valor1 valor2 ... valorn
Por exemplo:
x 100 TAM 20 VAL 4
Declara uma variável com identificador "
x
", no endereço 100, com tamanho 20 e com o
primeiro
valor
inicializado com 4 (os
valores
nos endereços 101 ao 119 são
inicializados por omissão com o valor 0).
A smântica das declarações compreende as seguintes características:
- cada identificador de variável é único, não podendo haver mais que uma variável com o
mesmo identificador;
- não é obrigatório declarar variáveis contiguamente, a partir do endereço 0, podendo-se
deixar buracos na Memória de Dados;
- o espaço reservado para uma variável não pode colidir com o reservado para outra, i.e.,
os intervalos [endereço, endereço+tamanho-1] têm de ser mutuamente exclusivos para todas as
variáveis declaradas;
- a inicialização do espaço alocado a uma variável é facultativa, sendo garantida, por
omissão, a inicialização desse espaço com o valor 0;
- a iniciliazção das variáveis pode ser feita com qualquer valor inteiro no intervalo
[-128, 255];
- é possível não declarar qualquer variável na Memória de Dados; neste caso, qualquer
acesso que se faça a esta Memória deverá ter em conta uma inicialização a 0 desse espaço.
6.1.2. Zona de Código: instruções
A Zona de Código inicia-se pela palavra reservada
CODIGO
e
prolonga-se até ao fim do texto.
O conjunto das instruções pode-se dividir em três grupos de acordo com as repectivas
funcionalidades: instruções para manipulação de valores e endereços, instruções aritméticas e
lógicas e instruções de controlo da sequência de execução do progrma.
6.1.2.1. Manipulação de Valores e Endereços
- PUSH [valor]
- Coloca
valor
no topo da Stack;
- PSHA [endereço ou identificador de variável]
- Coloca o endereço fornecido ou o endereço da variável correspondente ao identificador
fornecido no topo da Stack;
- LOAD
- Retira da Stack um endereço e vai buscar a essa posição de memória o valor lá armazenado
que coloca no topo da Stack;
- LDA
- Retira da Stack um endereço e vai buscar a essa posição de memória um endereço que coloca
no topo da Stack;
- STORE
- Retira da Stack primeiro um valor, depois um endereço e coloca na posição da Memória de
Dados referente ao endereço o valor retirado inicialmente da Stack;
- STRA
- Retira da Stack primeiro um endereço, depois outro endereço e coloca na posição da Memória de
Dados referente ao segundo endereço o primeiro endereço retirado da Stack;
- IN
- Coloca no topo da Stack o conteúdo da posição especial
input
resultante da leitura de um valor via teclado;
- OUT
- Escreve no monitor o valor que é retirado do topo da Stack;
- INC
- Coloca na Stack o conteúdo (código ASCII) da posição especial
input
, resultante
da leitura de um carácter via teclado;
- OUTC
- Escreve no monitor o carácter cujo código ASCII é retirado da Stack;
Observações: as instruções
PUSH, LOAD
e
STORE
operam sobre valores inteiros enquanto que
PSHA, LDA
e
STRA
operam sobre endereços.
6.1.2.2. Instruções Aritméticas e Lógicas
- ADD
- Retira dois inteiros da Stack, soma-os e coloca na Stack o resultado;
- SUB
- Retira dois inteiros da Stack, subtrai o segundo ao primeiro e coloca na Stack o resultado;
- MUL
- Retira dois inteiros da Stack, multiplica-os-os e coloca na Stack o resultado;
- DIV
- Retira dois inteiros da Stack, divide o primeiro pelo segundo e coloca na Stack o resultado;
- ADDA
- Retira um inteiro e um endereço da Stack; soma o inteiro ao endereço calculando um novo
endereço que é por fim colocado na Stack;
- AND
- Retira dois inteiros da Stack, calcula a sua conjunção lógica e coloca na Stack o resultado;
- OR
- Retira dois inteiros da Stack, calcula a sua disjunção lógica e coloca na Stack o resultado;
- NOT
- Retira um inteiro da Stack, calcula a sua negação lógica e coloca na Stack o resultado;
- EQ
- Retira dois inteiros da Stack, verifica se são iguais e coloca na Stack o resultado da
comparação;
- NE
- Retira dois inteiros da Stack, verifica se são diferentes e coloca na Stack o resultado da
comparação;
- LT
- Retira dois inteiros da Stack, verifica se o primeiro é menor que o segundo e coloca na
Stack o resultado dessa
comparação;
- LE
- Retira dois inteiros da Stack, verifica se o primeiro é menor ou igual que o segundo e coloca na
Stack o resultado dessa
comparação;
- GT
- Retira dois inteiros da Stack, verifica se o primeiro é maior que o segundo e coloca na
Stack o resultado dessa
comparação;
- GE
- Retira dois inteiros da Stack, verifica se o primeiro é maior ou igual que o segundo e coloca na
Stack o resultado dessa
comparação;
- ANDB
- Retira dois inteiros da Stack, calcula a sua conjunção
bit-a-bit
e coloca na Stack o resultado;
- ORB
- Retira dois inteiros da Stack, calcula a sua disjunção
bit-a-bit
e coloca na Stack o resultado;
- NOTB
- Retira um inteiro da Stack, calcula a sua negação
bit-a-bit
e coloca na Stack o resultado;
Observações:
- Em todas as operações binárias o segundo operando é retirado da Stack antes do
primeiro;
- À excepção de
ADDA
, cujo resultado é um endereço, todas as outras operações
resultam num inteiro;
- Nas operações lógicas, o resultado é 0 (FALSO) ou 1 (VERDADEIRO);
6.1.2.3. Instruções de Controlo
- JMP [id-label ou endereço ou endereço-relativo]
- Salta incondicionalmente para o endereço calculado a partir do argumento (i.e.,
coloca em IP esse endereço); a execução do programa continua com o código armazenado
no endereço da MProg especificado por
id-label
, ou no
endereço (em valor absoluto
relativo ao início da MProg) ou somando ao IP o endereço-relativo passado como
argumento; neste último caso, o valor do argumento deverá obrigatoriamente conter o
sinal + ou - antes do valor numérico
- JMPV [id-label ou endereço ou endereço-relativo]
- Retira o valor no topo da stack e testa-o (assumindo que lá está um valor Booleano):
se for Verdadeiro salta para o endereço calculado a partir do argumento; se for
Falso a execução continua na instrução apontada pelo valor do IP;
- CALL [id-label ou endereço ou endereço-relativo]
- Guarda na Stack o endereço da instrução que se lhe segue e prossegue executando a
instrução que se encontra no endereço passado como argumento (Chamada incondicional de uma
subrotina);
- RET
- Efectua o retorno de uma subrotina: a execução do programa continua na instrução que
está
no endereço que é retirado do topo da Stack;
- HALT
- Pára a execução do programa;
- NOOP
- Não faz nada, serve apenas para gastar tempo...
Observações:
- Um endereço absoluto é um endereço relativo ao iníco da MProg (endereço 0);
- Quando às instruções
JMP, JMPF e CALL
é passado um endereço
relativo, o respectivo endereço calcula-se somando ao endereço da instrução seguinte o
off-set
que foi passado;
- A instrução
HALT
deve ser usada para terminar os programas.