Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методичні вказівки КР СПЗ
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Механіко технологічний
Кафедра:
Кафедра програмного забезпечення
Інформація про роботу
Рік:
2014
Тип роботи:
Методичні вказівки до курсової роботи
Предмет:
Системне програмне забезпечення
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Кіровоградський національний технічний університет
Механіко-технологічний факультет
Кафедра програмного забезпечення
Методичні вказівки до виконання курсової роботи з системного програмного
забезпечення
для студентів спеціальності 6.050102 “Комп’ютерна інженерія”
Розробив:
викл. каф. ПЗ
Бісюк В.А.
Затверджено
на засіданні кафедри
програмного забезпечення
протокол № від
Кіровоград 2014
1. Мета роботи
Мета роботи: вивчення складових частин, основних принципів побудови та функціонування компіляторів, практичне освоєння методів побудови найпростіших компіляторів для заданого вхідного мови.
Курсова робота полягає в створенні компілятора з заданої підмножини мови Паскаль або С з незначними модифікаціями і спрощеннями (повний опис вхідного і вихідного мов дано далі до завданні для кожного варіанту).
Результатами курсової роботи є програмна реапізація заданого компілятора і пояснювальна записка, оформлена відповідно до вимог стандартів та завдання на курсову роботу.
Для програмної реалізації компілятора рекомендується використовувати мову програмування Object Pascal або С/С++.
Можливо використовувати інші мови і системи програмування за погодженням з викладачем.
Компілятор рекомендується побудувати з наступних складових частин:
1. Лексичний аналізатор.
2. Синтаксичний аналізатор.
3. Оптимізатор.
4. Генератор результуючого коду.
Для побудови компілятора рекомендується використовувати методи, освоєні в ході виконання лабораторних робіт з курсу «Системне програмне забезпечення ».
2. Порядок виконання роботи
Рекомендований порядок виконання роботи представлений в табл. 1.1.
Таблиця 1.1. Рекомендовані етапи і час виконання курсової роботи
№
п/п
Етап виконання
Роботи
Час
викон.
(тижн.)
Результат
1
Отримання завдання
2
Вибір однієї з трьох форм граматики,
запис граматики вхідної мови
в обраній формі граматики
1
Граматика вхідної
мови
3
Визначення кордону між лексичним
і синтаксичним аналізаторами,
вибір методу взаємодії між ними
0,25
Опис лексичного
аналізатора
4
Вибір способу організації
таблиці ідентифікаторів
0,25
Опис обраного
способу організації
таблиці ідентифікаторів
5
Побудова лексичного аналізатору
0,5
Граф переходів автомата
лексичного аналізатора
6
Програмна реалізація лексичного
Аналізатора
2
Програмний код
лексичного аналізатора
7
Вибір класу КС-граматик для
побудови синтаксичного аналізатора
0,5
Опис синтаксичного
аналізатора, обґрунтування
вибору
8
Програмна реалізація
синтаксичного аналізатора
3,5
Програмний код
синтаксичного аналізатора
9
Вибір використовуваних форм
внутрішнього представлення програми
0,5
Опис обраних форм
внутрішнього представлення програми, обґрунтування
вибору
10
Опис використовуваного алгоритму
Оптимізації
0,5
Алгоритм роботи
оптимізатора (блок-схема)
11
Програмна реалізація оптимізатора
2
Програмний код
оптимізатора
12
Реалізація генератора результуючого
Коду
2
Програмний код
генератора
результуючого коду
13
Налагодження компілятора в цілому
1
Програмний код
розробленого
компілятора
14
Оформлення пояснювальній записки
1,5
Пояснювальна
записка
15
Підготовка курсової роботи до захисту
0,5
16
Захист курсової роботи
Разом
16
3. Вимоги до змісту пояснювальній записки
Пояснювальна записка до курсової роботи повинна містити наступні розділи:
1. Короткий виклад мети роботи.
2. Завдання з лабораторної роботи (номер варіанту і повний опис свого
варіанту).
3. Граматика вхідної мови в одному з трьох можливих видів:
■ форма Бекуса-Наура;
■ форма з метасимволом;
■ графічна форма.
4. Опис обраного способу організації таблиці ідентифікаторів з обґрунтуванням зробленого вибору.
5. Опис лексичного аналізатора і обраного методу його взаємодії з синтаксичним аналізатором.
6. Граф переходів чи інший опис кінцевого автомата лексичного аналізатора.
7. Обґрунтування вибору класу КС-граматик для побудови синтаксичного аналізатора.
8. Опис синтаксичного аналізатора в залежності від обраного класу КС-граматик (включаючи всі необхідні керуючі таблиці і множини).
9. Вибір форм внутрішнього представлення програми, що використаний в компіляторі з обґрунтуванням зробленого вибору.
10. Опис використовуваного методу породження результуючого коду.
11. Опис використовуваного методу оптимізації.
12. Інформація про організацію побудованого компілятора, його розбиття на проходи, кількість проходів в компіляторі.
13. Висновки по виконаній роботі.
14. Приклад вхідних програми і результуючої програми, побудованої компілятором.
15. Текст програми компілятора.
Приклади вхідних і результуючої програм, а також текст програми компілятора рекомендується оформляти у вигляді додатків до тексту пояснювальної записки.
В якості основи побудови синтаксичного аналізатора допускається вибрати будь-який клас КС-граматик. Опис синтаксичного аналізатора має бути повним, містити всі керуючі таблиці і множини, необхідні для побудови алгоритму функціонування аналізатора (розпізнавача).
Допускається для побудови лексичного і (або) синтаксичного аналізаторів використовувати автоматизовані методи побудови аналізаторів (наприклад на основі програм LEX і YACC). В цьому випадку не потрібно приводити граф переходів кінцевого автомата (для лексичного аналізатора) і опис синтаксичного аналізатора.
У такому варіанті відповідні розділи пояснювальної записки повинні містити наступну інформацію: обґрунтування вибору програми, використовуваної в якості засобу автоматизованого побудови розпізнавача, і текст вхідного файлу, створеного для виконання автоматизованого побудови лексичного або синтаксичного аналізатора.
4. Завдання на курсову роботу
Компілятор повинен запускатися командним рядком з кількома вхідними параметрами. Першим і головним вхідним параметром має бути ім'я вхідного файлу, другим параметром може бути ім'я результуючого файлу.
Вимоги до решти параметрів командного рядка і керуючих ключів (якщо вони необхідні) встановлюються виконавцем самостійно. Командний рядок повинен бути достатнім для функціонування компілятора. Крім інтерфейсу командного рядка можлива наявність додаткового інтерактивного інтерфейсу користувача у компілятора (в тому числі і графічного) на розсуд виконавця роботи.
Вхідна мова компілятора повинна задовольняти наступним вимогам:
- вхідна програма починається ключовим словом prog (program) 'і закінчується ключовим словом end;
- вхідна програма може бути розбита на рядки довільним чином, всі пробіли і переноси рядка повинні ігноруватися компілятором;
- текст вхідної програми може містити коментарі будь-якої довжини, які повинні ігноруватися компілятором (вид коментаря заданий у варіанті завдання);
- вхідна програма повинна являти собою єдиний модуль, що містить лінійну послідовність операторів, виклики процедур і функцій не передбачаються;
- повинні бути передбачені такі варіанти операторів вхідної програми:
■ оператор присвоювання виду <змінна>: = <вираз>;
■ умовний оператор виду if <вираз> then <оператор> або if <вираз> then <оператор> else <оператор>;
■ складний (составной рус.) оператор виду begin _ end;
■ оператор циклу, передбачений варіантом завдання;
Вирази в операторах можуть містити наступні операції (мінімум):
■ арифметичні операції додавання (+) і віднімання (-);
■ операції порівняння «менше» (<), «більше» (>), «дорівнює» (=);
■ логічні операції І (and), АБО (or), HІ (not);
■ додаткові арифметичні операції, передбачені варіантом завдання;
□ операндами у виразах можуть виступати ідентифікатори (змінні) і константи (тип допустимих констант вказаний у варіанті завдання);
□ все ідентифікатори, що зустрічаються у вихідній програмі, повинні сприйматися як змінні, що мають тип, заданий у варіанті завдання (попереднього опису ідентифікаторів у вихідній програмі не потрібен);
□ повинні враховуватися два зумовлені ідентифікатора InpVar і CompileTest, сенс яких буде ясний з приведеного далі опису вихідної мови.
Пріоритет операцій виконавець роботи повинен вибрати самостійно (пріоритет операцій враховується в граматиці вхідної мови). для зміни пріоритету операцій повинні використовуватися круглі дужки.
Повний опис вхідної мови має бути заданий в граматиці вхідної мови, яка будується виконавцем на першому етапі роботи. Граматика вхідної мови повинна передбачати будь-які вхідні ланцюжки, що задовольняють викладеним вимогам. Допускаються будь-які модифікації вхідної мови по вибору виконавця, якщо вони не виходять за рамки зазначених вимог.
Допускається розширювати набір дозволених операцій і операторів вступного мови при умові задоволення заданим мінімальним вимогам, але при цьому не дозволяється використовувати операції та оператори з інших варіантів завдання - всі такі оператори обов'язково повинні трактуватися як помилкові.
Компілятор повинен перевіряти наступні семантичні обмеження вхідної мови:
□ не допускається привласнення значень константам;
□ не допускається привласнення значення ідентифікатору InpVar;
□ не допускається використовувати ідентифікатор CompileTest, інакше як для присвоєння йому значень.
В якості вихідного (результуючого) мови повинен використовуватися мова асемблера процесорів типу Intel 80x86 в модифікації вбудованої мови асемблера компілятора Pascal виробництва фірми Borland.
Результуюча програма повинна мати наступний вигляд:
Prog <Ім’я_програми>;
{Обирається виконавцем}
Var InpVar- <Тип_даних>:
[Тип даних вказано в варіанті завдання}
Var <Список_змінних>: <Тип_даних>
{Список змінних повинен містити перелік всіх змінних з вхідної програми}
Function CompileTestdnpVar: <Тип_данихх>)- <Тип_даних>
{Змінні CompileTest і InpVar є попередньо визначеними в тексті вхідної програми}
Begin
Asm
{Сюди повинен бути включений текст результуючей програми породженої компілятором}
end:
end:
begin
read1n(InpVar).
writeln(CompileTest(InpVar)).
end
5. Варіанти завдань
Таблиця 1.2. Варіанти завдань на виконання курсової роботи
№ Тип Додаткові Оператор Оптимі Тип Тип
констант операції циклу -зація даних комент.
№ Тип Додаткові Оператор Оптимі Тип Тип
констант операції циклу -зація даних комент.
№ Тип Додаткові Оператор Оптиці Тип Тип
констант операції циклу -зація даних комент
Нижче пояснюються цифрові позначення використані в табл. 1.2.
Типи констант:
2 — двійкові;
8 — вісімкові;
16 — шістнадцяткові.
Додаткові операції:
*, / — множення і ділення,
» « — зсуви вправо и вліво (арифметичні або логічні — на вибір);
++ — інкремент (збільшення значення змінної на 1);
-- декремент (зменшення значення змінної на 1).
Типи додаткових операторів циклу:
1. Цикл с передумовою виду while <вираз> do <оператор>.
2. Цикл с післяумовою виду repeat <оператор> until <вираз>.
3. Цикл с післяумовою виду do <оператор> while <вираз>.
4. Два варіанта циклу з перерахуванням по заданій змінній виду
for <змінна>: =<вираз> to <вираз> do <оператор>
або
for <змінна>:=<вираз> downto <вираз> do <оператор>.
Типи коментарів:
1. Коментар в фігурних дужках: {...}.
2. Коментар в круглих дужках із зірочкою: (*_.*).
3. Коментар за подвійною косою рискою до кінця рядка: //._.
4. Коментар всередині косих рисок з зірочкою: /*_*/.
Методи оптимізації:
1. Виключення зайвих операцій.
2. Згортка об’єктного коду.
Порядок оцінки результатів роботи
Виконана курсова робота оцінюється за такими показниками:
зміст пояснювальної записки;
функціональність побудованого компілятора;
здатність виконавця відповідати на питання и за змістом пояснювальній записки і по суті роботи.
Текст пояснювальної записки має задовольняти вимогам ГОСТ і стандартів університету. Зміст пояснювальної записки має задовольняти вимогам цього завдання на виконання курсової роботи.
Функціональність компілятора перевіряється шляхом подачі на його вхід
найпростіших контрольних прикладів (в тому числі і прикладів помилкових вхідних програм). При цьому отримана в результаті програма перевіряється методом компіляції її в системі програмування Delphi 5 з подальшим виконанням. Результат виконання порівнюється з підрахованим вручну результатом виконання контрольного прикладу.
Функціональність компілятора в першу чергу оцінюється по заданим
мінімальним вимогам і по працездатності компілятора (відсутність «зависань» і нерегламентованих повідомлень про помилки при будь-яких вхідних даних).
Додаткові бонуси при оцінці компілятора можуть бути отримані за
наступні розширення заданої мінімальної функціональності:
реалізація додаткових ключів і параметрів управління роботою
компілятора;
наявність у компілятора додаткового інтерактивного інтерфейсу з
користувачем;
ефективна («скорочена») обробка логічних операцій та операцій
порівняння (метод її реалізації описаний у прикладі виконання лабораторної
роботи № 4 в частині, присвяченій опису генератора коду і схем СУ-перевода);
реалізація додаткових операторів і операцій вхідної мови. В
якості найбільш очевидного розширення вхідної мови пропонується реалізувати оператор виходу з циклу (break) і переходу до наступної ітерації циклу (continue);
додатковий семантичний контроль вхідної програми;
будь-які додаткові методи оптимізації результуючої програми (як
машинно-незалежні, так і машинно-залежні);
розширена діагностика помилок, генерація попереджень з приводу
операторів вхідної мови, що викликають сумніви з точки зору їх семантики.
Не допускається реалізовувати функціональність, передбачену іншими
варіантами курсової роботи, - така функціональність розглядається не як
додатковий бонус, а як недолік компілятора.
Додаткові бонуси не враховуються і не зараховуються, якщо не
реалізована мінімальна функціональність компілятора, передбачена варіантом завдання.
Здатність виконавця курсової роботи відповідати на питання за змістом
пояснювальної записки і по суті роботи перевіряється в особистій бесіді з
викладачем при захисті курсової роботи.
Рекомендації по виконанню роботи
У будь-якому випадку при ознайомленні з прикладом виконання роботи і при виконанні роботи за своїм завданням треба звернути увагу на такі основні
моменти:
1. Побудова граматики вхідної мови - це визначальний момент в курсовій роботі. Правильно побудована граматика істотно спростить виконання роботи, а помилки, навпаки, можуть істотно збільшити трудомісткість подальших етапів. Рекомендується, побудувавши граматику, відразу ж проконсультуватися з викладачем, щоб виправити можливі помилки на ранній стадії.
2. Той, хто виконує курсову роботу повинен вирішити для себе, як він буде будувати лексичний і синтаксичний аналізатори: самостійно (вручну) або автоматизованим методом (з використанням спеціалізованого ПО - рекомендуються програми LEX і YACC). Автоматизований метод простіший і швидший, але вимагає від автора роботи часу на освоєння спеціалізованого програмного забезпечення. Можливо поєднувати обидва методи: наприклад, побудувати лексичний аналізатор за допомогою програми LEX (вона досить проста у використанні), а синтаксичний аналізатор - вручну. Рекомендації щодо цього кожен повинен вибрати, оцінивши свої сили в можливості освоєння нового програмного забезпечення.
3. Створення лексичного аналізатора - це етап, який не являє особливої
складності, так як побудова КА для лексичного аналізатора являє собою повністю формалізований процес (при виконанні якого в першу чергу важлива уважність). Але при виконанні цього етапу головне завдання не в тому, щоб правильно побудувати КА - в цьому, найчастіше, немає проблем, - а в тому, щоб максимально ефективно розділити аналіз, який виконується лексичним аналізатором, і аналіз, що виконується аналізатором синтаксичним. Як правило, чим більше роботи виконує лексичний аналізатор, тим краще. Уже побудувавши граматику мови, потрібно мати уявлення про те, які елементи мови виділятимуться на етапі лексичного аналізу.
4. Вибір класу КС-граматики для створення синтаксичного аналізатора -
це, з точки зору автора, другий за важливістю етап після побудови граматики. Завдання складено так, що будь-яка вхідна мова може бути задана граматиками, аналізованими принаймні трьома методами: методом рекурсивного спуску (або ж LL(1)-граматикою), методом на основі граматик операторного передування і методом на основі LR(1) або LALR(1)-граматик. Важливо побудувати граматику вхідної мови так, щоб вона відповідала методу, який нас цікавить, або ж вміти перетворити її до необхідного виду. На жаль, тут немає формалізованих рекомендацій. Найпростіший шлях - взяти для опису граматики мови прийоми і правила, розглянуті при виконанні лабораторної роботи №3, тоді для побудови синтаксичного распознавателя з великою ймовірністю підійде метод на основі граматик операторного передування.
5. Вибір форми внутрішнього представлення програми, методів оптимізації і генерації результуючого коду - це взаємозалежні процеси. Оскільки розглянуті раніше методи і алгоритми були засновані на
використанні тріад, автор не рекомендує намагатися використовувати інші форми внутрішнього представлення.
Необхідну додаткову інформацію можна знайти в літературі по компіляторам і системам програмування [1-4,7].
Приклад виконання курсової роботи
Як приклад для ілюстрації виконання курсової роботи буде взята вхідна мова, яка, з одного боку, не збігається ні з одним із варіантів завдання, а з іншого боку - дозволяє добре проілюструвати всі методи і технічні прийоми, які корисні при виконанні роботи.
Багато методів, технічних прийомів та їх реалізація в курсовій роботі будуть взяті з лабораторних робіт № 1-4, які були розглянуті раніше. Інші методи, навпаки, будуть реалізовані інакше, щоб проілюструвати всі існуючі можливості, їх переваги та недоліки. У кожному разі буде дане пояснення, чому використаний той чи інший метод.
У прикладі проілюстровані наступні цікаві моменти:
поділ лексичного і синтаксичного аналізаторів з метою спрощення
роботи останнього (на прикладі унарної арифметичної операції «-» і операції порівняння типу «не дорівнює»);
виявлення присвоювання значень константам на етапі синтаксичного розбору (в лабораторних роботах № 3 і 4 ця ж операція виконувалася на етапі семантичного аналізу перед генерацією коду);
можливості перетворення вихідної граматики, зміни синтаксису
вхідної мови та модифікації алгоритму, синтаксичного розбору на основі аналізу правил граматики (на прикладі умовного оператора);
модифікація остовно граматики при необхідності розрізняти
правила;
методи обробки логічних операцій і операцій порівняння;
найпростіший семантичний аналіз і модифікація результуючого
коду на етапі семантичного аналізу (на прикладі обробки змінних InpVar і СоmpileTest);
елементарні методи машинно-залежної оптимізації результуючого
коду.
Для реалізації курсової роботи будуть використовуватися програмні модулі, створені при виконанні лабораторних робіт № 1-4, код яких не залежить від вхідної мови. Такий підхід ілюструє, наскільки зручно і ефективно
виділяти не залежну від вхідної мови частину компілятора в окремі модулі або бібліотеки.
Завдання для прикладу виконання роботи
В якості прикладу візьмемо наступні умови для вхідної мови:
1. Тип допустимих констант: десяткові.
2. Додаткова операція: унарний арифметичний мінус (-).
3. Оператор циклу: while (<вираз>) do <оператор>.
4. Оптимізація: обидва методи (1 і 2).
5. Тип даних: Long integer (longint, 32 біт).
6. Тип коментаря: фігурні дужки ({...}).
Крім того, модифікуємо синтаксис умовного оператора (два типи):
if (<вираз>) <оператор> else <оператор>;
if (<вираз>) <оператор>;
і доповнимо перелік операцій порівняння операцією «не дорівнює» (<>).
Отримаємо вхідну мову, що поєднує в собі елементи синтаксису мов C ++
(елементи оператора циклу і умовний оператор) і Object Pascal (оператор циклу, составной оператор begin _ end, оператор присвоювання і коментарі).
В якості результуючої (вихідної) мови компілятора будемо
використовувати мову асемблера процесорів типу Intel 80386 і більш пізніх модифікацій в модифікації для системи програмування Delphi 5 [9, 23, 28, 41, 44]. Щоб виключити неоднозначності при роботі з цією системою програмування, змінимо семантичні обмеження вхідної мови:
зробимо допустимим використання імені змінної CompileTest в
будь-яких операторах вхідної мови (а не тільки в операторах присвоювання);
заборонимо використання змінних з ім'ям Result, так як таке ім'я
змінної є наперед визначеним в цільовій обчислювальній системі.
Крім того, в іменах змінних у вхідномій мові не повинні відрізнятися малі та великі літери (наприклад, змінні з іменами «i» та «I» повинні сприйматися як одна і та ж змінна).
Граматика вхідної мови
Граматику вхідної мови побудуємо на основі фрагментів граматик,
розглянутих у завданнях з лабораторної роботи № 3. Там є правила для лінійних операцій (арифметичні і логічні операції) і для умовного оператора. За аналогією з умовним оператором побудуємо оператор циклу. Для складеного оператора і всієї програми в цілому залишиться визначити ще одне поняття - послідовність операторів. Будемо розглядати послідовність операторів як ланцюжок операторів, розділених знаком «крапка з комою».
В результаті отримаємо КС-граматику у формі Бекуса-Наура:
G ({prog, end., if, else, begin, end, while, do, or, xor, and, not, <,>, =, <>, (,), -, +, um, a, c, ;, : = }, {S, L, O, B, C D, E, T, F}, P, S)
з правилами Р:
Жирним шрифтом виділено термінальні символи.
Всього в побудованій граматиці G 28 правил. Нетермінальні символи
граматики мають наступний зміст:
S - вся програма;
L - послідовність операторів (може складатися і з одного
оператора);
О - оператор (п'ять видів: повний умовний оператор, неповний
умовний оператор, складений оператор, оператор циклу, оператор присвоювання);
В, С - логічний вираз і його елементи;
D - операція порівняння або логічний вираз дужках;
E, T, F- арифметичне вираз і його елементи.
Можна звернути увагу на наступні моменти в граматиці:
операція um («унарний мінус») позначена окремим термінальним
символом, що не збігається зі знаком арифметичної операції віднімання («-»), хоча в тексті вихідної програми ці два символи ідентичні;
константи і змінні позначені двома різні ми термінальними
символами - а і c відповідно - це говорить про те, що вони повинні розрізнятися на етапі синтаксичного аналізу;
операція заперечення not обов'язково вимагає після себе виразу в
дужках, що не зовсім відповідає традиційному записи логічних операцій
(але не суперечить завданню!), традиційний запис міг би бути записаний
у вигляді правил:
D → not D |G
G → E <E | E> E | E = E | E <> E | (B)
Останній приклад показує, що розробник граматики не зобов'язаний слідувати загальноприйнятим шаблонам: він може відходити від них, якщо це не суперечить завданням. Нерідко це допомагає істотно скоротити трудомісткість виконання роботи (далі будуть проілюстровані ще дві проблеми, пов'язані з унарним знаком «мінус» і умовним оператором).
Опис обраного способу організації таблиці ідентифікаторів
Для організації таблиці ідентифікаторів виберемо комбінований спосіб, оскільки в ньому відсутні обмеження на кількість вхідних ідентифікаторів і він не потребує розробки складної і ефективної хеш-функції (розробка комбінованої таблиці в даному випадку простіше, ніж вибір хорошої хеш-функції).
В якості такого способу візьмемо комбінацію хеш-адресації і бінарного
дерева, яка була використана при виконанні лабораторної роботи № 1.
Програмний код, який реалізує таку таблицю ідентифікаторів, наведено в
лістингах П3.1 і П3.2 в додатку 3. Для того щоб в таблиці ідентифікаторів в іменах змінних не розрізнялися рядкові і прописні літери, цей код повинен бути відкомпільований із зазначенням відповідних умов.
Опис лексичного аналізатора
Для побудови лексичного аналізатора скористаємося підходом,
використаним в лабораторній роботі № 2.
Задача лексичного аналізатора для описаної вище мови полягає в тому,
щоб розпізнавати і виділяти в початковому тексті програми всі лексеми цієї
мови. Лексемами даної мови є:
дванадцять ключових слів мови (prog, end., іf, else, begin, end,
while, end, not, or, xor і and);
роздільники: відкриває і закриває круглі дужки, крапка з комою;
знаки операцій: присвоювання, порівняння (чотири знаки),
додавання, віднімання і унарний мінус;
ідентифікатори;
цілі десяткові константи без знака.
Можна помітити, що end і end. - це різні лексеми.
Крім перерахованих лексем розпізнавач повинен вміти визначати і виключати з вхідного тексту коментарі, принцип побудови яких описаний вище. Для виділення коментарів ключовими символами повинні бути дужки, які відриваються і закриваються.
Окремої уваги заслуговує знак «унарний мінуса», який не випадково
був узятий в якості ілюстрації для цього прикладу.
Якщо не робити різниці між унарним мінусом і бінарним, то правила
граматики G для символів Е, Т та F мали б наступний вигляд:
Е → Е - Т | Е + Т | Т
T → - T | F
F → (Е) | a | c
Однак така граматика буде дуже складна для синтаксичного аналізу, оскільки в ній виникає проблема вибору правила між Е –Т і –Т при виконанні згортки (можна перевірити і прийти до висновку, що вона, наприклад, не є граматикою операторного передування). Перетворення для цієї граматики неочевидні.
Але можливе більш просте рішення, якщо зрозуміти, як розрізнити дві операції (унарний і бінарний знаки «мінус») на етапі лексичного аналізу. Видмінність можна зробити, якщо зауважити, що бінарний мінус завжди слідує після операнда (змінної або константи) або після круглої дужки, що закривається, в той час як унарний мінус - або після знака операції, або після
круглої дужки, що відкривається. Такий аналіз цілком під силу КА, якщо в нього додати ще один стан, який буде визначати, яку лексему (унарний або бінарний мінус) зіставляти з вхідним символом « - ». Оскільки перед унарним
мінусом, як і перед будь-якими іншими лексемами, може бути коментар, то доведеться додати два стани (щоб розрізняти, в якому місці КА зустрівся початок коментаря, і після завершення коментаря повернутися в те ж місце).
Таким чином, незначне ускладнення КА лексичного аналізатора дозволить уникнути серйозних проблем на етапі синтаксичного аналізу.
Даний приклад ілюструє, як важливо раціонально провести межу між
лексичним і синтаксичним аналізом.
Інший приклад з заданої вхідної мови ще більш очевидний, хоча він і не
веде до настільки серйозних ускладнень при лексичному розборі: це знак операції «не дорівнює» - «<>». Його можна розглядати як дві лексеми або як одну. У першому випадку перевірка правильності цієї операції буде йти на етапі синтаксичного аналізу, у другому випадку - на етапі лексичного аналізу. Обидва варіанти можуть бути без проблем реалізовані, але другий з них представляється все ж більш логічним.
Як правило, якщо є можливість виявлення помилки на більш ранніх стадіях компіляції, краще такою можливістю скористатися. З цієї рекомендації є винятки - їй краще не слідувати в тих випадках, коли ранній аналіз не дає істотних переваг, але може порушити логічну стрункість мови чи граматики, ускладнить їх сприйняття людиною.
Наприклад, в тій же вихідній мові поєднання if {і wbile ( можуть бути
розглянуті як єдині лексеми (позначимо їх if_ і w_l) та виявлені на етапі лексичного аналізу. При цьому синтаксичний аналізатор не отримує ніяких переваг, але правила граматики для нетермінального символу будуть мати вигляд:
О → if_ В) О else О | if_ В) О | begin L end | w_I f В) do О | а: = Е
Логічна цілісність і структура правил порушені, так як людині важко сприймати дужку, що закривається при відсутності дужки, що відкривається, а тому від такого варіанту краще відмовитися (хоча остаточне рішення, звичайно, завжди залишається за розробником компілятора).
В даній мові лексичний аналізатор завжди може однозначно визначити
межі лексеми, тому немає необхідності в його взаємодії з синтаксичним аналізатором та іншими елементами компілятора.
Прийнявши до уваги правила та угоди, розглянуті для КА в лабораторній роботі № 2, повністю КА можна описати таким чином:
Функція переходів (δ) для цього КА приведена в додатку 2.
З початкового стану КА літери «р», «е», «i», «b», «w», «о», «х», «а» і «n» ведуть в початок ланцюжків станів, кожний з яких відповідає ключовому слову (ланцюжок, що починається з «е», відповідає трьом ключовим словам):
стану Р1, Р2, РЗ, Р4 - ключовому слову prog;
стану El, E2, ЕЗ - ключовим словами end і end.;
стану І1, І2 - ключовому слову if;
стану В1, В2, ВЗ, В4, В5 - ключовому слову begin;
стану Wl, W2, W3, W4, В5 - ключовому слову while;
стану El, L2, L3, L4 - ключовому слову else;
стану Dl, D2 - ключовому слову do;
стану Ol, О2 - ключовому слову or;
стану XI, Х2, ХЗ - ключовому слову хог;
стану Al, A2, A3 - ключовому слову and;
стану N1, N2, N3 - ключовому слову not.
Решта літер ведуть до стану, відповідному змінній (ідентифікатору) - V. Якщо в якомусь з ланцюжків зустрічається літера, що не відповідає ключовому слову, або цифра, то КА також переходить в стан V, а якщо зустрічається межа лексеми - запам'ятовує вже прочитану частину ключового слова як змінну (щоб правильно виділяти такі ідентифікатори, як «і» або «els», які збігаються з початком ключових слів).
Цифри ведуть в стан, що відповідає вхідний константі, - D. Фігурна дужка, що відкривається, веде в стан С, який відповідає виявленню коментаря - з цього стану КА виходить, тільки якщо отримає на вхід фігурну дужку, що закривається. Ще один стан - G - відповідає лексемі «знак присвоювання». В нього КА переходить, отримавши на вхід двокрапку, і очікує в цьому стані символу «рівність».
Знаки арифметичних операцій («+» і - «-»), знаки операцій порівняння («<», «>» та «=»),кругла дужка, що відкривається, а також останні символи ключових слів переводять КА в стан S, який відрізняється від початкового стану тим, що в цьому стані КА сприймає символ «-» як знак унарної операції заперечення, а не як знак операції віднімання. Якщо в стані S на вхід КА надходить фігурна дужка, відкривається, то він переходить в стан С1 (а не в стан С), з якого по фігурній дужці, що закривається знову повертається в стан S.
Рис. 5.1. Граф переходів скороченого КА
(без урахування ключові слів)
У ще один стан - стан L - КА переходить, коли на його вхід надходить знак «<». У стані L автомат перевіряє, чи є знак «<» початком лексеми «<>» («не дорівнює») або ж це окрема лексема «<» («менше»).
Стан Н - початковий стан КА, а стани F і S - його кінцеві стани. Оскільки КА працює з безперервним потоком лексем, перейшовши в кінцевий стан Н, він відразу повинен повертатися в початковий стан, щоб розпізнавати чергову лексему. Тому в моделюючій програмі два стани (Н і F) можна об'єднати в один.
У функцію переходів КА не входить стан «помилка», щоб не захаращувати її. В цей стан КА переходить завжди, коли отримує на вхід символ, по якому немає переходів з поточного стану.
Видно, що граф переходів для даного КА буде занадто громіздким, щоб його можна було наочно представити на малюнку. Граф переходів скороченого КА (без урахування розпізнавання ключових слів) представлений на рис. 5.1.
Реалізація даного КА виконана аналогічно реалізації КА, побудованого в
лабораторній роботі № 2. Для опису структур даних лексем, що не залежать
від вхідної мови, використовується модуль LexElem, який був створений при
виконанні лабораторної роботи № 2 (лістинг П3.4, додаток 3). Типи допустимих
лексем описані в модулі LexType (лістинг ПЗ.З, додаток 3), а функціонування
автомата моделюється в модулі LexAuto (лістинг П3.5, додаток 3).
Опис синтаксичного аналізатора
Для побудови синтаксичного аналізатора використовуватимемо аналізатор на основі граматик операторного передування. Цей аналізатор є лінійним розпізнавачем (час аналізу лінійно залежить від довжини вхідного ланцюга), для нього існує простий і ефективний алгоритм побудови розпізнавача на основі матриці передування [1-3, 7]. До того ж алгоритм «зсув-згортка» для даного типу аналізатора був розроблений при виконанні лабораторної роботи № 3, а оскільки він не залежить від вхідної мови, він може бути без модифікацій використаний в даній роботі.
Побудова розпізнавача
Для побудови аналізатора на основі граматики операторного передування необхідно побудувати матрицю операторного передування (порядок її побудови був детально розглянутий при виконанні лабораторної роботи № 3).
Побудуємо множини крайніх лівих і крайніх правих символів граматики G. На першому кроці отримаємо множини, наведені в табл. 5.3.
Таблиця 5.3. Множини крайніх лівих і крайніх правих символів. Крок 1
Символ U
L(U)
R(U)
F
T
E
D
C
B
O
L
S
(, a, c
um, F
E, T
(, not, E
C, D
B, C
if, begin, while, a
L, O
Prog
), a, c
T, F
T
E, )
D
C
O, E, end
O, ;
end.
Після завершення побудови ми отримаємо множини, представлені в табл. 5.4 (детальна побудова множин крайніх лівих і крайніх правих символів описано при виконанні лабораторної роботи № 3).
Таблиця 5.4. Множини крайніх лівих і крайніх правих символів. Результат
Після цього необхідно побудувати множини крайніх лівих і крайніх правих термінальних символів. На першому кроці візьмемо всі крайні ліві і крайні праві термінальні символи з правил граматики G. Отримаємо множини, представлені в табл. 5.5.
Таблиця 5.5. Безлічі крайніх лівих і крайніх правих термінальних
символів. крок 1
Доповнимо множини, представлені в табл. 5.5, на основі раніше побудованих множин
14.05.2018 22:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора