Теория и реализация языков программирования




Функции FIRST и FOLLOW


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

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

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


Рис. 4.3. 

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

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

Определим FOLLOW(A) для нетерминала A как множество терминалов a, которые могут появиться непосредственно справа от A в некоторой сентенциальной форме грамматики, то есть множество терминалов a таких, что существует вывод вида S

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

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

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

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

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

X \in (N \cup T)
.

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

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

.

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

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

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

do { continue = false; Для каждого нетерминала X Для каждого правила X

Y1Y2...Yk {i=1; nonstop = true; while (i
k && nonstop) {добавить FIRST(Yi) n {e} к FIRST(X); if (Были добавлены новые элементы) continue = true; if (e
FIRST (Yi) nonstop = false; else i+ = 1; } if (nonstop) {добавить e к FIRST(X); continue = true; } } } while (continue);




Содержание  Назад  Вперед