КУРСОВИЙ ПРОЕКТ
з дисципліни СИСТЕМНЕ ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ
Тема – РОЗРОБКА КОМПІЛЯТОРА ДЛЯ СТВОРЕННЯ ЛІНІЙНИХ ПРОГРАМ ОБЧИСЛЕННЯ ПРОСТИХ АРИФМЕТИЧНИХ ВИРАЗІВ НА ОСНОВІ АЛГОРИТМУ ТРАНСЛЯЦІЇ РУТИСХАУЗЕРА З ВИВОДОМ РЕЗУЛЬТАТІВ.
АНОТАЦІЯ
В даному проекті розроблений компілятор, який дозволяє створювати лінійні програми обчислення простих математичних виразів на основі алгоритму трансляції Рутисхаузера. Програма транслює вирази з додаванням, відніманням, множенням і діленням знакових 16-розрядних змінних та літералів. Окрім цього реалізовані функції вводу з клавіатури та виводу змінних на екран. Результатом роботи компілятора є *.exe файл.
SUMMARY
A compiler which allows to create linear programs for calculation of simple mathematical expressions, based on Rutishauser translation algorithm, is developed in this project. The program translates expressions with addition, subtraction, multiplication and division of signed 16-bit variables and literals. Except for it the functions of input from a keyboard and showing of variables on a screen are realized. The result of compilers work is *.exe file.
ЗМІСТ
Стор
1. БЛОК-СХЕМА ВИКОНАННЯ ПРОГРАМИ.....................................................6
2. ОПИС АЛГОРИТМУ РУТИСХАУЗЕРА...........................................................9
3. ОПИС ПРОГРАМИ……………………………………………………………12
4. ТЕКСТ ПРОГРАМИ.……………………………………………….…………...
5. ТЕКСТ ПІДПРОГРАМ………………………………………………………….
6. ВИСНОВКИ..........................................................................................................
7. ПЕРЕЛІК ВИКОРИСТАНИХ ЛІТЕРАТУРНИХ ДЖЕРЕЛ..............................
КП.КС-05.00.00.000 ПЗ
Зм. | Лист | № докум | Підпис | Дата
Розроб. | Блєдних | КОМПІЛЯТОР ДЛЯ СТВОРЕННЯ ЛІНІЙНИХ ПРОГРАМ ОБЧИСЛЕННЯ ПРОСТИХ АРИФМЕТИЧНИХ ВИРАЗІВ НА ОСНОВІ АЛГОРИТМУ РУТИСХАУЗЕРА | Літ. | Арк. | Аркушів
Перевір. | Мельничук | 5 | 28
Реценз. | ІМЕ ГА
Н.Контр.
Затверд.
1 БЛОК-СХЕМА ВИКОНАННЯ ПРОГРАМИ
Рис. 1. Блок-схема виконання програми
КП.КС-05.00.00.000 ПЗ | Арк.
6
Зм. | Арк. | № докум | Підпис | Дата
Рис. 1. Блок-схема виконання програми (продовження)
КП.КС-05.00.00.000 ПЗ | Арк.
7
Зм. | Арк. | № докум | Підпис | Дата
Рис. 1. Блок-схема виконання програми (продовження)
КП.КС-05.00.00.000 ПЗ | Арк.
8
Зм. | Арк. | № докум | Підпис | Дата
2 ОПИС АЛГОРИТМУ РУТИСХАУЗЕРА
Алгоритм Рутисхаузера – один з найбільш простих, його особливістю є припущення про повну дужечність в структурі виразу. Під дужечністю розуміють запис виразу таким чином, що порядок і пріоритет операцій задається розстановкою дужок, а не явний пріоритет операцій при цьому не враховується.
В процесі обробки виразу на основі повної дуженної структури алгоритм присвоює кожному символу оброблюваного рядка номер рівня (пріоритету) за наступними правилами:
Правило 1: Якщо поточний символ – це дужка, що відкривається або заміна, то значення пріоритету зростає на одиницю.
Правило 2 : Якщо поточний символ – це знак операції або дужка що закривається, то пріоритет зменшується на одиницю.
Таким чином, для виразу (А + (B * С)) присвоєння значення рівнів пріоритету буде здійснюватись наступним чином
№ символу
1
2
3
4
5
6
7
8
9
Символ
(
А
+
(
В
*
С
)
)
Рівень пріоритету
1
2
1
2
3
2
3
2
1
Алгоритм трансляції складається з наступних кроків:
Крок 1: Здійснити розстановку пріоритетів;
Крок 2: Виконати пошук триплету (трійки символів) з максимальним значенням рівнів пріоритету;
Крок 3: Виділити трійку (два операнди з максимальним значенням рівнів пріоритету і операції між ними);
Крок 4: Здійснити обчислення, результат якого занести в проміжну змінну;
Крок 5: З вихідного рядка видалити виділений триплет разом з дужками, а на її місце помістити проміжну змінну, яка позначає результат зі значенням рівня пріоритету на одиницю менше ніж у виділеного триплету (трійки символів);
КП.КС-05.00.00.000 ПЗ | Арк.
9
Зм. | Арк. | № докум | Підпис | Дата
Крок 6: Виконувати операції 2, 3, 4 і 5 доти поки у вхідній послідовності не лишиться одна змінна, що позначає результат.
Генерований триплет
Вираз
+AB>R
(
(
(
(
А
+
В
)
·
С
)
/
D
)
-
E
)
0
1
2
3
4
5
4
5
4
3
4
3
2
3
2
1
2
1
0
*RC>S
(
(
(
R
*
C
)
/
D
)
-
E
)
0
1
2
3
4
3
4
3
2
3
2
1
2
1
0
/SD>Q
(
(
S
/
D
)
-
E
)
0
1
2
3
2
3
2
1
2
1
0
-QE>T
(
Q
-
E
)
0
1
2
1
2
1
0
КП.КС-05.00.00.000 ПЗ | Арк.
10
Зм. | Арк. | № докум | Підпис | Дата
3 ОПИС ПРОГРАМИ
Вхідний файл може включати змінні, що містять в імені (ім’я має довжину 31 символ) великі та малі букви англійського алфавіту (регістр символів не ігнорується), літерали (від -32768 до 32767), операції +(додавання), -(віднімання), *(множення), /(ділення), =(присвоєння значення змінній) та дужки “(”, “)”. Окрім цього, є оператори вводу (input <змінна>) та виводу (print <змінна>) змінних, що задаються тільки малими буквами і не можуть бути використані, як назви змінних. Коментарі програмою не підтримуються! Окремий рядок у вхідному файлі може мати одну з чотирьох форм:
A=((C-4)*B) // Присвоєння змінній значення виразу
var=-64 // Присвоєння змінній значення змінної або числа
input a // Ввід значення змінної з клавіатури
print F // Вивід значення змінної на екран
Змінні є 16-розрядними знаковими числами, тому їх значення та результат обчислень мають входити в діапазон від -32768 до 32767.
Програма формує текст програми на мові Асемблер для процесора 80386 з арифметичним співпроцесором 80387. Співпроцесор використовується для двостороннього перетворення між двійковими та двійково-десятковими числами в операторах вводу/виводу змінних. Для цих перетворень резервується 10 байт в сегменті даних. Оператори вводу/виводу реалізовані викликом відповідної підпрограми. Текст цих підпрограм наведений в четвертому розділі пояснювальної записки.
Арифметичні вирази обробляються за алгоритмом трансляції Рутисхаузера із заміною триплету на проміжну змінну “@”. В об’єктному коді її еквівалентом є регістр АХ, в якому зберігається проміжний результат обчислення виразу. Кодові взірці для усіх можливих конструкцій наведені в Табл. 1. Слід зауважити, що для присвоєння змінній значення числа формується не асемблерна команда, а директива <назва_змінної> DW <значення_змінної> в сегменті даних.
КП.КС-05.00.00.000 ПЗ | Арк.
11
Зм. | Арк. | № докум | Підпис | Дата
Таблиця 1
Конструкція
Асемблер
Довжина коду
(байт)
<змінна1>=<змінна2>
mov ax, <змінна2>
mov word [si+<змінна1>],ax
6
<змінна>=@
mov word <змінна>,ax
3
input <змінна>
lea bx, [si+<змінна>]
call input
6(7)
print <змінна>
lea bx, [si+<змінна>]
call print
6(7)
<змінна1>+<змінна2>
mov ax, <змінна1>
add ax, [si+<змінна2>]
6(7)
<змінна>+<число>
mov ax, <змінна>
add ax, <число>
6
<число>+<змінна>
mov ax, <число>
add ax, [si+<змінна>]
6(7)
<змінна>+@ або @+<змінна>
add ax, [si+<змінна>]
3(4)
<число>+@ або @+<число>
add ax, <число>
3
<змінна1>-<змінна2>
mov ax, <змінна1>
sub ax, [si+<змінна2>]
6(7)
<змінна>-<число>
mov ax, <змінна>
sub ax, <число>
6
<число>-<змінна>
mov ax, <число>
sub ax, [si+<змінна>]
6(7)
<змінна>-@
sub ax, [si+<змінна>]
neg ax
5(6)
@-<змінна>
sub ax, [si+<змінна>]
3(4)
<число>-@
sub ax, <число>
neg ax
5
@-<число>
sub ax, <число>
3
<змінна1>*<змінна2>
mov ax,<змінна1>
imul [si+<змінна2>]
6(7)
<змінна>*<число> або