Функции FIRST и FOLLOW

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

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

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

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

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

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

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

 

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

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

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

(N 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

(N 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.


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

---

---