Обчислення виразів на стековій машині

«Стековою машиною» називається алгоритм, що проводить обчислення по правилах зворотного польського запису. Алгоритм обчислення виразів у ЗПЗ для стекової машини:

1. Обробка вхідного символу

· Якщо на вхід поданий операнд, він міститься у вершині стеку.

· Якщо на вхід поданий знак операції, то відповідна операція виконується над необхідною кількістю значень, витягнутих зі стека, узятих у порядку додавання. Результат виконаної операції кладеться у вершину стеку.

2. Якщо вхідний набір символів оброблений не цілком, перейти до кроку 1.

3. Після повної обробки вхідного набору символів результат обчислення виразу лежить у вершині стека.

 

Генерація коду з використанням співпроцесора

        

         Реалізувавши проміжний код у вигляді зворотного польського запису можна легко згенерувати вихідний асемблерний код для цільової машини з архітектурою i86 і наявним співпроцесором. Головною перевагою використання співпроцесора в цьому випадку є те, що він функціонує за правилами стекової машини описаної в 3.3. Таким чином відпадає необхідність розподілу регістрів і організація зберігання проміжних результатів, яка необхідна при використанні проміжного тріадного коду для генерації вихідного асемблерного коду програми. Єдиним обмеженням є необхідність слідкувати за переповненням стеку співпроцесора.

       Використовуючи ЗПЗ розробляються процедури для генерації основних синтаксичних конструкцій вхідної мови. Розглянемо деякі з цих процедур.

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

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

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

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

       Процедура генерації занесення в стек співпроцесора змінної. Процедура викликається при виявлені у виразі змінної. Генерує команду занесення в стек співпроцесора змінної.

       Процедура виконання арифметичної операції. Процедура викликається при виявлені у виразі записаному у ЗПЗ операції, яка має виконатися над операндами в стеку співпроцесора.

       Процедура виконання операції присвоєння. Процедура викликається після завершення обчислення виразу, записаного у формі ЗПЗ. Виштовхує з вершини стеку співпроцесора результат операції і передає його змінній-приймачу.

       Процедура генерації логічної операції. Процедура викликається при виявлені у виразі записаному у ЗПЗ логічної операції. При цьому генерується операція порівняння операндів стеку співпроцесора та занесення результату порівняння в регістр прапорців процесора.

Процедура генерації оператора циклу типу while. Процедура викликається при виявлені синтаксичної конструкції, що описує цикл while. При цьому вона повинна:

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

 

Детальніше про особливості генерації коду та приклади реалізації генераторів коду можна довідатися у [1, 2].

Література

1. Ахо А., Сети Р., Ульман Дж. Компиляторы. Принципы, технологии, инструменты. М.: Изд-во «Вильямс», 2001.–768 с

2. Молчанов А.Ю. Системное программное обеспичение. Лабораторный практикум. – СПб.: Питер, 2005. – 284с.:ил.

3. Хантер Р. Проектирование и конструирование компиляторов. - М.: Финансы и статистика, 1984. - 232 с.

4. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. - М.: Мир. 1975. - 554 с.

5. Льюис Ф., Розенкранц Д., Смирну Д. Теоретические основы проектирования компиляторов. - М.: Мир, 1979. - 656 с.

6. Рейруорд-Смит В. Дж. Теория формальных языков. - М.: Радио и связь, 1988. - 128 с.

7. Ваймгартен Ф. Трансляция языков программирования. – М.: Мир, 1977.

8. Бек Л. Введение в системное программирование. – М.: Мир, 1988. – 448 с.

9. Касьянов В.Н. Оптимизирующие преобразования программ. – М.: Наука, 1988.

10. Серебряков В.А. Лекции по конструированию компиляторов, Москва 1993.

11. Варсанофьев Д.В., Дымченко А.Г. Основы компиляции, 1991.

12. Легалов А.И. Основы проектирования компиляторов, Курс лекций, 2000.

13. Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программирование. Основы построения трансляторов. – СПб.: КОРОНА принт, 2004. – 256 с.

14. Соколов А.П. Системы программирования. Теория, методы, алгоритмы. – М.: Финансы и статистика, 2004. – 320 с.

15. Костельцев А.В. Построение интерпретаторов и компиляторов. – М.: Наука и техника, 2001. – 224 с.

16. http://habrahabr.ru/blogs/algorithm/50509/

17. http://www.cs.man.ac.uk/~pjj/cs211/flexdoc.html

18. http://www.cl.cam.ac.uk/~mgk25/iso-14977.pdf

19. http://ru.wikipedia.org/wiki/Обратная_польская_запись

20. http://citforum.ru/programming/theory/serebryakov/9.shtml