Функции FIRST и FOLLOW

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

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

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

) как множество терминалов, с которых

Рис. 4.3.

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

. Если

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

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

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

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

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

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

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

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

Метод. Выполнить шаги 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);

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