Ybadoo - Soluções em Software Livre
Tutoriais
Compiladores

(Deitel, 2003) À primeira vista, pode parecer loucura, mas nesse problema você vai construir seu próprio computador. Não, você não irá soldar componentes. Em vez disso, você utilizará a poderosa técnica de simulação baseada em software para criar um modelo em software orientado a objetos do Simpletron. Você não se decepcionará. O simulador de Simpletron transformará o computador que você está utilizando em um Simpletron e você realmente será capaz de executar, testar e depurar os programas escritos em SML.

Quando você executa o simulador de Simpletron, ele deve começar exibindo:

Welcome to Simpletron!
Please enter your file program:

O usuário deve fornecer um arquivo contendo o código-fonte em SML, para ser carregado para a memória do Simpletron. Suponha que o usuário tenha fornecido o seguinte código-fonte:

+1007
+1008
+2007
+3008
+2109
+1109
+4300
+0000
+0000
+0000

Simule a memória do Simpletron como um array unidimensional memory que tem 100 elementos. Após armazenar as instruções do arquivo na sua memória, o Simpletron apresenta a seguinte mensagem ao usuário:

Simpletron loading completed!
Simpletron execution begins!

Agora, o programa em SML foi armazenado no array memory. A seguir, o Simpletron executa seu programa em SML. A execução começa com a instrução na posição 00 e continua na sequência, a menos que seja desviada para alguma outra parte do programa por uma transferência de controle.

Use a variável accumulator para representar o registrador acumulador. Use a variável instructionCounter para manter o controle da posição na memória que contém a instrução que está sendo executada. Use a variável operationCode para indicar a operação que está sendo atualmente executada, isto é, os dois dígitos da esquerda da palavra que contém a instrução. Use a variável operand para indicar a posição da memória sobre a qual a instrução atual opera. Deste modo, operand é composto pelos dois dígitos mais à direita da instrução que está sendo atualmente executada. Não execute instruções diretamente da memória. Em vez disso, transfira a próxima instrução que vai ser executada da memória para uma variável instructionRegister. Então, "retire" os dois dígitos da esquerda e coloque-os em operationCode; "retire" os dois dígitos da direita e coloque os mesmos em operand. Quando o Simpletron começa a execução, os registradores especiais são todos inicializados com zero.

Agora, vamos fazer um "passeio" pela execução da primeira instrução de SML, +1007, na posição de memória 00. Isto é chamado de um ciclo de execução de instrução.

O instructionCounter nos informa a posição da próxima instrução a ser executada. Realizamos uma busca (fetch) do conteúdo dessa posição a partir de memory utilizando o comando:

instructionRegister = memory[instructionCounter];

O código de operação e o operando são extraídos do registrador de instrução pelos comandos:

operationCode = instructionRegister / 100;
operand = instructionRegister % 100;

Agora o Simpletron deve determinar que o código da operação é, na verdade, uma instrução read (e não uma write, uma load, etc.). A estrutura switch diferencia as doze operações de SML.

Na estrutura switch, o comportamento de várias instruções de SML é simulado como mostrado na Tabela 1. Discutimos as instruções de desvio brevemente e deixamos as outras para o leitor.

Tabela 1: comportamento de diversas instruções SML no Simpletron
InstruçãoDescrição
READExibe um diálogo de entrada com o prompt input :
Converte o valor digitado em um inteiro e armazena-o na posição memory[operand].
LOADaccumulator = memory[operand];
ADDaccumulator += memory[operand];

Quando o programa de SML completar a execução, o nome e o conteúdo de cada registrador, bem como o conteúdo completo da memória devem ser exibidos. Esse tipo de impressão é frequentemente chamado de dump de memória. Para ajudá-lo a programar seu método de dump, um exemplo de formato de dump é mostrado na Figura 1. Observe que um dump, depois de executar um programa Simpletron, mostra os valores reais das instruções e os valores dos dados no momento em que a execução terminou. O exemplo de dump supõe que a saída será enviada para a tela do vídeo.

Figura 1: um exemplo de dump

REGISTERS:
+0000 Accumulator
00 Instruction Counter
+0000 Instruction Register
00 Operation Code
00 Operand

MEMORY:
0 1 2 3 4 5 6 7 8 9
0 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000
1 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000
2 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000
3 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000
4 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000
5 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000
6 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000
7 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000
8 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000
9 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000 +0000

Vamos prosseguir com a execução da primeira instrução de nosso programa, a saber, o +1007 na posição de memória 00. Como indicamos, a instrução switch simula isso pedindo que o usuário digite um valor na entrada, lendo o valor, convertendo o valor em um inteiro e armazenando-o na posição de memória memory[operand].

Um texto informativo (input : ) deve ser exibido na tela, antes da leitura ser executada, para solicitar que o usuário forneça um dado de entrada. O Simpletron espera o usuário digitar um valor e apertar a tecla return. O valor é então armazenado na posição 07.

Nesse momento, a simulação da primeira instrução está completa. Tudo que falta é preparar o Simpletron para executar a próxima instrução. Uma vez que a instrução que acabou de ser executada não era uma transferência de controle, necessitamos somente incrementar o registrador contador de instruções, como segue:

++instructionCounter;

Isso completa a execução simulada da primeira instrução. O processo inteiro (isto é, o ciclo de execução da instrução) começa novamente, com a busca da próxima instrução a ser executada.

Consideremos, agora, como instruções de desvio - transferências de controle - são simuladas. Tudo o que necessitamos fazer é ajustar o valor no contador de instruções apropriadamente. Então, a instrução de desvio incondicional (40) é simulada dentro da estrutura switch como:

instructionCounter = operand;

A instrução condicional "desvia se o acumulador for zero" é simulado como:

if(accumulador == 0)
{
instructionCounter = operand;
}

O simulador deve verificar vários tipos de erros. Durante a fase de entrada de dados, por exemplo, cada número que o usuário digita deve estar no intervalo de -9999 a +9999. O simulador deve testar se cada número fornecido está nesse intervalo e, se não estiver, continuar solicitando que o usuário digite novamente o número até que o usuário forneça um número correto.

Durante a fase de execução, o simulador deve verificar a ocorrência de vários erros sérios, tais como tentativas de divisão por zero, tentativas de execução de códigos de operações inválidos, estouros de acumulador (isto é, operações aritméticas que resultam em valores maiores do que +9999 ou menores do que -9999) e coisas semelhantes. Tais erros sérios são chamados de erros fatais. Quando um erro fatal é descoberto, o simulador deve imprimir uma mensagem de erro como:

error : attempt to divide by zero!
Simpletron execution abnormally terminated!

O simulador deve sempre imprimir um dump completo de computador no formato discutido anteriormente. Isso ajudará o usuário a localizar o erro no programa, caso algum imprevisto ocorra.

 

InterpretException.java LoadException.java Simpletron.java

Arquivo InterpretException.java

/*************************************************************************
* Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br) *
* Ybadoo - Solucoes em Software Livre (ybadoo.com.br) *
* *
* Permission is granted to copy, distribute and/or modify this document *
* under the terms of the GNU Free Documentation License, Version 1.3 or *
* any later version published by the Free Software Foundation; with no *
* Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A *
* A copy of the license is included in the section entitled "GNU Free *
* Documentation License". *
* *
* Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic) *
* OpenJDK Version "1.8.0_121" *
* OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode) *
*************************************************************************/
package com.ybadoo.tutoriais.cmp.tutorial10.exercicio01;

/**
* Exceção na interpretação do código escrito em
* Simpletron Machine Language
*/
public class InterpretException extends Exception
{
/**
* Identificador de serialização da classe
*/
private static final long serialVersionUID = 1L;

/**
* Constructs a new InterpretException with null as its detail message
*/
public InterpretException()
{
super();
}

/**
* Constructs a new InterpretException with the specified detail message
*
* @param message the detail message
*/
public InterpretException(String message)
{
super(message);
}

/**
* Constructs a new InterpretException with the specified detail message
* and cause
*
* @param message the detail message
* @param cause the cause
*/
public InterpretException(String message, Throwable cause)
{
super(message, cause);
}

/**
* Constructs a new InterpretException with the specified cause and a
* detail message of (cause==null ? null : cause.toString())
* (which typically contains the class and detail message of cause)
*
* @param cause the cause
*/
public InterpretException(Throwable cause)
{
super(cause);
}
}

Arquivo LoadException.java

/*************************************************************************
* Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br) *
* Ybadoo - Solucoes em Software Livre (ybadoo.com.br) *
* *
* Permission is granted to copy, distribute and/or modify this document *
* under the terms of the GNU Free Documentation License, Version 1.3 or *
* any later version published by the Free Software Foundation; with no *
* Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A *
* A copy of the license is included in the section entitled "GNU Free *
* Documentation License". *
* *
* Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic) *
* OpenJDK Version "1.8.0_121" *
* OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode) *
*************************************************************************/
package com.ybadoo.tutoriais.cmp.tutorial10.exercicio01;

/**
* Exceção na leitura do arquivo contendo o código-fonte para
* a memória da Simpletron Machine
*/
public class LoadException extends Exception
{
/**
* Identificador de serialização da classe
*/
private static final long serialVersionUID = 1L;

/**
* Constructs a new LoadException with null as its detail message
*/
public LoadException()
{
super();
}

/**
* Constructs a new LoadException with the specified detail message
*
* @param message the detail message
*/
public LoadException(String message)
{
super(message);
}

/**
* Constructs a new LoadException with the specified detail message and
* cause
*
* @param message the detail message
* @param cause the cause
*/
public LoadException(String message, Throwable cause)
{
super(message, cause);
}

/**
* Constructs a new LoadException with the specified cause and a detail
* message of (cause==null ? null : cause.toString())
* (which typically contains the class and detail message of cause)
*
* @param cause the cause
*/
public LoadException(Throwable cause)
{
super(cause);
}
}

Arquivo Simpletron.java

/*************************************************************************
* Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br) *
* Ybadoo - Solucoes em Software Livre (ybadoo.com.br) *
* *
* Permission is granted to copy, distribute and/or modify this document *
* under the terms of the GNU Free Documentation License, Version 1.3 or *
* any later version published by the Free Software Foundation; with no *
* Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A *
* A copy of the license is included in the section entitled "GNU Free *
* Documentation License". *
* *
* Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic) *
* OpenJDK Version "1.8.0_121" *
* OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode) *
*************************************************************************/
package com.ybadoo.tutoriais.cmp.tutorial10.exercicio01;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.text.DecimalFormat;
import java.util.Scanner;

/**
* Classe responsavel pela simulacao da Simpletron Machine
*/
public class Simpletron
{
/**
* Quantidade de palavras armazenadas na memoria
*/
public static final int MEMORY = 100;

/**
* Le uma palavra do teclado para uma posicao especifica da memoria
*/
public static final int READ = 10;

/**
* Escreve na tela uma palavra de uma posicao especifica da memoria
*/
public static final int WRITE = 11;

/**
* Carrega uma palavra de uma posicao especifica na memoria para o
* acumulador
*/
public static final int LOAD = 20;

/**
* Armazena uma palavra do acumulador em uma posicao especifica na memoria
*/
public static final int STORE = 21;

/**
* Adiciona uma palavra de uma posicao especifica na memoria a palavra
* armazenada no acumulador
*/
public static final int ADD = 30;

/**
* Subtrai uma palavra de uma posicao especifica na memoria a palavra
* armazenada no acumulador
*/
public static final int SUBTRACT = 31;

/**
* Divide uma palavra de uma posicao especifica na memoria a palavra
* armazenada no acumulador
*/
public static final int DIVIDE = 32;

/**
* Multiplica uma palavra de uma posicao especifica na memoria a palavra
* armazenada no acumulador
*/
public static final int MULTIPLY = 33;

/**
* Desvia para uma posicao especifica na memoria
*/
public static final int BRANCH = 40;

/**
* Desvia para uma posicao especifica na memoria se o acumulador for
* negativo
*/
public static final int BRANCHNEG = 41;

/**
* Desvia para uma posicao especifica na memoria se o acumulador for zero
*/
public static final int BRANCHZERO = 42;

/**
* Finaliza o programa
*/
public static final int HALT = 43;

/**
* Formato numerico dos dados da memoria
*/
private final DecimalFormat memoryFormatter;

/**
* Memoria da Simpletron Machine
*/
private int[] memory;

/**
* Acumulador da Simpletron Machine
*/
private int accumulator;

/**
* Contador de instrucoes da Simpletron Machine
*/
private int instructionCounter;

/**
* Codigo da operacao
*/
private int operationCode;

/**
* Operando
*/
private int operand;

/**
* Leitor do teclado
*/
private Scanner scanner;

/**
* Se a Simpletron Machine esta em processamento
*/
private boolean processing;

/**
* Construtor padrao
*/
public Simpletron()
{
processing = false;

memory = new int[MEMORY];

for(int i = 0; i < memory.length; i++)
{
memory[i] = 0;
}

accumulator = 0;
instructionCounter = 0;
operationCode = 0;
operand = 0;

scanner = new Scanner(System.in);

memoryFormatter = new DecimalFormat("+0000;-0000");
}

/**
* Ler o arquivo contendo o codigo-fonte para a memoria
* da Simpletron Machine
*
* @throws LoadException problemas na leitura do codigo-fonte
*/
private void load() throws LoadException
{
BufferedReader leitor = null;

System.out.print("Please enter your file program: ");

String source = scanner.nextLine();

try
{
leitor = new BufferedReader(new FileReader(source));

String line = leitor.readLine();

int counter = 0;

while(line != null)
{
int word = Integer.parseInt(line);

if((word >= -9999) && (word <= 9999))
{
memory[counter] = word;

counter = counter + 1;
}
else
{
throw new NumberFormatException();
}

line = leitor.readLine();
}
}
catch(FileNotFoundException exception)
{
throw new LoadException("error : attempt to file not found!", exception);
}
catch(IOException exception)
{
throw new LoadException("error : attempt to invalid file!", exception);
}
catch(NumberFormatException exception)
{
throw new LoadException("error : attempt to invalid instruction!", exception);
}
finally
{
try
{
leitor.close();
}
catch(IOException exception)
{
/*
* nothing to do
*/
}
}

System.out.println("Simpletron loading completed!");
}

/**
* Interpretar a instrucao READ
*/
private void readInstruction()
{
System.out.print("input : ");

int number = 0;

try
{
number = Integer.parseInt(scanner.nextLine());
}
catch(NumberFormatException exception)
{
number = Integer.MIN_VALUE;
}

if((number >= -9999) && (number <= 9999))
{
memory[operand] = number;

instructionCounter = instructionCounter + 1;
}
else
{
System.out.println("error : attempt to invalid number!");
}
}

/**
* Interpretar a instrucao WRITE
*/
private void writeInstruction()
{
System.out.print("output: ");
System.out.println(memoryFormatter.format(memory[operand]));

instructionCounter = instructionCounter + 1;
}

/**
* Interpretar a instrucao LOAD
*/
private void loadInstruction()
{
accumulator = memory[operand];

instructionCounter = instructionCounter + 1;
}

/**
* Interpretar a instrucao STORE
*/
private void storeInstruction()
{
memory[operand] = accumulator;

instructionCounter = instructionCounter + 1;
}

/**
* Interpretar a instrucao ADD
*
* @throws InterpretException problemas na interpretacao da instrucao ADD
*/
private void addInstruction() throws InterpretException
{
accumulator = accumulator + memory[operand];

if((accumulator >= -9999) && (accumulator <= 9999))
{
instructionCounter = instructionCounter + 1;
}
else
{
throw new InterpretException("error : attempt to accumulator overflow!");
}
}

/**
* Interpretar a instrucao SUBTRACT
*
* @throws InterpretException problemas na interpretacao da instrucao SUBTRACT
*/
private void subtractInstruction() throws InterpretException
{
accumulator = accumulator - memory[operand];

if((accumulator >= -9999) && (accumulator <= 9999))
{
instructionCounter = instructionCounter + 1;
}
else
{
throw new InterpretException("error : attempt to accumulator overflow!");
}
}

/**
* Interpretar a instrucao DIVIDE
*
* @throws InterpretException problemas na interpretacao da instrucao DIVIDE
*/
private void divideInstruction() throws InterpretException
{
if(memory[operand] != 0)
{
accumulator = accumulator / memory[operand];

instructionCounter = instructionCounter + 1;
}
else
{
throw new InterpretException("error : attempt to divide by zero!");
}
}

/**
* Interpretar a instrucao MULTIPLY
*
* @throws InterpretException problemas na interpretacao da instrucao MULTIPLY
*/
private void multiplyInstruction() throws InterpretException
{
accumulator = accumulator * memory[operand];

if((accumulator >= -9999) && (accumulator <= 9999))
{
instructionCounter = instructionCounter + 1;
}
else
{
throw new InterpretException("error : attempt to accumulator overflow!");
}
}

/**
* Interpretar a instrucao BRANCH
*/
private void branchInstruction()
{
instructionCounter = operand;
}

/**
* Interpretar a instrucao BRANCHNEG
*/
private void branchnegInstruction()
{
if(accumulator < 0)
{
instructionCounter = operand;
}
else
{
instructionCounter = instructionCounter + 1;
}
}

/**
* Interpretar a instrucao BRANCHZERO
*/
private void branchzeroInstruction()
{
if(accumulator == 0)
{
instructionCounter = operand;
}
else
{
instructionCounter = instructionCounter + 1;
}
}

/**
* Interpretar a instrucao HALT
*/
private void haltInstruction()
{
processing = false;
}

/**
* Interpretar o codigo escrito em Simpletron Machine Language
*/
private void interpret() throws InterpretException
{
System.out.println("Simpletron execution begins!");

processing = true;

while(processing)
{
int instructionRegister = memory[instructionCounter];

operationCode = instructionRegister / 100;

operand = instructionRegister % 100;

switch(operationCode)
{
case READ : readInstruction();
break;
case WRITE : writeInstruction();
break;
case LOAD : loadInstruction();
break;
case STORE : storeInstruction();
break;
case ADD : addInstruction();
break;
case SUBTRACT : subtractInstruction();
break;
case DIVIDE : divideInstruction();
break;
case MULTIPLY : multiplyInstruction();
break;
case BRANCH : branchInstruction();
break;
case BRANCHNEG : branchnegInstruction();
break;
case BRANCHZERO: branchzeroInstruction();
break;
case HALT : haltInstruction();
break;
default : throw new InterpretException("error : attempt to unknown instruction!");
}
}

System.out.println("Simpletron execution terminated!");
}

/**
* Apresentar o dump da Simpletron Machine
*/
private void dump()
{
DecimalFormat variableFormatter = new DecimalFormat(" 00");

System.out.println();

System.out.println("REGISTERS:");

String temp = memoryFormatter.format(accumulator).substring(0, 5);
System.out.println(temp + " Accumulator");

temp = variableFormatter.format(instructionCounter);
System.out.println(temp + " Instruction Counter");

temp = memoryFormatter.format(memory[instructionCounter]);
System.out.println(temp + " Instruction Register");

temp = variableFormatter.format(operationCode);
System.out.println(temp + " Operation Code");

temp = variableFormatter.format(operand);
System.out.println(temp + " Operand");

System.out.println();

System.out.println("MEMORY:");

System.out.print(" ");

for(int i = 0; i < 10; i++)
{
System.out.print(" " + i);
}

System.out.println();

for(int i = 0; i < memory.length; i += 10)
{
System.out.print((i / 10) + " ");

for(int j = i; j < i + 10; j++)
{
System.out.print(memoryFormatter.format(memory[j]) + " ");
}

System.out.println();
}
}

/**
* Executar a Simpletron Machine
*/
public void execute()
{
System.out.println("Welcome to Simpletron!");

try
{
load();

interpret();
}
catch(Exception exception)
{
System.out.println(exception.getMessage());

System.out.println("Simpletron execution abnormally terminated!");
}
finally
{
dump();
}
}

/**
* Metodo principal da linguagem de programacao Java
*
* @param args argumentos da linha de comando (nao utilizado)
*/
public static void main(String[] args)
{
Simpletron simpletron = new Simpletron();

simpletron.execute();
}
}

Deitel, H. M. (2003). Java, como programar. 4ª edição. Porto Alegre: Bookman. 1.386 páginas.