Головна

Мал. 2.

Означення. Будемо говорити, що ланцюжок , побудований на основі граматики проаналізований, якщо відоме одне з його дерев виводу. Зафіксуємо послідовність номерів правил, які були використані під час побудови синтаксичного дерева виводу в G з урахуванням стратегії виводу.

Означення. Лівостороннім аналізом ланцюжка будемо називати послідовність номерів правил, які були використані при лівосторонньому виводі в G.

Приклад: Для граматики зі схемою Р

для ланцюжка побудуємо лівосторонній аналіз :

З наведеного вище виводу ланцюжка лівосторонній аналіз буде: , а синтаксичне дерево виводу зображено на Мал. 4.

Нехай лівосторонній аналіз ланцюжка . Знаючи досить легко побудувати (відтворити) синтаксичне дерево. Відтворення (синтез) синтаксичного дерева можна виконати, скориставшись однією з стратегій синтаксичного аналізу:

- стратегія "зверху донизу";

- стратегія "знизу вгору".

S

T

T * F

F ( S )

a S + T

T F

F a

a

Мал. 4

Стратегія синтаксичного аналізу "зверху донизу" - це побудова синтаксичного дерева крок за кроком починаючи від кореня до крони.

Алгоритм 2. Синтез синтаксичного дерева на основі лівостороннього аналізу ланцюжка .

П0: Побудуємо корінь дерева та позначимо його аксіомою S. Тоді, якщо , то

П1: Побудуємо дерево висоти один, взявши зі схеми Р правило з номером р1 виду (Мал. 5):

S

... ...

Мал. 5.

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

Сформулюємо декілька проблем для стратегії аналізу "зверху донизу":

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

, де - будь-який нетермінал граматики .

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

2. існують підкласи класу КС-граматик, які природно забезпечують стратегію аналізу "зверху донизу". Один з таких підкласів - це LL(k)-граматики, які забезпечують синтаксичний аналіз ланцюжка за час , де , та при цьому є однозначним.



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

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

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