Разработка компиляторов
Алгоритм построения множества FIRST
Прежде всего, определим множество FIRST для всех символов грамматики:
- если X - терминал, то FIRST (X) = X
- для правила добавим к множеству FIRST (X)
- если 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 определяются следующим образом:
