НОУ ІНТУІТ, Лекція,Опис синтаксису

2.3. Використання БНФ

Все, що потрібно знати про БНФ, уже сказано. Для ефективного використання цього методу опису мов розглянемо деякі прагматичні спостереження.

Застосування БНФ

БНФ опис дозволяє:

• зрозуміти синтаксис існуючих мов (як мов програмування);
• визначити синтаксис мови, яку потрібно спроектувати;
• написати синтаксичний аналізатор - парсер (parser).

Друге застосування не таке фантастичне, як здається з першого погляду. Можливо, вам ще не скоро доведеться проектувати мову загальноцільового застосування - суперник таких мов, як C #, Java або Eiffel. Але програмістам досить часто доводиться мати справу з "малими" мовами. Щоразу, коли доводиться обробляти дані складного формату, ці дані можна розглядати як пропозиції деякої мови, синтаксис якої зручно задати, використовуючи БНФ. Вправи цієї лекції вимагатимуть від вас виконання такої роботи.

Третій додаток (побудова аналізатора) корисно при написаннікомпіляторівта інших інструментів, призначених для обробки програм, а в більш загальному випадку - структурованих текстів. Одним з перших завдань для таких інструментів є реконструкція структури тексту у форміабстрактного синтаксичного дерева. Це робота аналізатора, як ми побачимо у наступній лекції. Будь-якому аналізатору необхідний формальний опис синтаксису мови – він може отримати його з БНФ-граматики.

Мова, що народжується граматикою

БНФ-граматику можна розглядати двома доповнюючими способами, що випливають із двох пропозицій у визначенні поняття граматики.

• Цемеханізм розпізнавання, що дозволяє визначити,чи є деяка послідовність з термінальних зразків та обмежувачів фразою нашої мови, і, якщо це так, відновити її синтаксичну структуру. Ця думка на граматику корисна при написанні аналізатора.
• Граматика є також породжувальним механізмом: застосовуючи її правила, можна згенерувати всі фрази мови, одну за одною.

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

Ці чотири механізми породження речень застосовуйте доти, доки хоч одне з них буде застосовним. Зрештою, будуть породжені всі пропозиції мови. Процес цей зазвичай не завершується, оскільки, як ми бачили, мови, які становлять інтерес на практиці, є нескінченними.

Рекурсивні граматики

Останнє спостереження може спричинити деяке побоювання. Що, якщо, застосовуючи процес до А, ми повинні будемо застосувати його до В, а це призведе до того, що ми знову зустрінемо А? Продукція для складового оператора є добрим прикладом:

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

Час тесту!

Через рекурсію граматика може здатися безглуздою. Алебудемо прагматиками і запитаємо себе, чи не можна використовувати граматику для генерування зразків, застосовуючи описаний вище процес. Зауважимо, що в продукції для Game одна з гілок, stop, є термінальною, що дозволяє згенерувати першу пропозицію (зразок Game):

Але тепер ми можемо використовувати отриману інформацію для генерування зразків Head_start та Tail_start, що визначаються через Game. Відповідні продукції скажуть нам, що heads stop є зразком Head_start, а tails stop – зразком Tail_start. Скористаємося цими зразками в продукції для Game, отримаємо два нові зразки:

• heads stop
• tails stop

Отримавши ці зразки, і застосовуючи той самий процес, можна отримати таку безліч зразків:

• heads heads stop
• heads tails stop
• tails heads stop
• tails tails stop

Цей процес подвоєння зразків можна продовжувати. Стає зрозумілим і загальна конструкція зразка Game: він представляє послідовність "голів" і "хвостів", що йдуть у довільному порядку, вона закінчується терміналом stop. Неважко довести, що така послідовність є зразком. Трохи складніший доказ того, що зразків іншого виду для Game немає.

Дуже проста мова цієї граматики з початковим нетерміналом Game можна розглядати як всі послідовності можливих наслідків кидання монети при грі в "орел або решка". Послідовність закінчується тоді, коли гравець кричитьstop. Цю мову можна описати і не рекурсивною граматикою:

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

Застосовуючи для створення мови продукційні правила, мивикористовували стратегію, в якій термінали переважно нетерміналів. Вибравши іншу стратегію, можна впасти в нескінченний цикл, не згенерувавши жодної пропозиції. Наприклад, почавши з першої можливості для нетерміналу Game, отримаємо Head_start, а після його заміни – heads Game. Багаторазово застосовуючи цю ж стратегію для Game, отримаємо послідовність, в якій завжди є нетермінал Game, що не дає створити пропозицію мови, яка за визначенням складається тільки з термінальних символів.

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

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

марні. Ці проблеми докладно обговорюватимуться у лекції, присвяченій рекурсії. Більш тонким випадком є ​​граматики, що містять лексеми, але є леворекурсивними, як у прикладі:

Для простоти в цій граматиці Assignment вважається терміналом, визначеним поза граматикою (за аналогією з лексемами, що визначаються на рівні лексичного аналізу). Ця граматика має сенс і породжує такі пропозиції, як:

• assignment_1
• assignment_1; assignment_2

і так далі. Для отримання конструктивного виду таких рекурсивних визначень необхідна загальна теорія, нарис якої буде дано пізніше.

---