Синтаксичний аналіз. Лекція з Інші. Робота № 104

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

Синтаксичний аналіз

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

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

Рік:

2024

Тип роботи:

Лекція

Предмет:

Інші

Завантажити

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

Синтаксичний аналіз Контексно-вільні і вкорочувальні контексно-вільні граматики традиційно служать основою для синтаксичного аналізу при компіляції. Опис вхідної мови включає правила синтаксису, у відповідності з якими породжуються тексти вхідних програм. Кожному синтаксичному правилу у КВ-граматиці відповідає правило виводу (продукція) граматики. Тому послідовність правил виводу граматики, які застосовуються для породження тексту програми, визначає її структуру. Виводів деякого ланцюжка EMBED Equation.3 у граматиці G у загальному випадку може бути досить багато. Це пояснюється тим, що правила підстановки можуть застосовуватись до будь-якого входження нетермінального символу. Якщо деякий проміжний ланцюжок містить більше одного нетермінального символу, то різний порядок застосування одних і тих самих правил підстановки до цих символів дає в результаті різні виводи. При цьому заключний термінальний ланцюжок і синтаксична структура, яка визначається будь-яким з таких виводів, залишаються незмінними. Зазвичай розглядаються не всі можливі виводи, а лише так звані лівосторонні (або правосторонні) виводи. Означення. Вивід ланцюжка EMBED Equation.3 у КВ-граматиці називають G називають лівим (лівостороннім), якщо у цьому виводі кожна наступний проміжний ланцюжок утворюється шляхом заміни найлівішого нетермінального символу згідно з відповідним правилом виводу. Означення. Вивід ланцюжка EMBED Equation.3 у КВ-граматиці називають G називають правим (правостороннім), якщо у цьому виводі кожна наступний проміжний ланцюжок утворюється шляхом заміни найправішого нетермінального символу згідно з відповідним правилом виводу. Наприклад, для ланцюжка EMBED Equation.3 у граматиці EMBED Equation.3 Можна побудувати такі виводи: 1) EMBED Equation.3 2) EMBED Equation.3 3) EMBED Equation.3 Тут (2) − лівосторонній вивід; (3) − правосторонній вивід; (1) не є ні лівостороннім, ні правостороннім. Ці три виводи є еквівалентними у тому сенсі, що у одних і тих самих місцях сентенціальних форм застосовуються одні і ті ж самі правила виводу, але у різному порядку. Будувати синтаксичну структуру у вигляді кроків виводу не зовсім зручно, оскільки у такій формі явно не видно структуру програми. Більш наочним є зображення структури програми у вигляді дерева виводу (синтаксичного дерева). Під деревом виводу (синтаксичним деревом) у граматиці G будемо розуміти скінченний зв'язний орієнтований граф, що має такі властивості: У нього є одна вершина, у яку не входить жодна дуга; цю вершину будемо називати коренем дерева, корінь дерева відповідає аксіомі граматики. У кожну з його інших вершин входить лише одна дуга; вершини, які не мають вихідних дуг, називаються заключними вершинами дерева або листям, у КВ-граматиці їм відповідають термінальні символи граматики ( а також порожні ланцюжки у ВКВ-граматиці). Проміжним (не заключним) вершинам відповідають нетермінальні символи граматики. Граф не містить контурів. Кожна вершина дерева виводу у КВ-граматиці позначена символом 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 побудовано дерево 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 і відповідних дуг; 3) дерево EMBED Equation.3 − шукане дерево для виводу EMBED Equation.3 . Якщо ланцюжок EMBED Equation.3 термінальний, то ні подальший вивід, ні добудова дерева неможливі. S R + S R + S R a b c На малюнку показано дерево виводу ланцюжка EMBED Equation.3 для граматики з попереднього прикладу. Лівосторонньому виводу ланцюжка відповідає обхід дерева виводу згори донизу і зліва направо. Аналогічно визначається і правосторонній вивід, тільки орієнтація шляху обходу дерева − згори донизу і справа наліво. Означення. КВ-граматика G називається неоднозначною, якщо існує хоча б один ланцюжок EMBED Equation.3 , для якого існує два чи більше різних дерев виводу. Це твердження рівносильно тому, що ланцюжок EMBED Equation.3 має два чи більше лівосторонніх (правосторонніх) виводів. Означення. КВ-граматика G називається однозначною, якщо для кожного ланцюжка EMBED Equation.3 існує тільки одне дерево виводу. Зауважимо, що одну і ту саму мову можна породити за допомогою багатьох породжувальних граматик. Означення. Мова називається неоднозначною, якщо вона не може бути породжена жодною однозначною граматикою. Приклад неоднозначної граматики: EMBED Equation.3 де EMBED Equation.3 У цій граматиці для ланцюжка EMBED Equation.3 можна побудувати такі дерева виводу: SHAPE \* MERGEFORMAT S b S S EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 b S a a EMBED Equation.3 EMBED Equation.3 SHAPE \* MERGEFORMAT S b S S EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 b S a a 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 Відповідне дерево виводу матиме вигляд SHAPE \* MERGEFORMAT S b S S EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 b Q a a EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 Якщо граматика використовується для опису мови програмування, вона повинна бути однозначною. Проблема, чи породжує дана КВ-граматика однозначну мову (тобто, чи існує еквівалентна до неї однозначна КС-граматика) є алгоритмічно нерозв'язною. Але можна вказати деякі види правил виводу, які приводять до неоднозначності. (1) EMBED Equation.3 (2) EMBED Equation.3 (3) EMBED Equation.3 (4) 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 і граматики G побудувати трикутник і заповнити його внутрішню частину деревом виводу (деревом розбору). S a1 a2 . . . an Взагалі кажучи, не має значення, у який спосіб буде заповнюватись внутрішня частина трикутника. Розглянемо три способи такого заповнення. S S S a1 a2 . . . an a1 a2 . . . an a1 a2 . . . an а) б) с) Мал.. Основні способи побудови синтаксичного аналізатора. Стратегія синтаксичного розбору, зображена на мал..а), називається розбором згори донизу (низхідний розбір). Оскільки реальні програми можуть мати досить великий обсяг, тому на практиці застосовуються методи заповнення трикутника, використовуючи частини речення (програми). Очевидний спосіб розбору речення частинами − перебирати слова по одному зліва направо у їх природній послідовності. При цьому використовуються дві основні стратегії заповнення трикутника розбору: згори донизу і зліва направо (мал.. б) або знизу догори і зліва направо (мал.с). Відзначимо можливі проблеми проведення розбору: 1. Припустимо, що при проведенні низхідного розбору потрібно замінити найлівіший нетермінальний символ EMBED Equation.3 , при цьому є EMBED Equation.3 правил EMBED Equation.3 Як дізнатись, яким ланцюжком замінити EMBED Equation.3 ? 2. При висхідному розборі на кожному кроці редукується основа. Як знайти основу і той нетермінальний символ, до якого вона зводиться? Відповіді на ці питання не завжди очевидні. Одним із підходів є вибір одного з можливих варіантів навмання. Якщо пізніше виявиться помилка («глухий кут»), тоді потрібно повернутись і спробувати інший варіант. Цей процес називається поверненням. Очевидно, що велика кількість повернень може спричинити велику тривалість аналізу. На нинішній час розроблені і використовуються на практиці багато алгоритмів розбору. Вибір алгоритму синтаксичного розбору для конкретної КВ-граматики, у загальному випадку, обумовлює швидкість його виконання. Кожен з алгоритмів використовує ту чи іншу стратегію розбору і у більшості випадків накладає різні обмеження на правила КВ-граматик. Тобто можливі певні еквіваленті перетворення заданої граматики для проведення синтаксичного аналізу тим чи іншим методом. Ці перетворення у кінцевому рахунку забезпечують однозначність, детермінованість граматичного розбору; усувають зайві кроки у дереві розбору; прості емпіричні критерії вибору правила виводу з множини альтернативних.

Лекція Інші

01.01.1970 03:01-

Коментарі

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

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

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

поділитись