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

Нетер-мінал

Вхідний символ

id

+

*

(

)

$

E

E’

T

T’

F

E→TE’

T→FT’

F→id

E’→+TE’

T’→ε

T’→*FT’

E→TE’

T→FT’

F→(E)

E’→ε

T’→ε

E’→ε

T’→ε

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

               Для вхідного потоку id+id*id предиктивний синтаксичний аналізатор робить послідовність кроків,  зображену у табл. 4.2.

Покажчик входу вказує  на самий  лівий символ  у колонці “Вхід”. Якщо уважно проаналізувати дії аналізатора,  то видно, що його вихід збігається з послідовністю продукцій, які використовуються в лівому породженні. Якщо до прочитаних вхідних символів приписати символи у стеку (від вершини до дна), то одержимо лівосентенціальну форму в породженні.

4.3Функції FIRST і FOLLOW

               При побудові предиктивного аналізатора   корисними виявляються дві функції, зв'язані з граматикою  G. Ці функції, FIRST і FOLLOW, дозволяють побудувати   таблицю предиктивного розбору для G, якщо, звичайно, це можливо. Множини, що породжуються цими функціями, можуть, крім того, бути використані при відновленні після помилок.

Таблиця 4.2 

Стек

Вхід

Вихід

$E

$E’ T

$E’ T’ F

$E’ T’ id

$E’ T’

$E’

$E’ T+

$E’ T

$E’ T’ F

$E’ T’ id

$E’ T’

$E’ T’ F*

$E’ T’ F

$E’ T’ id

$E’ T’

$E’ 

$

id+id*id$

id+id*id$

id+id*id$

id+id*id$

+id*id$

+id*id$

+id*id$

id*id$

 id*id$

 id*id$

*id$

*id$

id$

id$

$

$

$

E→TE’

T→FT’

F→id

T’→ε

E’→+TE’

T→FT’

F→id

T’→*FT’

F→id

T’→ε

E’→ε

Якщо α – довільний рядок символів граматики, то визначимо FIRST(α) як множину терміналів, з яких починаються рядки, виведені з α. Якщо αε, то ε також належить FIRST(α).

Визначимо  FOLLOW(A)   для  нетермінала   A  як   множину терміналів a, що можуть з'явитися безпосередньо праворуч від A у деякій сентенціальній  формі,  тобто  множину терміналів a таких, що існує породження вигляду SαAaβ  для деяких α і β. Відзначимо, що між A і a у процесі виведення можуть з'явитися нетермінальні символи,  з яких виводиться ε. Якщо A може виявитися крайнім правим символом деякої сентенціальної форми, то $ належить FOLLOW(A). 

Для побудови FIRST(X) для всіх символів  граматики  X застосуємо такий алгоритм.

Алгоритм 4.2 Побудова множини FIRST для   символів граматики 

Крок 1 Якщо X  – термінал,  то FIRST(X) = {X}; якщо X - нетермінал, то FIRST(X)={}.

Крок 2 Якщо є продукція  X→ ε, то  додати ε до FIRST(X).

Крок 3 Якщо X  – нетермінал   і  є продукція X→Y1Y2...Yk,  то   включити  a   у  FIRST(X),  якщо  для        деякого  і   aFIRST(Yi)  і ε належить усім множинам        FIRST(Y1), ... ,FIRST(Yi-1), тобто Y1...Yi-1ε. Якщо ε належить FIRST(Yi) для всіх i=1,2,...,k, то додати ε до  FIRST(X). Наприклад, усе, що належить FIRST(Y1)        належить також  і FIRST(X).  Якщо з Y1 не виводиться        ε, то ми нічого більше не додаємо до FIRST(X), але якщо        Y1ε, то додаємо FIRST(Y2)  і т.д.

Тепер  FIRST  для  будь-якого  рядка  X1X2...Xn  можна  обчислити у такий спосіб.

Вважаємо FIRST(X1X2...Xn)={}.

Додамо до  FIRST(X1X2...Xn)  усі  не  ε-символи  з FIRST(X1). Додамо також всі не ε-символи з FIRST(X2), якщо εFIRST(X1), всі не ε-символи з   FIRST(X3), якщо ε належить як FIRST(X1),  так  і  FIRST(X2),  і  т.д. Нарешті, додамо ε до FIRST(X1X2...Xn), якщо для всіх  і  FIRST(Xi) містить ε.

Для обчислення  FOLLOW(A) для  нетермінала A застосуємо такий алгоритм.

Алгоритм 4.3  Побудова FOLLOW(X) для всіх X-нетерміналів граматики 

Крок 1 Помістити $ у FOLLOW(S), де S – початковий символ і $ – правий кінцевий маркер.

Крок 2 Якщо є продукція A→αBβ, то усі елементи з множини FIRST(β), за винятком ε, додати до FOLLOW(B).

Крок 3 Поки ні до якої множини FOLLOW(X) не можна буде додати ні одного символа: якщо є продукція  A→αB або A→αBβ, де  FIRST(β) містить  ε  (тобто βε), то усі елементи з множини FOLLOW(A) додати до FOLLOW(B).

Повернемося знову до граматики  (4.2):

E→TE' ,        E’→+TE' | ε ,

            T→ FT ' ,       T’→*FT ' | ε ,

            F→ (E) | id .

 Для неї:

    FIRST(E) =FIRST(T)=FIRST(F)={(, id};

    FIRST(E')={+, ε} ;

    FIRST(T')={*, ε} ;

    FOLLOW(E)=FOLLOW(E')={), $} ;

    FOLLOW(T)=FOLLOW(T')={+, ), $};

    FOLLOW(F)={+, *, ), $}.