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

1)  перенесення  s, де s – стан;

2)  згортання у відповідності з продукцією A →β;

3) допуск;

4)  помилку.

Функція goto одержує як аргументи стан і символ граматики і повертає новий стан.

Конфігурація LR аналізатора  – це  пара, перший  компонент якої – вміст стека, а другий –  непереглянута частина вхідного потоку (s0X1s1X2s2...Xmsm, aiai+1 ... an$). Ця конфігурація відповідає правосентенціальній формі X1X2...Xmaiai+1 ... an.

Префікси правосентенціальних форм, що можуть з’явитися у стеку аналізатора, називаються активними   префіксами.

Активний префікс – це такий префікс правосентенціальної форми, що не переходить праву границю основи цієї форми.

Черговий крок синтаксичного аналізатора  визначається поточним вхідним символом ai і символом  стану на  вершині  стека  sm відповідно до значення елемента таблиці  дій action[sm,ai]. Конфігурації, що виходять після кожного з чотирьох типів дій, такі.

1 Якщо action[sm,ai] = “перенесення s”,  то синтаксичний аналізатор виконує перенесення, переходячи у конфігурацію (s0X1s1X2s2...Xmsmais, ai+1 ... an$). Синтаксичний аналізатор переносить у стек поточний вхідний символ aiі черговий стан s, який визначається значенням action[sm,ai]; поточним вхідним станом стає ai+1.

2 Якщо action[sm,ai] = “згортання A→β”, синтаксичний аналізатор виконує згортання, переходячи у конфігурацію (s0X1s1X2s2...Xm-rsm-rAs, ai+1 ... an$), де s=goto[sm-r,A], а r – довжина β, правої частини продукції. Тут синтаксичний аналізатор спочатку видаляє із стека  2r символів  (r символів стану і r символів граматики), так  що на вершині виявляється стан sm-r. Потім аналізатор  поміщає в стек A (ліву  частину продукції) і s – вміст елемента таблиці goto[sm-r,A]. Поточний вхідний символ  не змінюється. Для LR-аналізаторів  послідовність  символів Xm-r+1  ...  Xm , що видаляються  із стека,  завжди відповідає  β – правій частині продукції згортання.

  3 Якщо action[sm, ai] = “допуск”, то синтаксичний аналіз завершено.

  4 Якщо action[sm, ai] = “помилка”, аналізатор знайшов помилку і виконуються дії з діагностицки і відновлення.

Нижче наведено алгоритм LR-аналізу. Усі LR-аналізатори ведуть себе однаково. Різниця між ними полягає  у  різному змісті таблиць дій і переходів.

Алгоритм 4.5  Алгоритм LR-аналізу.

Установити покажчик ip на перший символ w$

repeat forever

begin

    Нехай s – стан на вершині стека, а a – символ, 

    на який вказує ip;

    if action[s, a] = “перенесення s' ” then begin

          Помістити у стек a і потім s'  

          на вершину стека;

          перемістити ip до наступного

          вхідного символа.

    end

    else if

        action [s, a] = “згортання A →β” then begin

        видалити зі стека 2*| β | символів;

        нехай s' - стан на вершині стека;

        помістити у стек A, а потім

        стан goto[s',A];

        вивести продукцію A →β.

    end

    else if   action [s, a] = “допуск” then

        return

    else error

end 

Спочатку в стеку поміщено початковий стан s0, а у вхідному буфері  – w$. Потім аналізатор виконує наведену нижче  програму доти, поки не буде досягнуте успішне завершення або знайдена помилка.

Візьмемо граматику арифметичних виразів з бінарними операціями “+” і “*”:

(1)  E →E + T,        4)  T →F ,

(2)  E →T ,               5)  E →( E ) ,(4.3)

(3)T →T * F,          (6)  E →id .

Функції синтаксичного аналізу action і goto показані у табл. 4.5.

У таблиці використані такі коди дій:

1) si означає перенесення в i–й стан на вершині стека;

2) rj означає згортання у відповідності з продукцією номер j;

3)  acc  означає допуск вхідного рядка;

4)  порожній елемент означає помилку.

Значення goto[s, a] для термінала a шукається у полі action, зв'язаному з перенесенням для вхідного символа aв стані s. Поле goto дає значення goto[s, A] для нетерміналів A.

Таблиця 4.5