Однопроходныйдвухпроходный транслятор з мови математичних виразів на мову дерев виведення

Кафедра ЕВА

Звіт по курсовій роботі

з дисципліни

«Системне Програмне Забезпечення»

на тему

«Однопрохідний / двопрохідний транслятор з мови математичних виразів на мову дерев виводу.

Інтерпретатор мови дерев виведення »

Москва 2009

Анотація

Мета даної курсової роботи:

- Вивчення принципів побудови трансляторів

- Написання на мові C + + класу, що реалізує наступні дії над математичними виразами:

- Лексичний аналіз

- Синтаксичний аналіз

- Обчислення значення

- Написання транслятора з мови математичних виразів на мову дерев виведення

- Написання інтерпретатора мови дерев виведення

Теоретичне введення

Теорія побудови трансляторів використовується в багатьох областях, пов'язаних з програмним забезпеченням. Важливість цієї теми можна проілюструвати на прикладі мови високого рівня C + +: для розробки програми на C + + потрібно набагато менше часу, ніж на мовах більш низького рівня.

Формальні граматики

Формальне визначення граматики. Форма Бекуса-Наура

Граматика - це опис способу побудови речень деякої мови. Іншими словами, граматика - це математична система, яка визначає мову. Фактично, визначивши граматику мови, ми вказуємо правила породження ланцюжків символів, що належать цій мові. Таким чином, граматика - це генератор ланцюжків мови.

Правило (або продукція) - це впорядкована пара ланцюжків символів (α, β). У правилах важливий порядок ланцюжків, тому їх частіше записують у вигляді α → β (або α:: = β). Такий запис читається як «α породжує β» або «β за визначенням є α».

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

Мова, заданий граматикою G, позначається як L (G).

Дві граматики G і G 'називаються еквівалентними, якщо вони визначають один і той же мова: L (G) = L (G'). Дві граматики G і G 'називаються майже еквівалентними, якщо задані ними мови відрізняються не більш, ніж на порожню ланцюжок символів:

Формально граматика G визначається як четвірка G (VT, VN, P, S), де:

VT - множина термінальних символів або алфавіт термінальних символів;

VN - безліч нетермінальних символів або алфавіт нетермінальних символів;

Р - безліч правил (продукцій) граматики, виду , Де ,

S - цільовий (початковий) символ граматики .

Алфавіти термінальних і нетермінальних символів граматики не перетинаються: . Цільовий символ граматики - це завжди нетермінальний символ. Безліч називають повним алфавітом граматики G.

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

У безлічі правил граматики може бути кілька правил, що мають однакові ліві частини, види: . Тоді ці правила поєднують разом і записують у вигляді: . Одному рядку в такій запису відповідає відразу n правил.

Таку форму запису правил граматики називають формою Бекуса-Наура. Форма Бекуса-Наура передбачає, як правило, також, що нетермінальні символи беруться в кутові дужки: <>.

Приклад граматики, визначальною мова цілих десяткових чисел із знаком:

С ({0,1,2. 3,4.5. 6,7.8.9 .-,+}, {<число>, <чс>. <Цифра>}, Р, <число>)

P:

<<Число> -> <чс> | + <чс> | - <чс>

<<Чс> -> <цифра> | <чс> <цифра>

<<Цифра> -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Розглянемо складові елементи граматики G:

• множина термінальних символів VT містить дванадцять елементів: десять десяткових цифр і два знаки;

• безліч нетермінальних символів VN містить три елементи: символи <число>, <чс> та <цифра>;

• безліч правил містить 15 правил, які записані в три рядки (тобто є тільки три різних правих частині правил);

• цільовим символом граматики є символ <число>.

Назви нетермінальних символів не зобов'язані бути осмисленими. Це зроблено для зручності розуміння правил граматики людиною. Наприклад, в програмі на мові Pascal можна змінити імена ідентифікаторів, і при цьому не зміниться сенс програми. Для термінальних символів це невірно. Набір термінальних символів завжди строго відповідає алфавітом мови, що визначається граматикою.

Принцип рекурсії в правилах граматики

Особливість розглянутих вище формальних граматик в тому, що вони дозволяють визначити нескінченна безліч ланцюжків мови за допомогою кінцевого набору правил. Наведена вище в прикладі граматика для цілих десяткових чисел зі знаком визначає нескінченна безліч цілих чисел за допомогою 15 правил. У такій формі запису граматики можливість користуватися кінцевим набором правил досягається за рахунок рекурсивних правил. Рекурсія в правилах граматики виражається в тому, що один з нетермінальних символів визначається сам через себе. Рекурсія може бути безпосередньою (явної) - тоді символ визначається сам через себе в одному правилі, або непрямої (неявній) - тоді те ж саме відбувається через ланцюжок правил.

У розглянутій вище граматиці G безпосередня рекурсія присутній у правилі: <чс> <Чс> <цифра>.

Щоб рекурсія не була нескінченною, для бере участь в ній нетермінального символу граматики повинні існувати також і інші правила, які визначають його, минаючи його самого, і дозволяють уникнути нескінченного рекурсивного визначення (у противному випадку цей символ у граматиці був би просто не потрібен). Такими правилами є <чс> <Цифра> - у граматиці G.

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

Якщо спробувати дати визначення тому, що ж є числом, то почати можна з того, що будь-яка цифра сама по собі є число. Далі можна помітити, що будь-які дві цифри - це теж число, потім - три цифри і т.д. Якщо будувати визначення числа таким методом, то воно ніколи не буде закінчено (в математиці розрядність числа нічим не обмежена). Однак можна помітити, що кожен раз, породжуючи нове число, ми просто дописуємо цифру справа (оскільки звикли писати зліва направо) до вже написаного ряду цифр. А цей ряд цифр, починаючи від однієї цифри, теж у свою чергу є числом. Тоді визначення для поняття «число» можна побудувати таким чином: «число - це будь-яка цифра або інше число, до якого справа дописана будь-яка цифра». Саме це і складає основу правил граматики G і відображено в правилах

<Чс> <Цифра> | <чс> <цифра>. Інші правила в цій граматиці дозволяють додати до числа знак і дають визначення поняттю «цифра».

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

Завдання розбору

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

Граматики та розпізнавачі - два незалежні методи, які реально можуть бути використані для визначення будь-якої мови. Однак при створенні компілятора для деякої мови програмування виникає завдання, яке вимагає пов'язати між собою ці методи завдання мов. Розробників компіляторів цікавлять, перш за все, синтаксичні конструкції мов програмування. Для цих конструкцій доведено, що завдання розбору для них можна вирішити. Більше того, для них знайдені формальні методи її вирішення. Оскільки мови програмування не є чисто формальними мовами і несуть в собі певний сенс (семантику), то завдання розбору для створення реальних компіляторів розуміється дещо ширше, ніж вона формулюється для чисто формальних мов. Компілятор повинен не просто встановити приналежність вхідний ланцюжка символів заданому мови, а й визначити її смислове навантаження. Для цього необхідно виявити ті правила граматики, на підставі яких ланцюжок була побудована.

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

Види рекурсій та розбору

Правила, що мають вигляд

1) T -> T * A

2) T -> A * T

Називаються леворекурсівнимі і праворекурсівнимі відповідно.

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

T -> A M

M -> * A | M

При висхідному розборі в правилах неприпустима права рекурсія. Аналогічним чином перетворюються правила з правого рекурсією в правила з лівого рекурсією.

Класифікація мов і граматик

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

Класифікація граматик по Хомського

Відповідно до класифікації, запропонованої американським лінгвістом Ноамом Хомським, формальні граматики класифікуються за структурою їхніх правил. Якщо всі без винятку правила граматики задовольняють деякій заданій структурі, то таку граматику відносять до певного типу.

Хомський виділив чотири типи граматик.

Тип 0: граматики з фразовой структурою

На структуру їх правил не накладається ніяких обмежень: для граматики виду G (VT, VN, P, S), правила мають вигляд: , Де .

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

Практичного застосування граматики, що відносяться тільки до типу 0, не мають.

Тип 1: контекстно-залежні (КЗ) та неукорачівающіе граматики

У цей тип входять два основні класи граматик:

Контекстно-залежні граматики G (VT, VN, P, S), мають правила виду:

, Де

Неукорачівающіе граматики G (VT, VN, P, S), мають правила виду:

, Де

Структура правил КЗ-граматик така, що при побудові пропозицій заданого ними мови один і той же нетермінальний символ може бути замінений на ту чи іншу ланцюжок символів в залежності від того контексту, в якому він зустрічається. Саме тому ці граматики називають «контекстно-залежними». Ланцюжки і на правилах граматики позначають контекст ( - Лівий контекст, а - Правий контекст), в загальному випадку будь-яка з них (або навіть обидві) може бути порожньою. Неукорачівающіе граматики мають таку структуру правил, що при побудові речень мови, заданого граматикою, будь-яка ланцюжок символів може бути замінена на ланцюжок символів не меншої довжини. Звідси і назва «неукорачівающіе».

Доведено, що ці два класи граматик еквівалентні.

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

Тип 2: контекстно-вільні (КС) граматики

Контекстно-вільні (КС) граматики G (VT, VN, P, S), мають правила виду: , Де . Такі граматики також іноді називають неукорачівающімі контекстно-вільними (НКР) граматиками (видно, що в правій частині правила у них повинен завжди стояти як мінімум один символ). Існує також майже еквівалентний їм клас граматик - вкорочують контекстно-вільні (УКБ) граматики G (VT, VN, P, S), , Правила яких можуть мати вигляд: , Де .

Різниця між цими двома класами граматик полягає лише в тому, що в УКС-граматиках у правій частині правил може бути присутнім порожня ланцюжок (X), а в НКС-граматиках - ні. Доведено, що ці два класи граматик майже еквівалентні.

КС-граматики широко використовуються при описі синтаксичних конструкцій мов програмування. Синтаксис більшості відомих мов програмування заснований саме на КС-граматиках.

Усередині типу КС-граматик крім класів НКР і УКБ виділяють ще ціла безліч різних класів граматик, і всі вони відносяться до типу 2.

Тип 3: регулярні граматики

До типу регулярних відносяться два еквівалентних класу граматик: леволінейние і праволінейние.

Леволінейние граматики G (VT, VN, P, S), можуть мати правила двох видів: або , Де .

У свою чергу, праволінейние граматики G (VT, VN, P, S), можуть мати правила теж двох видів: або , Де .

Ці два класи граматик еквівалентні і відносяться до типу регулярних граматик.

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

Співвідношення між типами граматик

Типи граматик співвідносяться між собою особливим чином. З визначення типів 2 і 3 видно, що будь-яка регулярна граматика є КС-граматикою, але не навпаки. Також очевидно, що будь-яка граматика може бути віднесена до типу 0, оскільки він не накладає жодних обмежень на правила. У той же час існують вкорочують КС-граматики (тип 2), які не є ні контекстно-залежними, ні неукорачівающімі (тип 1), оскільки можуть містити правила виду , Неприпустимі в типі 1.

Одна і та ж граматика в загальному випадку може бути віднесена до кількох класифікаційним типами (наприклад, як вже було сказано, всі без винятку граматики можуть бути віднесені до типу 0). Для класифікації граматики завжди вибирають максимально можливий тип, до якого вона може бути віднесена. Складність граматики обернено пропорційна номером типу, до якого належить граматика.

Перекладачі

Формальне визначення транслятора

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

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

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

Етапи трансляції. Загальна схема роботи транслятора

На рис. 2.1 представлена ​​загальна схема роботи компілятора. З неї видно, що в цілому процес компіляції складається з двох основних етапів - аналізу та синтезу. На етапі аналізу виконується розпізнавання тексту вихідної програми, створення і заповнення таблиць ідентифікаторів. Результатом його роботи служить якесь внутрішнє представлення програми, ясна компілятору. На етапі синтезу на підставі внутрішнього представлення програми та інформації, що міститься в таблиці ідентифікаторів, породжується текст результуючої програми. Результатом цього етапу є об'єктний код. Крім того, у складі компілятора присутня частина, відповідальна за аналіз і виправлення помилок, яка за наявності помилки в тексті вихідної програми повинна максимально повно інформувати користувача про тип помилки і місце її виникнення. У кращому випадку компілятор може запропонувати користувачеві варіант виправлення помилки.

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

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

- Розпізнавання мови початкової програми

- Генерація результуючої програми на заданому мовою.

Далі дається перелік основних фаз (частин) компіляції та короткий опис їх функцій.

Лексичний аналізатор (сканер) - це частина компілятора, яка читає літери програми мовою оригіналу і будує з них слова (лексеми) вихідного мови. На вхід лексичного аналізатора надходить текст початкової програми, а вихідна інформація передається для подальшої обробки компілятором на етапі синтаксичного розбору. З теоретичної точки зору лексичний аналізатор не є обов'язковою, необхідною частиною компілятора. Однак існують причини, які визначають його присутність практично у всіх компіляторах.

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

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

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

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

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

Інтерпретатори

Інтерпретатор - програма, яка сприймає вихідну програму на вхідному (вихідному) мовою і виконує її.

Інтерпретатор, також як і транслятор, аналізує текст початкової програми, але він не породжує результуючу програму, а відразу виконує вихідну відповідно до її змістом, заданим семантикою її мови.

Lex і Yacc

Огляд генераторів коду

Системи GNU / Linux поставляються з декількома програмами для написання програм. Можливо найбільш популярні:

• Flex, генератор лексичного аналізатора

• Bison, генератор синтаксичного аналізатора

• Gperf, розвинений генератор хеш-функції

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

• Вхідні параметри для цих функцій є дуже складними і їх непросто виразити у вигляді, коректному для C-коду.

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

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

Кожне з цих інструментальних засобів призначено для створення конкретного типу програм. Bison використовується для генерування синтаксичних аналізаторів; Flex - для генерування лексичних аналізаторів. Інші кошти присвячені, в основному, автоматизації конкретних аспектів програмування.

Наприклад, інтегрування методів доступу до бази даних у імперативні мови програмування часто є рутинною роботою. Для її полегшення і стандартизації призначений Embedded SQL - система метапрограмування, використовувана для простого комбінування доступу до бази даних і C.

Хоча існує чимало доступних бібліотек, що дозволяють звертатися до баз даних в C, використання такого генератора коду як Embedded SQL робить комбінування C і доступу до бази даних набагато більш легким шляхом об'єднання SQL-сутностей в C в якості розширення мови. Багато реалізації Embedded SQL, однак, в основному є простими спеціалізованими макропроцесора, генеруючими звичайні C-програми. Тим не менше, використання Embedded SQL робить для програміста доступ до бази даних більш природним, інтуїтивним і вільним від помилок в порівнянні з прямим використанням бібліотек. За допомогою Embedded SQL заплутаність програмування баз даних маскується макромовою

Спільне використання Lex і Yacc

До 1975 року процес написання компіляторів займав дуже багато часу. Потім Lesk [1975] і Johnson [1975] опублікували праці по lex і yacc. Ці утиліти сильно спростили написання компіляторів. Деталі реалізації можуть бути знайдені у Aho [1986]

Шаблони коду поміщаються на вхід Lex. Lex читає шаблони і генерує C код для лексичного аналізатора або сканера.

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

Токени є числовим представленням рядків спрощує обробку.

Коли лексичний аналізатор знаходить ідентифікатори у вхідному потоці, вони вносяться до таблиці символів. Таблиця символів також може містити іншу інформацію таку, як тип даних (цілий або речовий) і місце змінної в пам'яті. Усі наступні посилання на ідентифікатори посилаються на відповідний індекс таблиці символів.

Код граматики подаються на вхід yacc. Yacc читає граматику і генерує C код для синтаксичного аналізатора або розбирача. Синтаксичний аналізатор використовує граматичні правила, які дозволяють йому аналізувати токени з лексичного аналізатора і створити синтаксичне дерево. Синтаксичне дерево встановлює іерархічскую структуру токенів. Наприклад, оператор precedence і асоціативності (associativity) показані в синтаксичному дереві. Наступний крок, генерація коду, здійснюється з допомогою обходу синтаксичного дерева. Деякі компілятори створюють машинний код, коли як деякі - програму на мовах асемблера.

Команди для створення компілятора, bas. Exe, наведені нижче:

yacc - d bas.y # create y.tab.h, y.tab.c

lex bas.l # create lex.yy.c

cc lex.yy.c y.tab.c - obas.exe # compile / link

Yacc читає граматичні описи в bas. Y і генерує синтаксичний аналізатор (parser), який включає функцію yyparse, у файлі y. Tab. C. Файл bas. Y містить в собі оголошення токенів. Включення опції - d веде до того, що yacc генерує визначення для токенів і поміщає їх у файл y. tab. h. Lex читає шаблони, описані в bas. l, включають файл y. tab. h і генерує лексичний аналізатор, який включає функцію yylex, у файлі lex. yy. c. Нарешті, лексичний аналізатор (lexer) і синтаксичний аналізатор (parser) компілюються і компонуються разом, утворюючи виконуваний файл bas. Exe. З main, ми викликаємо yyparse, щоб запустити компілятор. Функція yyparse автоматично викликає yylex, щоб отримати кожен токен.

Lex

Theory

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

Далі випливає представлення простого шаблону, що становить регулярний вираз, яке шукає ідентифікатори. Lex читає цей шаблон і створює C код для лексичного аналізатора, який шукає ідентифікатори.

letter (letter | digit) *

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

• повторення, представлене оператором «*» (repetition)

• чергування, представлене оператором «|» (alternation)

• об'єднання (concatenation)

Будь-яке регулярне вираз може бути представлено автоматом з кінцевим числом станів (finite state automaton, FSA). Ми можемо уявити FSA, що використовує стану і переходи між станами. Існує одне початковий стан і одне, або більше, кінцевих станів або дозволених станів.

На рис. 3, стан 0 - є початковим станом, а стан 2 - дозволеним станом. Коли відбувається читання символу, здійснюється перехід з одного стану в інший. Коли читається перший символ, здійснюється перехід до стану 1. Автомат залишається в стані 1, поки читаються букви (letters) або цифри (digits). Коли здійснюється читання іншого символу, крім букви або символу, здійснюється перехід в стан 2, дозволене стан. Будь FSA може бути представлений за допомогою комп'ютерної програми. Наприклад, цей автомат з 3 ма станами програмується наступним чином:

start: goto state0

state0: read c

if c = letter goto state1

goto state0

state1: read c

if c = letter goto state1

if c = digit goto state1

goto state2

state2: accept string

Це техніка, яка використовується lex. Регулярні вирази транслюються за допомогою lex в комп'ютерну програму, яка реалізує FSA. Використовуючи наступний вхідний символ і поточний стан, наступний стан визначається за допомогою індексування в згенерованої комп'ютером таблиці станів.

Тепер стає легко зрозуміти обмеження в lex. Наприклад, lex не може бути використаний.

Таблиця 1. Елементарні шаблони (Pattern Matching Primitives)

Метасимвол (Metacharacter)	Збіги (Matches)
.	Будь-який символ, крім перекладу рядка
\ N	Символ переведення рядка
*	0 або більше копій попередніх виразів
+	1 або більше копій попередніх виразів
?	0 або 1 копія попередніх виразів
^	Початок рядка
$	Кінець рядка
a | b	a або b
(Ab) +	Одна або більше копій ab (Угрупування, grouping)
«A + b»	літерал «a + b» (C escapes still work)
[]	Клас символів

Таблиця 2. Приклади шаблонів (Pattern Matching Examples)

Вираз (Expression)	Збіги (Matches)
abc	abc
abc *	ab abc abcc abccc ...
abc +	abc abcc abccc ...
a (bc) +	abc abcbc abcbcbc ...
a (bc)?	a abc
[Abc]

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

Наступні два оператори дозволені у класі символів: дефіс («-», hyphen) і циркумфлекс («^», circumflex). При використанні між двома символами дефіса, представляється діапазон символів. Циркумфлекс, при використанні його як першого символу, заперечує вираз. Якщо два шаблони збігаються з деякою рядком, використовується найбільш шаблон, по якому знайдено найбільш довга рядок, у разі, якщо довжина однакова, використовується перший шаблон.

... Definitions ...

%%

... Rules ...

%%

... Subroutines ...

Вхідні дані lex діляться на 3 секції, з символами%%, що розділяють секції. Це проілюстровано у прикладі. Перший приклад - це найменший можливий файл lex:

%%

Вхідні дані копіюються вихідні по одному символу за раз. Перший роздільник%% потрібно завжди, так як завжди повинна бути секція правил. Якщо не специфікувати жодного правила, тоді дія за замовчуванням - збіг за все і копіювання у вихідні дані. За замовчуванням для вхідних та вихідних даних використовуються stdin і stdout, відповідно. Ось деякий приклад, з використанням коду за замовчуванням:

%%

/ * Збіг все, крім символу нового рядка * /

ECHO;

/ * Збіг символу переведення рядка * /

\ N ECHO;

%%

int yywrap (void) {

return 1;

}

int main (void) {

yylex ();

return 0;

}

Два шаблону специфіковані в секції правил. Кожен шаблон повинен починатися в першому стовпці, тобто має слідувати за пробільних символів. Опціональне дія асоціюється з шаблоном. Дія може бути одиничним вираженням мовою C або множинним, укладеним в дужки. Все, не починається з першого стовпця, дослівно копіюється у генерований C файл. Можна використовувати це для специфікації коментарів у lex файлі. У цьому прикладі є 2 вирази:

«.» І «\ n» з дією ECHO, асоційованим з кожним шаблоном. Кілька макросів і змінних визначені в lex. ECHO - це макрос, який пише код, що співпадає з шаблоном. Ця дія за замовчуванням для кожної неспівпадаючий рядка. Зазвичай ECHO визначається як

# Define ECHO fwrite (yytext, yyleng, 1, yyout)

Змінна yytext - покажчик на збіглася рядок (що закінчується NULL-символом), і yyleng - довжина співпала рядка. Вираз yyout є вихідним файлом і за замовчуванням є stdout. Функція yywrap викликається lex, коли вхідні дані закінчилися. Повертає 1, якщо закінчено, 0 якщо потрібна подальша обробка. Кожна програма на C вимагає main функцію. У цьому випадку просто викликається yylex,

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

Наступний приклад приєднує зліва номер лінії для кожної лінії в файлі. Деякі реалізації lex зумовлюють обчислення yylineno. Вхідний файл для lex - це yyin, і є за замовчуванням stdin.

% {

int yylineno;

%}

%%

^(.*) \ N printf ("% 4d \ t% s», + + yylineno, yytext);

%%

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

yyin = fopen (argv [1], «r»);

yylex ();

fclose (yyin);

}

Секції визначень складаються із замін, коду та початкових станів. Код в секціях визначення просто копіюється в початок генерується C файлу, при цьому код повинен бути в дужках% {»і«%} ». Заміни полегшуються правилами збіги шаблонів. Наприклад, можна визначити цифри і символи:

digit [0-9]

letter [A-Za-z]

% {

int count;

%}

%%

/ * Match identifier * /

{Letter} ({letter} | {digit}) * count + +;

%%

int main (void) {

yylex ();

printf («number of identifiers =% d \ n», count);

return 0;

}

Пробіл повинен розділяти терм і асоційоване вираз. Посилання на підстановки в секціях правил оточені дужками ({letter}), щоб розрізняти їх з символами. Коли відбувається збіг в секції правил, асоційований C код виконується. Ось програма, яка рахує кількість символів, слів і ліній в файлі (подібна команді wc в Unix):

% {

int nchar, nword, nline;

%}

%%

\ N {nline + +; nchar + +;}

[^ \ T \ n] + {nword + +, nchar + = yyleng;}

{Nchar + +;}

%%

int main (void) {

yylex ();

printf ("% d \ t% d \ t% d \ n», nchar, nword, nline);

return 0;

}

Реалізація lex в Unix

У цілому підсистема LEX для систем UNIX включає наступні файли:

/ Usr / ccs / bin / lex;

lex.yy.c;

/ Usr / ccs / lib / lex / ncform;

/ Usr / lib / libl.a;

/ Usr / lib / libl.so.

У каталозі / usr / ccs / lib / lex є файл-заготівля ncform, який LEX використовується для побудови ЛА. Цей файл є вже готовою програмою лексичного аналізу. Але в ньому не визначені дії, які необхідно виконувати при розпізнаванні лексем, відсутні й самі лексеми, не сформовані робочі масиви і т.д. За допомогою команди lex файл ncform добудовується. У результаті ми отримуємо файл зі стандартним ім'ям lex.yy.c. Якщо LEX-програма розміщена у файлі program.l, то для отримання ЛА з ім'ям program необхідно виконати наступний набір команд:

lex program.l

cc lex.yy.c - ll - o program

Якщо ім'я вхідного файлу для команди lex не вказано, то буде використовуватися файл стандартного вводу. Прапор - ll потрібно для підключення / usr / ccs / lib / libl.a - бібліотеки LEX. Якщо необхідно отримати самостійну програму, як у даному випадку, підключення бібліотеки обов'язково, оскільки з неї підключається головна функція main. В іншому випадку, якщо є необхідність включити ЛА в якості функції в іншу програму (наприклад, в програму синтаксичного аналізу), цю бібліотеку необхідно викликати вже при збиранні. Тоді, якщо main визначено в зухвалому ЛА програмі, редактор зв'язків не буде підключати розділ main з бібліотеки LEX.

Загальний формат виклику команди lex:

lex [-ctvn - V - Q [y | n]] [file]

Прапори:

- C - включає фазу генерації Сі-файлу (встановлюється за умовчанням);

- T - помістити результат в стандартний файл виводу, а не в файл lex.yy.c;

- V - вивести розміри внутрішніх таблиць;

- N - не виводити розміри таблиць (встановлюється за умовчанням);

- V - вивести інформацію про версію LEX в стандартний файл помилок;

- Q - вивести (Qy) або не виводити (Qn, встановлюється за умовчанням) інформацію про версію у файл lex.yy.c.

YACC - Yet Another Compiler Compiler

Граматики для yacc описуються за допомогою Форми Бекуса-Наура (Backus Naur Form, BNF)

Цю техніку була ввели John Backus і Peter Naur і використовували її, щоб описати ALGOL60. Граматика BNF може бути використана для опису контекстно-вільних мов. Більшість конструкцій сучасного програмування можуть бути представлені в BNF.

Наприклад, граматика для вираження, яке множить і складає числа може бути представлена ​​наступним чином:

E -> E + E

E -> E * E

E -> id

Були специфіковані 3 правила продукції. Терми, які можуть бути з лівого боку правил продукції (lhs) продукції, такі як E (expression), є нетермінальним символами. Терми, такі як id (identifier) ​​є термінальними символами (токенами, що повертаються lex) і можуть бути тільки з правого боку правил продукції (rhs).

Ця граматика визначає, що вираз може бути сумою двох виразів, твором двох висловів чи ідентифікатором. Можна використовувати цю граматику, щоб згенерувати вирази:

E -> E * E (r2)

-> E * z (r3)

-> E + E * z (r1)

-> E + y * z (r3)

-> X + y * z (r3)

На кожному кроці ми розширюємо терм, замінюємо ліву частину продукції відповідної правою частиною. Числа праворуч показують якесь правило застосовується. Щоб розпізнати вираз, необхідна зворотна операція. Крім того, що необхідно починати з одиничного нетермінального (початкового символу), і генерувати вираз з граматики. Це відомо під терміном висхідний (bottom-up) аналіз і використання стека для зберігання термів. Ось деякий приклад у зворотному порядку:

1. X + y * z shift

2 x. + Y * z reduce (r 3)

3 E. + Y * z shift

4 E +. y * z shift

5 E + y. * Z reduce (r3)

6 E + E. * Z shift

7 E + E *. z shift

8 E + E * z. reduce (r3)

9 E + E * E. reduce (r2) emit multiply

10 E + E. reduce (r1) emit add

11 E. accept

Структура YACC-програми

Кожен файл специфікацій складається з трьох секцій: оголошення, (граматичні) правила, і програми. Секції розділяються символами подвійного відсотка "%%». Іншими словами, повний файл специфікації виглядає як:

опису

%%

правила

%%

програми

Секція оголошень може бути порожня. Більш того, якщо секція програм опущена, то друга мітка "%%» також може бути опущена; таким чином, мінімальна дозволена специфікація Yacc є:

%%

правила

Приклад найпростішої програми на YACC'e:

% Token name

% Start e

%%

e: e '+' m | e '-' m | m;

m: m '*' t | m '/' t | t;

t: name | '(' e ')';

%%

Секція правил містить інформацію про те, що символ name є лексемою (терміналом) граматики, а символ e - її початковим нетерміналом.

Граматика записана звичайним чином - ідентифікатори позначають терміналів і нетерміналів, символьні константи типу '+' '-' - термінали. Символи: |; - належать метамови і читаються «є за визначенням», «або» та «кінець правила» відповідно.

Семантичні дії

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

Дії, що складаються з декількох операторів, слід брати у фігурні дужки. Наприклад:

A: '(' B ')'

{Hello (1, «abc»);}

і

XXX: YYY ZZZ

{Printf («a message \ n"); flag = 25;}

є граматичними правилами з діями.

Щоб забезпечити зв'язок дій з аналізатором, використовується спецсимволи «долар» ($). Щоб повернути значення, дія звичайно привласнює його псевдопеременной $ $. Наприклад, дія, яка не робить нічого, але повертає одиницю:

{$ $ = 1;}

Щоб отримати значення, повернуті попередніми діями і лексичним аналізатором, дія може використовувати псевдопеременние $ 1, $ 2 і т.д., які відповідають значенням, повернутим компонентами правій частині правила, вважаючи зліва направо. Таким чином, якщо правило має вигляд:

A: BCD;

то $ 2 відповідає значенню, поверненого нетерміналом C, a $ 3 - нетерміналом D. Більш конкретний приклад:

expr: '(' expr ')';

Значенням, що повертається цим правилом, зазвичай є значення виразу в дужках, що може бути записано так:

expr: '(' expr ')'

{$ $ = $ 2;}

За замовчуванням, значенням правила вважається значення, повернене першим елементом ($ 1). Таким чином, якщо правило не має дії, Yacc автоматично добаляет його у вигляді $ $ = $ 1;, завдяки чому для правила виду

A: B;

зазвичай не потрібно самому писати дію.

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

A: B

{$ $ = 1;}

C

{X = $ 2; y = $ 3;}

;

У результаті розбору Іксу (x) присвоїти значення 1, а ігрек (y) - значення, повернене нетерміналом C. Дія, що стоїть у середині правила, вважається за його компоненту, тому x = $ 2 присвоює X-у значення, повернене дією $ $ = 1;

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

NEW_ACT: / * empty * / / * НОВЕ ПРАВИЛО * /

{$ $ = 1;}

;

A: B NEW_ACT C

{X = $ 2; y = $ 3;}

;

У більшості додатків дії не виконують введення / виведення, а конструюють і обробляють у пам'яті структури даних, наприклад дерево розбору. Такі дії найпростіше виконувати викликаючи підпрограми для створення і модифікації структур даних. Припустимо, що існує функція node, написана так, що виклик node (L, n1, n2) створює вершину з міткою L, гілками n1 і n2 і повертає індекс свіжоствореної вершини. Тоді дерево розбору може будуватися так:

expr: expr '+' expr

{$ $ = Node ('+', $ 1, $ 3);}

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

% {

int variable = 0;

%}

Такі рядки, поміщені в розділ оголошень, оголошують змінну variable типу int і роблять її доступною для всіх дій. Всі імена внутрішніх змінних Yacca починаються c двох літер y, тому не слід давати своїм змінним імена типу yymy.

Лексичний аналіз

Програміст, який використовує Yacc має написати сам (або створити за допомогою програми типу Lex) зовнішній лексичний аналізатор, який буде читати символи з вхідного потоку (якого - це внутрішня справа лексичного аналізатора), виявляти термінальні символи (токени) і передавати їх синтаксичному аналізатору, побудованому Yaccом (можливо разом з якимсь значенням) для подальшого розбору. Лексичний аналізатор має бути оформлений як функція з ім'ям yylex, що повертає значення типу int, яке являє собою тип (номер) виявленого у вхідному потоці токена. Якщо є бажання повернути ще якесь значення (наприклад номер у групі), воно може бути присвоєно глобальної, зовнішньої (стосовно yylex) змінної на ім'я yylval.

Лексичний аналізатор і Yacc повинні використовувати однакові номери токенів, щоб розуміти один одного. Ці номери зазвичай вибираються Yaccом, але можуть вибиратися і людиною. У будь-якому випадку механізм define мови Сі дозволяє лексичному аналізатору повертати ці значення в символічному вигляді. Припустимо, що токен на ім'я DIGIT був визначений у секції оголошень специфікації Yaccа, тоді відповідний текст лексичного аналізатора може виглядати так:

yylex ()

{

extern int yylval;

int c;

...

c = getchar ();

...

switch (c) {

...

case "0":

case '1 ':

...

case '9 ':

yylval = c - "0";

return DIGIT;

...

}

...

Вищенаведений фрагмент повертає номер токена DIGIT і значення, рівне цифрі. Якщо при цьому сам текст лексичного аналізатора був поміщений в секцію програм специфікації Yacca - є гарантія, що ідентифікатор DIGIT був визначений номером токена DIGIT, причому тим самим, який очікує Yacc.

Такий механізм дозволяє створювати зрозумілі, легкі в модифікації лексичні аналізатори. Єдиним обмеженням є заборона на використання в якості імені токена слів, зарезервірованих або часто використовуваних у мові Сі слів. Наприклад, використання в якості імен токенів таких слів як if або while, майже напевно призведе до виникнення проблем при компіляції лексичного аналізатора. Крім цього, ім'я error зарезервовано для токена, службовця справі обробки помилок, і не повинно використовуватися.

Як вже було сказано, номери токенів вибираються або Yaccом, або людиною, але частіше Yaccом, при цьому для окремих символів (наприклад для (або;) вибирається номер, рівний ASCII кодом цього символу. Для інших токенів номери вибираються починаючи з 257.

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

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

Дуже непоганим засобом для створення лексичних аналізаторів є програма Lex. Лексичні аналізатори, побудовані з її допомогою чудово гармоніюють з синтаксичними аналізаторами, побудованими Yaccом. Lex можна легко використовувати для побудови повного лексичного аналізатора з файлу специфікацій, заснованого на системі регулярних виразів (на відміну від системи граматичних правил для Yacca), але, правда, існують мови (наприклад Фортран) не потрапляють ні під яку теоретичну схему, але для них доводиться писати лексичний аналізатор вручну.

Реалізація Yacc в Unix

YACC (1)

НАЗВА

yacc - ще один компілятор компіляторів

СИНТАКСИС

yacc [-v] [-d] [-l] [-t] граматика

ОПИС

Команда yacc перетворює контекстно-вільну граматику в набір таблиць для простого LR (1) - розбору. Граматика може містити неоднозначності; щоб їх подолати, використовуються задані правила передування.

Вихідний файл y.tab.c перетвориться C-компілятором в програму yyparse, яку потрібно скомпонувати з програмою лексичного аналізу yylex, а також з підпрограмою main і підпрограмою обробки помилок yyerror. Ці підпрограми повинні бути надані користувачем; при породженні лексичних аналізаторів корисний lex (1).

Допустимі опції:

ФАЙЛИ

y.output

y.tab.c

y.tab.h Визначення кодів лексем.

yacc.tmp Тимчасовий файл.

yacc.debug Тимчасовий файл.

yacc.acts Тимчасовий файл.

/ Usr / lib / yaccpar Прототип алгоритму розбору для

C-програм.

СМ. ТАКОЖ

lex (1).

ДІАГНОСТИКА

У стандартний протокол направляється інформація про кількість конфліктних ситуацій типу «згортка-згортка» і «перенесення-згортка»; більш докладні повідомлення містяться у файлі y.output. Аналогічним чином повідомляється про продукціях, недосяжних з початкового символу граматики.

ОБМЕЖЕННЯ

Так як імена файлів фіксовані, в даному каталозі в кожен момент часу може бути активним тільки один процес yacc

Постановка завдання

Реалізувати:

- Транслятор з мови математичних виразів на мову дерев виведення

- Інтерпретатор мови дерев виведення

До розробляються програмами пред'являються наступні вимоги:

- Реалізація здійснюється на мові C + +.

- Функціональність транслятора й інтерпретатора повинна бути реалізована у вигляді класу (Клас Analyser).

Повинна бути забезпечена підтримка наступного функціональності:

- Обчислення математичних виразів з будь-яким ступенем вкладеності

- Підтримка у виразах чисел з плаваючою точкою

- Математичні операції:

- «+», «-» (Бінарний / унарний), «*», «/», «^» (піднесення до степеня)

- Підтримка функцій:

log (), exp (), sin (), cos (), tan (), acos (), asin (), atan ()

- Ігнорування прогалин, символів табуляції та перенесення рядка

- Оптимізація синтаксичного дерева

- Об'єднання проходів синтаксичного та лексичного аналізаторів в один прохід. (Звідси назва «однопрохідний / двопрохідний». Другий прохід опціональний - це прохід оптимізатора.)

- Запис / читання синтаксичного дерева в файл / з файлу

Транслятор

Граматика синтаксичного аналізатора

Граматика описана у вигляді форми Бекуса-Наура, розширеної метасимволи.

Вихідна граматика

EXPR -> [<+>|<->] EXPR <+> TERM | [<+>|<->] EXPR <-> TERM | [<+>|<->] TERM

TERM-> TERM <*> FACTOR | TERM </> FACTOR | FACTOR

FACTOR-> FACTOR <^> POW {<^>} 0 | POW

POW-> <number> | <var_name> | <(> EXPR <)> | FUNC <(> EXPR <)>

FUNC-> <log> | <exp> | <sin> | <cos> | <tan> | <acos> | <asin> | <atan>

Пояснення:

1) <e> це порожній символ

3) {DIGIT} n - це ітерація DIGIT, де n - натуральне число

4) {<^>} 0 це відсутність подвійного зведення в ступінь

5) імена змінних не повинні збігатися з іменами функцій, підтримуваних інтерпретатором.

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

Еквівалентна граматика без лівої рекурсії

EXPR-> [<+>|<->] TERM MORETERMS

MORETERMS-> <+> TERM MORETERMS | <-> TERM MORETERMS | <e>

TERM-> FACTOR MOREFACTORS

MOREFACTORS-> <*> FACTOR MOREFACTORS | </> FACTOR MOREFACTORS | <e>

FACTOR-> POW MOREPOWS

MOREPOWS-> <^> POW {<^>} 0 | <e>

POW-> <number> | <var_name> | <(> EXPR <)> | FUNC <(> EXPR <)>

FUNC-> <log> | <exp> | <sin> | <cos> | <tan> | <acos> | <asin> | <atan>

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

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

+, -, *, /, ^, (,)

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

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

У даному аналізаторі нетерміналом граматики ставиться у відповідність функція-обробник. Сенсом предиктивного аналізу є однозначне визначення наступного викликається функції-обробника на основі поточної лексеми.

Відповідність нетерміналів функцій-обробникам:

POW: powNT ()

FACTOR: factorNT ()

TERM: termNT ()

EXPR: exprNT ()

Взаємодія аналізаторів

У Analyser реалізовано об'єднання проходів лексичного та синтаксичного аналізаторів в один прохід. При перегляді наступної лексеми синтаксичним аналізатором викликається функція, що реалізує витяг лексеми з вхідного рядка, що містить математичний вираз.

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

Оптимізатор

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

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

Алгоритм оптимізації

1) Перегляд поточного вузла

2) Перевірка цього вузла на константність:

да:

- Обчислення його значення

- Звільнення пам'яті, виділеної для піддерева з вершиною в цьому вузлі

- Створення нового сайту, що містить обчислену константу

немає:

- Перехід до кроку 3)

3) Операція цього вузла + або * (операція «-» не розглядається, оскільки при побудові синтаксичного дерева бінарний «-» замінюється унарним «-». Приклад: 1-2 перетвориться в 1 + (-2)):

да:

- Формування векторів покажчиків на константні та неконстантние (включаючи не безпосередні) підвузли даного вузла з тією ж операцією. Якщо зустрічається подузел, операція якого відрізняється від операції даного вузла, то:

- Додавання вказівника на цей подузел у вектор вказівників на неконстантние вузли

- Перехід до кроку 1) для цього підвузли

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

- Звільнення пам'яті, виділеної для вузлів, покажчики на які містяться у векторі покажчиків на константні вузли

- Побудова нового піддереві на основі вектора неконстант і обчисленої константи

немає:

- Перехід до кроку 1) для всіх безпосередніх подсистемами даного вузла

Приклад оптимізації

Початкове математичне вираз:

(4 ^ 2 + (2 ^ 3 * 2) ^ 0.5 + x * (1 +2 +3 +4 + (2 * 3 * 4 * x )))+(( 1 +2) + sin (x +1 +2)) - (log (sin (x)) +1)

Формат рядка для синтаксичного дерева у висновку програми має наступний:

(<Указатель_на _текущую_вершіну>) <список_указателей_на_непосредственные підвузли | значеніе_подузла> <операція>

або

(<Указатель_на _текущую_вершіну>) <функція | константа | мінлива> [<список_указателей_на_непосредственные підвузли>] [<значення>]

Для цієї формули неоптимізованою синтаксичне дерево має вигляд:

Syntax Tree: (not optimized)

(0x8050da8) left = 0x8050d28 right = 0x8050d98 op = +

(0x8050d98) right = 0x8050d88 op =-

(0x8050d88) left = 0x8050d58 right = 0x8050d78 op = +

(0x8050d78) CONST = 1

(0x8050d58) op = l next = 0x8050d48

(0x8050d48) op = s next = 0x8050d38

(0x8050d38) VAR = x

(0x8050d28) left = 0x8050c38 right = 0x8050d18 op = +

(0x8050d18) left = 0x8050c88 right = 0x8050d08 op = +

(0x8050d08) op = s next = 0x8050cf8

(0x8050cf8) left = 0x8050cc8 right = 0x8050ce8 op = +

(0x8050ce8) CONST = 2

(0x8050cc8) left = 0x8050c98 right = 0x8050cb8 op = +

(0x8050cb8) CONST = 1

(0x8050c98) VAR = x

(0x8050c88) left = 0x8050c58 right = 0x8050c78 op = +

(0x8050c78) CONST = 2

(0x8050c58) CONST = 1

(0x8050c38) left = 0x8050aa8 right = 0x8050c28 op = +

(0x8050c28) left = 0x8050ab8 right = 0x8050c18 op =*

(0x8050c18) left = 0x8050b68 right = 0x8050c08 op = +

(0x8050c08) left = 0x8050be8 right = 0x8050bf8 op =*

(0x8050bf8) VAR = x

(0x8050be8) left = 0x8050bb8 right = 0x8050bd8 op =*

(0x8050bd8) CONST = 4

(0x8050bb8) left = 0x8050b88 right = 0x8050ba8 op =*

(0x8050ba8) CONST = 3

(0x8050b88) CONST = 2

(0x8050b68) left = 0x8050b38 right = 0x8050b58 op = +

(0x8050b58) CONST = 4

(0x8050b38) left = 0x8050b08 right = 0x8050b28 op = +

(0x8050b28) CONST = 3

(0x8050b08) left = 0x8050ad8 right = 0x8050af8 op = +

(0x8050af8) CONST = 2

(0x8050ad8) CONST = 1

(0x8050ab8) VAR = x

(0x8050aa8) left = 0x80509e8 right = 0x8050a98 op = +

(0x8050a98) left = 0x8050a68 right = 0x8050a88 op = ^

(0x8050a88) CONST = 0.5

(0x8050a68) left = 0x8050a38 right = 0x8050a58 op =*

(0x8050a58) CONST = 2

(0x8050a38) left = 0x8050a08 right = 0x8050a28 op = ^

(0x8050a28) CONST = 3

(0x8050a08) CONST = 2

(0x80509e8) left = 0x80509b8 right = 0x80509d8 op = ^

(0x80509d8) CONST = 2

(0x80509b8) CONST = 4

nodes num: 47

Як видно з висновку, кількість вузлів у синтаксичному дереві одно 47.

Після проходу оптимізатора дерево має наступний вигляд:

Syntax Tree: (optimized)

(0x8050da8) left = 0x8050aa8 right = 0x8050c28 op = +

(0x8050c28) left = 0x8050e08 right = 0x8050ab8 op =*

(0x8050ab8) VAR = x

(0x8050e08) left = 0x8050b08 right = 0x8050c08 op = +

(0x8050c08) left = 0x8050b88 right = 0x8050bf8 op =*

(0x8050bf8) VAR = x

(0x8050b88) CONST = 24

(0x8050b08) CONST = 10

(0x8050aa8) left = 0x80509e8 right = 0x8050d08 op = +

(0x8050d08) op = s next = 0x8050cf8

(0x8050cf8) left = 0x8050ce8 right = 0x8050c98 op = +

(0x8050c98) VAR = x

(0x8050ce8) CONST = 3

(0x80509e8) left = 0x80509b8 right = 0x8050d98 op = +

(0x8050d98) right = 0x8050d58 op =-

(0x8050d58) op = l next = 0x8050d48

(0x8050d48) op = s next = 0x8050d38

(0x8050d38) VAR = x

(0x80509b8) CONST = 22

nodes num: 19

Це дерево відповідає формулі:

22-log (sin (x)) + sin (3 + x) + x * (10 +24 * x)

Як видно з висновку, кількість вузлів у синтаксичному дереві одно 19, проти 47, що призводить до підвищення швидкості виконання програми.

Збереження синтаксичного дерева в файл

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

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

Аналогічним чином відбувається вилучення дерева з файлу.

Інтерпретатор

Інтерпретатор виконує витяг з файлу синтаксичного дерева, що є результатом виконання транслятора.

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

Висновок

У роботі було розглянуто теоретичні основи побудови трансляторів.

Результатом роботи є:

- Клас Analyser, який реалізує заявлену функціональність

- Транслятор з мови математичних виразів на мову дерев виведення

- Інтерпретатор мови дерев виведення