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

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

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

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

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

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

-

-

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

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

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

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

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

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

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

S

… …..

Мал. 1.

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

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

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

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

S

… …..

……….