Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Емуляція на ПЕОМ багаторегiстрових машин
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2007
Тип роботи:
Теорія
Предмет:
Інші
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра АСУ
Звіт
з лабораторної роботи №2
з дисципліни
“ Теорія алгоритмів і математичні основи представлення знань ”
на тему:
Емуляція на ПЕОМ багаторегiстрових машин
IНТЕРПРЕТАТОР ОПЕРАТОРНИХ I ПРЕДИКАТНИХ АЛГОРИТМIВ
Мета лабораторної роботи - автоматизувати процес доведення рекурсивності (алгоритмiчностi)певних функцій f : N^K -> N i g : E*^k -> E* шляхом емуляції на ПЕОМ N-БРМ i E*-БРМ , що дасть змогу беспосередньо перевiрити правiльнiсть побудови N-БРМ Мf i E*-БРМ М*g, для бiльш глибокого засвоїння прямих методів доведення рекурсивностi функцiй (предикатiв).
I. ЗАГАЛЬНІ ПОЛОЖЕННЯ
Мінімальні вимоги:
Комп'ютер . . . . . . . IBM PC або сумісний на рівні BIOS
Операційна система. . . MS-DOS версі∙ 3.0 або новіше
Вільна пам'ять. . . . . до 50 Кбайт
Внутрішні характеристики:
- всі дискові операці∙ и операці∙ управління пам'яттю
виконані на рівні DOS через int 21h
- операці∙ опиту клавіатури виконані на рівні BIOS
через int 16h
- вивід одразу у відео ОЗП та через int 10h
Текст програми:
- для компілятору Turbo Pascal 7.0
Запуск:
OPERALG ім'я_файлу [/d] [/i]
Тут ім'я_файлу - це повне ім'я з розширенням файлу з програмою,
але якщо воно задаїться без розширення і крапки, то інтерпретуїться як
ім'я з розширенням .opr по замовченню.
Ключ /d вказуїться тоді, коли потрібно відлагоджувати програму,
бо в цьому випадку програма починаї виконуватися по-кроково, виводячи
кожен раз обмежену екраном сторінку тексту програми і біжучі значення
змінних алгоритму користквача.
Недокументований ключ /i дозволяї почати відлагодження або робо-
ту без отримання початково∙ заставки і повідомлення про опрацьовані
рядки.
Опис програми:
Програма призначена для інтерпретаці∙ програм (операторних і
предикатних алгоритмів, далі ОПА), створених для абстрактних багато-
регістрових машин (БРМ). Програма як і машина отримуї дані (числа),
аргументи функці∙ ОПА, і починаї виконувати спеціальним чином складе-
ний алгоритм по перетворенню цих чисел.
У в а г а ! В інтерпретаторі наявні деякі розширені можливості,
які іноді не відповідають канонічним принципам конструювання ОПА.
ОПА може використовувати 30 цілочисельних змінних значеннями від
-32768 до 32767, а саме: x0...x9, y0...y9, z0...z9, а також константи
тих самих значень. Всі змінні ї глобальними.
Числа, що вводяться, одразу копіюються в змінні x0...x9.
Числа, що повинні вивестися, перед цим засобами ОПА мають бути
записані в змінні y0...y9.
ОПА читаїться з наперед створеного у будь-якому редакторі
ASCII-файлу, як правило, з розширенням .opr, наприклад такого виду:
2 | 2
; Ввід: x0,x1. Вивід: y0,y1.
// Додавання і перевірка підпрограм: y0=x0+x1, y1=2*x1-1.
y0=x0 ;(q23)-дана мітка ї закоментована і не інтерпретуїться
y1=-1
q1 P0(x1) (R)
y0=y0+1
CALL (q3) // Виклик п/п з поверненням на наступний рядок
x1=x1-1 (q1)
; Підпрограма
q3 y1=y1+2
RET
Регістр літер та пробіли в довільному місці рядка ОПА не мають
ніякого значення (крім першого рядка файла).
В цьому файлі обов'язково в першому рядку вказуються параметри
ОПА у вигляді
n | m
де n-кількість аргументів (вхідних змінних); m-кільксість значень
(вихідних змінних). Тоді вхід ОПА: x0...x[n-1], вихід: y0...y[m-1].
Далі в кожному рядку вказуються інструкці∙ ОПА, коментарі (що
починиються з символів ';' або '//') або рядок не містить ні одного
символа (для читабельності програми).
Кожна інструкція ОПА повинна розміщуватися в одному рядку і мати
наступний формат:
[qНОМЕР1] оператор [({qНОМЕР2|T|F|R|Я}[,{qНОМЕР3|T|F|R|Я}])]
Після не∙ може бути необов'язковий коментар: [{;|//} коментар]. Тут
і далі діють наступні позначення:
[a] - елемент a необов'язковий, крім певних умов;
{a|b} - обов'язково мають бути або a, або b;
- НОМЕР1 - номер мітки дано∙ інструкці∙, по якій сюди маї здійсню-
ватися перехід (0-251);
- НОМЕР2 - номер першо∙ мітки, по якій після виконання ції∙
інструкці∙ буде здійснюватися звідси перехід в залеж-
ності від оператора і результатів його виконання (0-251,
замість мітки може стояти спец. символ, який означаї:
R,Я - кінець роботи алгоритму з виводом результуючих
чисел,
T - кінець роботи алгоритму з виводом результуючого
значення .TRUE. (істина) для предикатних алго-
ритмів,
F - кінець роботи алгоритму з виводом результуючого
значення .FALSE. (хиба) для предикатних алго-
ритмів;
- НОМЕР3 - номер друго∙ мітки, по якій після виконання ції∙
інструкці∙ буде здійснюватися звідси перехід в залеж-
ності від оператора і результатів його виконання (0-251,
замість мітки може стояти аналогічний спец. символ.
Якщо цей формат не дотримуїться, то виводиться повідомлення про
помилку з номером того рядка в .opr-файлі, де вона ї.
Даний інтерпретатор підтримуї наступні оператори:
1) зм1={зм2|к1} [ОП {зм3|к2}] [(qA)] - змінній зм1 присвоюїться
значення змінно∙ зм2 (або константи к1) чи значення
бінарного виразу з виконанням операці∙ (OП - знак опе-
раці∙). Потім відбуваїться перехід на мітку qA або на
наступну інструкцію, якщо qA відсутня:
x1=x1+12 (q2)
y0=123
y3=y4
z9=2*2 (Я)
2) P0(зм1) (qA[,qB]) - якщо зм1=0 відбуваїться перехід на мітку qA,
інакше на мітку qB або на наступну інструкцію, якщо qB
відсутня:
P0(x0) (q1,q2)
P0(y1) (q33)
P0(z5) (T,q4)
3) CALL (qA[,qB]) - перехід на підпрограму по мітці qA, ∙∙ виконання
і повернення з не∙ по мітці qB або на наступну
після CALL інструкцію, якщо qB відсутня:
CALL (q24,q105)
CALL (q3)
CALL (q11,R)
4) RET - повернення з підпрограми згідно оператора CALL, що ∙∙ викли-
кав.
Апарат підпрограм розроблений за парадігмою мови програмування
BASIC у класичному варіанті (GO SUB, RETURN).
В операторі присвоїння можливі наступні бінарні операці∙:
a + b - додавання a і b;
a - b - урізане віднімання b від a;
a * b - множення a на b;
a / b - ділення a на b;
a % b - залишок від ділення a на b;
a \ b - звичайне віднімання b від a.
Виконуватися ОПА починаї з першо∙ від початку інструкці∙ і
закінчуї виконання при посиланні на мітки R,Я,T,F, при виконанні ос-
танньо∙ в тексті ОПА інструкці∙ без посилання або при виникненні поми-
лок виконання, про які видаїться блимаюче повідомлення.
В режимі відлагодження виводиться сторінка тексту ОПА, де знахо-
диться біжуча виконувана його інструкція. Курсор вказуї на інструкцію,
яка буде виконана при натисканні клавіші. У правому вікні виводяться
біжучі значення ненульових змінних (змінні, які невидимі дорівнюють
нулю !). Якщо натискаїться ESCape, то відбуваїться вихід з інтерпрета-
тора (наприклад для виправлення помилки або при зависанні ОПА), F10 -
вихід з відлагоджувача (наприклад для введення інших аргументів),
інакше продовження виконання ОПА.
Інтерпретатор дозволяї вводити нові значення аргументів для вико-
нання одного ОПА, а вихід з нього в нормальних умовах здійснюїться
введенням на запит будь-якого аргументу нечислового значення (наприк-
лад "q").
В даній реалізаці∙ програма не може містити більше 300
інструкцій, оперувати з числами, які не входять у визначений діапазон
Integer. Якщо з'являїться повідомлення Runtime error 201 at ... (що
означаї переповнення діапазону чисел) необхідно уважно проглянути і
відлагодити текст алгоритму.
Зміна цих обмежень досягаїться зміною розробником тексту інтерпре-
татора на мові Pascal.
Завдання 27: 27. x^3+2*x^2-3*x -2^x
Текст програми:
1 | 1
// X^3
y0=1
x5=x0
p(x5) (R,q40)
q40 x5=x5-1
p(x5) (q41,q42)
q41 y0=2 (R)
q42 y0=0
x2=x0
x3=x0
q0 x1=x0
q1 P0(x1) (q4,q3)
q3 y0=y0+1
x1=x1-1 (q1)
q4 x2=x2-1 //(q4)
P0(x2) (q5,q0)
q5 x2=x0
x3=x3-1
P0(x3) (q6,q0)
//X^2
q6 x4=y0
y0=0
x2=x0
q7 x1=x0
q8 P0(x1) (q10,q9)
q9 y0=y0+1
x1=x1-1 (q8)
q10 x2=x2-1 //(q4)
P0(x2) (q11,q7)
//X^3+X^2
q11 y0=y0*2
q12 P0(x4) (q14,q13)
q13 y0=y0+1
x4=x4-1 (q12)
q14 x4=y0
y0=x0
x2=1
q15 x1=x0
q16 P0(x1) (q18,q17)
q17 y0=y0+1
x1=x1-1 (q16)
q18 p(x2) (q21,q19)
q19 x2=x2-1 (q15)
q21 p(y0) (q23,q22)
q22 y0=y0-1
x4=x4-1 (q21)
q23 y0=2
x1=x0-2
q24 x2=y0
q25 p(x2) (q27,q26)
q26 y0=y0+1
x2=x2-1 (q25)
q27 p(x1) (q29,q28)
q28 x1=x1-1 (q24)
q29 p(y0) (q31,q30)
q30 x4=x4-1
y0=y0-1 (q29)
q31 y0=x4 (R)
Результати роботи програми:
x0 = 2
Результуючe значення:
y0 = 6
Введўть 1 аргумент:
x0 = 5
Результуючe значення:
y0 = 128
Введўть 1 аргумент:
x0 = 6
Результуючe значення:
y0 = 206
Завдання 44: NOT(( X < Y) AND ( Y > Z))
Текст програми:
3 | 1
//NOT((X<Y) AND (Y>Z))
z0=x0
z1=x1
z2=x2
q0 p(z0) (q1,q2)
q1 p(z1) (T,q4)
q2 p(z1) (T,q3)
q3 z0=z0-1
z1=z1-1 (q0)
q4 z0=x0
z1=x1
z2=x2
q7 p(z2) (q8,q9)
q8 p(z1) (T,F)
q9 p(z1) (T,q10)
q10 z1=z1-1
z2=z2-1 (q7)
Результати роботи програми:
Введўть 3 аргументи:
x0 = 8
x1 = 9
x2 = 2
Результуючe значення: .FALSE.
Введўть 3 аргументи:
x0 = 10
x1 = 20
x2 = 20
Результуючe значення: .TRUE.
Введўть 3 аргументи:
x0 = 8
x1 = 7
x2 = 9
Результуючe значення: .TRUE.
Введўть 3 аргументи:
x0 = 7
x1 = 5
x2 = 6
Результуючe значення: .TRUE.
Висновок: Під час виконання лабораторної роботи я вивчив методи емуляції на ПЕОМ багаторегiстрових машин, та IНТЕРПРЕТАТОР ОПЕРАТОРНИХ I ПРЕДИКАТНИХ АЛГОРИТМIВ
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора