Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Опис вхідної мови транслятора
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лекція
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
Опис вхідної мови транслятора
Перша і головна відмінність одної мови програмування від іншої − це її синтаксис. Основне призначення синтаксису − надати систему позначень для обміну інформацією між програмістом і транслятором. Але при розробці деталей синтаксису частіше враховують другорядні критерії − зробити програму зручної для читання, написання і трансляції, а також, щоб програма була однозначною. Якщо зручність читання програми та її запису потрібні користувачу мови програмування, то простота трансляції та відсутність неоднозначності мають значення насамперед при процесі трансляції. Ці вимоги, взагалі кажучи, суперечливі, і знаходження компромісу є однією з центральних задач при розробці мови програмування.
Розробка нової мови починається з означення її синтаксису. Для опису синтаксису мови програмування, у свою чергу, також потрібні певні засоби. Мову, призначену для опису іншої мови, називають метамовою. Мова, що використовується для опису синтаксису мови, називається метасинтаксичною мовою. У метасинтаксичних мовах використовується спеціальна сукупність умовних знаків, яка утворює нотацію цієї мови.
Історично першою метасинтаксичною мовою, яка використовувалась на практиці для опису синтаксису мов програмування (зокрема, мови Алгол-60), є нормальні форми Бекуса, скорочене позначення БНФ ( бекусова нормальна форма або бекусово-наурова форма). Основне призначення БНФ − подання у компактному вигляді строго формальних і однозначних правил написання основних конструкцій мови програмування, яка описується.
Формальне означення синтаксису мови програмування зазвичай називається граматикою.
За допомогою БНФ описують два класи об'єктів: 1) основні символи мови програмування; 2) імена конструкцій описуваної мови або, так звані, металінгвістичні змінні.
Кожна металінгвістична формула (форма) описує правила побудови конструкцій мови і складається з двох частин. У лівій знаходиться металінгвістична змінна для позначення відповідної конструкції, за нею − металінгвістична зв'язка ::= , зміст якої − «означується як» або «є». У правій частині формули вказується один або декілька варіантів побудови конструкції, яка означується у лівій частині. Для побудови конструкції, яка означується даною формулою, потрібно вибрати деякий варіант її побудови із правої частини формули і підставити замість кожної металінгвістичної змінної деякі ланцюжки основних символів. Варіанти правої частини відокремлюються металінгвістичною зв'язкою │, яка має зміст «або».
Самі мета лінгвістичні змінні позначаються словами, що пояснюють зіст описуваної конструкції і беруться у кутові дужки < > .
Для прикладу наведемо означення десяткового числа за допомогою БНФ:
1. < десяткове ціле число > ::= < число без знаку > │
+ < число без знаку > │ - < число без знаку >
2. < число без знаку > ::= < цифра > │ < число без знаку > < цифра >
3. < цифра > ::= 0 │1 │2 │3 │4 │5 │6 │7 │8 │9
Наприклад, десяткове число +165 будується за цими формулами так:
< десяткове ціле число >
+ < число без знаку >
+ < число без знаку > < цифра >
+ < число без знаку > 5
+ < число без знаку > < цифра >5
+ < число без знаку > 65
+< цифра >65
+165
Особливістю багатьох металінгвістичних формул є наявність у них рекурсій, тобто використання для опису деяких конструкцій цих самих конструкцій. Рекурсія може бути явною і неявною. Зокрема, серед наведених вище правил у правилі 2 зустрічається явна рекурсія. Неявна рекурсія буде у тому випадку, коли при побудові конструкції на деякому кроці використовується металінгвістична змінна, яка використовується для позначення цієї самої конструкції.
Наявність рекурсій ускладнює читання і розуміння мета лінгвістичних формул, але дає змогу за допомогою скінченої кількості правил описати мову, яка може містити нескінченну кількість ланцюжків основних символів. Адже мови програмування нескінченні − на цих мовах можна написати нескінченну кількість правильних програм, і при описі їх синтаксису за допомогою БНФ завжди будуть присутні явні чи неявні рекурсії.
На практиці для опису синтаксису мов програмування застосовують і інші мета-лінгвістичні мови. Одна з цілей їх використання − усунути деяку неприродність зображення у БНФ загальних синтаксичних конструкцій для необов'язкових, альтернативних та таких, що повторюються, елементів правил.
Фігурні дужки
У НБФ тільки за допомогою рекурсії можна задати ланцюжок з довільної кількості елементів. Припустимо, що фігурні дужки { , } є метасимволами і використовуються там, де необхідно вказати, що ланцюжок, що взятий у фігурні дужки, може або бути відсутнім, або повторюватись довільну кількість разів. Тоді наведене вище правило
< число без знаку > ::= < цифра > │ < число без знаку > < цифра >
можна переписати у вигляді
< число без знаку > ::= < цифра > { < цифра > }
Обидва способи запису вважаються еквівалентними. Для того, що задати мінімальну або максимальну кількість повторень ланцюжка, після фігурних дужок можна використовувати надрядкові і / або підрядкові індекси. Наприклад, описати число, яке має обмежену довжину ( не менше 1 цифри і не більше 5 цифр ), можна у такий спосіб:
< число без знаку > ::= < цифра > { < цифра > }15
Фігурні дужки дають змогу використовувати метасимвол │ для вказівки на можливість вибору. Так, правило утворення ідентифікаторів довільної довжини ( перша буква, далі − буква або цифра) можна записати так:
< ідентифікатор > ::= < буква > {< буква > │ < цифра > }
Квадратні дужки
Квадратні дужки [ , ] часто використовують для того, що вказати факультативний (необов'язковий) ланцюжок. Так правило
< десяткове ціле число > ::= < число без знаку > │
+ < число без знаку > │ - < число без знаку >
можна переписати так
< десяткове ціле число > ::= [ + ] < число без знаку > │ - < число без знаку >
і навіть так
< десяткове ціле число > ::= [ + │- ] < число без знаку >
Круглі дужки, факторизація
Круглі дужки як метасимволи можуть використовуватись так само, як і звичайні дужки в арифметичних виразах. Наприклад, правило
< десяткове ціле число зі знаком > ::= + < число без знаку > │ - < число без знаку >
можна переписати так
< десяткове ціле число зі знаком > ::= (+│ - ) < число без знаку >
де спільна частина < число без знаку > винесена за дужки. Дужки можуть бути вкладеними на довільну глибину так само, як і у арифметичних виразах.
Наведені метасимволи можна використовувати для запису одного правила. Так, правило
< вираз > ::= < число без знаку > │< вираз > + < число без знаку >
│< вираз > - < число без знаку >
можна переписати у у вигляді
< вираз > ::= < число без знаку >{ ( +│ - ) } < число без знаку >
Метасимволи як символи мови
Іноді доводиться описувати мову, для якої наведені метасимволи є символами мови (входять у її алфавіт). У цьому випадку будемо виділяти метасимволи за допомогою шрифту ( підкреслювання, курсив тощо). Часто символ мови береться у апострофи (лапки): '(', ')' , '[', ']', '{' , '}' , '│' Тоді апостроф, якщо він є символом, зображається лапками і береться в апострофи: ' '' ' .
БНФ та інші метамови дали можливість формального опису мови, що стало поштовхом для застосування математичних засобів для системного опису і дослідження мов програмування, використання математичного апарату як основи для синтаксичного аналізу у трансляторах.
Зауважимо, що БНФ не дають змоги описувати контексні (семантичні) залежності у мовах програмування. Для цього використовуються інші засоби, так звані метасемантичні мови.
Формальні мови і граматики. Основні терміни
Систематичне використання математичних методів для опису мов програмування започатковане у 1960 р. Тоді виявилось, що БНФ, які використовувались для опису синтаксису мови Алгол-60, мають строге формальне обґрунтування за допомогою засобів математичної лінгвістики. З цього часу і почалась історія розвитку і застосування формального математичного апарату − теорії формальних мов і граматик − для проектування і конструювання трансляторів.
Спочатку наука про мови − лінгвістика − зводилась до вивчення конкретних природних мов, їх класифікації, з'ясуванню подібності і відмінностей між ними. Виникнення і розвиток метаматематики, що вивчала мову математики, проведення робіт з вивчення засобів комунікації тварин та інші дослідження привели у 30-х роках ХХ століття до значно ширшого поняття про мову, коли під мовою розуміють всякий засіб спілкування, що складається з:
знакової системи, тобто множини допустимих послідовностей знаків;
змістовних множини цієї системи;
відповідності між послідовностями знаків і змістом, який ставиться у відповідність допустимим послідовностям.
Знаками можуть бути букви абетки, математичні позначення, звуки тощо. Математична лінгвістика розглядає тільки такі знакові системи, які складаються з символів деякого алфавіту, а послідовностями знаків − тексти, тобто мови розглядаються як довільні послідовності осмислених текстів. При цьому правила, які визначають множину текстів, утворюють синтаксис мови, а опис змістовних множин і відповідність між змістом і текстом − семантику мови. Семантика мови залежить від характеру об'єктів, які описуються даною мовою, і засоби її вивчення різні для різних типів мов. Синтаксис, як виявилось, меншою мірою залежить від призначення мови і може вивчатись за допомогою методів, які не залежать від змісту і призначення мови. Математичний апарат для вивчення синтаксису мови стали називати теорією формальних граматик. З точки зору синтаксису мову розуміють вже не як засіб спілкування, а як множину формальних об'єктів − послідовностей символів алфавіту. Термін «формальний» підкреслює, що об'єкти і операції над ними розглядаються чисто формально, без будь-яких змістовних інтерпретацій об'єктів. Наведемо основні терміни і означення цієї теорії.
Літера ( або символ) − це простий неподільний знак; множина літер утворює алфавіт. Алфавіт − це скінченна не порожня множина літер, тому до алфавітів можна застосувати теоретико-множинні позначення. Зокрема, якщо А і В такі алфавіти, що EMBED Equation.3 , то говоритимемо, що А є підалфавітом В.
Ланцюжок (або слово) − це скінченна впорядкована послідовність літер алфавіту. Допускається також існування порожнього ланцюжка (не включає жодного символу алфавіту), який позначатимемо через EMBED Equation.3 ( EMBED Equation.3 не є символом алфавіту, EMBED Equation.3 ). Отже, ланцюжок у алфавіті А можна описати формально такими правилами: ланцюжок − це
1) EMBED Equation.3 ( порожній ланцюжок);
2) якщо EMBED Equation.3 − ланцюжок у алфавіті А, EMBED Equation.3 ( EMBED Equation.3 − символ алфавіту EMBED Equation.3 ), то EMBED Equation.3 теж є ланцюжком у алфавіті А;
3) EMBED Equation.3 буде ланцюжком у алфавіті А тоді і тільки тоді, коли він утворений згідно з правилами 1) і 2).
Кожен ланцюжок EMBED Equation.3 у алфавіті А має скінченну довжину, яку позначаємо EMBED Equation.3 . Таким чином, EMBED Equation.3 ; EMBED Equation.3 .
Якщо EMBED Equation.3 і EMBED Equation.3 − ланцюжки у алфавіті А, то їх конкатенацією (катенацією, зчепленням) EMBED Equation.3 є ланцюжок, утворений шляхом дописування символів ланцюжка EMBED Equation.3 після символів ланцюжка EMBED Equation.3 . Наприклад, якщо EMBED Equation.3 , EMBED Equation.3 , то EMBED Equation.3 , EMBED Equation.3 . Для будь-яких ланцюжків EMBED Equation.3 , EMBED Equation.3 EMBED Equation.3 .
EMBED Equation.3 -м степенем ланцюжка EMBED Equation.3 (позначається EMBED Equation.3 ) називається конкатенація EMBED Equation.3 ланцюжків EMBED Equation.3 , EMBED Equation.3 , EMBED Equation.3 .
Так само можна означити степені алфавіту А:
EMBED Equation.3 , EMBED Equation.3 , EMBED Equation.3 для EMBED Equation.3 .
Використовуючи наведені поняття, означуються ще дві операції над алфавітом А.
Ітерація множини А − це множина
EMBED Equation.3 ,
усічена ітерація
EMBED Equation.3 .
Очевидно, що EMBED Equation.3 , EMBED Equation.3 .
Приклад. Якщо EMBED Equation.3 , то EMBED Equation.3 включає ланцюжки
EMBED Equation.3 …
Мова EMBED Equation.3 у алфавіті А − це підмножина ланцюжків скінченої довжини у цьому алфавіті. Очевидно, що кожна мова є підмножиною множини EMBED Equation.3 . Але мова EMBED Equation.3 включає тільки ті ланцюжки, які завдяки додатковій інформації про їх семантику вважаються осмисленими і побудовані згідно з правилами синтаксису.
У мовах програмування альтернативами для термінів літера, ланцюжок, алфавіт є терміни слово, речення, словник відповідно. Словами вважаються ідентифікатори, константи, службові слова, розділювачі, а реченнями − оператори. Набір слів утворює словник мови.
Теорія формальних граматик займається описом, розпізнаванням і перетворенням мов. Вона дозволяє дати відповідь на ряд прикладних питань. Наприклад, чи можуть мови з деякого класу розпізнаватись швидко і просто; чи належить дана мова певному класу тощо.
У загальному випадку існують два основних способи опису окремих класів мов:
за допомогою процедури, яка породжує ланцюжки мови;
за допомогою процедури, яка розпізнає ланцюжки мови.
Перший спосіб передбачає використання граматики, яка описує спосіб утворення тих ланцюжків, які належать досліджуваній мові, друга − використання деякого абстрактного пристрою розпізнавання (автомату). При побудові трансляторів використовуються обидва способи: граматика як засіб опису синтаксису мови програмування, а автомат − як модель алгоритму розпізнавання речень мови, який і кладеться в основу побудови транслятора. При цьому методично (і технологічно) спочатку конструюється граматика, а потім за цією граматикою будується алгоритм розпізнавання.
Породжувальна граматика
Означення. Формальною породжувальною граматикою називаєься четвірка EMBED Equation.3 , де
Т − скінченна непорожня множина символів, яка називається термінальним (основним) словником граматики G; елементи множини Т називають термінальними символами (терміналами);
EMBED Equation.3 − скінченна непорожня множина символів, яка називається нетермінальним (допоміжним) словником граматики G, EMBED Equation.3 Ø, EMBED Equation.3 − об'єднаний словник граматики G; елементи множини EMBED Equation.3 називаються не термінальними символами (або нетерміналами);
S − початковий символ (аксіома) граматики G; EMBED Equation.3 і позначає головний нетермінал (мету) граматики G;
P − скінченна множина правил граматики, тобто скінченна підмножина множини EMBED Equation.3 , елемент EMBED Equation.3 множини P називається правилом виводу (правилом підстановки, продукцією) і записується у вигляді EMBED Equation.3 . Двомісне відношення EMBED Equation.3 інтерпретується як «замінити» EMBED Equation.3 на EMBED Equation.3 або «підставити EMBED Equation.3 замість EMBED Equation.3 ».
Множина правил підстановки P називають також схемою граматики. Ланцюжок, який стоїть у лівій частині правила виводу, обов'язково містить хоча б один нетермінальний символ. У правій частині у загальному випадку може стояти довільний ланцюжок з термінальних і нетермінальних символів, включаючи і порожній ланцюжок EMBED Equation.3 .
Надалі для зручності запису елементи з нетермінального словника EMBED Equation.3 позначатимемо великими латинськими літерами, термінальні символи − малими латинськими літерами, довільні ланцюжки − грецькими буквами.
Для запису правил з однаковими лівими частинами
EMBED Equation.3 EMBED Equation.3 … EMBED Equation.3
будемо користуватись записом EMBED Equation.3 ( так само, як у БНФ).
Приклад. У граматиці EMBED Equation.3 основний словник EMBED Equation.3 , допоміжний словник EMBED Equation.3 , аксіома EMBED Equation.3 , а множина правил EMBED Equation.3 .
Для скорочення запису іноді для опису граматики будемо вказувати тільки множину правил виводу, де великими латинськими буквами позначено нетермінальні символи, EMBED Equation.3 − аксіома граматики, всі інші символи − термінальні.
Говорять, що ланцюжок EMBED Equation.3 безпосередньо виводиться з ланцюжка EMBED Equation.3 у граматиці G ( EMBED Equation.3 ), якщо EMBED Equation.3 , EMBED Equation.3 , і серед правил підстановки є правило EMBED Equation.3 .
Наприклад, ланцюжок EMBED Equation.3 безпосередньо виводиться з ланцюжка EMBED Equation.3 у граматиці EMBED Equation.3 .
Говорять, що ланцюжок EMBED Equation.3 виводиться з ланцюжка EMBED Equation.3 у граматиці G ( EMBED Equation.3 ), якщо знайдеться послідовність ланцюжків EMBED Equation.3 така, що ланцюжок EMBED Equation.3 безпосередньо виводиться з ланцюжка EMBED Equation.3 у граматиці G, тобто EMBED Equation.3 при EMBED Equation.3 або EMBED Equation.3 . Відношення EMBED Equation.3 називають транзитивним замиканням, а послідовність EMBED Equation.3 − виводом ланцюжка EMBED Equation.3 з ланцюжка EMBED Equation.3 у граматиці G.
У граматиці EMBED Equation.3 EMBED Equation.3 , оскільки існує вивід
EMBED Equation.3 .
Ланцюжок називається EMBED Equation.3 сентенціальною формою, якщо він виводиться з аксіоми граматики: EMBED Equation.3 .
У розглянутому вище прикладі сентенціальними формами є ланцюжки EMBED Equation.3 EMBED Equation.3 , а порожній ланцюжок − ні.
Множина всіх сентенціальних форм, які складаються лише з термінальних символів, називається мовою, що породжується даною граматикою:
EMBED Equation.3 .
Так, EMBED Equation.3 .
Граматики EMBED Equation.3 і EMBED Equation.3 називаються еквівалентними, якщо EMBED Equation.3 .
Наприклад, граматики EMBED Equation.3 , EMBED Equation.3
де EMBED Equation.3 , EMBED Equation.3 , еквівалентні, оскільки обидві породжують мову EMBED Equation.3 .
Граматики EMBED Equation.3 і EMBED Equation.3 називаються майже еквівалентними, якщо EMBED Equation.3 .
Іншими словами, граматики майже еквівалентні, якщо мови, що ними породжуються, відрізняються не більше, ніж на EMBED Equation.3 .
Наприклад, граматики EMBED Equation.3 , EMBED Equation.3
де EMBED Equation.3 , EMBED Equation.3 , майже еквівалентні, оскільки обидві породжують мову EMBED Equation.3 . EMBED Equation.3 складаються з усіх ланцюжків з множини EMBED Equation.3 і порожнього ланцюжка EMBED Equation.3 , який не належить мові
Еквівалентні граматики можуть мати різні властивості, що спрощують або ускладнюють алгоритми транслятора.
Важливо зауважити, що породжувальна граматика описує правила породження ланцюжків мови, але порядок застосування правил підстановки не фіксується.
Практичне застосування граматик пов'язане з розв'язуванням проблеми розпізнавання. Проблема розпізнавання розв'язна, якщо існує такий алгоритм, який за скінченну кількість кроків дає відповідь на питання про належність довільного ланцюжка над основним словником граматики до мови, яка породжується даною граматикою. Якщо такий алгоритм існує, то мова є такою, що розпізнається. Якщо до того ж кількість кроків алгоритму залежить від довжини ланцюжка і може бути оуінена до виконання алгоритму, то кажуть, що мова легко розпізнається.У іншому випадку немає сенсу говорити про побудову. Тому на практиці розглядаються такі класи породжувальних граматик, які відповідають мовам, що розпізнаються. Найбільш важливі класи таких мов можна означити у рамках класифікації мов, запропонованої у 1959 р. американським лінгвістом Н.Хомським (класифікація за Хомським). Він запропонував класифікувати формальні мови за типом правил граматик, які їх породжують.
Клас 0. Правила виводу граматики мають вигляд EMBED Equation.3 без будь-яких обмежень на рядки EMBED Equation.3 і EMBED Equation.3 . Мови цього класу можуть служити моделлю природних мов.
Клас 1. Для всіх правил виводу EMBED Equation.3 виконуються такі умови:
EMBED Equation.3 , EMBED Equation.3 , EMBED Equation.3 , EMBED Equation.3 , EMBED Equation.3 .
Породжувальна граматика з такими правилами і породжувана нею мова називаються контексно-залежними (КЗ-граматика). У КЗ-граматиці кожне правило виводу вказує на підстановку деякого непорожнього ланцюжка EMBED Equation.3 замість нетермінала EMBED Equation.3 за умови, що EMBED Equation.3 знаходиться у оточенні EMBED Equation.3 , тобто рядки EMBED Equation.3 розглядаються як контекст, у якому EMBED Equation.3 можна замінити на EMBED Equation.3 . Мови класу 1 можуть породжуватись також граматикою, права частина кожного правила якої не коротша за її ліву частину ( EMBED Equation.3 , EMBED Equation.3 ), тобто довжина ланцюжка при виводі може тільки збільшуватись. Така граматика називається невкорочувальною. Клас КЗ-граматик еквівалентний класу невкорочувальних граматик.
Клас 2. Всі правила граматики мають вигляд EMBED Equation.3 , де EMBED Equation.3 , EMBED Equation.3 . Заміна нетермінала EMBED Equation.3 на ланцюжок EMBED Equation.3 проходить без урахування контексту, тому граматики цього класу називають контексно-вільними (КВ-граматиками). Якщо припустити, що EMBED Equation.3 , тобто можлива підстановка порожнього ланцюжка EMBED Equation.3 замість нетермінала EMBED Equation.3 , то граматика буде вкорочувальною КВ-граматикою (ВКВ-граматикою). Доведено, що для довільної ВКВ-граматики можна побудувати майже еквівалентну КВ-граматику, яка породжує ту саму мову, що й задана граматика, за винятком порожнього ланцюжка. ВКВ-граматики мають практичне значення, оскільки саме вони використовуються для опису мов програмування. Майже еквівалентність ВКВ і КВ-граматик дозволяє звести вивчення властивостей ВКВ-граматик до вивчення відповідних властивостей КВ-граматик. Тому КВ-граматики мають провідну роль при формальному вивченні синтаксису мов програмування і побудові синтаксичного аналізатора транслятора.
Клас 3. Всі правила виводу мають вигляд: EMBED Equation.3 , EMBED Equation.3 , де EMBED Equation.3 , EMBED Equation.3 (праволінійна граматика) або EMBED Equation.3 , EMBED Equation.3 , де EMBED Equation.3 , EMBED Equation.3 (ліволінійна граматика). Множина мов, які породжуються праволінійними граматиками, збігається з множиною мов, які породжуються ліволінійними граматиками. Мови, які породжуються граматиками класу 3 (автоматними або регулярними граматиками), називаються також автоматними або регулярними мовами.
З іншого боку, основні класи мов можуть бути означені за допомогою абстрактних пристроїв розпізнавання (автоматів). Надалі особливу увагу звернемо на скінченні автомати, за допомогою яких можна розпізнавати ланцюжки, що належать регулярним мовам, оскільки за допомогою регулярних граматик можна описати деякі підмножини мов програмування.
Як було зазначено раніше, для опису синтаксису мов програмування використовуються нормальні форми Бекуса. Виявляється, що між БНФ і КВ-граматиками є тісний зв'язок − вони, по суті, еквівалентні, відмінності є лише у позначеннях. Так елементу «::=» з БНФ у КВ-граматиці відповідає відношення EMBED Equation.3 , металінгвістичним змінним з БНФ у КВ-граматиці відповідають нетермінальні символи, а основним символам мови − термінальні символи КВ-граматики.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора