Формули Бекуса-Наура для мови Pascal

<програма> ::= <заголовок програми> <блок>.

<заголовок програми> ::= program <і’мя> ( <і’мя файла> {, <і’мя файла> });

<і’мя файла> ::= <і’мя>

<і’мя> ::= <буква> { <буква чи цифра> }

<буква чи цифра> ::= <буква> | <цифра>

<блок> ::= <розділ міток> <розділ констант> <розділ типів> <розділ змінних>

 <розділ процедур і функцій> <розділ операторів>

<розділ міток> ::= <пусто> | label <мітка> {, < мітка > };

<мітка> ::= <ціле без знаку>

<розділ констант> ::= <пусто> | const <визначення константи>

{; <визначення константи> };

<визначення константи> ::= <і’мя> = <константа>

<константа> ::= <число без знаку> | <знак> <число без знаку> | <ім’я константи> |

                           <знак> <ім’я константи> | <рядок>

<число без знаку> ::= <ціле без знаку> | <дійсне без знаку>

<ціле без знаку> ::= <цифра> {<цифра>}

<дійсне без знаку> ::= <ціле без знаку>. <цифра> {<цифра>} |

                                           <ціле без знаку>. <цифра> {<цифра>} E <порядок> |

                                           <ціле без знаку> E <порядок>

<порядок> ::= <ціле без знаку> | <знак> <ціле без знаку>

<знак> ::= + | –

<ім’я константи> ::= <ім’я>

<рядок> ::= ’ <символ> {<символ>} ’

<розділ типів> ::= <пусто> | type <визначення типу> {; <визначення типу> };

<визначення типу> ::= <ім’я> = <тип>

<тип> ::= <простий тип> | <складовий тип> | <вказівний тип>

<простий тип> ::= <скалярний тип> | <обмежений тип> | <ім’я типу>

<скалярний тип> ::= ( <ім’я> {, <ім’я> })

<обмежений тип> ::= <константа> .. <константа>

<ім’я типу> ::= <ім’я>

<складовий тип> ::= <неупакований складовий тип> |

                                 packed <неупакований складовий тип>

<неупакований складовий тип> ::= <регулярний тип> | <комбінований тип> |

                                               <множинний тип> | <файловий тип>

<регулярний тип> ::= array[ <тип індекса> {, <тип індекса> }] of   <тип компонента>

<тип індекса> ::= <простий тип>

<тип компонента> ::= <тип>

<комбінований тип> ::= record <список полів> end

<список полів> ::= <фіксована частина> | <фіксована частина>

                                      <варіантна частина> | <варіантна частина>

<фіксована частина> ::= <секція запису> {; <секція запису> }

<секція запису> ::= <ім’я поля> {, <ім’я поля> }: <тип> | <пусто>

<варіантна частина> ::= case <дискримінант> <ім’я типу> of <варіант> {; <варіант> }

<дискримінант> ::= <ім’я поля>: | <пусто>

<варіант> ::= <список міток варіанту>: ( <список полів> ) | <пусто>

<список міток варіанту> ::= <мітка варіанту> {, <мітка варіанту> }

<мітка варіанту> ::= <константа>

<множинний тип> ::= set of <базовий тип>

<базовий тип> ::= <простий тип>

<файловий тип> ::= file of <тип>

<вказівний тип> ::= ^ <ім’я типу>

<розділ змінних> ::= <пусто> | var <опис змінної> {; <опис змінної> };

<опис змінної> ::= <ім’я> {, <ім’я> }: <тип>

<розділ процедур і функцій> ::= { <опис процедури чи функції> ;}

<опис процедури чи функції> ::= <опис процедури> | <опис функції>

<опис процедури> ::= <заголовок процедури> <блок>

<заголовок процедури> ::= procedure <ім’я> |

                                               procedure <ім’я> (<розділ формальних параметрів>

                                               {; <розділ формальних параметрів> });

<розділ формальних параметрів> ::= <група параметрів> | var <група параметрів> |

                                               function <група параметрів> | procedure <ім’я> {, <ім’я> }

<група параметрів> ::= <ім’я> {, <ім’я> }: <ім’я типу>

<опис функції> ::= <заголовок функції> <блок>

<заголовок функції> ::= function <ім’я>: <тип результату> |

                                        function <ім’я> ( <розділ формальних параметрів>

                                        {; <розділ формальних параметрів> }): <тип результату>;

<тип результату> ::= <ім’я типу>

<розділ операторів> ::= <складовий оператор>

<оператор> ::= <непозначений оператор> | <мітка>: <непозначений оператор>

<непозначений оператор> ::= <простий оператор> | <складний оператор>

<простий оператор> ::= <оператор присвоювання> | <оператор процедури> |

                                                <оператор переходу> | <порожній оператор>

<оператор присвоювання> ::= <змінна> := <вираз> | <ім’я функції> := <вираз>

<змінна> ::= <повна змінна> | <компонентна змінна> | <вказівна змінна>

<повна змінна> ::= <ім’я змінної>

<ім’я змінної> ::= <ім’я>

<компонентна змінна> ::= <індексована змінна> | <позначення поля> | <буфер файла>

<індексована змінна> ::= <змінна-масив> [ <вираз> {, <вираз> }]

<змінна-масив> ::= <змінна>

<позначення поля> ::= <змінна-запис>. <ім’я поля>

<змінна-запис> ::= <змінна>

<ім’я поля> ::= <ім’я>

<буфер файла> ::= <змінна-файл>^

<змінна-файл> ::= <змінна>

<вказівна змінна> ::= <змінна-посилання> ^

<змінна-посилання> ::= <змінна>

<вираз> ::= <простий вираз> | <простий вираз> <операція відношення> <простий вираз>

<операція відношення> ::= = | <> | < | <= | > | >= | in

<простий вираз> ::= <доданок> | <знак> <доданок> |

                                                                  <простий вираз> <адитивна операція> <доданок>

<адитивна операція> ::= + | – | or

<доданок> ::= <множник> | <доданок> <мультиплікативна операція> <множник>

<мультиплікативна операція> ::= * | / | div | mod | and

<множник> ::= <змінна> | <константа без знаку> | ( <вираз> ) |

                                                    <позначення функції> | <множина> | not <множник>

<константа без знаку> ::= <число без знаку> | <рядок> | <ім’я константи> | nil

<позначення функції> ::= <ім’я функції> | <ім’я функції> ( <фактичний параметр>

                                                                                                        {, <фактичний параметр> })

<ім’я функції> ::= <ім’я>

<множина> ::= [ <список елементів> ]

<список елементів> ::= <елемент> {, <елемент> } | <пусто>

<елемент> ::= <вираз> | <вираз> .. <вираз>

<оператор процедури> ::= <ім’я процедури> | <ім’я процедури> ( <фактичний параметр>       {, <фактичний параметр> })

<ім’я процедури> ::= <ім’я>

<фактичний параметр> ::= <вираз> | <змінна> | <ім’я процедури> | <ім’я функції>

<оператор переходу> ::= goto <мітка>

<порожній оператор> ::= <пусто>

<складний оператор> ::= <складовий оператор> | < вибираючий оператор > |

                                                             <оператор циклу> | <оператор приєднання>

<складовий оператор> ::= begin <оператор> {; <оператор> } end

< вибираючий оператор > ::= <умовний оператор> | <оператор варіанту>

<умовний оператор> ::= if <вираз> then <оператор> |

                                          if <вираз> then <оператор> else <оператор>

<оператор варіанту> ::= case <вираз> of <елемент списку варіантів>

                                                                    {; <елемент списку варіантів> } end

<елемент списку варіантів> ::= <список міток варіанту>: <оператор> | <пусто>

<список міток варіанту> ::= <мітка варіанту> {, <мітка варіанту> }

<оператор циклу> ::= <цикл з передумовою> | <цикл з післяумовою> |

                                   <цикл з параметром>

<цикл з передумовою> ::= while <вираз> do <оператор>

<цикл з післяумовою> ::= repeat <оператор> {; <оператор> } until <вираз>

<цикл з параметром> ::= for <параметр циклу> := <список циклу> do <оператор>

<список циклу> ::= <початкове значення> to <кінцеве значення> |

                                   <початкове значення> downto <кінцеве значення>

<параметр циклу> ::= <ім’я>

<початкове значення> ::= <вираз>

<кінцеве значення> ::= <вираз>

<оператор приєднання> ::= with <список змінних-записів> do <оператор>

<список змінних-записів> ::= <змінна-запис> {, <змінна-запис> }

 

2.2. Способи побудови синтаксичного аналізатора

           

Синтаксичний аналізатор – це частина компілятора, транслятора чи інтерпретатора, яка перевіряє текст вхідної програми на відповідність синтаксичним правилам мови. При цьому синтаксичний аналізатор вирішує такі задачі:

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

встановлює типі і перевіряє коректність кожної синтаксичної конструкції;

представляє синтаксичні конструкції у вигляді проміжного коду, який легко обробляти на стадії генерації коду.

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

Синтаксичний аналізатор працює у відповідності до правил контестно-вільної граматики, яка задається, наприклад, формулами Бекуса-Наура. При цьому існує неоднозначна ситуація, хто, лексичний аналізатор чи синтаксичний аналізатор має виділяти деякі конструкції задані правилами контестно-вільної граматики? До таких конструкцій належать ключові слова, константи і ідентифікатори. При цьому відсутні правила, які чітко регламентують сфери відповідальності лексичного і синтаксичного аналізаторів. Тому розподіл обов’язків між ними визначає розробник.

 

2.2.1. Низхідний аналіз

 

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

· наявність опису граматики мови програмування формулами Бекуса-Наура;

· розробка процедур для кожного з правил граматики;

· кожна лексема однозначно визначає альтернативу вибору.

Синтаксичний аналіз розділеного на лексеми тексту програми починається з правила граматики найвищого рівня, що визначає кінцеву мету розбору. Тобто з кореня дерева, яке описує, наприклад, що таке програма. Далі аналіз продовжується до листків дерева граматичного розбору. При цьому проводиться аналіз послідовності лексем і здійснюється спроба виділити лексему, яка визначається одним з правил граматики. Після виділення лексеми викликають процедуру для обробки даного правила граматики. Робота процедури полягає в полексемному скануванні таблиці лексем і правила граматики та співставленні послідовності виділених лексем цьому правилу граматики. Якщо при скануванні правила граматики зустрічається нетермінальний символ, то для нього викликається процедура обробки відповідного правила граматики, яке відповідає цьому нетерміналу. Виклики процедур продовжуються доти, поки в правилі не зустрінеться термінальний символ. Оскільки правила граматики можуть містити рекурсію, то передбачається можливість рекурсивного виклику процедур. Процедура повертає істину у випадку вдалого виділення синтаксичної конструкції, або хибу, якщо виділити конструкцію не вдалося. При невдачі необхідно повернутися до початкової лексеми та продовжити пошук правила для виділення наступної конструкції. Таким чином забезпечується механізм вибору вірної альтернативи, якщо правило граматики складається з кількох альтернатив, або в наявності є кілька правил, що відповідають терміналу. Якщо для лексеми, що зустрілася, не підходить жодне з правил граматики, то видається повідомлення про граматичну помилку.

 

2.2.2. Приклад низхідного граматичного розбору

 

Розглянемо приклад граматичного розбору розділу оголошення змінних, що задається наступними тестом програми:

Variables _v1, _v2: int4;

Нехай після обробки лексичним аналізатором даний рядок буде трансформований у таку послідовність лексем:

1 2 3 2 4 5 6

що задається наступною таблицею відповідності лексем їх числовим еквівалентам:

1 – Variables

2 – ідентифікатор

3 –,

4 –:

5 – int4

6 –;

 

Нехай розділу оголошень відповідає наступні граматичні правила описані в термінах нотації Бекуса-Наура:

 

<розділ оголошень>::=Variables {<ідентифікатор>{,< ідентифікатор >}:<тип>;}

< ідентифікатор >::=_<буква або цифра>{<буква або цифра>}

<буква або цифра>::= <буква> | <цифра>

<буква>::=a|b|c|d|…|z

<цифра>::=0|1|2|3|4|5|6|7|8|9

<тип>::=int2|int4|real

Таким чином, зустрівши лексему з числовим еквівалентом 1 синтаксичний аналізатор викличе процедуру обробки правила <розділ оголошень>. Наступною лексемою відповідно до цього правила має іти нуль або більше повторень нетерміналу <ідентифікатор> у відповідність якому ставиться числовий еквівалент лексеми 2. На даному етапі не відбувається виклик процедури для правила ідентифікатор, оскільки передбачається, що лексема, яка відповідає правилу <ідентифікатор> виділяється на етапі лексичного аналізу з занесенням назви ідентифікатора в таблицю ідентифікаторів. Тобто ця процедура реалізована в лексичному аналізаторі.

Наступними лексемами є лексеми з числовими еквівалентами 3 і 2, які відповідають блоку {,< ідентифікатор >}. Після цього зустрічається лексема 4 і лексема 5. При цьому лексема 5 відповідає нетерміналу <тип>. Для обробки цього нетерміналу (правила) викликається відповідна процедура. Оскільки для правила <тип> передбачено наявність лексеми int4, то дана процедура поверне істину. Останньою іде лексема-обмежувач командного рядка з цифровим еквівалентом 6.

Таким чином, пересвідчившись, що весь рядок вхідної програми відповідає правилу граматики <розділ оголошень> процедура обробки цього правила поверне істину.

 

2.2.3. Розробка низхідного синтаксичного аналізатора

2.2.3.1. Опис вхідної мови в термінах нотації Бекуса-Наура

 

<програма>                      ::= Program begin <блок> end.

<блок>                             ::= <розділ змінних><розділ операторів>

<розділ змінних>              ::= <пусто>| float <змінна>{, <змінна>};

<змінна >                         ::= <буква>{<буква>|<цифра>}

<буква>                        ::= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h

                                         |і|j|k|l|m|n|o|p|q|r|s| t|u|v|w|x|y|z

<цифра>                          ::= 0|1|2|3|4|5|6|7|8|9

<розділ операторів>         ::= {<простий оператор>|<оператор вводу>|<оператор виводу>|<цикл>}

<простий оператор>         ::= <порожній оператор>|<оператор присвоювання>

<порожній оператор>        ::= <пусто>;

<оператор присвоювання>::= <змінна> = <вираз>;

<вираз>                            ::= { ( <доданок> ) }<доданок>|<знак><доданок>|<доданок>

                                         <адитивна операція><доданок>

<адитивна операція>        ::= + | -

<доданок>                        ::= <множник>|<множник><мультиплікативна операція><множник>

<мультиплікативна операція>::= * | /

<множник>                       ::= <змінна>|<число>

<число>                           ::= <число без знаку>|<знак><число без знаку>

<число без знаку>            ::= <дійсне без знаку>

<дійсне без знаку>           ::= <цифра>{<цифра>}. <цифра>{<цифра>}|<цифра>{<цифра>}

<знак>                              ::= < + | - >

<опертор виводу >           ::= printf ( <string> );

<оператор вводу >           ::= scanf (%f, & <змінна> );

<string>                            ::= <рядок>|” %f ”,<змінна>

<рядок >                          ::= ”{<бц>}”

<бц>                                ::= <буква>|<цифра>

<цикл>::= while( <змінна> <ло> <змінна> ) begin {порожній оператор} | {<розділ операторів>} end;

<ло>                                ::= != | == | <= | >= | < | >

 

2.2.3.2. Розробка дерева граматичного розбору

 

    На рис.2.1. зображено дерево граматичного розбору, яке відповідає БНВ з 2.2.3.1. Оскільки перевірка коректності імен ідентифікаторів (змінних) відбувається на етапі лексичного аналізу, то в дереві граматичного розбору розбір ідентифікаторів відсутній. Так само для розбору виразів викликається процедура перетворення виразу в постфіксну форму, яка крім перетворення в постфіксну форму здійснює контроль дужок і генерацію помилок.

Рис. 2.1. Дерево граматичного розбору.

 

2.2.4. Висхідний аналіз

 

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

Серед висхідних методів аналізу виділяють:

1. Метод обрізки основ

2. Метод операторного передування

3. LR-аналізатори

Зокрема генератори синтаксичних аналізаторів, такі як Yacc використовують в своїй роботі механізми LR-аналізаторів. Іншим відомими генераторами синтаксичних аналізаторів є Bison, ZUBR, що використовують LALR граматики в своїй роботі.

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

 

2.2.5. Генератори синтаксичних аналізаторів

 

Генератори синтаксичних аналізаторів розглянемо на прикладі програми Zubr. ZUBR – це LALR(1) генератор синтаксичних аналізаторів. Синтаксичні аналізатори, що створюються за допомогою ZUBR реалізують висхідний LALR(1) розбір. LALR(1) – це модифікація висхідного LR(k) розбору, де LR означає читання вхідних символів зліва на право і використання правостороннього висновку, k – кількість символів, що попередньо проглядаються. Таким чином в своїй роботі ZUBR використовує контекстно-вільні граматики з властивостями LALR(1), що є підмножиною LR(1) граматик.

ZUBR приймає на вхід специфікацію синтаксичного аналізатора написану користувачем і генерує функцію граматичного розбору, що по замовчуванню називається zubr_parse(), яка відповідає заданим правилам граматики. Граматика задається у формі близькій до БНФ. Наприклад нетермінал <digit> задається таким чином:

digit: ‘1’ | ‘2’ | ‘3’ | ’4’ | ‘5’ | ‘6’ | ‘7’ | ‘8’| ‘9’| ‘0’;

 На вхід функції синтаксичного аналізатора через стек поступають термінальні символи, які генерує функція лексичного аналізатора, що зветься zubr_lex() і повинна бути написана користувачем або згенерована в деякий спосіб. Для утворення функції лексичного аналізатора можна скористатися генератором лексичних аналізаторів Lex або Flex. Задачею лексичного аналізатора є інформувати про прочитання відповідного терміналу. Термінали – це цілі числа, яким співставленні мнемонічні імена, наприклад термінал COMMA задається таким чином:

#define COMMA 259

Таке визначення терміналу генерується програмою ZUBR автоматично в процесі створення тексту вихідного файлу.

Специфікація синтаксичного аналізатора складається з трьох секцій і має наступну структуру:

декларації

%%

правила

%%

програми

Секція правил має мати бодай одне правило, наприклад

digit: ‘1’ | ‘2’ | ‘3’ | ’4’ | ‘5’ | ‘6’ | ‘7’ | ‘8’| ‘9’| ‘0’;

Імена, що представляють термінали слід декларувати заздалегідь в секції декларацій:

       %token name1 name2 ….

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

Найважливішим нетерміналом є стартовий нетермінал, який намагатиметься вивести граматичний аналізатор. Він задається:

%start symbol

де symbol – стартовий нетермінал.

Кінець вводу задається спеціальним терміналом, що називається ”end-marker”. Якщо при граматичному розборі виведеться symbol до зустрічі з end-marker то це означатиме коректне завершення граматичного розбору і функція zubr_parse() поверне 0.

Детальніше про генератор синтаксичних аналізаторів ZUBR можна довідатися у [15].

 

2.2.6. Приклад тексту специфікації для ZUBR

 

/**************************************************************

MAIN.Y

 **************************************************************/

%{

#include "init.h"

#include "symtab.h"

#include "mathf.h"

#include "code.h"

#include "main.h"

 

#define code2(c1,c2) code(c1); code(c2)

#define code3(c1,c2,c3) code(c1); code(c2); code(c3)

 

int indef;

 

%}

// початок секції декларацій

// оголошення типу елементів стеку

%union

{

SYMBOL *sym;

INST  *inst;

int narg;

}

// перлік терміналів

%token <sym> NUMBER VAR BLTIN UNDEF STRING

%token <sym> ADDEQ SUBEQ MULEQ DIVEQ

%token <sym> PRINT WHILE IF ELSE

%token <sym> FUNCTION PROCEDURE RETURN FUNC PROC READ

%token <narg> ARG

%type <inst> expr assign

%type <inst> stmt stmtlist prlist cond while if begin end

%type <sym> procname

%type <narg> arglist

//перелік операцій з вказанням асоціативності

%right '='

%right ADDEQ SUBEQ MULEQ DIVEQ

%left OR

%left AND

%left GT GE LT LE EQ NE

%left '+' '-' /* left associative, same precedence */

%left '*' '/' /* left associative, higher precedence */

%left UNARYMINUS NOT

%right '^'  /* power */

 

%start list

// кінець секції декларацій

 

 

%%

// початок секції визначення правил

list: /* nothing */

  | list '\n'

  | list defn '\n'

  | list assign '\n' { code2((INST)void_pop, STOP); return(1); }

  | list stmt '\n' { code (STOP);            return(1); }

  | list expr '\n' { code2((INST)print, STOP); return(1); }

  | list error '\n'

    {

       zubr_errok;

    }

 ;

/*

У фігурних дужках визначаються семантичні процедури, що будуть викликані при застосуванні заданого правила. Через символ $х, де х – елемент стеку здійснюється доступ до елементів стеку. Вершина стеку позначається як $$. $$ завжди містить те, що і $1. 

*/

assign: VAR '=' expr { code3((INST)varpush, (INST)$1, (INST)assign); }

  | VAR ADDEQ expr { code3((INST)varpush, (INST)$1, (INST)Yaddeq); }

  | VAR SUBEQ expr { code3((INST)varpush, (INST)$1, (INST)Ysubeq); }

  | VAR MULEQ expr { code3((INST)varpush, (INST)$1, (INST)Ymuleq); }

  | VAR DIVEQ expr { code3((INST)varpush, (INST)$1, (INST)Ydiveq); }

  | ARG '=' expr

    { defnonly("$"); code2((INST)argassign, (INST)$1); $$ = $3; }

 ;

 

stmt: expr          { code((INST)pop); }

  | RETURN

    { defnonly("return"); code((INST)procret); }

  | RETURN expr

    { defnonly("return"); $$ = $2; code((INST)funcret); }

  | PROCEDURE begin '(' arglist ')'

    { $$ = $2; code3((INST)call, (INST)$1, (INST)$4); }

  | PRINT prlist  { $$ = $2; }

  | while cond stmt end

    {

       ($1)[1] = (INST)$3; /* тіло циклу */

       ($1)[2] = (INST)$4; /* end */

    }

  | if cond stmt end

    {

       ($1)[1] = (INST)$3; /* частина then */

       ($1)[3] = (INST)$4; /* end */

    }

  | if cond stmt end ELSE stmt end

    {

       ($1)[1] = (INST)$3; /* частина then */

       ($1)[2] = (INST)$6; /* частина else */

       ($1)[3] = (INST)$7; /* end */

    }

  | '{' stmtlist '}' { $$ = $2; }

 ;

 

cond: '(' expr ')' { code(STOP); $$ = $2; }

 ;

 

while: WHILE { $$ = code3((INST)whilecode, STOP, STOP); }

 ;

 

if: IF

    {

       $$ = code((INST)ifcode);

       code3(STOP, STOP, STOP);

    }

 ;

 

begin: /* nothing */ { $$ = pprog; }

 ;

 

end: /* nothing */ { code(STOP); $$ = pprog; }

 ;

stmtlist: /* nothing */ { $$ = pprog; }

  | stmtlist '\n'

  | stmtlist stmt

 ;

 

expr: NUMBER  { code2((INST)constpush, (INST)$1); }

  | VAR     { code3((INST)varpush, (INST)$1, (INST)eval); }

  | ARG

    { defnonly("$"); $$ = code2((INST)arg, (INST)$1); }

  | assign  { code3((INST)varpush, (INST)$1, (INST)eval); }

  | FUNCTION begin '(' arglist ')'

    { $$ = $2; code3((INST)call, (INST)$1, (INST)$4); }

  | READ '(' VAR ')'

    { $$ = code2((INST)varread, (INST)$3); }

  | BLTIN '(' expr ')' { code2((INST)bltin, (INST)$1->u.ptr); }

  | BLTIN '(' expr ',' expr ')'

    {

       code2((INST)bltin2, (INST)$1->u.ptr);

    }

  | expr '+' expr        { code((INST)Yadd); }

  | expr '-' expr        { code((INST)Ysub); }

  | expr '*' expr        { code((INST)Ymul); }

 

  | expr '/' expr        { code((INST)Ydiv); }

 

  | expr '^' expr        { code((INST)power); }

  | '(' expr ')'         { $$ = $2; }

  | '-' expr %prec UNARYMINUS { code((INST)negate); }

  | expr GT expr        { code((INST)gt); }

  | expr GE expr        { code((INST)ge); }

  | expr LT expr        { code((INST)lt); }

  | expr LE expr        { code((INST)le); }

  | expr EQ expr        { code((INST)eq); }

  | expr NE expr        { code((INST)ne); }

  | expr AND expr        { code((INST)and); }

  | expr OR expr        { code((INST)or); }

  | NOT expr             { $$ = $2; code((INST)not); }

 ;

 

prlist: expr         { code((INST)prexpr); }

  | STRING       { $$ = code2((INST)prstr, (INST)$1); }

  | prlist ',' expr { code((INST)prexpr); }

  | prlist ',' STRING { $$ = code2((INST)prstr, (INST)$3); }

    ;

 

defn: FUNC procname

    { $2->type = FUNCTION; indef = 1; }

    '(' ')' stmt

    { code((INST)funcret); defin($2); indef = 0; }

  | PROC procname

    { $2->type = PROCEDURE; indef = 1; }

    '(' ')' stmt

    { code((INST)procret); defin($2); indef = 0; }

 ;

 

procname: VAR

  | FUNCTION

  | PROCEDURE

 ;

 

arglist: /* nothing */ { $$ = 0; }

  | expr        { $$ = 1; }

  | arglist ',' expr { $$ = $1 + 1; }

 ;

// кінець секції правил

%%

 

/******************** END OF GRAMMAR ***********************/

 

char *progname;

 

FILE *input_file;

char *input_file_name;

 

int lineno = 1;

 

// функція-обробник попереджень

void warning(char *s, char *t)

{

fprintf(stderr, "%s: %s", progname, s);

if(t) fprintf(stderr, " %s", t);

fprintf(stderr, " near line %d\n", lineno);

}

 

// функція-обробник помилок

void zubr_error(char *s)

{

warning(s, (char *)0);

}

 

int follow(int expect, int ifyes, int ifno)

{

register FILE *f = input_file;

register int c;

 

c = getc(f);

 

if(c == expect) return(ifyes);

ungetc(c, f);

return(ifno);

}

 

int backslash(int c)

{

register FILE *f = input_file;

static char tabl[] = "b\bf\fn\nr\rt\t";

char *p = (char *)0;

 

if(c!= '\\') return(c);

 

c = getc(f);

p = (char *)index(tabl, c); /* or strchr() */

if(islower(c) && p!= (char *)0)

return(p[1]);

return(c);

}

 

// лексичний аналізатор

int zubr_lex(void)

{

register FILE *f = input_file;

register int c;

 

lineno++;

 

 

while((c = getc(f)) == ' ' || c == '\t' || c == '\r')

;

if(c == EOF) return(0);

if(c == '.' || isdigit(c))

{

double d = 0.0;

int n = getc(f);

 

  /* даній функції scanf() не можна віддавати число "." */

if(c == '.' &&!isdigit(n))

{

    ungetc(n, f);

// install – функція реєстрації лексем

zubr_lval.sym = install("", NUMBER, d);

    return(NUMBER);

}

ungetc(n, f);

 

/* number */

ungetc(c, f);

n = fscanf(f, "%lf", &d);

zubr_lval.sym = install ("", NUMBER, d);

 

return(NUMBER);

}

if(isalpha(c))

{

SYMBOL *sp;

char sbuf[256], *p = sbuf;

 

do

{

    *p++ = c;

} while((c=getc(f))!= EOF && isalnum(c));

 

ungetc(c, f);

*p = '\0';

// lookup – функція, яка здійснює пошук зареєстрованих лексем

if((sp = lookup(sbuf)) == (SYMBOL *)0)

    sp = install(sbuf, UNDEF, 0.0);

zubr_lval.sym = sp;

 

return(sp->type == UNDEF? VAR: sp->type);

}

 

if(c == '$')

{

int n = 0;

 

while(isdigit(c = getc(f)))

    n = 10 * n + c - '0';

ungetc(c, f);

 

if(n == 0)

    warning("strange $...", (char *)0);

zubr_lval.narg = n;

 

return(ARG);

}

 

if(c == '"')

{

SYMBOL *sp;

char sbuf[256], *p;

 

for(p =sbuf; (c = getc(f))!= '"'; p++)

{

    if(c == '\n' || c == EOF)

       warning("missing quote", "\"");

    if(p >= sbuf + sizeof(sbuf) - 1)

    {

       *p = '\0';

       warning("string too long", sbuf);

    }

    *p = backslash(c);

}

*p = '\0';

 

   zubr_lval.sym = (SYMBOL *)emalloc(strlen(sbuf) + 1);

strcpy((char *)zubr_lval.sym, sbuf);

 

return(STRING);

}

 

if(c == '\n') { lineno++; return(c); }

 

 

switch(c)

{

case '+': return follow('=', ADDEQ, '+');

    case '-': return follow('=', SUBEQ, '-');

case '*': return follow('=', MULEQ, '*');

case '/': return follow('=', DIVEQ, '/');

 

case '>': return follow('=', GE, GT);

case '<': return follow('=', LE, LT);

case '=': return follow('=', EQ, '=');

case '!': return follow('=', NE, NOT);

case '|': return follow('|', OR, '|');

case '&': return follow('&', AND, '&');

 

default: return(c);

}

 

}

 

// головна функція

int main(int argc, char *argv[])

{

 

progname = argv[0];

if (argc < 2)

{

fprintf(stderr, "usage: %s file.name\n", progname);

exit(1);

}

 

input_file_name = argv[1];

 

if((input_file = fopen(input_file_name, "rb")) == NULL)

{

printf("Cannot open file: %s\n", input_file_name);

exit(1);

}

 

printf("\ninput file = '%s':\nWORK PROGRAM: %s:\n\n",

                       input_file_name, progname);

 

 

init();

 

for(initcode(); zubr_parse(); initcode())

{

execute(progbase);

}

 

 

if(input_file) fclose(input_file);

 

return(0);

}

 

 

/******************* END OF FILE MAIN.Y *********************/

3. Генератор коду

3.1. Загальні принципи генерації коду

 

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

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

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

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

 

3.2. Способи внутрішнього представлення програм

 

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

Відомі 3 загальні форми запису виразів:

1. Префіксна. Форма притаманна запису функцій, командам мови асемблер, тріади.
2. Інфіксна. Ця форма відповідає загальноприйнятому запису арифметичних операцій.
3. Постфіксна. Використовується у стекових машинах і мові Forth.

Ці з форми запису лежать в основі форм внутрішнього представлення програм:

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

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