Реферати

Курсова робота: Однопроходний/двухпроходний транслятор з мови математичних виразів на мову дерев висновку

Траханиот, Юрій Дмитрович. (на прізвисько Малий) (2-я підлога. XV - 1-я четв. XVI в.) - придворний і дипломат на службі у Великих князів Московських Івана III і його сина Василя III, можливо, перекладач.

Утворення Московської держави 2. Зміст Уведення 3 1. Фактори, що ведуть до утворення національних централізованих держав. 4 2. Особливості утворення Російської держави. Співвідношення соціально-економічних, внури- і зовнішньополітичних факторів і характеру об'єднавчого процесу. 5

Взаємодія туропертора і турагента. ЗМІСТ УВЕДЕННЯ Туристська індустрія, відповідно до російського законодавства, являє собою сукупність готелів і інших засобів розміщення, засобів транспорту, об'єктів суспільного харчування, об'єктів і засобів розваги, об'єктів пізнавального, ділового, оздоровчого, спортивного й іншого призначення, організацій, що здійснюють туроператорскую і турагентскую діяльність, а також організацій, що надають екскурсійні послуги і послуги гідів-перекладачів.

Вавилония. Вавилония, держава початку 2-го тисячоріччя - 539 до н.е. на півдні Месопотамії (територія сучасного Іраку). У період розквіту (при Хаммурапи) - централізована рабовласницька держава. Завойована персами.

Робоча партія марксистської єдності. План Уведення 1 Історія 2 Міжнародні зв'язки 3 ПОУМ у мистецтві і примітки Введення Рабо́сподіваючись па́ртия маркси́стского еди́нства (исп.

Кафедра ЕВА

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

по дисципліні

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

на тему

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

Інтерпретатор мови дерев висновку»

Москва 2009

Анотація

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

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

- написання на мові З++ класу, реалізуючий наступні дії над математичними виразами:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Р:

< < число > - > < чс > ¦ + < чс > ¦ - < чс >

< < чс > - > < цифра > ¦ < чс > < цифра >

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача розбору

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

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

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

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

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

1) Т- > Т * А

2) Т- > А * Т

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

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

Т- > AM

M- > * А ¦ M

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

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

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

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

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

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

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

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

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

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

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

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

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

де

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

де

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Транслятори

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Lex і Yacc

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Код граматики подаються на вхід yacc. Yacc читає граматику і генерує З код для синтаксичного аналізатора або разборщика. Синтаксичний аналізатор використовує граматичні правила, які дозволяють йому аналізувати токени з лексичного аналізатора і створити синтаксичне дерево. Синтаксичне дерево встановлює иерархичскую структуру токенов. Наприклад, оператор 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содержіт в собі оголошення токенов. Включення опції до того, що 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 читає цей шаблон і створює З код для лексичного аналізатора, який шукає ідентифікатори.

letter (letter¦digit)*

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

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

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

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

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

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

start: goto state0

state0: read з

if з = letter goto state1

goto state0

state1: read з

if з = letter goto state1

if з = digit goto state1

goto state2

state2: accept string

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

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

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

Метасимвол (Metacharacter)

Збігу (Matches).

Будь-який символ, крім перекладу рядка

\n

Символ перекладу рядка

*

0 або більше за копії попередніх виразів

+

1 або більше за копії попередніх виразів?

0 або 1 копія попередніх виразів

^

Початок рядка

$

Кінець рядка

а¦b

а або b

(ab)+

Одна або більше за копії ab (угруповання, grouping)

«а+b»

літерал« а+b » (З escapes still work)

[]

Клас символів

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

Вираження (Expression)

Збігу (Matches)

abc

abc

abc*

ab abc abcc abccc...

abc+

abc abcc abccc...

a(bc)+

abc abcbc abcbcbc...

a(bc)?

а abc

[abc]

Одне з: а, b, з

[a-z]

Будь-який символ, a-z

[a\ з:][ а, -, z

[-az]

Одне з:][ -, а, z

[A-Za-z0-9]+

Один або більше за символи алфавіта або цифр

[\t\n]+

Пробельние символи

[^ab]

Всі, крім:][ а, b

[а^b]

Одне з:][ а, ^, b

[а¦b]

Одне з:][ а, ¦, b

а¦b

Одне з:][ а, b

Регулярні вирази в 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();][

return0;][

}

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

«.» і «\n» з действиемECHO, асоційованим з кожним шаблоном.][ Трохи макросів і змінних конкретніші в lex.][ECHO- це макрос, який пише код, співпадаючий з шаблоном.][ Ця дія за умовчанням для кожного неспівпадаючого рядка.][ ОбичноECHOопределяется як

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

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

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

Name

Function

int yylex(void)

Викликається для запуску лексичного аналізатора, повертає токен

char *yytext

Покажчик на рядок,

що співпав yyleng

Довжина рядка,

що співпав yylval

Значення, що асоціюється з токеном

int yywrap(void)

Wrapup- обгортка повертає 1 - якщо завершена, 0 - якщо не завершено

FILE *yyout

Вихідний файл

FILE *yyin

Вхідний файл

INITIAL

Початкова умова старту

BEGIN

Умова перемикаюча умова старту

ECHO

Записати рядок,

що співпав Наступний приклад приєднує зліва номер лінії для кожної лінії в файлі]. Деякі реалізації 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);

}

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

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);

return0;

}

Пропуск повинен розділяти терм і вираження, що асоціюється. Посилання на підстановки в секціях правил оточені дужками ({letter}), щоб розрізнювати їх з символами. Коли відбувається збіг в секції правил, що асоціюється З код виконується. Ось програма, яка вважає кількість символів, слів і ліній в файлі (подібна команді 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);

return0;

}

Реалізація 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.lcc lex.yy.c - ll - об program

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

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

lex [-ctvn - V - Q [у¦n]] [file]

Прапори:

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

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

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

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

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

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

YACC - YetAnotherCompilerCompiler

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

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

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

Е - > Е + Е

Е - > Е * Е

Е - > id

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

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

Е - > Е * Е (r2)

- > Е * z (r3)

- > Е + Е * z (r1)

- > Е + у * z (r3)

- > х + у * z (r3)

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

1. х + у * zshift

2 х. + у * zreduce(r3)

3 E. + у * z shift

4 Е +. у * z shift

5 Е + у. * z reduce(r3)

6 E + E. * z shift

7 Е + Е *. z shift

8 Е + Е * z. reduce(r3)

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

10 E + E. reduce(r1) emit add

11 E. accept

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

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

описи

%%

правила

%%

програми

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

%%

правила

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

%token name

%start е

%%

е: е '+' m ¦ е '-' m ¦ m;

m: m '*' t ¦ m '/' t ¦ t;

t: name ¦ ' (' е ')';)(

%%

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

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

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

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

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

А:)( ' (' В ')'{hello (1, «abc»);)(}

і

XXX:)( YYY ZZZ{printf («amessage\n»); flag = 25;)(}

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

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

{$$ = 1;)(}

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

А:)( BCD;)(

те $2 відповідає значенню, поверненому нетерминалом З, а $3 - нетерминалом D. Болеє конкретний приклад:)(

expr:)( ' (' expr ')';)(

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

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

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

А:)( В;)(

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

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

А:)( В{$$ = 1;)(}З{х = $2;)( у = $3;)(};

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

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

NEW_ACT:)( /* empty */ /* НОВЕ ПРАВИЛО */{$$ = 1;)(};А:)( В NEW_ACT З{х = $2;)( у = $3;)(};

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

expr:)( expr '+' expr{$$ = node ('+', $1, $3);)(}

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

%{int variable = 0;)(%}

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

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

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

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

yylex(){extern int yylval;)(int з;)(.. c =. getchar();)(.. switch (з) {.. case '0':.case '1':)(.. case '9':.yylval = з - '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 перетворюється З-компілятором в програму yyparse, яку треба скомпоновать з програмою лексичного аналізу yylex, а) також з підпрограмою main і підпрограмою обробки помилок yyerror.)( Ці підпрограми повинні бути надані користувачем;)( при породженні лексичних аналізаторів корисний lex(1).)(

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

- v

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

- d

Сгенеріровать файл y.tab.h, який містить визначення #define, зв'язуючі задані користувачем «імена лексем» з призначеними програмою yacc «кодами лексем», що дозволяє використати коди лексем в початкових файлах, відмінних від y.tab.c.

-l

Не вставляти в програму y.tab.c оператори #line.)( Рекомендується використати тільки після того, як граматика і інші компоненти повністю налагоджені.)(

- t

За допомогою коштів умовної компіляції в програму y.tab.c завжди вставляються відлагоджувальний оператори, однак за умовчанням компілятор їх) пропускає. Якщо вказана опція - t, то при відсутності інших вказівок відлагоджувальний оператори будуть скомпільовані. Незалежно від використання опції - t компіляцією відлагоджувальний операторів управляє змінна препроцесора YYDEBUG. Якщо YYDEBUG має ненульове значення, відлагоджувальний оператори компілюються; при нульовому значенні вони пропускаються. Коли програма сформована без відлагоджувальний коду, її розмір менше і швидкість виконання декілька вище.

ФАЙЛИ

y.outputy.tab.cy.tab.h Визначення кодів лексем.yacc.tmp Тимчасовий файл.yacc.debug Тимчасовий файл.yacc.acts Тимчасовий файл./usr/lib/yaccpar Прототип алгоритму розбору дляC-програм.

СМ. ТАКОЖ

lex(1).

ДІАГНОСТИКА

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

ОБМЕЖЕННЯ

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

Постановка задачі

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

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

- інтерпретатор мови дерев висновку

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

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

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

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

- обчислення математичних виразів з будь-якою мірою вкладеності- підтримка у виразах чисел з плаваючою точкою- математичні операції:- «+», «-» (бінарний / унарний), «*», «/», «^» (зведення в міру) - підтримка функцій:log(), exp(), sin(), cos(), tan(), acos(), asin(), atan() - ігнорування пропусків, символів табуляції і перенесення рядка- оптимізація синтаксичного дерева- об'єднання проходів синтаксичного і лексичного аналізаторів в один прохід. (Звідси назва «однопроходний / двухпроходний». Другий прохід опциональний - це прохід оптимизатора.) - запис / читання синтаксичного дерева в файл/з файла

Транслятор

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

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

Початкова граматика

EXPR- > [ < + > ¦ < - > ] EXPR < + > TERM ¦ [ < + > ¦ < - > ] EXPR < - > TERM ¦ [ < + > ¦ < - > ] TERMTERM- > TERM*FACTOR ¦ TERM < / > FACTOR ¦ FACTORFACTOR- > FACTOR < ^ > POW{ < ^ > } 0 ¦ POWPOW- > < number > ¦ < var_name > ¦ < ( > EXPR < ) > ¦ FUNC < ( > EXPR < ) > FUNC- > < log > ¦ < exp > ¦ < sin > ¦ < cos > ¦ < tan > ¦ < acos > ¦ < asin > ¦ < atan >

Пояснення:

1) < е > це пустий символ3) {DIGIT} n - це ітерація DIGIT, де n - натуральне число4) { < ^ > } 0 ця відсутність двійчастого зведення в степень5) імена змінних не повинні співпадати з іменами функцій, що підтримуються інтерпретатором. Дана граматика дозволяє розбирати математичні вирази з урахуванням пріоритетів математичних операцій.

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

EXPR- > [ < + > ¦ < - > ] TERM MORETERMSMORETERMS- > < + > TERM MORETERMS ¦ < - > TERM MORETERMS ¦ < е > TERM- > FACTOR MOREFACTORSMOREFACTORS- > *FACTOR MOREFACTORS ¦ < / > FACTOR MOREFACTORS ¦ < е > FACTOR- > POW MOREPOWSMOREPOWS- > < ^ > POW{ < ^ > } 0 ¦ < е > 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+х*(1+2+3+4+(2*3*4*х)))+((1+2)+sin (х+1+2)) - (log (sin(х))+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=х

(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=х

(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=х

(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=х

(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=х

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

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

(0x8050bf8) VAR=х

(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=х

(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=х

(0x80509b8) CONST=22

nodes num: 19

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

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

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

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

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

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

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

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

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

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

Висновок

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

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

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

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

- інтерпретатор мови дерев висновку