Синтаксичний аналіз у ручному режимі двох прикладів операторів підмножини мови SQL варіантом як спадним, так і висхідним методами

Методи, які звичайно застосовуються в компіляторах, класифікуються як спадні (згори до низу, top-down) або висхідні (знизу нагору, bottom-up).

У спадному (низсхідному) граматичному розборі побудова синтаксичного дерева починається з кореня дерева (тобто з виділеного символу) і продовжується униз до листя, тобто до термінальних символів аналізованого рядка. Ціль такого процесу складається в тому, щоб систематично породжувати правила мови доти, поки не буде отримане речення, що збігається з аналізованим рядком. При цьому, можливо, прийдеться повертатися назад, якщо вибраний раніше ланцюжок побудови дерева виявився тупиковим. Щоб уникнути частих повернень назад, розроблені різноманітні варіанти проглядів вперед. Чим складніше граматика мови, тим більшою має бути 'дистанція' прогляду.

Породження правила можна відобразити за допомогою символу →, для якого запис 'x→y' інтерпретується як "рядок 'x' породжує рядок 'y'”.

Наведемо приклади розбору за граматикою визначення змінних мовою Pascal (див. п. 4.6) для рядка var a, z2, ba: char;

Спадний розбір зліва направо.

(1) <оператор_опису_змінних> → var <список_імен_змінних>: <тип_змінних>;

(3) var <список_імен_змінних>: <тип_змінних>; → var <список_імен_змінних>, id: <тип_змінних>;

(3) var <список_імен_змінних>, id: <тип_змінних>; → var <список_імен_змінних>, id, id: <тип_змінних>;

(2) var <список_імен_змінних>. id, id: <тип_змінних>;→ var id, id, id:<тип_змінних>;

(4) var id, id, id: <тип_змінних>; var id, id, id: char;

Вектор синтаксического разбору (послідовність правил при розборі) за спадним алгоритмом зліва направо (left-right – lr):

V спад_lr = < 1, 3, 3, 2, 4 >

Скориставшись гіпотетичною таблицею символів, яку б сформував лексичний аналізатор, синтаксичний аналізатор замінить токен id на конкретні лексеми, в результаті чого отримуємо рядок «var a, z2, ba: char;», який повністю співпадає з вхідним рядком, що свідчить про те, що він є синтаксично правильним. Нижче наводиться дерево граматичного розбору цього рядка.

При підіймальному (висхідному) граматичному розборі побудова синтаксичного дерева починається з "листя" (висячих вершин синтаксичного графа, якими є нетермінальні символи граматики) і продовжується просуванням нагору до кореня. При такому алгоритмі запис 'x → y' інтерпретується як 'у' зводиться до 'х'. Це так зване зворотне породження. Кроки цього породження для того ж самого рядка

«var a, z2, ba: char;» наведено нижче.

Тут теж скористаємося гіпотетичною таблицею символів, яку б сформував лексичний аналізатор. Синтаксичний аналізатор замінить лексеми a, z2, ba натокен id, в результаті чого отримуємо рядок «var id, id, id: char;»,

(2) var <список_імен_змінних>, id, id: char; → var id, id, id: char;

(3) var <список_імен_змінних>, id: char; → var <список_імен_змінних>, id: char;

(3) var <список_імен_змінних>: char; → var <список_імен_змінних>, id: char;

(4) var <список_імен_змінних>: <тип_змінних>; → var <список_імен_змінних>: char;

(1) <оператор_опису_змінних> → var <список_імен_змінних>: <тип_змінних>;

Вектор синтаксического разбору (послідовність правил при розборі) за підіймальним алгоритмом зліва направо:

V підійм_lr = < 2, 3, 3, 4, 1 >

Як бачимо, між векторми розбору V спад_lrй V підійм_lr не існує залажності крім того, що множини використаних правил співпадають.

Окрім напряму розбору зліва направо розбір можна здійснювати справа наліво (right-left – rl). Для цієї ж граматики і того ж самого рідка отримаємо:

V спад_rl = <1, 6, 3, 3, 2> і V підійм_rl = <6, 2, 3, 3, 1>

Як видно, існують такі залежності між цими векторами розбору зліва направо і векторами розбору справа наліво (rl):

V спад_lr = revers(V підійм_rl) і V підійм_lr = revers(V спад_rl),

де процедура revers переставляє правила вектора у зворотному порядку.

Поиск по сайту: