Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Нисхідний синтаксичний аналіз
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лекція
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
Низхідний синтаксичний аналіз
Загальна характеристика і проблеми низхідного аналізу
При низхідному синтаксичному аналізі вивід для заданого вхідного ланцюжка будують, виходячи з початкового символу граматики (аксіоми), тобто побудова дерева синтаксичного розбору починається з кореня і розгортається до листя. Для цього аналізуються декілька перших символів вхідного ланцюжка, і приймається рішення, яке саме правило для аксіоми варто застосувати, а після цього робиться спроба розпізнати елементи правої частини цього правила, визначаючи їх як проміжні цілі (підцілі).
Нехай вхідний рядок має вигляд 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 .
У загальному випадку, у процесі низхідного аналізу, виникають такі проблеми.
1. Ціль (підціль) визначається, використовуючи правило з лівою рекурсією.
Якщо EMBED Equation.3 − ціль, і перше правило для EMBED Equation.3 має вигляд EMBED Equation.3 , то у відповідності з даним методом буде сформовано підціль EMBED Equation.3 . У свою чергу, допоміжною підціллю знову буде EMBED Equation.3 і т.д.
Таким чином, для застосування методу низхідного аналізу, потрібно буде перетворити граматику, щоб усунути ліву рекурсію.
2. Якщо для нетермінальних символів є декілька альтернативних правил виводу
EMBED Equation.3
Як вгадати, яким з ланцюжків EMBED Equation.3 потрібно замінити нетермінальний символ EMBED Equation.3 ? Загального методу немає. Є деякі рекомендації.
Впорядкувати правила так, щоб найбільш ймовірні альтернативи вибирались першими. Зазвичай першою вибирають найдовшу альтернативу. Але у тому випадку, коли вхідний рядок містить помилку, все одно доведеться перебрати всі альтернативи.
Заглядати вперед на 1-2 символи, що дозволяє точніше вибирати альтернативу. Це робиться за допомогою функції
EMBED Equation.3
Використовуючи такі функції, можна для всіх EMBED Equation.3 побудувати EMBED Equation.3 . Тоді порівнюючи префікс залишку вхідного ланцюжка з елементами множини EMBED Equation.3 можна швидше, по-перше, і точніше, по-друге, вийти на прийнятну альтернативу.
Облік використаних у даних обставинах альтернатив. Якщо альтернативи мають однакові префікси і їх неприйнятність фіксується у межах цих префіксів, то можна пропускати цілу групу альтернатив з відповідними префіксами.
3. Проблема локалізації помилок. Компілятор, крім вказівки про наявність помилки, повинен локалізувати місце помилки. Помилка виявляється, коли всі можливі правила вичерпані. Для локалізації помилки всі альтернативи підходять однаковою мірою, тому у граматику доцільно вставити правила, що реагують на помилки (описати неправильні конструкції) і при розпізнаванні такого правила видавати сигнал про помилку або намагатись виправити її.
Детермінований синтаксичний низхідний аналіз
Існує цілий клас КВ-граматик, які допускають детермінований низхідний розбір, тобто розбір без повернень. Окрім високої швидкості розбору, детерміновані методи мають перевагу у компіляторах, де розбір іде паралельно з побудовою об'єктної програми. У таких компіляторах у випадку повернення доводиться відміняти виконані дії з побудови об'єктної програми, що обходиться досить дорого. Хоча підклас мов, які допускають детермінований розбір, вужчий за клас КВ-мов, виявилось, що більшість мов програмування допускають детермінований розбір.
Означення. КВ-граматика G називається LL(K)-граматикою, якщо для будь-якого ланцюжка EMBED Equation.3 і перших К термінальних символів, що виводяться з ланцюжка EMBED Equation.3 , існує не більше одної підстановки , яку можна застосувати до нетерміналу А, щоб одержати лівий вивід ланцюжка, який починається з EMBED Equation.3 і продовжується К термінальними символами.
Дві букви LL у LL(K) означають, що розбір ланцюжка проводиться зліва направо і використовуються лівосторонні виводи, а цифра К − що варіанти породжуючих правил вибираються за допомогою К попередньо проглянутих символів.
LL(1)-граматика є узагальненням S-граматики.
Означення. КВ-граматика G називається S -граматикою, якщо виконуються такі умови:
Права частина кожного правила починається з термінального символу.
Якщо два і більше правил мають однакові ліві частини, то їх праві частини повинні починатись з різних термінальних символів.
Метод рекурсивного спуску
Приклад. Задано граматику
EMBED Equation.3
Перевірити, чи належить ланцюжок caba! мові L(G).
S S
A B
EMBED Equation.3 EMBED Equation.3
c a b a ! c a b a !
S S
A B A B
A EMBED Equation.3 A EMBED Equation.3
c a b a ! c a b a !
S S
A B A B
EMBED Equation.3 A
A A A
c a b a ! c a b a !
Метод рекурсивного спуску (РС-метод) реалізується так: для кожного нетермінального символу граматики створюється окрема процедура, задача якої − із вказаного місця вхідного ланцюжка знайти підланцюжок, який виводиться з цього нетермінального символу. Якщо такий підланцюжок знайти не вдалось, формується ознака помилки і відбувається повернення у точку виклику (або викликається процедура обробки помилки, і розбір зупиняється). Якщо потрібний підланцюжок знайдено, робота процедури вважається нормально завершеною, і відбувається повернення у точку виклику. Тіло кожної такої процедури пишеться безпосередньо за правилами виводу відповідного нетермінального символу: для правої частини кожного правила відбувається пошук під ланцюжка, який виводиться з цієї правої частини. При цьому термінали розпізнаються самою процедурою, а нетермінали − окремими відповідними процедурами.
Програма для розбору ланцюжків мови, яка породжується наведеною вище граматикою, може бути такою.
#include <stdio.h>
char sym;
int f;
void A( );
void B( );
void S( )
{ A(); B();
if (sym!=’!’ ) f=0;}
void A( )
{ switch(sym){
case ‘a’: sym=getchar(); break;
case ‘c’: sym=getchar(); A(); break;
default: f=0; … }
}
void B( )
{ switch(sym){
case ‘d’: sym=getchar(); break;
case ‘b’: sym=getchar(); A(); break;
default: f=0; … }
}
main( )
{sym=getchar(); f=1; S();
if ((f==1)&&(getchar()==’\n’)) puts (“OK!”); else puts (“ERROR!”); }
РС-метод легко застосувати, якщо кожне правило граматики має вигляд;
А) або EMBED Equation.3 , де EMBED Equation.3 , і це єдине правило виводу для цього не терміналу;
Б) або EMBED Equation.3 , де EMBED Equation.3 , тобто якщо для нетермінала А правил виводу декілька, то всі вони повинні починатись з терміналів, причому всі ці термінали повинні бути різними.
Постає питання: якщо граматика не задовольняє наведені умови, то чи існує еквівалентна КВ-граматика, для якої можна застосувати метод рекурсивного спуску? На жаль, немає алгоритму, який давав би відповідь на це питання, тобто це алгоритмічно нерозв'язна проблема.
Зауважимо, що наведені умови є достатніми, але не є необхідними.
При описі синтаксису мов програмування часто зустрічаються правила, що описують послідовність однотипних конструкцій, які відокремлені одна від одної деяким знаком-розділювачем (наприклад, список ідентифікаторів при описі змінних, список параметрів при описі процедур тощо). Загальний вигляд цих правил такий:
EMBED Equation.3 ( або у скороченій формі EMBED Equation.3 ).
Формально тут не виконуються умови застосовності методу рекурсивного спуску, оскільки дві альтернативи починаються однаковими нетермінальними символами. Але якщо прийняти рішення, що у таких випадках ми будемо вибирати найдовший можливий ланцюжок, то розбір стає детермінованим.
Приклад. Нехай серед правил виводу у граматиці є таке правило: EMBED Equation.3 . Перепишемо його у вигляді: EMBED Equation.3 . Тоді відповідна процедура буде такою
void L( )
{ if (sym==’i’) {
while ( (sym=getchar() )==’,’)
(sym= getchar() ; if (sym!=’i’) {f=0; ………; break;} }
else {f=0; ………;} } }
При цьому важливо, щоб частина ланцюжка, яка слідує за підланцюжком, що виводиться з EMBED Equation.3 , не починалась з того самого символу, що й EMBED Equation.3 ( у даному прикладі це кома), інакше процедура EMBED Equation.3 намагатиметься зчитати частину вхідного ланцюжка, що не виводиться з EMBED Equation.3 .
Приклад. Нехай правила граматики мають вигляд
EMBED Equation.3
Якщо для цієї граматики написати програму для проведення аналізу РС-методом згідно з наведеними рекомендаціями, то ланцюжок EMBED Equation.3 буде визнано помилковим.
Зауважимо, що у мовах програмування такі проблеми не виникають. Для розглянутого прикладу можна було замінити входження нетерміналу В його правилом виводу: EMBED Equation.3
void L( )
{ if (sym==’i’) {
while ( (sym=getchar() )==’,’)
(sym= getchar() ; if (sym!=’i’) break; }
else {f=0; ………;} } }
void S( ) { sym=getchar( ); L( );
if ( (sym!=’b’)|| (getchar() !=’;’)){f=0; ………;} }
Якщо граматика не задовольняє наведені умови щодо застосовності РС-методу, можна спробувати замінити її еквівалентною граматикою з потрібними властивостями.
А) безпосередньо застосувати РС-метод не можна у випадку, коли у граматиці є нетермінальні символи, для яких праві частини правил виводу починаються з однакових термінальних символів, тобто мають вигляд
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 .
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора