CompNum-v0.9
86 pág.

CompNum-v0.9


DisciplinaTeoria da Computação565 materiais16.761 seguidores
Pré-visualização4 páginas
Andrade Ribeiro 
Exemplo 3 
\uf0a7 Máquina para computar a função \ud835\udc53 \ud835\udc5b = 0 
\uf0a7 Use a macro BRN e D (retorna o predecessor) 
62 
* 
BRN n=0 
n>0 
* 
D 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Combinando MTNs e Macros 
\uf0a7 As condições do estado inicial, permitem que 
a macro seja executada após a leitura de um 
símbolo branco em qualquer estado 
63 
qi M * 
\u2fd\u2192 
Computando 
\ud835\udc40\ud835\udc62\ud835\udc59\ud835\udc61(\ud835\udc5a, \ud835\udc5b): \ud835\udc5a × \ud835\udc5b 
64 
q0 q1 
\u2fd\u2192R 
q2 
1\u2192R 
 E1 
\u2fd\u2192 
* ME1 * 
 A * ME1 * 
q3 
* 
 MD1 
* 
 CP1,1 q7 q7 
\u2fd\u2192 1\u2192X,R 
1\u2192R 
q6 
q5 
X\u2192R 
1\u2192L 
1\u2192L 
\u2fd\u2192L 
 T 
 E1 
* 
 T 
q4 
* 
\u2fd\u2192 
1\u2192\u2fd,L 
X\u2192\u2fd,L 
X\u2192\u2fd,L 
 CP1 
\u2fd\u2192 
1\u2192X,R 
1\u2192R 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Construção de Programas em 
Computadores Modernos 
65 
Programa 
Executável 
compilador 
executa 
Linguagem de 
Progração de 
Alto-Nível 
codifica 
Computador moderno 
Processo simplificado 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Construção de Programas em 
Máquinas de Turing 
66 
Programa 
Executável 
compilador 
executa 
Linguagem de 
Progração de 
Alto-Nível 
codifica 
Máquinas de Turing 
Processo simplificado 
\u2fd a b c ... 
q0 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagem de Montagem 
para MTs 
\uf0a7 Princípio básico: 
\u2022 Um computador muda bits de posição em alguma 
localização da memória 
\u2022 MTs escreve símbolos na fita 
\uf0a7 Vamos projetar uma linguagem de montagem 
(assembly) para MTs 
\u2022 Descrição sequencial das ações e redirecionamentos 
do fluxo do programa 
\u2022 Simplificação do gerenciamento de memória 
\u2022 Vamos chamar esta linguagem de LMT 
 
 
 
67 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Registradores e 
espaço de trabalho 
Linguagem de Montagem para 
MTs: Framework Básico 
\uf0a7 Valores da entrada da MT são atribuídos para as 
variáveis \ud835\udc631, \u2026 , \ud835\udc63\ud835\udc58 
\uf0a7 \ud835\udc63\ud835\udc58+1, \u2026 , \ud835\udc63\ud835\udc5b são as variáveis locais usadas pelo 
programa: recebem o valor 0 quando a MT é 
inicializada 
68 
\u2fd \ud835\udc631 ... \u2fd \u2fd \ud835\udc63\ud835\udc58 \u2fd \ud835\udc63\ud835\udc58+1 ... \u2fd \u2fd \ud835\udc63\ud835\udc5b \u2fd \u2fd \u2fd ... 
variáveis de entrada variáveis locais 
posição HOME 
Valores de variáveis separados 
por pelo símbolo branco 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Registradores e 
espaço de trabalho 
Linguagem de Montagem para 
MTs: Framework Básico (2) 
\uf0a7 Após a incialização, a cabeça de le é posicionada 
no primeiro símbolo branco após as variáveis de 
entrada e locais: posição HOME 
\uf0a7 A cabeça le retorna para posição HOME entre a 
execução de instruções 
 69 
\u2fd \ud835\udc631 ... \u2fd \u2fd \ud835\udc63\ud835\udc58 \u2fd \ud835\udc63\ud835\udc58+1 ... \u2fd \u2fd \ud835\udc63\ud835\udc5b \u2fd \u2fd \u2fd ... 
variáveis de entrada variáveis locais 
posição HOME 
Valores de variáveis separados 
por pelo símbolo branco 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Registradores e 
espaço de trabalho 
Linguagem de Montagem para 
MTs: Framework Básico (3) 
 
 
70 
\u2fd \ud835\udc631 ... \u2fd \u2fd \ud835\udc63\ud835\udc58 \u2fd \ud835\udc63\ud835\udc58+1 ... \u2fd \u2fd \ud835\udc63\ud835\udc5b \u2fd \u2fd \u2fd ... 
variáveis de entrada variáveis locais 
posição HOME 
Valores de variáveis separados 
por pelo símbolo branco 
\uf0a7 À direita da posição HOME estão a versão da MT dos 
registradores 
\u2022 A primeiro valor (delimitador por símbolos brancos) está no 
registrador 1, o segundo no registro 2 e assim por diante 
\uf0a7 Restrição: Registrador \ud835\udc56 pode ser lido ou escrito apenas se 
os registradores 1,\u2026 , \ud835\udc56 \u2212 1 contém valores 
 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Conjunto de Instruções 
71 
Instrução Descrição 
INIT \ud835\udc63\ud835\udc56 Inicializa a variável local \ud835\udc63\ud835\udc56 para 0 
HOME \ud835\udc61 Move a cabeça le para HOME quando t variáveis estão alocadas 
LOAD \ud835\udc63\ud835\udc56 , t Carrega o valor da variável \ud835\udc63\ud835\udc56 no registrador \ud835\udc61 
STORE \ud835\udc63\ud835\udc56 , t Armaze o valor do registrador \ud835\udc61 na variável \ud835\udc63\ud835\udc56 
RETURN \ud835\udc63\ud835\udc56 Apaga as variáveis e deixa o valor de \ud835\udc63\ud835\udc56 na posição de saída 
CLEAR \ud835\udc61 Apaga o valor no registrador \ud835\udc61 
BRN L, \ud835\udc61 Redireciona para a instrução L se o valor no registrador t é 0 
GOTO L Execute a instrução L 
NOP Nenhuma operação (executada conjuntamente com GOTO) 
INC \ud835\udc61 Incrementa o valor do registrador \ud835\udc61 
DEC \ud835\udc61 Decrementa o valor do registradro t 
ZERO \ud835\udc61 Substitui o valor no registrador \ud835\udc61 por 0 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Inicialização da Fita 
\uf0a7 Inicialização é realizada pelas instruções INT e 
HOME 
72 
Instrução Implementação via Macros 
MDi-1 ZR MEi-1 INIT \ud835\udc63\ud835\udc56 
 
HOME \ud835\udc61 
 
 MDt 
* A macro ZR escreve 0 na posição imediatamente à 
direita da cabeça le 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Inicialização da Fita: Exemplo 
\uf0a7 Considere a inicialização de um programa com 
uma variável de entrada \ud835\udc56 e duas variáveis 
locais (abaixo, \ud835\udc5e é um estado qualquer) 
73 
Instrução Configuração 
INIT 2 
 
\ud835\udc92\u2fd\ud835\udc56 \u2fd 
\ud835\udc92\u2fd\ud835\udc56 \u2fd 0 \u2fd 
\ud835\udc92\u2fd\ud835\udc56 \u2fd 0 \u2fd0 \u2fd INIT 3 
 HOME 3 
 
\u2fd\ud835\udc56 \u2fd 0 \u2fd0 \ud835\udc92 \u2fd 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Instrução STORE 
\uf0a7 Move o valor do registrador \ud835\udc61 para uma variável 
especificada 
\uf0a7 Restrição: STORE \ud835\udc63\ud835\udc56 , t pode ser usado apenas 
quando \ud835\udc61 é o último registrador com uma variável 
atribuída 
\uf0a7 Espaçamento entre variáveis é mantido 
\uf0a7 Usa a macro INV para mover o valor do 
registrador para a posição correta 
\uf0a7 O valor do registrador \ud835\udc61 é apagado no final da 
operação 
 74 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Instrução STORE\ud835\udc63\ud835\udc56,1: Implementação 
\uf0a7 N é o número total de variáveis de entrada e locais; os 
expoentes indicam a repetição da sequência de macros 
75 
Instrução Implementação via Macros 
ME1 INV 
STORE \ud835\udc63\ud835\udc56, 1 
 
\ud835\udc5b \u2212 \ud835\udc56 + 1 
MD1 INV 
\ud835\udc5b \u2212 \ud835\udc56 
MD1 
E1 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Execução STORE\ud835\udc632,1: Exemplo 
76 
Instrução Configuração 
ME1 
 
\u2fd\ud835\udc631\u2fd \ud835\udc632\u2fd \ud835\udc633\ud835\udc92\u2fd \ud835\udc5f \u2fd 
INV 
 
\u2fd\ud835\udc631\u2fd \ud835\udc632\ud835\udc92\u2fd \ud835\udc633\u2fd \ud835\udc5f \u2fd 
\u2fd\ud835\udc631\u2fd \ud835\udc632\ud835\udc92\u2fd \ud835\udc5f \u2fd \ud835\udc633\u2fd 
ME1 
 INV 
 
\u2fd\ud835\udc631\ud835\udc92\u2fd \ud835\udc632\u2fd \ud835\udc5f \u2fd \ud835\udc633\u2fd 
\u2fd\ud835\udc631\ud835\udc92\u2fd \ud835\udc5f \u2fd \ud835\udc632\u2fd \ud835\udc633\u2fd 
\u2fd\ud835\udc631\u2fd \ud835\udc5f \ud835\udc92\u2fd \ud835\udc632\u2fd \ud835\udc633\u2fd MD1 
 INV 
 
\u2fd\ud835\udc631\u2fd \ud835\udc5f \ud835\udc92\u2fd \ud835\udc633\u2fd \ud835\udc632\u2fd 
MD1 
 
\u2fd\ud835\udc631\u2fd \ud835\udc5f \u2fd \ud835\udc633\ud835\udc92\u2fd\ud835\udc632\u2fd 
\u2fd\ud835\udc631\u2fd \ud835\udc5f \u2fd \ud835\udc633\ud835\udc92\u2fd \u2fd \u2fd E1 
 
Instrução STORE \ud835\udc63\ud835\udc56,\ud835\udc61: Implementação 
77 
Instrução Implementação via Macros 
ME1 INV 
STORE \ud835\udc63\ud835\udc56, \ud835\udc61 
 
\ud835\udc61 + \ud835\udc5b \u2212 \ud835\udc56 \u2212 1 
MD1 INV 
\ud835\udc61 + \ud835\udc5b \u2212 \ud835\udc56 \u2212 1 
MD1 
E1 
MEt-1 
INV 
MDt-2 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Instrução LOAD 
\uf0a7 Copia o valor da variável \ud835\udc63\ud835\udc56 no registrador \ud835\udc61 
\uf0a7 Restrição: os registradores 1, \u2026 , \ud835\udc61 \u2212 1 devem 
conter valores 
78 
Instrução Implementação via Macros 
ME\ud835\udc5b \u2212 \ud835\udc56 + 1 
LOAD \ud835\udc63\ud835\udc56, \ud835\udc61 
 
CP1, \ud835\udc5b \u2212 \ud835\udc56 + 1 + \ud835\udc61 
 
MD\ud835\udc5b \u2212 \ud835\udc56 + 1 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Instrução CLEAR 
\uf0a7 Apaga o valor do registrador especificado 
79 
Instrução Implementação via Macros 
MD\ud835\udc61 \u2212 1 
CLEAR \ud835\udc61 
 
E1 
 
MEt \u2212 1 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Instrução RETURN 
\uf0a7 Apaga todas as variáveis da fita, exceto a variável 
especificada 
\uf0a7 Restrição: nenhum registrador deve estar 
alocado 
\uf0a7 Juntamente com CLEAR, é usada para 
reconfigurar a fita para retornar o valor de uma 
determinada computação 
\uf0a7 Resultado final é a configuração básica de saída: 
\u2022 q \u2fd \ud835\udc63\ud835\udc56 \u2fd 
80 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Instrução RETURN \ud835\udc63\ud835\udc56: Implementação 
81 
Instrução Implementação via Macros 
 T 
RETURN \ud835\udc63\ud835\udc56 
 
MD1 
ED 
E\ud835\udc5b \u2212 \ud835\udc56 + 1 
EE 
E\ud835\udc56 \u2212 1 
MEn 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Instruções Aritméticas 
\uf0a7 As instruções INC, DEC, e ZERO são 
implementadas pelas macros que computam 
as funções sucessora, predecessora, e zero 
\uf0a7 Instruções aritméticas adicionais, de mais 
alto-nível, poderiam também ser definidas 
\u2022 Ex.: Função ADD 
82 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Instruções BRN e GOTO 
\uf0a7 Realizam o redirecionamento do fluxo de 
execução 
\uf0a7 GOTO L indica que a próxima instrução a ser 
executada é L 
\uf0a7 BRN \ud835\udc3f, \ud835\udc61 testa o valor do registrador L e realiza 
uma das seguintes ações: 
\u2022 Se o valor for diferente de zero, a instrução 
seguinte à instrução BRN é executada 
\u2022 Se o valor for zero, a instrução L é executada 
83 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Instrução BRN: Implementação 
84 
* 
BRN 
n > 0 
n=0 
Máquina para 
instrução 1 
Máquina para 
instrução 2 
E1 * * 
* 
E1 * 
BRN L,1 
\u201cinstrução 1\u201d 
... 
L:\u201cinstrução 2\u201d 
Código 
Após a execução de BRN, o 
conteúdo