Функции FIRST и FOLLOW

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

Пусть G = (N, T, P, S) - КС-грамматика. Для - произвольной цепочки, состоящей из символов грамматики, определим как множество терминалов, с которых

Рис. 4.3.

начинаются строки, выводимые из Если , то e также принадлежит .

Определим FOLLOW(A) для нетерминала A как множество терминалов a, которые могут появиться непосредственно справа отA в некоторой сентенциальной форме грамматики, то есть множество терминалов a таких, что существует вывод вида для некоторых . Заметим, что между 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 - нетерминал, положить .

(2) Если в P имеется правило X -> e, то добавить e к FIRST(X).

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

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

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

Выход. Множество .

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

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

(2) Положить .

(3)

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

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

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

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

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

(1) Положить для каждого символа .

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

(3) Если в P eсть правило вывода , где , то все элементы из , за исключением e, добавить к FOLLOW(B).

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

если в P есть правило или , , где содержит , то все элементы из FOLLOW(A) добавить к FOLLOW(B).

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

Например, 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') включаются $ и правая скобка. Поскольку , они также попадают и во множество FOLLOW(T). В соответствии с правилом вывода E -> TE', на шаге 3 в FOLLOW(T) включаются и все элементы из FIRST(E'), отличные от e.

Определим теперь функцию FIRSTk(R), где k - натуральное число и .

либо |w| < k и , либо для некоторого .

Если , то , где w - это первые k символов цепочки при и при .

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

Определение. Пусть - некоторый алфавит. Если L₁ и L₂ - подмножества , то положим

Лемма 4.1. Для любой КС-грамматики и любых

Доказательство оставляем читателю в качестве упражнения.

Aлгоритм 4.6. Вычисление функции .

Вход. КС-грамматика и цепочка .

Выход. .

Метод.Так как по последней лемме

то достаточно показать, как найти FIRST_k(X) для .

Если , то очевидно, что FIRST_k(X) = {X}.

Определим множества F_i(X) для каждого и возрастающих значений i >= 0:

(1) F_i(a) = {a} для всех и i >= 0:

(2) и существует правило из P, для которого либо |x| = k, либо |x| < k и .

(3) Допустим, что F₀, F₁..., F_i-1 уже определены для всех . Тогда

принадлежит P и

(4) Так как для всех A и i, то в конце концов мы дойдем до такого i, что F_i-1(A) = F_i(A) для всех . Тогда положим FIRST_k(A) = F_i(A) для этого значения i.