Методические указания к выполнению лабораторных работ по курсу ПСП

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ

Національний технічний університет

„Харківський політехнічний інститут”

Кафедра „Обчислювальна техніка та програмування”

 

 

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

«ПСП»

 

Харків 2010

 

ЗМІСТ

 

 

Завдання для комплексної лабораторної роботи…………………………………..…3

1. Стадії роботи компілятора…………………………………………………………..4

2. Побудова компіляторів………………………………………………………………4

3. Визначення формальної граматики і мови…………………………………………5

4. Типи формальних мов і граматик…………………………………………………...6

5. Побудова правил граматики..……………………………………………………….6

6. Контекстно-вільні граматики й автомати…………………………………………..9

6.1. Приведені граматики………………………………………………………………..9

6.2. Визначення непродуктивних символів...…………………………………………..9

6.3. Визначення недосяжних символів ………………………………………………..10

6.4. Виключення ліворекурсивних правил…………………………………………….10

6.5. Виключення ланцюгових правил………………………………………………….11

6.6. Магазинні автомати………………………………………………………………...11

7. Спадні розпізнавані………………………………………………………………….12

7.1. Розділені граматики…………………………………………………………………13

7.2. Побудова детермінованого спадного розпізнавача……………………………….13

7.2.1. Множина ВИБІР…………………………………………………………………14

7.2.2. Побудова функції ПЕРВ(µ)……………………………………………………..15

7.2.3. Побудова функції СЛІД(µ)……………………………………………………...16

7.2.4. Побудова функції ВИБІР(µ)…………………………………………………….16

7.3. Слаборозділені граматики………………………………………………………….17

7.4. LL(1) – граматики......................................................................................................17

7.5. Побудова магазинного автомата..............................................................................18

8. Приклади побудови спадного розпізнавача ............................................................19

9. Література………………………………………………………………………..……24

 

ЗАВДАННЯ ДЛЯ КОМПЛЕКСНОЇ ЛАБОРАТОРНОЇ РОБОТИ

1. Ціль роботи.

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

2. Тематика лабораторних робіт

2.1.Виконання лексичного аналізу (2 години).

2.2.Побудова правил граматики.. Спрощення граматики- виявлення непродуктивних та недосяжних символів, виключення ліворекурсивних правил (2 години).

2.3.Побудова множини Вибір, та функції Слід і Перв. Виконання перевірки на належність до розділеної, слаборозділеної або LL-граматики.(2 години).

2.4.Розробка команд роботи розпізнавача. Перевірка роботи на прикладах.(2 години).

2.5.Написання та відлагодження тексту програми розпізнавача.(5 годин).

2.6.Створити зручного інтерфейсу для користувача.(2 години).

Порядок виконання роботи

2.1. В залежності від номера прізвища по списку вибрати індивідуальне завдання з п.3.

Умови задач.

2. Змінні символьного типу. Оператор виводу. 3. Масиви чисел . 4. Оператор циклу з параметром.

ВСТУП

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

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

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

На вхід компілятора подається текст, написаний вхідною мовою – мовою, зрозумілою людині, а результатом роботи компілятора є текст мовою, зрозумілому пристрою.

 

1. СТАДІЇ РОБОТИ КОМПІЛЯТОРА

 

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

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

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

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

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

Всі стадії роботи компілятору тісно пов’язані з диспетчером таблиці символів та оброблювачем помилок. Неформально оброблювач помилок та диспетчер таблиці символів також можуть вважатися “стадіями” компілятору.

 

2. ПОБУДОВА КОМПІЛЯТОРА

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

 

3. ВИЗНАЧЕННЯ ФОРМАЛЬНОЇ ГРАМАТИКИ І МОВИ

 

Кінцева множина символів, неподільних у даному розгляді, називаєтьсясловником чи алфавітом, а символи, що входять у множину, - буквами алфавіту. Наприклад, алфавіт A = {a, b, c, +,?} містить 5 букв.

Послідовність букв алфавіту називається словом чи ланцюжком у цьому алфавіті. Число букв, що входять у слово, називається його довжиною.

Формальною породжуючою граматикою Г, називається наступна сукупність чотирьох об'єктів: Г = { Vт, V_А, I Î V_A, R },

деV_т- термінальний алфавіт(словник); букви цього алфавіту називаються термінальними символами; з них будуються ланцюжки, породжувані граматикою;

V_A - нетермінальний, допоміжний алфавіт (словник); букви цього алфавіту використовуються при побудові ланцюжків; вони можуть входити в проміжні ланцюжки, але не повинні входити в результат породження;

I - початковий символ граматики I Î V_A.

R - множина правил виводучипороджуючих правил виду a® b, деaі b- ланцюжки, побудовані з букв алфавітуV_т ÈV_A, які називають повним алфавітом(словником) граматики Г.

У множині правил граматики можуть також входити правила з порожньою правою частиною виду Е ® . Щоб уникнути невизначеності через відсутність символу в правій частині правила, умовимося використовувати символ порожнього ланцюжка, записуючи таке правило у видіЕ ®$.

Множина кінцевих ланцюжків термінального алфавіту V_т граматики Гвиведених з початкового символу Iназивається мовою породжуваною граматикою Г.

Приклад

Нехай задана граматика Г:

V_т = {a, b, c}

V_A = {I}

R = {I®abc}

Які ланцюжки можна одержати?

Мова: abc

 

Приклад

Дано граматику Г:

V_т = {a, b, c, d}

V_A = {I, B, C}

R = {I®aB, B®Cd, B®dc C®$}

Які ланцюжки можна одержати?

Мова:

I®aB®aCd®a$d®ad

I®aB®adc

 

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

a®b

bÎV_T

4. ТИПИ ФОРМАЛЬНИХ МОВ І ГРАМАТИК

У теорії формальних мов виділяються 4 типи граматик, яким відповідають 4 типи мов. Ці граматики виділяються шляхом накладення обмежень, що підсилюються, на правила граматики.

Граматика типу 0

Граматики типу 0, яка називають граматиками загального виду, не мають ніяких обмежень на правила породження.

a®b

де a, b Î V_T, V_A

Такі граматики не знайшли широкого застосування.

 

Граматика типу 1

aAb®awb, де AÎ VA wÎVA, VT

Граматика типу 2

AÎVA aÎVT, VA У лівій частині стоїть один нетермінал, права частина може містити ланцюжки VA, VT.

Граматика типу 3

Граматики типу 3 називають автоматними граматиками (А - граматиками). Правила висновку в таких граматиках мають вид:

A®a

A®a - правосторонні правила

A®Ba - лівосторонні правила

 

ПОБУДОВА ПРАВИЛ ГРАМАТИКИ

Наступним кроком є виявлення послідовності, в якій елементи структури можуть входити до заданих ланцюжків. Такі послідовності є основою для…   5.1.Опис списків

Алгоритм побудови правил граматики

2. Проаналізувати структуру ланцюжків, виділяючи початок і кінець, де повторюються символи чи групи символів. 3. Ввести позначення для складних структур символів, що складаються з груп,… 4. Побудувати правило для кожної з виділених структур, використовуючи для завдання повторюваних структур рекурсію.

Приклад.

I®bAd, I®c, A®cBd, A®aAd, B®dAf }, знаходимо, що тут непродуктивними є символи А і B.Після виключення правил, що… R' = {I ®a I a,

Приклад.

R = { I ®aIb, I ®c, A ®bI, A ®a }, знаходимо, що A є недосяжним символом.

Приклад

R={ E ® E + T | T , T ® T *F | F,

Виключення ланцюгових правил

Правило граматики виду A ® B, де A,B ÎVA, називається ланцюговим.Для КВ-граматики Г, що містить ланцюгові правила , можна побудувати… Ідея доказу полягає в наступному. Якщо схема граматики має вид R = {...,A ®… то така граматика еквівалентна граматиці зі схемою R' = {...,A ® aX,...},

LL(1) - граматики

· права частина кожного правила являє собою або порожній ланцюжок $, або починається з термінального чи не термінального символу; · якщо два правила мають однакові ліві частини, то праві частини правил… · множина ВИБІР, побудована для правил з однаковою лівою частиною, не містять однакових елементів.

Побудова магазинного автомата

Для кожної LL(1) граматики можна побудувати детермінований магазинний автомат М, що допускає мова, породжувана даною граматикою: L ( Г ) = L ( М… Задача побудови магазинного автомата для заданої LL(1) граматики формулюється… Як магазинний алфавіт приймемо наступне об'єднання: H = {Vт È Va È {h0}}. Побудову функції переходів…

Приклад 1.

1. Будуємо правила граматики 1. I® i = A ; 2. A® i C

Приклад 2.

1. Будуємо правила граматики   1. I®write A;|writelnA;

Развернуть

Открыть в широком формате