Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка транслюючої граматики та побудова компілятора для трансляції фрагменту на мові Паскаль
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
О
Факультет:
ТГВ
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2010
Тип роботи:
Інші
Предмет:
Лiнгвiстичне забезпечення САПР
Група:
КН-413
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра САПР
ПОЯСНЮВАЛЬНА ЗАПИСКА
до курсової роботи
з дисципліни “Лінгвістичне забезпечення САПР”
на тему:
«Розробка транслюючої граматики та побудова компілятора для трансляції фрагменту на мові Паскаль »
Допущено до захисту:
Львів 2010
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА”
/назва вищого учбового закладу/
Кафедра САПР
Дисципліна ЛІНГВІСТИЧНЕ ЗАБЕЗПЕЧЕННЯ САПР
Спеціальність КОМП’ЮТЕРНІ НАУКИ
Курс 4 _ Група КН-413 Семестр 7 .
Завдання
на курсовий проект ( роботу) студента
Іващук Тетяни Олегівни
/прізвище, ім’я, по - батькові/
1. Тема проекту /роботи/
Розробка транслюючої граматики та побудова компілятора для трансляції фрагменту програми
2. Термін здачі студентом закінченого проекту /роботи/
3. Вихідні дані для проекту /роботи/
Розробити транслюючи граматику та побудувати компілятор для трансляції програми:
PROGRAM LAB3;
VAR X,Y,A,B,H:REAL; I,N:INTEGER;
CONST P=3.14;
BEGIN
WRITELN('VVEDY A TA B: ');
READLN(A);
READLN(B);
WRITELN('VVEDY N');
READLN(N);
H:=(B-A)/N;
FOR I:=1 TO N DO
BEGIN
X:=A+I*H;
Y:=(1/PI)*(((2*X-1)/2)/ ((2*X+3)/2)+PI);
WRITELN('X=',X,' Y=',Y);
END;
END.
4. Зміст розрахунково-пояснювальної записки /перелік питань, які підлягають розробці/
Розробка лексичного аналізатора для вхідної програми
КВ-граматики для вхідної програми
Реалізація правил КВ-граматики у синтаксичному аналізаторі.
Лексичний та синтаксичний аналіз вхідної програми.
5. Перелік графічного матеріалу / з точним зазначенням обов’язкових креслень/
6. Дата видачі завдання
Реферат
Студент: Горук Тарас Ігорович
“Розробка транслюючої граматики та побудова компілятора для трансляції фрагменту програми на мові Паскаль”
Курсова робота. – НУ „ Львівська політехніка ”, каф.: САПР, дисципліна:
“ Лінгвістичне забезпечення САПР”, 2010.
Дана курсова робота складається з 28 сторінок, 2 рисунків, 10 таблиць.
В даній курсовій роботі розроблено транслюючи граматику та побудовано компілятор для трансляції фрагменту програми на мові Паскаль. Дана курсова робота виконується з метою поглиблення теоретичних знань та практичних навичок з курсу «Лінгвістичне забезпечення САПР», закріплення знань, отриманих при вивченні таких курсів, як «Основи програмування та алгоритмізації» та «Теорія алгоритмів», отримання навиків розробки математичних алгоритмів, розробки та відлагодження програмного забезпечення.
Календарний план
№ п/п
Назва етапів курсового проекту ( роботи )
Термін виконання етапів проекту ( роботи )
Примітки
Отримання індивідуального завдання
4.10.09
Аналіз завдання на курсову роботу (проект)
4.10.09 – 10.10.09
Пошук необхідної літератури
10.11.09 – 18.11.09
Вивчення і аналіз рекомендованої літератури
18.11.09 – 17.12.09
Розробка алгоритму програми
17.12.09 – 3.01.10
Розробка та відлагодження програми
3.01.10 – 13.01.10
Оформлення пояснювальної записки
13.01.10 – 21.01.10
Студент
Горук Тарас Ігорович
( підпис )
( прізвище, ім’я, по-батькові )
Керівник
Свірідова Тетяна Валеріївна
( підпис )
( прізвище, ім’я, по-батькові )
____________________2010 р
Зміст
Завдання
2
Реферат
3
Календарний план
4
Специфікація
6
1. Опис роботи
7
1.1. Теоретична частина
8
1.1.1. Відділення лексичного аналізу від синтаксичного
10
1.1.2. Лексичний аналіз (теоретичні відомості)
11
1.1.3. Методи синтаксичного розбору
12
1.1.4. Лексичний аналіз
14
1.1.5. Синтаксичний аналіз
17
1.2. Практична частина
21
1.2.1. Опис програми.
21
1.2.2. Результати виконання програми
22
1.2.3. Аналіз результатів і висновки
25
Загальний алгоритм роботи програми
26
Список використаної літератури
28
Специфікація
САПР
Система Автоматизованого Проектування
ЕОМ
Електронно-обчислювальна машина
СА
Скінчений автомат
ЛА
Лексичний аналіз
МПА
Автомат із магазинною пам’яттю
СС
Службове слово
ПЗ
Програмне забезпечення
1. ОПИС РОБОТИ
Невід'ємною частиною переважаючої більшості сучасних обчислювальних систем є компілятори та інтерпретатори. Вони дозволяють писати програми мовами так званого «високого рівня», які для розробника є набагато зручнішими та практичнішими, ніж асемблери, автокоди чи машинні коди. Звичайно, що мову високого рівня потрібно перекласти на мову машинних кодів та виконати її. Ці функції виконують компілятори та інтерпретатори. Зрозуміло, що через свою велику важливість компілятори та інтерпретатори стали причиною появи достатньо широкої області досліджень, яка займається методами та засобами їх розробки та підвищення ефективності.
Система автоматизованого проектування (САПР) – це організаційно-технічна система, яка містить комплекс засобів автоматизованого проектування, які взаємозв’язані з підрозділами проектної організації.
Функціональними складовими САПР є:
технічне забезпечення;
математичне забезпечення;
програмне забезпечення;
лінгвістичне забезпечення;
інформаційне забезпечення;
методичне забезпечення;
організаційне забезпечення;
Лінгвістичне забезпечення – це сукупність мов, які використовуються в САПР для представлення інформації про проектовані об’єкти, процеси і засоби проектування, якими обмінюються користувачі з ЕОМ і між собою в процесі автоматизованого проектування.
Існують наступні мови для спілкування з ЕОМ:
1) машинна мова - набір команд конкретної обчислювальної машини, який інтерпретується на апаратному рівні або за допомогою мікропрограм самої машини;
2) мови асемблера, або мови “ низького рівня ”, які в значній мірі відображають набір команд деякої конкретної машини;
3) мови керуючих карт і директивні мови, які використовуються для зв'язку з операційною системою;
4) мови високого рівня, які мають складну структуру і не залежать ні від набору команд, ні від операційної системи конкретної машини. Програму для обчислювальної машини, що дозволяє їй “розуміти” директиви і пропозиції вхідної мови, що використовуються програмістом, ми будемо називати “мовним процесором”.
1.1. Теоретична частина
Нижче подані визначення основних термінів, що використовуються в галузі лінгвістичного забезпечення.
Транслятор - обслуговуюча програма, що перетворить вихідну програму, надану вхідною мовою програмування, у робочу програму, представлену об'єктною мовою. Транслятори поділяються на компілятори та асемблери.
Компілятор - це обслуговуюча програма, що виконує трансляцію на машинну мову вхідної програми, записаної вхідною мовою програмування. Процес трансляції з таких мов звичайно називається компіляцією, а вхідні мови звичайно відносяться до мов програмування високого рівня.
Інтерпретатор - програма чи пристрій, що здійснює пооператорну трансляцію і виконання вихідної програми. На відміну від компілятора, інтерпретатор не породжує на виході програму машинною мовою. Розпізнавши команду вихідної мови, він відразу виконує її. Як у компіляторах, так і в інтерпретаторах використовуються однакові методи аналізу вихідного тексту програми. Але інтерпретатор дозволяє почати обробку даних після написання навіть однієї команди. Це робить процес розробки і налагодження програм більш гнучким. Тому, інтерпретуємі мови, типу Java Script, VB Script, одержали широке поширення. Недоліком інтерпретаторів є низька швидкість виконання програм. Звичайно інтерпретуємі програми виконуються в 50-100 разів повільніше програм, написаних у машинних кодах.
Синтаксис - сукупність правил деякої мови, що визначають формування його елементів. Інакше кажучи, це сукупність правил утворення семантично значимих послідовностей символів у даній мові. Синтаксис задається за допомогою правил, що описують поняття деякої мови. Прикладами понять є: змінна, вираз, оператор, процедура. Послідовність понять і їхнє припустиме використання в правилах визначає синтаксично правильні структури, що утворять програми. Саме ієрархія об'єктів, а не те, як вони взаємодіють між собою, визначаються через синтаксис. Наприклад, оператор може зустрічатися тільки в процедурі, а вираз в операторі, змінна може складатися з імені і необов'язкових індексів і т.д. Синтаксис не зв'язаний з такими явищами в програмі як "перехід на неіснуючу мітку" чи "змінна з даним ім'ям не визначена". Цим займається семантика.
Семантика - правила й умови, що визначають співвідношення між елементами мови і їхніх значеннєвих значень, а також інтерпретацію змістовного значення синтаксичних конструкцій мови. Об'єкти мови програмування не тільки розміщаються в тексті відповідно до деякої ієрархії, але і додатково зв'язані між собою за допомогою інших понять, що утворять різноманітні асоціації. Наприклад, змінна, для якої синтаксис визначає припустиме місце розташування тільки в описах і деяких операторах, має визначений тип, може використовуватися з обмеженою безліччю операцій, має адресу, розмір і повинна бути описана до того, як буде використовуватися в програмі.
Синтаксичний аналізатор - компонента компілятора, що здійснює перевірку вихідних операторів на відповідність синтаксичним правилам і семантиці даної мови програмування. Незважаючи на назву, аналізатор займається перевіркою і синтаксису, і семантики. Він складається з декількох блоків, кожний з який вирішує свої задачі. Більш докладно буде розглянутий при описі структури транслятора.
Процес компіляції розділяється на декілька етапів:
Лексичний і синтаксичний аналіз. Програма перетворюється в ланцюжок лексем, а потім у внутрішнє уявлення у вигляді дерева.
Генерація коду. Внутрішнє уявлення перетворюється в блоки команд процесора, які перетворюються в асемблеровський текст або в об’єктний код.
Асемблювання. Якщо генерується асемблерний текст, проводиться його асемблювання з метою отримання об’єктного коду.
На фазі лексичного аналізу (ЛА) вхідна програма, що є потоком символів, розбивається на лексеми – слова відповідно до визначень мови. Основним формалізмом, лежачим в основі реалізації лексичних аналізаторів, є кінцеві автомати і регулярні вирази. Лексичний аналізатор може працювати в двох основних режимах: або як підпрограма, що викликається синтаксичним аналізатором за черговою лексемою, або як повний прохід, результатом якого є файл лексем. В процесі виділення лексем ЛА може як самостійно будувати таблиці імен і констант, так і видавати значення для кожної лексеми при черговому зверненні до нього. В цьому випадку таблиця імен будується в подальших фазах (наприклад, в процесі синтаксичного аналізу). На етапі ЛА виявляються деякі (прості) помилки (неприпустимі символи, неправильний запис чисел, ідентифікаторів і ін.)
Основне завдання синтаксичного аналізу – розбір структури програми. Як правило, під структурою розуміється дерево, відповідне розбору в контекстно-вільній граматиці мови. В даний час найчастіше використовується або LL(1) – аналіз (і його варіант – рекурсивний спуск), або LR(1) –анализ і його варіанти (LR(0), SLR(1), LALR(1) та інші). Рекурсивний спуск частіше використовується при ручному програмуванні синтаксичного аналізатора, LR(1) – при використанні систем автоматизації побудови синтаксичних аналізаторів. Результатом синтаксичного аналізу є синтаксичне дерево з посиланнями на таблицю імен. В процесі синтаксичного аналізу також виявлення помилок, пов’язаних із структурою програми.
На етапі контекстного аналізу виявляються залежності між частинами програми, які не можуть бути описані контекстно-вільним синтаксисом. Це в основному зв’язки «опис- використання», зокрема аналіз типів об’єктів, аналіз областей видимості, відповідність параметрів, мітки та інші. В процесі контекстного аналізу будується таблиця символів, яку можна розглядати як таблицю імен, поповнену інформацією про описи (властивості) об’єктів.
Основним формалізмом, що використовується при контекстному аналізі, є атрибутні граматики. Результатом роботи фази контекстного аналізу є атрибутоване дерево програми. Інформація про об’єкти може бути як розосереджена в самому дереві, так і зосереджена в окремих таблицях символів. В процесі контекстного аналізу також можуть бути виявлені помилки, пов’язані з неправильним використанням об’єктів. Потім програма може бути переведена у внутрішнє представлення. Це робиться з метою оптимізації і/або зручності генерації коду. Ще однією метою перетворення програми у внутрішнє представлення є бажання мати переносимий компілятор. Тоді тільки остання фаза (генерація коду) є машинно-залежною. Як внутрішнє представлення може використовуватися префіксний або постфіксний запис, орієнтований граф, тріади, тетради та інші.
Нарешті, генерація коду – остання фаза трансляції. Результатом її є або асемблерний модуль, або об’єктний (або завантажувальний) модуль. В процесі генерації коду можуть виконуватися деякі локальні оптимізації, такі як розподіл регістрів, вибір довгих або коротких переходів, облік вартості команд при виборі конкретної послідовності команд. Для генерації коду розроблені різні методи, такі як таблиці рішень, зіставлення зразків, що включає динамічне програмування, різні синтаксичні методи.
1.1.1. Відділення лексичного аналізу від синтаксичного
Хоча лексичний і синтаксичний аналізи досить споріднені, існує низка серйозних причин для розділення лексичного і синтаксичного аналізу:
Значна частина часу компіляції витрачається на сканування літер. Виділення ж дозволяє сконцентрувати увагу на скороченні цього часу. Одним із способів скорочення часу є програмування частини або всього сканера на автокоді, а це зробити легше, якщо сканер виділений. Звичайно ж, ми не рекомендуємо користуватися автокодом, якщо не передбачається широке і масове застосування компілятора;
Синтаксис символів можна описати в рамках дуже простих граматик. Якщо відокремити сканування від синтаксичного розпізнавання, то можна розробити ефективну техніку розбору, яка найкращим чином враховує особливості цих граматик. Більш того, тоді для конструювання сканерів можна розробити автоматичні методи, в яких використовується ця ефективна техніка;
Оскільки сканер видає символи замість літер, синтаксичний аналіз на кожному кроці одержує більше інформації про те, що треба робити. Більш того, деякі специфічні перевірки контексту, необхідні при розборі символів, простіше і доречніше виконати в сканері, чим у формальному синтаксичному аналізаторі. Розвиток мов високого рівня вимагає уважного відношення як до лексичних, так і до синтаксичних властивостей мови. Розділення цих двох властивостей дозволить нам досліджувати їх незалежно один від одного;
Часто для представлення однієї і тієї ж мови існує декілька різних зовнішніх представлень. Наприклад в деяких реалізаціях Алголу службові слова поміщені в лапки і пропуски не грають ніякої ролі – вони просто ігноруються. У інших же компіляторах службові слова не можуть використовуватися як ідентифікатори і суміжні службові слова і ідентифікатори повинні відділятися один від одного принаймні одним пропуском. Зовнішні представлення на перфострічці, картах і на телетайпі можуть бути абсолютно різними.
1.1.2. Лексичний аналіз (теоретичні відомості)
Основне завдання лексичного аналізу – розбити вхідний текст, що складається з послідовності одиночних символів, на послідовність слів, що називаються лексемами, тобто виділити ці слова з безперервної послідовності символів. Всі символи вхідної послідовності з цієї точки зору розділяються на символи, що належать деяким лексемам, і символи, що розділяють лексеми (розділювачі). В деяких випадках між лексемами може і немає розділювачів. З іншого боку, в деяких мовах лексеми можуть містити незначущі символи .
Всі лексеми діляться на класи. Прикладами таких класів є числа (цілі, вісімкові, шістнадцяткові, дійсні і т.д.), ідентифікатори, рядки. Окремо виділяються ключові слова і символи пунктуації (іноді їх називають символи-обмежувачі). Як правило, ключові слова – це деяка кінцева підмножина ідентифікаторів. У деяких мовах (наприклад, ПЛ/1) сенс лексеми може залежати від її контексту і неможливо провести лексичний аналіз у відриві від синтаксичного. Лексичний аналізатор видає інформацію двох сортів: для синтаксичного аналізатора, що працює услід за лексичним, істотна інформація про послідовність класів лексем, обмежувачів і ключових слів, а для контексного аналізу, що працює услід за синтаксичним, важлива інформація про конкретні значення окремих лексем (ідентифікаторів, чисел і т.д.). Тому загальна схема роботи лексичного аналізатора така. Спочатку виділяємо окрему лексему (можливо, використовуючи символи- роздільники). Якщо виділена лексема – обмежувач, то він (точніше, деяка його ознака) видається як результат лексичного аналізу. Ключові слова розпізнаються або явним виділенням безпосередньо з тексту, або спочатку виділяється ідентифікатор, а потім робиться перевірка на приналежність його безлічі ключових слів. Якщо так, то видається ознака відповідного ключового слова, якщо ні – видається ознака ідентифікатора, а сам ідентифікатор зберігається окремо. Якщо виділена лексема належить якому-небудь з інших класів лексем (число, рядок і т.д.), то видається ознака класу лексеми, а значення лексеми зберігається.
Лексичний аналізатор може працювати або як самостійна фаза трансляції, або як підпрограма, що працює за принципом «дай лексему». У першому випадку виходом лексичного аналізатора є файл лексем, в другому – лексема видається при кожному зверненні до лексичного аналізатора (при цьому, як правило, тип лексеми повертається як значення функції «лексичний аналізатор», а значення передається через глобальну змінну). З погляду формування значень лексем, лексем, що належать класам, лексичний аналізатор може або просто видавати значення кожної лексеми і в цьому випадку побудова таблиць переноситься на пізніші фази, або він може самостійно будувати таблиці об’єктів (ідентифікаторів, рядків, чисел і т.д.). В цьому випадку як значення лексеми видається покажчик на вхід у відповідну таблицю.
Робота лексичного аналізатора описується формалізмом скінчених автоматів. Проте безпосередній опис скінченого автомата незручно практично. Тому для опису лексичних аналізаторів, як правило, використовують або формалізм регулярних виразів, або формалізм контекстний вільних граматик, а саме підкласу автоматних, або регулярних, граматика. Всі три формалізм (скінчених автоматів, регулярних виразів і автоматних граматик) мають однакову виразну потужність. По опису лексичного аналізатора у вигляді регулярного виразу або автоматної граматики будується скінчений автомат, що розпізнає відповідну мову.
1.1. 3. Методи синтаксичного розбору
Методів синтаксичного розбору існує достатньо багато, але в основному можна виділити два способи розбору:
Низхідний розбір. Суть розбору полягає в тому, що текст якоїсь програми, який із самого початку представлений у вигляді дуже великого рядка, поступово розбивається на лексеми, до лексем застосовується синтаксичний аналіз для побудови внутрішнього представлення програми;
Висхідний розбір. Суть цього типу розбору полягає в тому, що програма представляється у вигляді послідовності лексем. Які далі «від низу до верху» склеюються в складніші речення мови, після успішного склеювання проводиться побудова внутрішнього представлення програми.
Алгоритм розбору зверху вниз.
Основна проблема пророчого розбору – визначення правила виводу, яке потрібно застосувати до нетерміналу. Процес пророчого розбору (зверху-вниз) з погляду побудови дерева розбору можна проілюструвати. Фрагменти недобудованого дерева відповідають сентенціальним формам виводу. Спочатку дерево складається тільки з однієї вершини, відповідній аксіомі S. У цей момент по першому символу вхідного потоку пророчий аналізатор повинен визначити правило S->X1 X2 …, яке повинне бути застосоване до S. Потім необхідно визначити правило, яке повинне бути застосоване X1, і т.д., до тих пір, поки в процесі такої побудови сентенціальної форми, відповідної лівому виводу, не буде застосоване правило Y->a …. Цей процес потім застосовується для наступного найлівішого нетермінального символу сентенційної форми.
Рис. 1
Таблично-керований пророчий аналізатор має вхідний буфер, таблицю аналізу і вихід. Вхідний буфер містить розпізнаваний рядок, за яким слідує $ - правий кінцевий маркер, ознака кінця рядка. Магазин містить послідовність символів граматики з $ на дні. Спочатку магазин містить початковий символ граматики на верхівці і $ на дні. Таблиця аналізу – це двовимірний масив М[A, a], де А – нетермінал, і а – термінал або смвол $.
Аналізатор управляється програмою, яка працює таким чином. Вона розглядає X – символ на верхівці магазина і а – поточний вхідний символ. Ці два символи визначають дію аналізатора. Є три варіанти:
Якщо X=a=$, аналізатор зупиняється і повідомляє про успішне закінчення розбору;
Якщо X=at$, аналізатор видаляє X з магазина і просуває покажчик входу на наступний вхідний символ;
Якщо X – нетермінал, програма заглядає в таблицю M[X,a]. По цьому входу зберігається або правило для X, або помилка. Якщо, наприклад, M[X,a]= {X->UVW}, аналізатор замінює X на верхівці магазина на WVU { на верхівці U}. Вважатимемо, що аналізатор як вихід просто друкує використані правила виводу. Якщо M[X,a]=error, аналізатор звертається до підпрограми аналізу помилок.
1.1.4. Лексичний аналіз
У цьому пункті приведено результати лексичного аналізу завдання.
На етапі лексичного аналізу символи вхідної програми групуються в окремі лексичні одиниці – лексеми, які діляться на три групи і заносяться в окремі таблиці:
IDN – ідентифікатори – це імена змінних;
LIT – літерали – константи;
TRM – термінальні символи – розділювачі, операції, службові слова.
На основі цих трьох таблиць формується таблиця стандартних символів.
Ідентифікатори: LAB3, X, Y, A, B, H, I, N, P.
Сужбові слова: Program, VAR, REAL, INTEGER, CONST, BEGIN, READLN, WRITELN, FOR, TO, DO, END.
Розділювачі і знаки операцій: ; , : ( ) + * / = ‘ . .
Знак оператора присвоєння: := .
Константи (літерали): 1, 3.14, 2, 3, ‘VVEDY A TA B’, ‘VVEDY N’, ‘X=’, ‘Y=’.
У таблицю термінальних символів входять: службові слова, розділювачі і знаки операцій, знак оператора присвоєння.
Таблиця 1.1.4.1 Таблиця термінальних символів
Індекс
Символ
Розділювач
Інші
1
PROGRAM
Службове слово
2
;
Так
3
VAR
Службове слово
4
,
Так
5
:
Так
6
REAL
Службове слово
7
INTEGER
Службове слово
8
CONST
Службове слово
9
=
Операція
10
BEGIN
Службове слово
11
WRITELN
Службове слово
12
(
Так
13
‘
Так
14
)
Так
15
READLN
Службове слово
16
:=
17
-
Операція
18
/
Операція
19
FOR
Службове слово
20
TO
Службове слово
21
DO
Службове слово
22
+
Операція
23
*
Операція
24
END
Службове слово
25
.
Так
Таблиця 1.1.4.2 Таблиця ідентифікаторів
Індекс
Ім’я
Атрибути
Адреса
1
LAB3
Заповнюється на стадії синтаксичного аналізу
Заповнюється на етапі генерації коду
2
X
3
Y
4
A
5
B
6
H
7
I
8
N
9
P
Таблиця 1.1.4.3 Таблиця літералів
Індекс
Літерал
Основа
Формат
Точність
Інші атрибути
Адреса
1
3.14
Fixed
Fixed
4
2
VVEDY A TA B
Fixed
Fixed
1
3
VVEDY N
Fixed
Fixed
1
4
1
Decimal
Fixed
1
5
2
Decimal
Fixed
1
6
3
Decimal
Fixed
1
7
X=
Fixed
Fixed
1
8
Y=
Fixed
Fixed
1
Таблиця 1.1.4.4 Таблиця стандартних символів
Тип
Індекс у відповідній таблиці
Вказівник на лексему
TRM
1
PROGRAM
IDN
1
LAB3
TRM
2
;
TRM
3
VAR
IDN
2
X
TRM
4
,
IDN
3
Y
IDN
4
A
IDN
5
B
IDN
6
H
TRM
5
:
TRM
6
REAL
IDN
7
I
IDN
8
N
TRM
7
INTEGER
TRM
8
CONST
IDN
9
P
TRM
9
=
LIT
1
3.14
TRM
10
BEGIN
TRM
11
WRITELN
TRM
12
(
TRM
13
‘
LIT
2
VVEDY A TA B
TRM
14
)
TRM
15
READLN
LIT
3
VVEDY N
TRM
16
:=
TRM
17
-
TRM
18
/
TRM
19
FOR
LIT
4
1
TRM
20
TO
TRM
21
DO
TRM
22
+
TRM
23
*
LIT
5
2
LIT
6
3
LIT
7
X=
LIT
8
Y=
TRM
24
END
TRM
25
.
Правила граматики на етапі лексичного аналізу:
<ідентифікатор>::= <буква> | <буква-цифра>;
<буква>::= A | B | C | … | Z;
<буква-цифра>::= <буква><буква-цифра> | <цифра><буква-цифра>|;
<цифра>::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9;
<числовий літерал>::= <цифри>|<цифри>.<цифри>;
<цифри>::= <цифра><цифри>|<цифрa>
<термінал>::= <операція>|<розділювач>|<службове слово>;
<операція>::= + | - | * | / | :=|=;
<розділювач>::= ; | , | : | ( | ) | ‘ | .;
<службове слово> ::= PROGRAM | VAR | REAL | INTEGER | CONST | BEGIN | WRITELN | READLN | FOR | TO | DO | END.
1.1.5. Синтаксичний аналіз
Синтаксичний аналіз виконується на основі КВ-граматик та принципів роботи МП-автоматів.
Для початку виконаємо заміну слів на одиночні символи, що представлятимуть слова як лексеми:
Таблиця 1.1.5.1. Заміна послідовності символів символами
№
Вхідне слово
Вихідний символ
1.
PROGRAM
p
2.
VAR
v
3.
LAB3, X, Y, A, B, H, I, N, P
i
4.
CONST
c
5.
3.14, 1, 2, 3
n
6.
“VVEDY A TA B”, ”VVEDY N”, “X=”, “Y=”
s
7.
REAL, INTEGER
y
8.
BEGIN
b
9.
END;
d
10.
END.
e
11.
READLN
r
12.
WRITELN
w
13.
:=
a
14.
FOR
f
15.
TO
t
16.
DO
o
Рис. 2.1.5.1 Зображуюче дерево заголовка програми та розділу опису змінних.
Отже, КВ-граматика має наступні характеристики:
G=(VT, VN, g0, P)
VT={p, v, i, c, n, s, y, b, e, d, r, w, a, f, t, o, :, ;, (, ), ‘, =, ,}
VN={P, N, O, A, C, Z, D, E, B, G, H, T, I, J, K, Q, R, L, S, U, M, W, X, Y}
g0=P
P – скінчена множина правил.
Правила:
1) P→NOT
2) N→pi;
3) O→AB|B
4) A→vC
5) C→Dy;Z
6) Z→C|
7) D→iE
8) E→:|,D
9) B→Cg|
10) G→i=Y
11) Y→nH|’s’H
12) H→,G|;
13) T→bIe
14) I→JI|bId|
15) J→K|L|M|W
16) K→r(Q;
17) Q→iR
18) R→,Q|)
19) L→w(S;
20) S→iU|’s’U
21) U→,S|)
22) M→iaV - (V – математичний вираз, який перевіряється на правильність окремо,
23) V→; після чого замінюється на “;”)
24) W→fMtX
25) X→ioI|noI
МП-автомат, побудований на основі заданої вище граматики.
М=(Q, ∑, Г, , q0, Z0, F );
Q={S};
∑={ p, v, i, c, n, s, y, b, e, d, r, w, a, f, t, o, :, ;, (, ), ‘, =, , , ┤};
Г= {P, N, O, A, C, Z, D, E, B, G, H, T, I, J, K, Q, R, L, S, U, M, W, X, Y, p, v, i, c, n, s, y, b, e, d, r, w, a, f, t, o, :, ;, (, ), ‘, =, , ,▼};
- функція переходів (задана у таблиці 1.1.5.2);
q0=S1;
Z0=P;
F=ДОПУСТИТИ
Таблиця 1.1.5.2. Функція переходів МП-автомата.
№
Конфігурація автомата
Операції, які виконуються при даній конфігурації
Над магазином
Над вхідним ланцюжком
Вх.с.
В.м.
Ст.
1.
p
P
S
ЗАМІНИТИ(P→TON)
ТРИМАТИ
2.
p
N
S
ЗАМІНИТИ(N→;ip)
ТРИМАТИ
3.
v
O
S
ЗАМІНИТИ(O→BA)
ТРИМАТИ
4.
v
A
S
ЗАМІНИТИ(A→Cv)
ТРИМАТИ
5.
i
C
S
ЗАМІНИТИ(C→Z;yD)
ТРИМАТИ
6.
i
Z
S
ЗАМІНИТИ(Z→C)
ТРИМАТИ
7.
i
D
S
ЗАМІНИТИ(D→Ei)
ТРИМАТИ
8.
i
G
S
ЗАМІНИТИ(G→Y=i)
ТРИМАТИ
9.
i
I
S
ЗАМІНИТИ(I→IJ)
ТРИМАТИ
10.
i
J
S
ЗАМІНИТИ(J→M);
ТРИМАТИ
11.
i
Q
S
ЗАМІНИТИ(Q→Ri)
ТРИМАТИ
12.
i
S
S
ЗАМІНИТИ(S→Ui)
ТРИМАТИ
13.
i
M
S
ЗАМІНИТИ(M→Vai)
ТРИМАТИ
14.
i
X
S
ЗАМІНИТИ(X→Ioi)
ТРИМАТИ
15.
c
O
S
ЗАМІНИТИ(O→B)
ТРИМАТИ
16.
c
Z
S
ВИШТОВХНУТИ
ТРИМАТИ
17.
c
B
S
ЗАМІНИТИ(B→Gc)
ТРИМАТИ
18.
n
X
S
ЗАМІНИТИ(X→Ion)
ТРИМАТИ
19.
n
Y
S
ЗАМІНИТИ(Y→Hn)
ТРИМАТИ
20.
b
O
S
ВИШТОВХНУТИ
ТРИМАТИ
21.
b
Z
S
ВИШТОВХНУТИ
ТРИМАТИ
22.
b
B
S
ВИШТОВХНУТИ
ТРИМАТИ
23.
b
H
S
ВИШТОВХНУТИ
ТРИМАТИ
24.
b
T
S
ЗАМІНИТИ(T→eIb)
ТРИМАТИ
25.
b
I
S
ЗАМІНИТИ(I→dIb)
ТРИМАТИ
26.
e
I
S
ВИШТОВХНУТИ
ТРИМАТИ
27.
d
I
S
ВИШТОВХНУТИ
ТРИМАТИ
28.
r
I
S
ЗАМІНИТИ(I→IJ)
ТРИМАТИ
29.
r
J
S
ЗАМІНИТИ(J→K)
ТРИМАТИ
30.
r
K
S
ЗАМІНИТИ(K→;Q(r)
ТРИМАТИ
31.
w
I
S
ЗАМІНИТИ(I→IJ)
ТРИМАТИ
32.
w
J
S
ЗАМІНИТИ(J→L)
ТРИМАТИ
33.
w
L
S
ЗАМІНИТИ(L→;S(w)
ТРИМАТИ
34.
f
I
S
ЗАМІНИТИ(I→IJ)
ТРИМАТИ
35.
f
J
S
ЗАМІНИТИ(J→W)
ТРИМАТИ
17.07.2020 15:07-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора