6.4 Построение множества follow

Для каждого нетерминала грамматики можно построить множество follow, то есть множество терминалов, которые можно встретить непосредственно после нетерминала в какой-либо последовательности, соответствующей грамматике.

Алгоритм построения множества follow заключается в следующем. Вначале символ конца входной последовательности помещается в множество follow стартового нетерминала (шаг 1). Затем выполнятся шаги 2-4 до тех пор, пока можно еще что-либо добавить в множество follow(X).

2. Если есть правило АB, то в множество follow(В) добавляем множество first() без . То есть, если есть правило, утверждающее, что за В следует , то за нетеримналом будут следовать терминалы, с которых начинается последовательность .

3. Если есть правило АB, то в множество follow(B) добавляется множество follow(A). То есть, если есть правило, утверждающее, что нетерминалом В заканчивается последовательность А, то за нетрминалом В будут следовать те же терминалы, что и за всей последовательностью А.

4. Если есть продукция АB и пустая последовательность принадлежит first(), то в множество follow(B) добавляется множество follow(A). Если последовательность  не пуста, то терминалы, которые могут следовать за В уже найдены на шаге 1. Если же последовательность  пуста, то шаг 3 фактически сводится к шагу 2.

Рассмотрим построение множеств follow для нетерминалов грамматики, приведенной на рисунке 16.

Стартовым является нетерминал GOAL, поэтому на первом шаге follow(GOAL):=eof. Затем рассмотрим продукции грамматики, при этом будем считать, что  может являться пустой последовательностью.

Условию второго шага построения множества follow соответствуют следующие продукции.

EXPRTERM EXPR1, поэтому в follow(TERM) добавляем first(EXPR1) - 

TERMFACTOR TERM1, следовательно, в follow(FACTOR) заносим first(TERM1) - 

Условию третьего правила удовлетворяют следующие продукции.

GOALEXPR, на основании этого заносим в follow(EXPR) follow(GOAL).

EXPRTERM EXPR1, поэтому в follow(EXPR1) добавляем follow(EXPR).

EXPR1+ EXPR, эта продукция позволяет занести в follow(EXPR) follow(EXPR1). Однако выполнять это не нужно, так как follow(EXPR1)=eof, а follow(EXPR) уже содержит этот элемент.

TERMFACTOR TERM1, поэтому в follow(TERM1) добавляем follow(TERM).

TERM1 * TERM, следовательно в follow (TERM) можно занести follow(TERM1), но все элементы, которые можно было бы добавить уже содержаться в этом множестве.

Теперь рассмотрим продукции, соответствующие четвертому шагу алгоритма построения множества follow. Пустая последовательность  принадлежит множеству first только двух нетерминалов: EXPR1 и TERM1, поэтому на четвертом шаге будет рассмотрено только две продукции.

EXPRTERM EXPR1, на основе этого в follow(TERM) добавим follow(EXPR).

TERMFACTOR TERM1, следовательно в follow(FACTOR) занесем follow(TERM).

Результаты вышеизложенных рассуждений сведены в таблице 3. Заметим, что продукции 4 и 9 не рассматривались, так как они с точки зрения построения множества follow эквиваленты продукциям 3 и 8 соответственно. Так же не рассматривались продукции 5, 9, 10, 11, так как они не подходят ни под одно условие.

Таблица 4 – Множество FOLLOW, после первой итерации.

нетерминал	шаги				follow
	1	2	3	4
GOAL	{eof}				{eof}
EXPR			{eof}		{eof}
EXPR1			{eof}		{eof}
TERM		{+, -}		{eof}	{+, -, eof}
TERM1			{+, -}		{+, -}
FACTOR		{*, /}		{eof}	{*, /, eof}

Теперь необходимо еще раз повторить шаги 2 – 4. Новые элементы в множество follow можно добавить на шаге 3. Рассматривая продукцию TERMFACTOR TERM1, в follow(TERM1) нужно добавить follow(TERM). Теперь follow(TERM)={+, -, eof}. Таким образом, в follow(TERM1) добавляем элемент eof. Аналогично на четвертом шаге, рассматривая продукцию TERMFACTOR TERM1, в follow(FACTOR) занесем элементы + и -, которые отсутствуют в этом множестве, но на данном этапе принадлежат follow(TERM). Еще одно выполнение шагов 2-4 ничего нового к множеству follow не добавит, поэтому алгоритм закончил работу. Результат работы алгоритма представлен в таблице 5.

Таблица 5 Множество FOLLOW, после второй итерации.

нетерминал	шаги				follow
	1	2	3	4
GOAL	{eof}				{eof}
EXPR			{eof}		{eof}
EXPR1			{eof}		{eof}
TERM		{+, -}		{eof}	{+, - eof}
TERM1			{+, -, eof}		{+, -, eof}
FACTOR		{*, /}		{eof, +, /}	{*, /, eof, +, /}