Разработка компиляторов

       

Алгоритм построения множества FIRST


Прежде всего, определим множество FIRST для всех символов грамматики:

  1. если X - терминал, то FIRST (X) = X
  2. для правила добавим к множеству FIRST (X)
  3. если X - нетерминал и - правило грамматики, то добавим терминал а в FIRST(X), если для некоторого i этот терминал a принадлежит и принадлежит всем множествам , , то есть . Если принадлежит для всех , то добавим в FIRST(Y).

Теперь сформулируем сам алгоритм построения множества FIRST(w).

Вход. КС-грамматика G=(N, T, P, S) и цепочка w терминальных и нетерминальных символов.

Выход. FIRST (w).

Метод. Добавим в FIRST (X 1 X 2 …X k) все непустые символы из FIRST (X1). Затем, если принадлежит FIRST (X1), то добавим все непустые символы из FIRST (X2), и так далее. Наконец, если для всех j FIRST (Xj) содержит пустой символ, то мы добавим в множество FIRST (X1 X2…Xk) .

Пример. Рассмотрим грамматику с правилами:

Для этой грамматики множества FIRST определяются следующим образом:



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