Формальний опис вхідної мови програмування

 

Розробити компілятор заданої вхідної мови програмування.

- три типи даних: логічний тип даних (boolean), знаковий цілочисельний тип (1byte) та беззнаковий цілочисельний тип розміром 1 байт;

- змінних з довільної довжини;

- арифметичні операції над цілими: +, -, *, /, “-” (унарний мінус), ^ (операція піднесення до степеню);

- символи групування арифметичних операцій “(”, “)”

- логічні операції над цілими: <, >, ==, | =;

- логічну операцію над логічними даними NOT;

- оператор присвоєння “=”;

- оператори блоку “{“, “}”;

- оператор виводу (print);

- оператор виконання дії за умовою (if-then-else);

- оператор циклу (do-while);

Визначимо окремі термінальні символи та нерозривні набори термін.

Символів(ключові слова);

{(usigned

}) char

; < if

= > then

+ = = else

- <> while

^ NOT do

* program true

/ bool false

print

До термінальних символів віднесемо також усі цифри (0-9), латинські букви (a-z, A-Z) та символ пробілу (“ ”). Всього 28+10+52+1=91 термінальних виразів. Це “цеглинки”, з яких має будуватися текст будь-якої вхідної програми.

- символ “ | ” розділяє альтернативи

- символи “ [ ”,“ ] ” означає необов’язковість

- символи “ { ”,“ } ” означає повтор

Формальний опис заданої мови BNF:

<program>::= prog <block>

<block>::= {<statement> | [{<statement >}]}

<statement>::= <declaration> | <operator>

<declaration>::=<type><ident>;

<operator>::=<bind> | <if-then-else> | <do-while > | <print>

<bind>::=<ident> = <expression>;

<if-then-else>::= if <bool expression> then <bloc> [else<bloc>]

<while-do>::= while <bool_ehpression> do <bloc>

<print>::= print <ident> | <int-const> | <log-const>;

<type>::= boolean | byte | ubyte

<ident>::=<letter> [{<letter>}]

<byte_corst>::= [] <number> [{<number>}]

<bool_const>::= true | false

<letter>::= a | …| z | A | … | Z

<number>::= 0 | 1 | … | 9

<logic.conct>::= true | fals

<expression>::=<num.expression>|<bool_expression>|<log.expression>

<num.expression>::=<num_operand>[{<num.operation><num.operand>}]

<bool_expression>::=<num.operand>[{<bool.operation><num_operand>}]

<logic_expression>::=<logic_operand>[{|<logic.operand>}]

<logic_operand>::= (<logic_expression>) | <ident>|<logic_const>

<num.operand>::=(<num.expression>) | <ident> | <byte_const>

<num.operation>::= * | / | + | - | ^

<bool_operation>::= < | > | = = | < >

<log_expression>::=<log_operand> [{NOT<log_operand>}]

<log_operand>:: (<log_expression>) | <cident> | <logic_const>

 

Розробка компілятора вхідної мови програмування

 

Процедурно-орієнтовані мови програмування, такі як FORTRAN, Pascal, C, C++ та ін. засновані на принципі послідовного виконання операторів, команд або директив. Їх базові оператори, операції, команди та директиви можна класифікувати по трьох основних групах:

а) Безумовні оператори (statements) обрахунків та перетворень;

б) Оператори обробки розгалужень та передачі управління;

в) Оператори організації циклічної обробки.

В загальному випадку віртуальна машина складається з інформаційного, операційного, управляючого та комунікаційного компонентів. Будь-яка віртуальна машина повинна мати:

а) Пам’ять різних видів та типів для збереження кодів програм і даних (інформаційний компонент) і механізми доступу до неї;

б) Вказівник поточної операції (основа управляючої компоненти), що змінюється при підрахунку номера оператора;

в) Блок виконання операцій (operators), який реалізує функції операційних та управляючих компонентів. Разом з інтерфейсним обладнанням він реалізує комунікаційний компонент, який забезпечує зв’язок ВМ із зовнішнім світом.

Загальна схема компілятора

Можна виділити сім різних логічних задач:

а. Інтерпретація – визначення точного змістового навантаження, створення матриці та таблиць з допомогою програм інтерпретації;

б. Машинно-незалежна оптимізація – створення оптимальнішої матриці;

в. Лексичний аналіз – розпізнавання базових елементів та створення стандартних символів;

г. Синтаксичний аналіз – розпізнавання базових синтаксичних конструкцій з використанням редукцій;

д. Розподіл пам’яті – модифікація таблиць ідентифікаторів та літералів. В матриці розміщується інформація, з допомогою якої генерується код, який розподіляє динамічну пам’ять;

е. Генерація коду – використання макропроцесора для отримання більш оптимального вихідного коду;

Фази з першої по четверту машинно-незалежні і визначаються тільки мовою. Фази з п’ятої по сьому – машинно-залежні і не залежать від мови. З метою забезпечення вищої ефективності ці фази можуть не розділятись так чітко.

Компілятор необхідно оцінювати не тільки по об’єктному коду, що генерується, але також і по об’єму оперативної пам’яті, що він займає і по часу, що потрібен для трансляції. На жаль, ці критерії оптимальності часто досить суперечливі. Крім того, оптимальність коду обернено пропорційна складності, розміру та часу роботи самого компілятора. Насправді необхідні компроміси.

Компілятором використовуються бази даних, що забезпечують зв’язки між фазами: вхідний код, таблиця стандартних символів, таблиця термінальних символів, таблиця ідентифікаторів, таблиця літералів, редукції, матриця, кодові продукції, код компоновки, кінцевий об’єктний код.