Синтаксичний аналіз. Спадний аналіз. Предиктивний аналізатор. Висхідний аналіз, страница 10

Ми говоримо, що пункт А→β₁•β₂допустимийдля активного префікса αβ₁, якщо існує породження S'αAqαβ₁β₂w.Взагалі пункт може бути допустимим для багатьох активних префіксів. Той факт, що А→β₁•β₂допустимий для αβ₁ , свідчить про те, що саме варто вибрати – перенесення або згортання – при виявленні αβ₁у стеку. Зокрема, якщо β₂ ≠ε, то це припускає, що основа ще не цілком перенесена в стек і чергова дія аналізатора – перенесення. Якщо β₂ = ε, то А→β₁ – основа, і ми повинні виконати згортання відповідно до цієї продукції. Звичайно, два допустимих пункти можуть указувати на різні дії для того самого активного префікса. Частина цих конфліктів може бути вирішена шляхом перегляду чергового вхідного символа, а інші доведеться вирішувати спеціальними методами. Однак не слід вважати, що всі конфлікти дій синтаксичного аналізатора можуть бути дозволені, якщо LR-метод використовується для побудови таблиці синтаксичного аналізу довільної граматики.

Обчислити множину допустимих пунктів для кожного активного префікса, що може з'явитися у стеку LR-аналізатора, досить просто. Насправді, основна теорема теорії LR-аналізу засвідчує, що множина допустимих пунктів для активного префікса γ у точності дорівнює множині пунктів, досяжних з початкового стану по шляху, позначеному γ, у детермінованому автоматі, побудованому за канонічною системою множин пунктів, з переходами, що даються функцією goto. По суті, множина допустимих пунктів містить у собі всю корисну інформацію, що може бути зібрана зі стека. Наведемо відповідний приклад.

Знову розглянемо граматику (4.4). Зрозуміло, що рядок Е+Т* є активним префіксом граматики. Автомат після прочитання Е+Т* буде перебувати у стані I₇, що містить такі пункти:

Т→Т*•F,

F→•E ,

F→• id  .

Ці пункти допустимідля Е+Т*. Для того щоб побачити це, розглянемо такі три правих породження:

Е'  Е  Е+Т Е+Т*F ,

Е'  Е  Е+Т Е+Т*F  Е+Т*(E) ,

Е'  Е  Е+Т Е+Т*F  Е+Т*id  .

Перше породження показує допустимість T→Т*•F, друге  –  F→• (E),а третє –  F→• id  для активного префікса Е+Т*.

Тепер покажемо, як побудувати функції actionі gotoSLR-аналізу за детермінованим скінченним автоматом, що розпізнає активні префікси. Наш алгоритм не дає однозначно визначеної таблиці дій синтаксичного аналізу для всіх граматик, але він успішно працює для багатьох граматик мов програмування. Дану нам граматику Gрозширюємо до граматики G'і на основі G'будуємо C – канонічну систему множин пунктів для G'. За системою C ми будуємо action, функцію дій синтаксичного аналізу, і goto, функцію переходів, відповідно до наведеного далі алгоритму. Він вимагає знання FOLLOW(А) для кожного нетермінала  A  граматики.

Алгоритм 4.8  Алгоритм побудови таблиці SLR-аналізу

1 Побудуємо C= {I₀ , I₁, …, I_n} – систему множин LR(0)-пунктів для граматики G'.

2 Стан i будується на основі I_i. Дії синтаксичного аналізу для стану  i  визначаються в такий спосіб:

a) якщо [А→α•aβ]I_i, і  goto(I_i ,  а)=I_j то визначити action[i,а] як “перенесення j ”; тут а повинно бути терміналом;

b) якщо [А→α•]I_i, то визначити action[i, а] як “згортання А→α” для всіх  а з FOLLOW(А); тут А не повинно бути S';

c) якщо [S'→S•]I_i, то визначити action[i, $] як “допуск”.

Якщо за цими правилами генеруються конфліктуючі дії, ми говоримо, що граматика не є SLR(1). Алгоритм не в змозі побудувати синтаксичний аналізатор для неї.

3 Переходи goto для стану i і всіх нетерміналів А будуються за правилом: якщо goto(I_i , а)=I_j ,то goto[i,A]=j.

4 Усі записи, не визначені за правилами 2 і 3, трактуються як "помилка”.

5 Початковий стан синтаксичного аналізатора являє собою стан, побудований з множини пунктів, що містить [S'→•S].

Таблиця синтаксичного аналізу, що складається з функцій actionі goto, обумовлених алгоритмом 4.8, називається SLR(1)-таблицеюграматики G. LR-аналізатор, що використовує SLR(1)-таблицю для граматики G, називається SLR(1)-аналізатором для G, а відповідна граматика – SLR(1)-граматикою.

Приклад 4.3

Побудуємо SLR-таблицю для граматики (4.4). Спочатку розглянемо множину пунктів I₀:

Е'→ • E,                    T→ • F ,

Е→• Е+Т,                 F→ • (Е),

Е→ •Т ,                       F→• (id) .                  

T→ •Т*F ,