Висхідний синтаксичний аналіз. Лекція з Інші. Робота № 105

Перехід до торгівельного партнера Binance

Висхідний синтаксичний аналіз

Інформація про навчальний заклад

ВУЗ:

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

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

Інформація про роботу

Рік:

2024

Тип роботи:

Лекція

Предмет:

Інші

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Висхідний синтаксичний аналіз. Загальні принципи висхідного аналізу При такій стратегії дерево синтаксичного аналізу будується, рухаючись від листя (вхідної програми, яка розглядається як рядок символів) до кореня дерева (аксіоми граматики). Аналізатор (розпізнавач) шукає частину рядка, яку можна звести до нетермінального символу. Таку частину рядка називають фразою. У більшості висхідних розпізнавачів відшукується найлівіша фраза, що безпосередньо зводиться до нетермінального символу (така фраза називається основою). Основа заміняється нетермінальним символом. У отриманому рядку знову відшукується основа, заміняється нетермінальним символом і т.д. Процес продовжується або до отримання початкового символу (аксіоми), або до встановлення неможливості зведення рядка до початкового символу. Послідовність проміжних рядків, яка закінчується початковим символом, утворює розбір. Якщо рядок не зводиться до початкового символу, то розбір не існує, і вхідна програма синтаксично некоректна. Приклад 1. Нехай задано граматику EMBED Equation.3 і вхідний ланцюжок EMBED Equation.3 . Правосторонній вивід цього ланцюжка у заданій граматиці має вигляд EMBED Equation.3 Відстеження отриманого правого виводу у зворотньому порядку можна інтерпретувати як побудову дерева виводу. E E R R * i i R i E E R R * i i R i E E R R * i i R i E E R R * i i R i + E E R R * i i R i E E R R * i i R i i+ i* i R + i* i E + i* i E + R* i E + R E Кожен підкреслений підланцюжок є основою ланцюжка, в якому він зустрічається, тобто для вхідного ланцюжка основою є і . Оскільки на останньому кроці отримано аксіому граматики Е, то ланцюжок синтакично правильний. Приклад 2. Для рядка і+ основою є і. Після заміни і на R одержимо рядок R + i* , основою якого є R, наступний рядок − E + i*, далі − рядок E + R*. Якщо припустити, що E + R −основа, одержимо рядок E*, а якщо R −основа, то рядок E + Е*. Подальше зведення неможливе, розбору немає, рядок синтаксично некоректний. В загальному випадку висхідний розпізнавач як і низхідний, може робити «помилкові» редукції, які заводять у «глухий кут». Приклад 3. Для рядка і*і заміна і на R, а R на Е дає рядок Е * і, який зводиться до рядка Е * R, а потім до незвідного рядка Е * Е . Тут потрібно повернутись до рядка R*і і виконати редукцію R*і до R , яка дає рядок R, що зводиться до початкового символу. Для того, щоб при застосуванні конкретного методу синтаксичного аналізу розпізнавач працював в одному напрямку (зліва направо) без «глухих кутів» і повернень, граматика повинна мати певні властивості. Різні методи аналізу висувають різні вимоги до граматик. Іноді застосування конкретного методу можливе лише після суттєвої зміни граматики. При цьому потрібно слідкувати, щоб задана і змінена граматика були еквівалентні. На кожному кроці процесу задачею лівостороннього висхідного розпізнавача є визначення основи. Різні методи висхідного аналізу як раз і відрізняються способом відшукання основи або іншої безпосередньо звідної фрази, що виконує ту ж саму роль, що й основа. Найбільш універсальним методом є LR(k)-метод. Термін LR(k) означає, що детермінований синтаксичний аналізатор читає вхідний ланцюжок зліва (Left), і видає її правий (Right) аналіз на основі вже прочитаної частини вхідного ланцюжка (лівий контекст) і фіксованого числа попередньо проглянутих символів (максимум k). Взагалі, будь-яка з однозначних КВ-граматик може розглядатись як LR(k)-граматика, при цьому k=0, 1, …. Але на практиці LR(k)-метод не став широко вживаним через свою громіздкість. До того ж було доведено, що якщо для опису процесу породження речень деякої мови побудовано КВ-граматику, яка є LR(k)-граматикою, то така сама мова може породжуватись і LR(1)-граматикою (але, на жаль, немає загальних рекомендацій щодо побудови такої граматики). Іншими словами, до всіх КВ-мов, речення яких можна розбирати детерміновано, можна застосувати LR(1)-метод, тобто у випадку висхідного розбору збільшення кількості попередньо проглянутих символів (k) не дає можливості проведення детермінованого аналізу для більшої кількості мов, на відміну від LL-методів розбору ( LL(k)-метод дає можливість проведення детермінованого розбору для більшої кількості мов, ніж LL(1)-метод). Виявилося також, що для опису синтаксису мов програмування буває достатньо не лише LR(1)-граматик, а навіть так званих SLR(1)-граматик. SLR(1)-граматика − проста (simple) LR(1)-граматика, яка відрізняється від LR(1)-граматики тим, що для визначення кінця основи у такій граматиці використовується тільки один проглянутий символ (як і у LR(1)), але до уваги не береться лівий контекст, тобто не враховується вже оброблена частина ланцюжка, у той час як при застосуванні LR(1)-методу у загальному випадку лівий контекст враховується і навіть грає визначальну роль. Існують і інші методи, які можна застосувати до вужчих класів КВ-граматик. Найвідоміший із них − метод передування, який можна застосувати до граматик простого передування. З позицій універсальності застосування різних методів до побудови детермінованого висхідного аналізатора для різних класів КВ-граматик, ці граматики утворюють ієрархію граматик, яка зображена на малюнку. Не існує загальної процедури, яка могла б визначити, до якого класу відноситься та чи інша КВ-граматика. Не можна, наприклад, визначити, чи існує таке значення k, для якого задана граматика буде LR(k)-граматикою. Але можна визначити, чи є задана граматика LR(k)-граматикою для конкретного значення k. Можна також з'ясувати, чи є задана КВ-граматика граматикою простого передування. З'ясувати такі речі можна лише шляхом застосування конкретного методу побудови синтаксичного аналізатора. Зауважимо, що побудова синтаксичних аналізаторів для граматик нижчого рівня є простішою, ніж для LR(1)-граматик. Тому на практиці зазвичай вибирають простіший метод і лише при неможливості аналізу цим методом заданої мови переходять до більш універсального методу. Детерміновані однозначні КВ-мови LR(1) LALR(1) SLR(1) LR(0) LL(1) З слабким передуванням З простим передуванням Метод передування Відношення передування Н.Вірт і Г.Вебер( Wirth N., Weber H.), узагальнюючи ранні роботи з синтаксичного аналізу, у 1966р. запропонували метод передування, який використовує поняття відношення передування. Нехай EMBED Equation.3 − деяка КВ-граматика, EMBED Equation.3 , EMBED Equation.3 , і нехай у процесі породження речень мови EMBED Equation.3 на деякому кроці отримано сентенціальну форму EMBED Equation.3 , тобто символи EMBED Equation.3 стоять поряд у сентенціальній формі. Їх сусідство можна охарактеризувати за допомогою відношень спеціального вигляду, які відображають одну з трьох можливих ситуацій, які виникають у процесі виводу. 1. EMBED Equation.3 , якщо EMBED Equation.3 є найлівішим (першим) символом деякої основи. 2. EMBED Equation.3 , якщо EMBED Equation.3 є найправішим (останнім) символом деякої основи. 3. EMBED Equation.3 , якщо обидва символи належать одній і тій самій основі. Ці відношення називаються відношеннями передування (precedence). Ні одне з цих відношень не є симетричним. Якщо для кожної впорядкованої пари символів граматики існує не більше одного відношення передування, то на кожному кроці синтаксичного аналізу можна легко виділити основу. Основою є найлівіша група символів рядка EMBED Equation.3 , що пов'язана відношеннями передування вигляду EMBED Equation.3 Приклад. Нехай для будь-якої впорядкованої пари термінальних і нетермінальних символів деякої граматики відомі відношення передування. Дано вхідний рядок з відношенням передування: EMBED Equation.3 Тоді символи EMBED Equation.3 утворюють основу. Отже, за означенням основи, повинно існувати правило вигляду EMBED Equation.3 . Заміняючи основу нетермінальним символом EMBED Equation.3 , приходимо до рядка EMBED Equation.3 . Нехай EMBED Equation.3 . Тоді основою буде EMBED Equation.3 . Якщо існує правило вигляду EMBED Equation.3 , то результатом редукції буде рядок EMBED Equation.3 . Якщо при цьому існує правило EMBED Equation.3 і EMBED Equation.3 − аксіома граматики, то аналіз завершено. Якщо на деякому кроці виявилось, що між символами немає жодного відношення передування, то це означає, що такі символи не можуть знаходитись поряд у жодному правильному ланцюжку. Ланцюжок буде неправильним і у тому випадку, якщо у результаті редукції не вдалось прийти до аксіоми граматики. Граматика простого передування (precedence grammar) Граматикою простого передування (precedence grammar) називається така граматика класу 2 за Хомським, у якій: для кожної впорядкованої пари символів EMBED Equation.3 виконується не більш, ніж одне з трьох відношень передування, що визначаються таким чином: А. EMBED Equation.3 , тоді і тільки тоді, коли існує правило EMBED Equation.3 , EMBED Equation.3 ; Б. EMBED Equation.3 , тоді і тільки тоді, коли існує правило EMBED Equation.3 і вивід EMBED Equation.3 , EMBED Equation.3 ; В. EMBED Equation.3 , тоді і тільки тоді, якщо існує правило EMBED Equation.3 і вивід EMBED Equation.3 , або правило EMBED Equation.3 і виводи EMBED Equation.3 , EMBED Equation.3 , EMBED Equation.3 . різні породжуючі правила мають різні праві частини. Перша умова забезпечує єдиність відношення передування для кожної впорядкованої пари символів в рядку і тим самим забезпечує правильність знаходження основи. Якщо між деякими двома символами немає відношення передування, то це означає, що вони не можуть знаходитись поряд ні в одному елементі розбору синтаксично правильної сентенціальної форми. Друга умова забезпечує однозначність редукцій. Правила знаходження відношень передування. Матриця передування Відношення передування можна знайти безпосередньо, користуючись означеннями, наведеними вище. Але зручніше запровадити додаткові означення. Нехай L(U) − множина символів, з яких можуть починатись ланцюжки, що виводяться з нетермінального символа U. Формально множина L(U) визначається у такий спосіб EMBED Equation.3 або EMBED Equation.3 Аналогічно, R(U) − множина символів, якими можуть закінчуватись ланцюжки, що виводяться з нетермінального символа U. Формально множина R(U) визначається у такий спосіб EMBED Equation.3 або EMBED Equation.3 Використовуючи множини L(U), R(U), пункти означення грамматики простого передування можна записати в дещо іншій формі: Б. EMBED Equation.3 , тоді і тільки тоді, коли існує правило EMBED Equation.3 і EMBED Equation.3 , EMBED Equation.3 ; В. EMBED Equation.3 , тоді і тільки тоді, якщо існує правило EMBED Equation.3 і EMBED Equation.3 або правило EMBED Equation.3 і EMBED Equation.3 , EMBED Equation.3 , EMBED Equation.3 . Приклад. Нехай правила граматики G мають вигляд: EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 Знайти відношення передування. Спочатку побудуємо множини L і R для всіх нетермінальних символів граматики. При цьому для кожного нетермінального символу U у множину R(U) записуємо всі символи, з яких починаються праві частини правил виводу для цього нетермінального символу, а у R(U) − символи, якими закінчуються відповідні праві частини. Проглядаємо отримані множини. Якщо у множині L(U) є нетермінальні символи EMBED Equation.3 , то у L(U) дописуємо всі символи, які входять у множину EMBED Equation.3 . Аналогічно добудовуємо множини R(U). Цей крок повторюємо до того часу, доки у множинах L(U) , R(U) перестануть з'являтись нові символи. Побудовані множини використаємо для знаходження відношень передування, які зручно записати у вигляді квадратної матриці передування. Розмір такої матриці − EMBED Equation.3 , де EMBED Equation.3 − кількість символів у словнику граматики EMBED Equation.3 . У матриці передбачено стовпець для маркера кінця рядка ├ і рядок для маркера дна стеку (початку рядка) ┤. Ці маркери не є символами граматики. Будемо вважати, що ┤ EMBED Equation.3 і EMBED Equation.3 ├ , де EMBED Equation.3 − будь-який символ граматики. Аналізуючи дані у матриці передування, доходимо висновку, що дана граматика не є граматикою простого передування. У тому випадку, коли між двома символами алфавіту існує більше одного відношення передування, граматика не є граматикою простого передування, і метод простого передування застосувати не можна. Але у деяких випадках можна побудувати еквівалентну заданій граматику простого передування. Так, у тому випадку, коли неоднозначність відношень обумовлена наявністю у правилах виводу безпосередньої лівосторонньої або правосторонньої рекурсії, можна застосувати спосіб стратифікації. Якщо серед правил граматики є правила вигляду EMBED Equation.3 , EMBED Equation.3 , і EMBED Equation.3 , EMBED Equation.3 , то згідно з наведеними вище правилами EMBED Equation.3 і EMBED Equation.3 . Розглянемо граматику з правилами EMBED Equation.3 , EMBED Equation.3 , EMBED Equation.3 , EMBED Equation.3 , EMBED Equation.3 Тоді EMBED Equation.3 і EMBED Equation.3 , отже неоднозначність відношень усунуто. Аналогічно можна діяти і у випадку правосторонньої рекурсії. Повертаючись до розглянутого вище прикладу, змінимо правила граматики у такий спосіб: EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 Тоді а матриця передування має вигляд Розпізнавач Основну ідею алгоритму розбору, що ґрунтується на відношеннях передування, можна описати так. Символи вхідного рядка почергово переписуються в стек до того часу, поки між символом у вершині стеку (позначимо його EMBED Equation.3 ) і черговим символом вхідного рядка (позначимо його EMBED Equation.3 ) не з’явиться відношення EMBED Equation.3 , тобто виявиться, що EMBED Equation.3 . Тоді стек проглядається у напрямку від вершини до початку до того часу, поки між двома черговими символами EMBED Equation.3 і EMBED Equation.3 не з’явиться відношення EMBED Equation.3 ,тобто EMBED Equation.3 . Частина ланцюжка від символу EMBED Equation.3 до символу EMBED Equation.3 − основа. Тепер серед правил граматики шукаємо правило вигляду EMBED Equation.3 і, якщо потрібно, викликається семантична програма для обробки рядка EMBED Equation.3 . Після цього у стеку фрагмент EMBED Equation.3 заміняється символом EMBED Equation.3 , і описаний вище процес заповнення стеку символами вхідного рядка продовжується (див. малюнок). При цьому вважаємо, що кожна сентенціальна форма міститься між символами маркера дна стеку (початку рядка) ┤і маркера кінця рядка ├ До редукції: Стек Вхідний рядок (необроблена частина) EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 ┤ Після редукції: Стек Вхідний рядок (необроблена частина) ┤ EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 Розбір закінчується, коли рядок зведено до аксіоми граматики (рядок правильний) або виявлено неможливість такого зведення (рядок неправильний). Описаний алгоритм простий і забезпечує повний синтаксичний контроль вхідної програми. Проілюструємо описаний алгоритм на прикладі розбору ланцюжка EMBED Equation.3

Лекція Інші

01.01.1970 03:01-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись