Головна

Синтаксичний аналіз в мовних процесорах

  1. B. Аналіз документів
  2. III-IV рівні. Курація хворих. Аналіз результатів обстеження і лікування. Форма перевірки: протокол обстеження, усне чи письмове опитування, вирішення ситуаційних задач.
  3. III. Порядок збору, узагальнення та аналізу інформації про злочини, порушені кримінальні справи, події, адміністративні корупційні правопорушення
  4. IV. Оцінювання мовних знань і вмінь
  5. LL(1)-синтаксичний аналізатор для мови Pascal
  6. SWOT - аналіз
  7. SWOT-аналіз "МУКАЧІВСЬКОЇ ЛИЖНОЇ ФАБРИКИ "ТИСА"".

Для визначення синтаксичної компоненти мови програмування використовують контекстно-вільні граматики (КС-граматики). На відміну від скінчено-автоматних граматик потужність класу КС-граматик достатня, щоб визначити майже всі так звані синтаксичні властивості мов програмування. Якщо цього недостатньо, то розглядають деякі спрощення у граматиках типу 2 або параметричні КС-граматики.

Звичайно, із синтаксичною компонентою мови програмування пов'язана семантична компонента. Тоді, якщо ми говоримо про семантику мови програмування, ми вимагаємо семантичної однозначності для кожної вірно написаної програми. За аналогією з семантикою, при описі синтаксичної компоненти мови програмування необхідно користуватися однозначними граматиками.

Означення. Граматика G називається неоднозначною, якщо існує декілька варіантів виводу в G ( ).

Приклад. Розглянемо таку граматику зі схемою Р.

Покажемо, що для ланцюжка існує щонайменше два варіанти виводу:

-

-

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

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

Означення. Синтаксичне дерево виводу в G - це впорядковане дерево, корінь котрого позначено аксіомою, в проміжних вершинах знаходяться нетермінали, а на кроні - елементи з . Побудова синтаксичного дерева виведення в G виконується покроково з урахуванням стратегії виводу в G.

Алгоритм. Побудова синтаксичного дерева ланцюжка в граматиці G з урахуванням лівосторонньої стратегії виводу:

П1. Будуємо корінь дерева та позначимо його аксіомою S.

П2. В схемі P граматики G візьмемо правило виду , де . Та побудуємо дерево висоти 1 (Мал. 1).

Пі. На кроні дерева, побудованого на попередньому кроку, візьмемо перший зліва направо нетермінал. Нехай це буде . Тоді в схемі P виберемо правило виду , де та побудуємо наступне дерево (Мал. 2).

S

... ...

Мал. 1.

Пункт Пі виконувати доти, доки на кроні дерева будуть елементи з .

Відмітимо очевидні факти, що випливають з побудови синтаксичного дерева:

- крона дерева, зображеного на мал. 2 наступна . Ланцюжок з крони - це термінальний ланцюжок.

- для однозначної граматики G існує лише одне синтаксичне дерево виводу в G.

S


... ...

...



Лабораторний практикум побудови лексичних аналізаторів. | Мал. 2.

Мови програмування та мовні процесори | Структура транслятора | Скінчені автомати | Мінімізація детермінованих скінчених автоматів | Скінчені автомати та праволінійні граматики | Регулярні множини та регулярні вирази | Польський інверсний запис для регулярних виразів | Застосування скінчених автоматів при розробці лексичних аналізаторів | На основі поточного стану. | Методика програмування лексичних аналізаторів на основі скінчених автоматів. |

© um.co.ua - учбові матеріали та реферати