5.1.4 Нерекурсивний предиктивнй аналіз

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

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

Рис. 5.5. Модель нерекурсивного предиктивного синтаксичного аналізатора

Предиктивнй синтаксичний аналізатор, керований таблицею, має вхідний буфер, стек, таблицю розбору й вихідний потік. Вхідний буфер містить аналізований рядок з маркером її правого кінця – спеціальним символом. Стек містить послідовність символів граматики з $ на дні. Завжди стек містить стартовий символ граматики безпосередньо над символом $. Таблиця розбору являє собою двомірний масив M[А,а], де А – нетермінал, a а – термінал або символ $.

Синтаксичний аналізатор керується програмою, що працює в такий спосіб. Програма розглядає X – символ на вершині стека, і а – поточній вхідний символ. Ці два символи визначають дії синтаксичного аналізатора. Є три варіанти.

1. Якщо X = а = $, синтаксичний аналізатор припиняє роботу й повідомляє про успішне завершення розбору.

2. Якщо X = а ≠ $, синтаксичний аналізатор знімає зі стеку X і переміщує покажчик вхідного потоку до наступного символу.

3. Якщо X ::= ε, синтаксичний аналізатор знімає зі стеку X, але не переміщує покажчик вхідного потоку до наступного символу.

4. Якщо X являє собою нетермінал, програма розглядає запис M[X,а] з таблиці розбору М. Цей запис являє собою або X-продукцію граматики або запис про помилку. Якщо, наприклад, M[X,а] = {X ::= UVW}, синтаксичний аналізатор заміщує X на вершині стеку на WVU (з U на вершині стека). Ми вважаємо, що як вихід синтаксичний аналізатор просто виводить використану продукцію, але, звичайно ж, тут може виконуватися будь-який необхідний код.

5. Якщо M[X,а] = error, синтаксичний аналізатор викликає програму відновлення після помилки.

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

Алгоритм 5.1. Нерекурсивний предиктивнй аналіз

Вхід. Рядок w і таблиця розбору M граматики G.

Вихід. У випадку wL(G) – ліве породження w; в іншому випадку – повідомлення про помилку.

Метод. Із самого початку синтаксичний аналізатор перебуває в конфігурації з $S (на його вершині – стартовий символ S граматики G) і рядком w$ у вхідному буфері. Програма, що використає для аналізу вхідного потоку таблицю предиктивного розбору М, показана на рис. 5.6.

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

repeat

позначимо через x символ на вершині стека,

а через а – символ, на який вказує ір.

if X – термінал або $ then

if X = a then

зняти зі стека x і перемістити ір

else error ()

else /* x - нетермінал */

if M[x,а] = х ::= Y₁Y₂...Y_k then begin

зняти x зі стеку;

помістити в стек Y_k, Y_k-1,..., Y₁, з Y₁

на вершині стека; вивести продукцію х ::= Y₁Y₂...Y_k

end

else error ()

until X = $ /* стек порожній */

Рис. 5.6. Програма предиктивного синтаксичного аналізу

Приклад 5.3. Розглянемо граматику (4.11) із приклада 5.2. Таблиця предиктивного аналізу цієї граматики показана на рис. 5.7. Порожні комірки таблиці означають помилки; непусті вказують продукції, за допомогою яких заміняються нетермінали на вершині стека. Помітимо, поки ми не вказуємо, яким чином вибирати запису з таблиці - про це поговоримо трохи пізніше.

Е ::= ТЕ'

Е' ::= +TЕ' | ε

T ::= FТ' (4.I1)

Т' ::= * FТ' | ε

F ::= (Е) | id

Нетермінал	Вхідний символ
	id	+	*	(	)	$
E	E → TE'			E → TE'
E'		E'→ +TE'			E' → ε	E' → ε
T	T → FT'			T → FT'
T'		T' → ε	T'→ *FT'		T' → ε	T' → ε
F	F → id			F → (E)

Рис. 5.7. Таблиця розбору для граматики (4.11)

При вхідному потоці id+id*id предиктивнй синтаксичний аналізатор здійснює послідовність переміщень, показану на рис. 5.8.

№	Стек	Вхід	Вихід
1	$E	id+id*id$
2	$E'T	id+id*id$	E → TE'
3	$E'T'F	id+id*id$	T → FT'
4	$E'T'id	id+id*id$	F → id
5	$E'T'	+id*id$
6	$E'	+id*id$	T' → ε
7	$E'T+	+id*id$	E'→ +TE'
8	$E'T	id*id$
9	$E'T'F	id*id$	T → FT'
10	$E'T'id	id*id$	F → id
11	$E'T'	*id$
12	$E'T'F*	*id$	T'→ *FT'
13	$E'T'F	id$
14	$E'T'id	id$	F → id
15	$E'T'	$
16	$E'	$	T' → ε
17	$	$	E' → ε

Рис. 5.8. Переміщення синтаксичного аналізатора при вхідному рядку id+id*id

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

5.1.5 Функції FIRST і FOLLOW

При побудові предиктивного синтаксичного аналізатора нам допоможуть дві функції, пов’язані із граматикою G, – FIRST й FOLLOW, які забезпечують заповнення таблиці предиктивного аналізу граматики G. Множини токенів, породжувані функцією FOLLOW, можуть також використатися як синхронізуючі токени в процесі відновлення після помилки в "режимі паніки" (дивись у розділі 6).

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

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

Щоб обчислити FIRST(X) для всіх символів X деякої граматики, будемо застосовувати наступні правила доти, поки до жодної із множин FIRST не зможуть бути додані ні термінали, ні ε.

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

2. Якщо існує продукція X ::= ε, додамо ε до FIRST(X).

3. Якщо X – нетермінал й існує продукція X ::= Y₁Y₂... Y_k, то помістимо а в FIRST(X), якщо для якогось i aFIRST(Y_i) і ε входить в усі множини FIRST(Y₁),…, FIRST(Y_i-1), тобто Y₁··· Y_i-1 →^* ε. Якщо ε є у всіх FIRST(Y_i), і = 1…k, то додаємо ε до FIRST(X). Наприклад, усе, що перебуває в множині FIRST(Y₁), є й у множині FIRST(X). Якщо Y₁ не породжує ε, то більше ми нічого не додаємо до FIRST(X), але якщо Y₁ →^* ε, то до FIRST(X) додаємо FIRST(Y₂) і т.д.

Тепер можна обчислити FIRST для будь-якого рядка X₁X₂...X_n наступним чином. Додамо до FIRST(X₁X₂...X_n) всі не-ε символи з FIRST(X₁). Додамо також всі не-ε символи з FIRST (X₂), якщо εFIRST (X₁), всі не-ε символи з FIRST(X₃), якщо ε є як в FIRST(X₁), так й в FIRST(X₂) і т.д. І нарешті, додамо ε до FIRST (X₁X₂...X_n), якщо для всіх i FIRST(X_i) містить ε.

Приклад 5.4. Звернемося знову до граматики (4.11):

(1) Е ::= ТЕ' (2) Е' ::= +TЕ' (3) Е' ::= ε (4) T ::= FТ'

(5) Т' ::= * FТ' (6) Т' ::= ε (7) F ::= (Е) (8) F ::= id

Тоді за правилом 1) побудови FIRST(Х) із продукцій (7) і (8) витікає

FIRST(F) = {(, id}

Оскільки нетермінал F не містить ε, то із продукційї (4) за правилом 3) випливає

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

Оскільки нетермінал T також не містить ε, то із продукції (1) за правилом 3) випливає

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

Оскільки нетермінали E' і T' містять ε, то із продукцій (3) і (6) за правилом 2) випливає, що FIRST(E') і FIRST(T') містять ε.

За правилом 3) із продукції (2) випливає, що FIRST(E') містить ще й термінал “+”, а із продукції (5) випливає, що FIRST(T') містить ще й термінал “*”.

Таким чином для граматики (4.11) отримали

FIRST(E) = FIRST(T) = FIRST(F)	=	{(, id}
FIRST(E')	=	{+, ε}
FIRST(T')	=	{*, ε}

Щоб обчислити FOLLOW(A) для всіх нетерміналів А, будемо застосовувати наступні правила доти, поки до жодної із множин FOLLOW не можна буде додати жодного символу.

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

2. Якщо є продукція А::=αВβ, то всі елементи множини FIRST(β), крім ε, поміщаються в множину FOLLOW(В).

3. Якщо є продукція A::=αВ або А::=αВβ, де FIRST(β) містить ε (β →^* ε), то всі елементи із множини FOLLOW(A) містяться в множину FOLLOW(В).

Приклад 5.4. Звернемося знову до граматики (4.11):

(1) Е ::= ТЕ' (2) Е' ::= +TЕ' (3) Е' ::= ε (4) T ::= FТ'

(5) Т' ::= * FТ' (6) Т' ::= ε (7) F ::= (Е) (8) F ::= id

Для обчислення множин FOLLOW поміщаємо $ в FOLLOW(E) відповідно до правила 1) для обчислення FOLLOW. А із продукції (7) за правилом 2) символ “)” теж входить до множини FOLLOW(E), оскільки FIRST(“)”) = {“)”), тобто

FOLLOW(E) = {), $} .

Відповідно до правила 3), застосованим до продукції (1) E::=ТE', враховуючи (3) Е' ::= ε, FOLLOW(E') = FOLLOW(E) = {), $}.

Із цих же міркувань із продукції (2) Е' ::= +TЕ' випливає, що {), $} входить до FOLLOW(T). А за правилом 2) до цієї продукції до FOLLOW(T) додаються всі елементи із FIRST(E') крім ε. Таким чином

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

Розглянемо тепер продукцію (5) Т' ::= * FТ'. За правилом 3) усі елементи FOLLOW(T') = {+, ), $} входять до множини FOLLOW(F). А за правилом 2) до цієї ж продукції до FOLLOW(F) додаються всі елементи із FIRST(Т') крім ε. Таким чином,

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

Усі множини FIRST(X) і FOLLOW(X) наведено нижче.

FIRST(E)=FIRST(T) = FIRST(F)	=	{(, id}
FIRST(E')	=	{+, ε}
FIRST(T')	=	{*, ε}
FOLLOW(E) = FOLLOW(E')	=	{), $}
FOLLOW(T) = FOLLOW(T')	=	{+, ), $}
FOLLOW(F)	=	{+,*,),$}