Проектування трансляторів

ЛЕКЦІЯ 1
СУТНІСТЬ ПРЕДМЕТА. ЗМІСТ КП. ТЕРМІНИ.
ОРГАНІЗАЦІЯ РОБІТ. МАТЕМАТИЧНИЙ АПАРАТ.
СТРУКТУРНА СХЕМА Перекладачі. ПРОХОДА Перекладачі.
СПИСОК ЛІТЕРАТУРИ
Дорогі колеги. Протягом двох семестрів ми будемо зани-
маться найцікавішим розділом системного і теоретичного прог-
раммірованія - теорією проектування трансляторів.
Представляюся. Семікопенко Геннадій Петрович, к.т.н.
2 викладач - Дмитриенко Наталія Олегівна.
1 семестр: Чи буде прочитаний курс основ проектування тран-
тора. Ви ознайомитесь з інструментальними засобами, які ре-
КОМЕНДА для виконання практичної роботи. В обов'язковому
порядку Вами буде розроблено, погоджено і затверджено ТЗ на КП.
Завершується семестр заліком. Його можна отримати при виконанні-
нии наступних умов:
- Затвердженого ТЗ на КП;
- Пояснювальної записки до КП та її захисту, або традиційної
здачі заліку по всьому курсу.
Я рекомендую шлях розробки ПЗ та її захисту як найбільш для
нас вигідний. Текст ПЗ з'явиться складовою частиною КП, а захищати те,
що Ви самі написали, набагато легше. Здача заліку все одно не
звільняє Вас від необхідності подальшого складання ПЗ та її
захисту у 2 семестрі. Таким чином, розробка пояснювальній
частини КП в 1 семестрі заощаджує час і студентам, і преподавате-
лям.
Цілі проектування:
- Ознайомлення з одним з існуючих інструментів созда-
ня трансляторів - генераторів лексичного і синтаксичного
аналізаторів;
- Ознайомлення з математичним апаратом - формальними
граматиками (G), що використовуються для опису штучних мов
(ІМ);
- Проектування іноземних мов (програмування, інформаційного, опи-
сательного і будь-яких інших);
- Формальний опис іноземних мов з використанням інструментальних
коштів;
- Налагодження лексичного (ЛА) і синтаксичного (СА) аналізу-
торів, що входять до складу проектованого транслятора;
- Розробка семантичних програм транслятора;
- Комплексна налагодження транслятора на контрольних (тестових)
прикладах;
- І, нарешті, що завершує підцілі - захист КП. Зміст КП:
- Вступ, в якому Ви викладаєте відомості про цілі розрядів
лення КП, його зв'язку з ризиком, призначення проектованого ИЯ;
- Короткий опис використовуваного математичного апарату;
- Опис інструментальних засобів - генераторів лексічес-
ких і синтаксичних аналізаторів;
- Неформальне опис розробленого іноземних мов (призначення, про-
ласть застосування, ефективність у порівнянні з традиційними ЯП
для реалізації конкретних процесів РИЗИК, приклади програм).
Якщо у конкретного студента не має уяви для розрядів
лення власного іноземних мов, він може використовувати логічно завершений-
ве підмножина існуючого іноземних мов (Фортран, Паскаль, ПЛ, мови
роботи з БД та інші);
- Формальний опис лексики і синтаксису ИЯ;
- Тексти тестових програм на ИЯ;
- Тексти тестових програм на проміжному мовою - очікує-
мый розробником результат трансляції. Як правило в якості
проміжного мови в КП використовується мова Сі;
- Дерево виведення фрагмента тестової програми;
- Семантичні програми (блоки, процедури, функції), ис-
пользуемие для генерації тексту на проміжному мовою і Запом-
нанія результатів трансляції;
- Протоколи результатів виконання процесів трансляції;
- Висновки;
- Список літератури. У 1 семестрі Ви можете мені не пред'яв-
лять тільки протоколи. Все інше повинно обов'язково присут-
ствовать в ПЗ КП.
ОРГАНІЗАЦІЯ налагодження. Усі, хто проходить практику в підрозділ-
леніях підприємства, оснащених ПЕОМ з операційною системою
МS-DOS, може їх використовувати для виконання КП. Для цього пер-
ші 3 людини, узгоджений зі мною ТЗ на КП, повинні нада-
вити дискети (по 1 шт.), на які я скопіюють інструментальне
ПО - генератори програм лексичного і синтаксичного аналізу-
торів - LEX і YACC відповідно. Є й частина документації
до ПЗ.
Проектування КП може вестися і на СМ-1420, що знаходяться в
розпорядженні кафедри.
ПЗ КП найкраще набрати на ПЕОМ та роздрукувати. У цьому слу-
чаї можна Вам подумати і про розподіл окремих складових
КП в залежності від інтересів конкретних студентів.
Ті з Вас, хто готовий здати мені КП зараз, завтра або через
місяць - буде заохочений підвищеної оцінкою. При цьому такі студен-
ти звільняються від подальшого відвідування лекцій і практичних
занять.
2 семестр: Налагодження розробленого ПЗ та оформлення проток-
лов роботи ЕОМ.
МАТЕМАТИЧНИЙ АПАРАТ - теорія формальних мов і грама-
тик. Докладніше ми ознайомимося з ним на наступних лекціях.
ПРОЦЕС ТРАНСЛЯЦІЇ - що виконується зі збереженням сенсу
перетворення вхідного повідомлення з однієї мови в вихідну пові-
щення на іншій мові.
Транслятор - програма, що виконує процес трансляції. В
разі виконання вихідної програми без отримання тексту на ви-
Ходна мовою, говорять про режим інтерпретації вхідний програми.
Відповідна програма, що забезпечує безпосередню тран-
сляцію вхідного тексту в послідовність команд ЕОМ, називає-
ся інтерпретатором.
СТРУКТУРНА СХЕМА Перекладачі:
- ЛА (сканер), який використовується для розбору лексики вихідного
мови (ІМ). Сканер послідовно переглядає літери вихідної
(транслюється) програми. З літер за певними правилами, за-
даними автоматною граматикою, сканер будує символи програми
(інакше - лексеми). Склад лексем визначається розробником іноземних мов і
транслятора з нього. Як правило, це числа, ідентифікатори, слу-
жебние слова, літерали (ланцюжки літер, що мають у програмі самос-
тоятельное значення);
- СА, що використовується для визначення синтаксису транслюється-
го тексту і управління процесом трансляції. Результат СА - дере-
у висновку;
- Семантичний аналіз, що використовується для визначення сенсу
трансльованого повідомлення (або його фрагмента). Результат семанті-
тичного аналізу - зберігання інформації про транслюється повідомленні в
спеціальних структурах (таблицях символів, ідентифікатори, кон-
стант, та інших);
- Синтезатор (генератор) тексту на проміжному мовою
(польський запис, тріади, тетради, графи, та інші). У Вашому КП в
як проміжний мови я рекомендую використовувати мову
програмування Сі;
- Генератор програми в об'єктних код;
- Редагування зв'язків, генерація програми у вигляді завантажувати
зочного модуля.
Принципи побудови транслятора
Загальні відомості
Компілятор повинен виконати аналіз вихідної програми, а
потім синтез об'єктно програми. Вихідна програма розкладається
на складові частини, потім з них будуються частини еквівалентної
об'єктно програми. Для цього на етапі аналізу компілятор будує
декілька таблиць, які потім використовуються як при аналізі, так
і при синтезі. Цей процес представлений на рис.
Процес перетворення мов програмування включає сле-
дмуть етапи:
1) розпізнавання у вихідному тексті програми різних сос-
тавляющіх мови;
2) етап синтаксичного аналізу, на якому розпізнаються
структури вихідної програми і перевіряється їх правильність;
3) встановлення зв'язку між використовуваними ідентифікаторами і
їх описом.
Генерування об'єктно коду
Спосіб взаємодії і метод об'єднання цих етапів в еди-
ний процес залежить від числа проходів компілятора.
Всі 4-е послідовних процесу: сканування, аналіз,
підготовку до генерації та генерацію команд - можна виконувати пос-
ледовательно або паралельно певним взаємним сінхроніза-
єю. Одним з критеріїв, що визначають вибір в даному випадку, є при-
ляется об'єм доступної пам'яті. Часто вигідно або навіть необхідно
мати кілька проходів.
У однопрохідних трансляторах ціла последоватеьлность прос-
тих перетворень (етапів) застосовується по черзі до кожної не-
великої частини вихідної програми таким чином, що робоча прог-
Рамі звертається в процесі єдиного перегляду вихідної
програми. У багатопрохідним транслятор послідовності преоб-
разованій застосовуються до всієї програмі як до цілого.
Є багато факторів, що визначають вибір числа проходів
при проектуванні трансляторів (час компіляції, час розрядів
лення, відносна незалежність фаз трансляції, розміри ОП
ЕОМ).
Деякі мови (Алгол-68, АДА) принципово вимагають для
своєї реалізації кілька проходів, зокрема можна рассмот-
реть двухпрохідному схему трансляції. Її особливості:
1) вона може використовуватися для мов програмування, в
яких визначає реалізація ідентифікатора з'являється (тек-
стуально) раніше будь-прикладної реалізації, що має місце для
більшості мов;
2) при написанні транслятора необхідно пректіровать проме-
жуточную мова, якою повинен представлятися вихідний текст
між програмними проходами.
Лексичний аналіз (сканер)
Сканер - найпростіша частина компілятора, іноді також називаються
ваемая лексичним аналізатором. Сканер переглядає літери ис-
Ходна програми зліва направо і будує символи програми - це-
круглі числа, ідентифікатори, службові слова, двухлітерние символи,
такі як ** і// i т.д. Символи передаються потім на обробку
фактичного аналізатора. На цій стадії може бути виключений ком-
коментарями. Сканер також може заносити ідентифікатори в таблицю
символів і виконувати іншу просту роботу, яка фактично
вимагає аналізу вихідної програми. Він може виконати велику
частину роботи з макрогенераціі в тих випадках, коли потрібно
тільки текстова підготовка.
Синтаксичний аналіз
Аналізатори виконують роботи з розчленовування вихідної прог-
Рамі на складові частини, формування її внутрішнього пред-
ня та занесенню інформації в таблицю символів та інші таблиці.
При цьому також виконується повний синтаксичний і семантичний
контроль програми.
Звичайний аналізатор являє собою синтаксично управ-
ляющие програму. Насправді прагнуть відокремити сінтак-
сис від семантики настільки, наскільки це можливо. Коли сінтак-
січескій аналізатор дізнається конструкцію вихідного мови, він викликають
кість відповідну семантичну програму, яка контролі-
рілої дану конструкцію з точки зору семантики і потім Запом-
нает інформацію про неї в таблиці символів або у внутрішньому перед-
уявлення програми.
Семантичний аналіз
Семантична програма здійснює семантичну оброблен-
ку, коли пов'язане з нею правило викликає семантичну редукцію.
Ми припускаємо, що кожного разу, коли в сентенціальной фор-
ме основа x знайдена і її можна привести до нетерміналу U, сінтак-
січескій Розпізнавач викликає програму, пов'язану з правилом
U:: = x. Генерується польська ланцюжок зберігається в одновимірному мас-
сиве Р. Ціла мінлива р. містить індекс, який вказує на пер-
вий вільний елемент масиву. Кожен елемент масиву може з-
тримати один символ (ідентифікатор або оператор). Припустимо
також, що викликана семантична програма має доступ до сім-
волам основи S (1) ... S (i), що знаходяться в синтаксичному стеку S,
який використовується розпізнавачем.
Розглянемо програму, пов'язану з правилом E1:: = E2 + T.
Якщо вона викликана, то ми можемо вважати, що польська запис для Е2
і Т вже отримана. При цьому масив Р містить
...
оскільки Е2 раположено лівіше Т. Праворуч від у вихідній прог-
Рамі знаходяться тільки термінали, тому що розбір проводиться зліва
направо. Отже, все, що потрібно від програми, - це
занести знак "+" до польської ланцюжок. При цьому інфіксная запис Е2
+ Т переводиться в суффіксную запис Е2 Т +. Следоватедьно, Сема-
тичні програма має вигляд Р (р): = '+'; p: = p +1.
Розглянемо семантичну програму для F:: = I, де I обоз-
початку довільний код. Відповідно до правил
польської запису ідентифікатори передують своїм операторам; бо-
леї того вони зустрічаються в тому ж порядку, що і в інфіксной за-
писи. Все, що необхідно зробити, - це занести ідентифікатор в
масив Р. Тому програма має такий вигляд;
Р (р) = S (i); p: = p +1 де S (i) - верхній символ стека.
Оскільки для кожної продукції ми пишемо одну семантичну прог-
Рамі, то це допомагає поділити обробку на дрібні незалежні
частини, кожну з яких можна запрограмувати окремо, що
дозволяє не думати про все відразу.
Невеликі зміни в синтаксисі або семантиці вимагають лише
незначних змін у відповідних правилах граматики
або семантичних програмах. Різні частини аналізу відокремлені
один від одного, тому внесення змін не представляє особливих
утруднень.
СПИСОК ЛІТЕРАТУРИ
1. Гріс Д. Конструювання компіляторів для цифрових обчислюва-
неністю машин. М., Мир, 1975 р.
2. Ахо А., Ульман Дж. Теорія синтаксичного аналізу, пере-
вода та компіляції. М. Мир 1978
3. Льюис Ф., Розенкранц Д., Стірнз Р. Теоретичні основи
проектування компіляторів. М., Мир, 1979 р.
4. Вірт, Вебер. Теорія перекладу, компіляції та редактірова-
вання. М., Мир, 1980 р.
5. Віленкін С.Я., Трахтенгерц Е.А. Математичне забезпе-
ня керуючих обчислювальних машин. М., Енергія, 1972 р.
6. Фельдман Дж., Гріс Д. Системи побудови трансляторів.
Сб Алгоритми і алгоритмічні мови, вып.5, ВЦ АН СРСР, 1971 р.
ЛЕКЦІЯ 2
ВИЗНАЧЕННЯ
Автомат з кінцевим числом станів - це п'ятірка виду
(K, Vt, M, S, Z), де:
K - алфавіт елементів, званих станами;
Vt - вхідний алфавіт (літери, які можуть зустрінеться в
ланцюжку або пропозицію);
M - відображення (або функція) безлічі К * Vt вo безліч K
(якщо M (Q, T) = R, то це означає, що зі стану Q при вхідний
літері T відбувається перемикання в стан R);
SC К - початковий стан;
Z - непорожній безліч заключних станів, кожне з
яких належить К.
Автомат - пристроєм, призначений для виконання цільових перевірок
напрям дій без безпосередній участі людини.
Абстpактний автомат - математична модель автомата, заданий-
ва множинами (вхідних символів, станів і вихідних символів)
і двох двомісних функцій (пеpеходов і виходів). Функція пеpехо-
дів отобpажает пеpвие дві безлічі під втоpое, а функція виходів,
відповідно - у третьому.
Кінцевий автомат - абстpактний автомат, все тpі визначають-
щие безлічі котоpого кінцеві.
V + - Транзитивне замикання безлічі V.
V * - рефлексивно-Транзитивне замикання безлічі V.
Фоpмальная гpамматіка - фоpмальная система Пpавил, описую-
щих в певному аспекті деякими мова G = (Vt, Vn, P, S), де:
Vt - множина термінальних символів;
Vn - безліч нетермінальних символів;
P - кінцевий набір правил підстановки;
S З Vn - початковий символ.
Символи в лівій і правій частинах правил в сукупності обра-
зуются словник V, V = Vt U Vn.
Символи граматики G, що зустрічаються в лівій частині правил,
називаються нетермінальнимі. Безліч нетерміналов Vn З V являє-
ся підмножиною словника, інша частина безлічі V утворює
безліч термінальних сімолов Vt З V.
В залежності від обмежень, що накладаються на грамматічес-
каіе правила (продукції), розрізняють 4 основних класу граматик
(по Хомського). Їх визначення міститься нижче.
Правила автоматною гpамматікі мають вигляд:
U:: = N чи U:: = NW, де NC Vt, а U, WC Vn.
Правила контекстно-вільної гpамматікі мають вигляд:
U:: = u, де U C Vn, u C V.
Правила контекстно-залежної граматики мають вигляд:
xUy:: = xuy, де U C Vn, x, u, y C V.
Граматика без обмежень на грамматічекіе правила:
u:: = v, де u C V + і v C V *.
Будь-яка кінцева послідовність символів алфавіту А називаються
ється ланцюжком.
Безпосередній висновок. Нехай G - граматика. Кажуть, що
ланцюжок v безпосередньо породжує ланцюжок w, тобто v -> w, якщо
для деяких ланцюжків x і y можна написати v = xUy, w = xuy, де
U:: = u - правило граматики G. Також кажуть, що w безпосереднім-
ного що виводиться з v.
Висновок. Нехай G - граматика. Ланцюжок v породжує ланцюжок w,
тобто v => w, якщо існує послідовність безпосередніх
висновків v = x1 -> x2 -> x3 -> ... -> Xn = w.
Формальна мова L (g) = (x | S => x, x З Vt +) Таким чином,
мова - це що виводиться з S підмножина множини всіх термо-
нальних ланцюжків, тобто ланцюжків у Vt.
Сентенціальная форма. S => x - ланцюжок символів мови х, по-
народжуваних з аксіоми S.
Пропозиція: (x | S => x, x C Vt *) - виводиться з аксіоми S
ланцюжок термінальних символів, що належить рефлексивно-транзит-
тивного замикання безлічі термінальних символів Vt *.
Транслятор - це програма, яка перетворює спільнота-
ние, написаний мовою L1, в повідомлення, написаний на мові L2,
зі збереженням сенсу.
Формальна мова характеризується алфавітом, лексикою, Сема-
тікой і синтаксисом.
????????????? ПРОПОЗИЦІЯ ???????????? ? ? ? ?
? ? ? ?
ВИЗНАЧЕННЯ ПІДЛЯГАЮТЬ Присудок ДОПОВНЕННЯ
? ? ? ?
голодний верблюд з'їв колючку
У самому загальному вигляді до складу транслятора повинні входити сле-
дмуть блоки:
- Лексичний аналіз;
- Синтаксичний аналіз;
- Семантичний аналіз;
- Синтез програми на проміжному мовою;
- Оптимізація програми;
- Синтез об'єктної програми.
Лексичний аналіз реалізується за допомогою лексичного аналі-
затору (сканера). ЛА виділяє лексеми з трансльованого спільнота-
ня і замінює їх на символи мови. У процесі аналізу можуть віз-
ника помилки.
Лексеми можуть бути наступних класів:
- Роздільники;
- Арифметичні операції: + -/*;
- Ключові слова: for, begin, end, do, to, step;
- Ідентифікатори.
Синтаксичний аналізатор розпізнає синтаксис мови (струк-
туру).
Семантичний розбір - це програма або група програм,
займається розпізнаванням змісту повідомлення.
Синтез програми - програма, яка займається генерацією
програми на проміжному мовою.
Оптимізація програми - синтез програми у вигляді об'єктного
коду.
Формальне визначення Граматика:
Граматика - впорядкована четвірка G = (Vт, Vn, P, S), SC
Vn, безлічі термінальних Vt і нетермінальних Vn символів, грам-
автоматично правил P, початковий нетермінальний символ S або аксіо-
ма.
Правила P безпосередньо визначають процес виведення. Хом-
ський ввів 4 класу граматик:
1. Автоматна граматика: символи, які зустрічаються в ле-
вої частини правил називаються нетерміналамі, вони утворюють множес-
тво нетермінальних символів Vn; символи, які входять до множес-
тво Vт, називаються терміналами. Нетермінали і термінали разом
утворюють словник V.
V = Vn U Vт
U:: = N, U:: = WN
N C Vт, U, W C Vn
На базі автоматною граматики будуються кінцеві або Беско-
нечние автомати, що використовуються для сканування або сінтаксічес-
кого аналізу.
2. Контекстно-вільна граматика:
U:: = u; U C Vn, u C V
? ?
ланцюжок рядок складається з
вихідного термін. і нетерм.
тексту символів
(нетерм.)
Рядок u згортається в U незалежно від контексту.
3. Контекстно-залежні граматики:
x U y:: = xuy
U C Vn; x, y, u C V
4. Граматика без обмеження на правила виводу:
V:: = u u C V *, V C V *
Граматика, яка дозволяє розбирати арифметичні Вира-
вання:
:: =?
+?
-
:: =?
*?
/
:: = ()? i
i - ідентифікатор
Алфавіт мови - це деякий непорожній кінцеве безліч
елементів, які називаються символами.
Будь-яка кінцева послідовність символів мови називає-
ся ланцюжком.
Порожня ланцюжок - ланцюжок, що не містить жодного символу.
Її довжина дорівнює 0.
Безліч ланцюжків в алфавіті звичайно позначаються великими
літерами.
Х = mABCn
? ?
голова хвіст
xy - конкатенація ланцюжків x, y. х - голова, у - хвіст цепоч-
ки z = xy.
Твір АВ двох множин ланцюжків А і В:
AB = (xy? x C A, y C B)
Ступінь ланцюжка: x ^ 0 - "", x ^ N = x ^ (N-1) * x
V * - рефлексивно-Транзитивне замикання (ітерація).
V + - Транзитивне замикання (усічена ітерація).
Нескінченні множини:
V * = V ^ 0 U V ^ 1 U ... U V ^ N U ...
Формальне опис рядки:
V *= (z? z = "", z = xU), z, x CV *, UCV - будь-який символ з V.
Рядок x безпосередньо породжує y щодо P (x-> y),
коли існують рядка u, w, (можливо порожні) такі, що x = uVw,
y = uzw, V:: = z C P.
Рядок x породжує y щодо P (x => y), коли сущес-
твует послідовність рядків x0, x1, x2, ... xN, така, що
x = x0, y = xN, xI-1 -> xI (I = 1,2 ,..., N).
Мова - деякий безліч пропозицій:
Lg = (x? x C Vt *, S => x).
Породження (або згортання) строк Lg можна представити в
вигляді дерева. Термінальні символи не породжують нових символів,
нетермінальние - породжують. Інакше термінальні символи - це ті,
на яких утворюються конструкції Lg.
Cентенціальная форма: S => x, х C V +.
Пропозиція - ланцюжок термінальних символів, виведених з
аксіоми: (x? S => x, x C Vt *)
Нехай w = xuy - сентенціальная форма. Тоді u - фраза для U C
Vn, якщо S => xUy і U => u. Проста фраза - якщо U -> u.
Основа - найбільша ліва проста фраза. Існують леворекурсів-
Цінні та праворекурсівние граматики. Різні граматики можуть по-
народжувати один і той же L. Ми можемо генерувати синтаксично пра-
вільні повідомлення.
:: =
::=? ::=?? ...
::=?? ...
::=?? ...
Використовуючи функції породження строк щодо синтаксису
цієї мови, можна генерувати рядки, формально належать
цій мові, правильні синтаксично, але невірні семантично (
Приклад - Глоклая куздра бодланула куздренка).
G1 і G2 еквівалентні, якщо породжувані ними мови Lg1 і Lg2
рівні. Еквівалентні перетворення граматик можуть бути вико-
користувався для зручності вибору семантичних програм.
Однозначна граматика - якщо існує тільки одне дерево
виводу для кожної пропозиції Lg.
Розбір або синтаксичний аналіз сентенціальной форми - це
побудова виводу і, можливо, синтаксичного дерева для неї.
Існують методи як спадного, так і висхідного розбій-
ра (щодо руху по синтаксичному дереву).
Безпосередній висновок xUy -> xuy називають канонічним, ес-
Чи u C Vt *. Висновок w => v канонічний, якщо всі безпосередні
висновки у ньому канонічні.
Сентенціальная форма, що має канонічний висновок - канони-
чна сентенціальная форма.
Згортання будемо називати проходом чи аналізом. У далекій-
шем будемо вважати, що в процесі аналізу зчитування вхідного
тексту відбувається зліва направо, а згортання починається з тієї
самої лівої частини рядка, який може бути згорнута без додат-
Передачі подальшого аналізу тексту. Таке згортання будемо
називати канонічним.
Відносини
->, => - Символи відносин між ланцюжками.
Пара ланцюжків (c, d) належить відношенню R, якщо виконує-
ся cRd.
Відношення P включає R, якщо з (c, d) CR слід (c, d) C Р.
Ставлення, зворотне R - R ^ (-1).
Рефлексивне ставлення - при справедливості сRc.
Наприклад: i
ставлення.
Транзитивне відношення R - якщо виконується aRb, bRc => aRc.
Твір R, P: cRPd - якщо існує е, таке що cRe і ePd.
Ітерація R - (позначається R *): aR * b - коли a = b або aR + b.
Обмеження, що накладаються на граматику G:
- Немає правил виду U:: = U;
- S => xUy, U => t, t C Vt * - приведена граматика;
Приклад. G - мову арифметичних виразів.
S:: = E
E:: = T
E:: = E + T
T:: = P
T:: = T * P
P:: = (E)
P:: = I

ЛЕКЦІЯ 3
АНАЛІЗ контекстно-ВІЛЬНИХ МОВ
За допомогою матриці передування
Будемо розглядати канонічне згортання контекстно-сво-
вільних (КС) мов. Знаходження ефективних методів згортання -
одне з найважливіших завдань в теорії побудови трансляторів. В рас-
сматріваемих алгоритмах аналізу вхідного тексту, написаного на
КС-мовою, використовуються відносини передування між кожною па-
рій сусідніх символів рядка.
Розглянемо докладніше відносини передування: нехай Si і
Sj - символи мови L (Si, Sj З V). Якщо в деякій рядку мови
вони можуть бути записані поруч (... SiSj ...), то між ними можуть
існувати тільки три відносини.
1. У рядку ... SiSj ... згортається частину рядка починається
???? з символу Sj, тобто Sj - самий лівий символ згортає під-
рядка. Якщо при цьому Si не є останнім символом іншого
рядка згортає підрядка, то будемо говорити, що Si предшес-
твует Sj. Запишемо це умова у вигляді Si
2. У рядку ... SiSj ... символи Si і Sj входять в одну й ту
?????? ж згортаючу частина строкі.Етот факт запишемо у вигляді Si = Sj і
будемо говорити, що Si і Sj входять в один і той же згортання.
3. У рядку ... SiSj ... згортається частину рядка кінчається
???? символом Si, тобто Si - самий правий символ згортання частини
рядка. Ця умова запишемо у вигляді Si> Sj і будемо говорити, що
Sj слід за Si.
Відносини назвемо відносинами передування. Відно-
ності передування зазвичай записуються у вигляді матриці, стіл-
бци і рядки якої відповідають символам словника V. На Перес-
ченіі i-ої рядка і j-го стовпця записується ставлення предшес-
твованія між символами Si і Sj. Елементами матриці є
знаки або порожньо. Останній випадок означає, що символи
Si і Sj ні в одному рядку мови не можуть стояти поруч.
Надалі буде введено формальне визначення відносин
передування і дано алгоритм їх визначення.
Зараз же ми розглянемо алгоритм аналізу програми, розробити конструкцію
танний Віртом і Вебером.
Перевага цього алгоритму полягає в тому, що він сни-
мает додаткові обмеження на граматику мови, і допускає,
щоб на правилах граматики два нетермінальних символу стояли ря-
буд. Але і в цьому алгоритмі потрібно, щоб між кожною парою
символів мови існувало не більше одного відносини передують-
вання та в безлічі синтаксичних правил не було двох однаковий-
вих правих частин, тобто правил, у яких праві частини однакові,
а ліві - різні.
Алгоритм заснований на канонічному згортання, тобто на виокрем-
леніі самої лівої згортання частини рядка. Блок-схема алгоритмів-
ма показана на рис. 1 (@ - символ початкового (кінцевого) ограни-
чітеля вхідного аналізованого тексту; не входить в алфавіт мови).
?????????????????????????????????? ? ^
????????????? ?
??????????? ? i: = i +1? 2? ?
? i: = 1? 1? ? ??? ?
? ??? ? j: = i? ?
? k: = 2? ? ? ?
? ? ? R: = L? ?
? R: = @? ? i k? ?
? i? ? ? ?
??????????? ? k: = k +1? ?
? ????????????? ?
? ? ?
? ___?___?
? /? 3 ?????????????? ?
? /??? Так? Кінець? 10? ?
?/R одно @ ?????>? роботи???? ?
? i /? алгоріта? ?
?/?????????????? ?
? _______/?
? ? ?
? ? ?
????????????????????>?? ?
????????????????????>?? Ні?
? ___?____?
? /? 4?
? /??? Ні?
?/R> L __________________________? ? i k/
? ?/
? ________/ ? Так?
? ?
? ____?______?
? /? 5?
? /??? ????????????? ?/R = R ______? ? 6?
? j-1 j/Да? j: = j-1???
? /? ?
? ___________/ ????????????? ? ? Ні
? ?????????????????? ? ? ? 7?
? ? U ? ? j i?
? ?????????????????? ? ?
? ?
? ????????????????? ? ? ? 8?
? ? Перехід на???
? ? семантичні?
? ? підпрограми?
? ? ?
? ????????????????? ? ?
? ???????????????? ? ? i: = j? 9?
????????????????? R: = u???
? i?
???????????????? Рис. 1. Блок-схема алгоритму згортання
На початку аналізу рядки у верхню комірку магазину запису-
ється перший символ програми, тобто символ "@" (блок 1).
Потім знаходиться самий правий символ самої лівої згортає-
мій частини рядка (блок 4). Для цього по матриці передування,
яка складається заздалегідь, перевіряють відносини предшествова-
ня між символом, що знаходяться у верхній комірці магазину Ri, і
черговим вхідним символом рядка Lk. Якщо умова Ri> Lk не ви-
виконується, то черговий вхідний символ записується у верхівку
магазину (блок 2) і процес продовжується до тих пір, поки не бу-
дет виконана умова Ri> Lk, тобто не буде знайдений найбільший пра-
вий символ самої лівої згортання частини рядка.
Потім знаходиться самий лівий символ цієї системи згортання частини
рядка. Для цього перевіряється відношення передування між
кожною парою символів Rj-1 = Rj, записаних в магазині (блоки 5 і
6). Порушення умови Ri = Rj означає, що згортається частина
рядка скінчилася і послідовність символів Rj ... Ri є са-
Травень згортається ліва частина рядка.
У кожного нетермінального символу може бути кілька са-
екпортувати лівих і правих самих символів.
По таблиці, яка є в транслятор, в якій записані
правила згортання, проводиться згортання (блок 7) і управ-
ня передається на відповідну семантичну підпрограму.
Семантична підпрограма генерує програму на вихідному язи-
ке, відповідну даному синтаксичному правилом (блок 8).
Після того, як генерування відповідного шматка вихід-
ної програми закінчено, символи Rj ... Ri "виштовхуються" з мага-
зина і в його верхню клітинку записується символ u (блок 9).
Процес продовжується до тих пір, поки у верхній комірці мага-
зина не буде виявлений символ "@" (блок 3), що визначає кінець
програми.
Для аналізу помилок в алгоритм включені наступні блоки:
Блок 11 перевіряє, чи можуть символи Rj і Lk стояти в рядку
поруч. Якщо в матриці передування (i, j)-ий елемент порожній (знак
_), То символи Si і Sj стояти поряд не можуть і здійснюється пе-
реход до блоку 15. Інакше управління передається в блок 4.
Блок 12 перевіряє значення величини j: якщо j = 1, то має
проводитися порівняння з символом "@", що за алгоритмом аналізу
взагалі бути не може. У цьому випадку перехід до блоку 15. Якщо j не
дорівнює 1, то перехід до блоку 5.
Блок 13 перевіряє, чи є правило з правою частиною Rj ... Ri в
граматики мови. Якщо так, перехід до блоку 7, інакше - до блоку 15.
Блок 14 перевіряє, чи є правило Rj ... Ri. Якщо так, то ал-
горітм аналізу та згортання вхідного тексту закінчений (перехід до
блоку 10); інакше в тексті є помилка, через яку він не може
бути згорнутий (перехід до блоку 15).
Блок 15 виводить повідомлення про помилку і переходить до аналізу
наступного оператора.
Таким чином, складний аналіз вхідного тексту, написаного
на вхідному мовою, реалізується простим алгоритмом.
Вимога єдиності відносин передування викликають
кість необхідність перебудови граматики мови. Усунення цієї
неоднозначності іноді стає досить трудомістким завданням.
Мак-Кіма розробив алгоритм аналізу вхідного тексту, який не
пред'являє до граматики мови вимоги однозначності ставлення-
ний передування.
Для визначення меж звернутій рядки він використовує не
одну, а дві матриці: перша - для знаходження самого правого сім-
вола рядки - назвемо М1, і друге - для знаходження самого ліво-
го символу рядка - М2. У М1 заносяться наступні відносини перед-
ходи: <або =),> і> = <(останнє означає> і або
=, Або (> або =),
<І> (останнє означає <і або =, або>).
При пошуку самого правого символу безразліно, яке від ноше-
ня передування, = або => знаходить-
ся між двома аналізованим символами. Тому ці відносини в
відповідних матрицях не розрізняються. У тих випадках, коли
між парою символів существуеют відношення> =
ниць звернутій рядка необхідна додаткова інформація.
Ця інформація задається у вигляді логічних функцій трьох аргументів.
При пошуку самого правого символу звернутій рядки з
допомогою матриці М1 використовується функція
| Істина, якщо Si> Lk;
Р1 (Si-1, Si, Lk) =
| Брехня в іншому випадку.
Функція Р1 істинна, якщо в контексті Si-1SiLk символ Si яв-
ляется самим правим символом звернутій рядки ... Si-1Si.
Тут Si - символ, що зберігається у верхній комірці стека, Si-1-сім-
віл, що зберігається в наступну комірку стека і Lk - черговий сім-
віл аналізованого тексту.
Таким чином, кожній парі символів, у яких в М1 записи-
але ставлення> =
дозволяють аналізувати вже не пару, а трійку символів для оп-
ределеніе правил кордону звернутій рядка. Але ця трійка вже
повинна бути визначена так, щоб відповідь була однозначна.
Аналогічно при пошуку самого лівого символу звернутій
рядка за допомогою матриці М2 використовується функція
| Істина, якщо Sj-1
Р2 (Sj-1, Sj, Sj +1) =
| Брехня в іншому випадку.
B контексті Sj-1SiSj 1 символ Sj є самим лівим симво-
лом звернутій рядка SjSj +1 ... . Тут Sj-1, Sj, Sj 1 - сім-
воли, що зберігається в j-1, j та j +1 осередках стека.
Кожній парі символів, у яких в М2 записано ставлення,
ставиться у відповідність декілька функцій Р2, що дозволяють, як і
функції Р1, аналізувати не пару, а трійку символів. Але ця
трійка вже має бути визначена так, щоб відповідь була однозначна-
ний.
Блок-схема алгоритму аналізу вхідного тексту за допомогою мат-
РИЦ передування і функцій Р1 і Р2 наведена на рис. 2. Літери
i і j позначають номери осередків магазину, k - номер чергового сім-
вола вхідного ТЕКТу, Riі Rj-символи, що знаходяться в i-х і j-х
осередках магазину, Lk - k-й символ вхідного тексту. На початку ана-
лізу рядки у верхню комірку магазину записується перший символ
програми, тобто символ "@" (блок 1). Потім проводиться перевірка
на кінець програми (блок 3). Якщо Lk = @, то виконання програм-
ми закінчено і здійснюється перехід до блоку 14. Якщо Lk НЕ сов-
падає @, здійснюється перехід до блоку 4.
Проводиться пошук самого правого символу самої лівої гори до-
ють рядка. Для цього по М1 перевіряється відношення предшес-
твованія між символами Lk і Ri (блок 4). Якщо це відношення
одно
мій рядки, то робиться запис чергового символу в магазин
(блок 2).
Якщо між символами Ri і Lk є ставлення, то
блоком 5 перевіряється функція Р1 для двох верхніх символів магази-
на і чергового символу вхідного тексту. При значенні функції Р1
- Брехня (на рис. 2), це значення позначено Л, тобто якщо Ri не
є самим правим символом, здійснюється перехід до блоку 2.
Якщо значення Р1 - істина (І), тобто Ri - самий правий символ
рядки, то здійснюється перехід до блоку 6.
Блоком 6 починається пошук самого лівого символу згортає-
мій рядка; j присвоюється значення i. За М2 визначається відно-
шеніе між символами Rj-1 і Rj (блок 7). Якщо відношення є =>,
тобто Rj не є найбільш лівим символом згортає рядка, то
j: = j-1 (блок 8) і визначається відношення між наступною парою
символів. Якщо відношення є
символом, здійснюється перехід до блоку 10. Блок 10 введений для
того, щоб у блоці 11 згортання завжди відбувалося від j-го до
i-го елемента.
Якщо між символами Rj-1 і Rj відношення> =
ся функція Р2 для трьох символів, що знаходяться в j-1, j і j +1- й
осередках магазину. Якщо значення Р2 - Л (Rj не є самим ле-
Першим символом), здійснюється перехід до блоку 8; якщо значення Р2
- І (Rj є самим лівим символом), то здійснюється пере-
хід до блоку 11.
Блоки 11,12 і 13 виробляють згортання, перехід на генерал-
ючий підпрограму і запис знову отриманого нетермінального
символу U у верхню комірку магазину. Вони в точності відпо-
обхідних документів блокам 7, 8, 9 на рис. 1. На рис. 1. не показані блоки
аналізу синтаксичних помилок. Вони аналогічні відповідним
блокам на рис. 2.
Метод Мак-Кіма звільняє від обмеження однозначності
відносин передування, який накладається методом Вірта, але він
вимагає, природно, великих об'eмов пам'яті для запису матриць і
функції. У транслятор з однією з версій мови PL/1 для машин се-
рії IBM-360 М1 склала 90x45 елементів, М2-90x90. Кожен еле-
мент займає 2 біти. Число функцій Р1 і Р2 наближалося до 450.
ЛЕКЦІЯ 4
Побудови матриць передування
І ПЕРЕТВОРЕННЯ ГРАМАТИКА
Розглянемо алгоритм складання матриці передування. Для
цього дамо формальні визначення відносин передування і
безліч самих лівих і правих самих символів.
1. Для будь-якої впорядкованої пари символів (Si, Sj) Si = Sj
тоді і тільки тоді, коли суті