Функции FIRST и FOLLOW

При построении таблицы предсказывающего анализатора нам потребуются две функции - FIRST и FOLLOW.

Пусть G = (N, T, P, S) - КС-грамматика. Для

- произвольной цепочки, состоящей из символов грамматики, определим FIRST(

) как множество терминалов, с которых начинаются строки, выводимые из

. Если

*e, то e также принадлежит FIRST(

Определим FOLLOW(A) для нетерминала A как множество терминалов a, которые могут появиться непосредственно справа от A в

некоторой сентенциальной форме грамматики, т.е. множество терминалов a таких, что существует вывод вида S

для некоторых

T)*. Заметим, что между A и a в процессе вывода могут находиться нетерминальные символы, из которых выводится e. Если A может быть самым правым символом некоторой сентенциальной формы, то $ также принадлежит FOLLOW(A).

Рассмотрим алгоритмы вычисления функции FIRST.

Алгоритм 4.3. Вычисление FIRST для символов грамматики.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Множество FIRST(X) для каждого символа X

T).

Метод. Выполнить шаги 1-3:

Если X - терминал, то положить FIRST(X) = {X}; если X - нетерминал, положить FIRST(X) =
.

Если в P имеется правило X

e, то добавить e к FIRST(X).

Пока ни к какому множеству FIRST(X) нельзя уже будет добавить новые элементы, выполнять:

если X - нетерминал и имеется правило вывода X
Y 1Y 2...Y k, то включить a в FIRST(X), если a
FIRST(Y i) для некоторого i, 1
i
k, и e принадлежит всем FIRST(Y 1), ..., FIRST(Y i-1), то есть Y 1...Y i-1
*e. Если e принадлежит FIRST(Y j) для всех j = 1, 2, ..., k, то добавить e к FIRST(X).

Алгоритм 4.4. Вычисление FIRST для цепочки.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Множество FIRST(X1X2...Xn), Xi

T).

Метод. Выполнить шаги 1-3:

При помощи предыдущего алгоритма вычислить FIRST(X) для каждого X
(N
T).

Положить FIRST(X1X2...Xn) =
.

Добавить к FIRST(X1X2...Xn) все не e-элементы из FIRST(X1). Добавить к нему также все не e-элементы из FIRST(X2), если e
FIRST(X1), не e-элементы из FIRST(X3), если e принадлежит как FIRST(X1), так и FIRST(X2), и т.д.
Наконец, добавить цепочку e к FIRST(X1X2...Xn), если e
FIRST(Xi) для всех i.

Рассмотрим алгоритм вычисления функции FOLLOW.

Алгоритм 4.5. Вычисление FOLLOW для

нетерминалов грамматики.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Множество FOLLOW(X) для каждого символа X

N.

Метод. Выполнить шаги 1-4:

Положить FOLLOW(X) =
для каждого символа X

N.

Добавить $ к FOLLOW(S).

Если в P eсть правило вывода A

B
, где
,

(N
T)* то все элементы из FIRST(
), за исключением e, добавить к FOLLOW(B).

Пока ничего нельзя будет добавить ни к какому множеству FOLLOW(X), выполнять:

если в P есть правило A

B или A

B
,
,

(N
T)*, где FIRST(
) содержит e (т.е.

*e), то все элементы из FOLLOW(A) добавить к FOLLOW(B).

Пример 4.4. Рассмотрим грамматику из примера 4.3. Для нее

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

Например, id и левая скобка добавляются к FIRST(F) на шаге 3 при i = 1, поскольку FIRST(id) = {id} и FIRST(”(”) = {”(”} в соответствии с шагом 1. На шаге 3 при i = 1, в соответствии с правилом вывода T

FT' к FIRST(T) добавляются также id и левая скобка. На шаге 2 в FIRST(E') включается e.

При вычислении множеств FOLLOW на шаге 2 в FOLLOW(E) включается $. На шаге 3, на основании правила F

(E), к FOLLOW(E) добавляется также правая скобка. На шаге 4, примененном к правилу E

TE', в FOLLOW(E') включаются $ и правая

скобка. Поскольку E'

*e, они также попадают и во множество FOLLOW(T). В соответствии с правилом вывода E

TE', на шаге 3 в FOLLOW(T) включаются и все элементы из FIRST(E'), отличные от e.

Содержание раздела