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

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

1) если X – терминал, то FIRST (X) = X

2) для правила X→ε добавим ε к множеству FIRST (X)

3) если X – нетерминал и X → Y₁Y₂ … Y_k – правило грамматики, то добавим терминал а в FIRST (X), если для некоторого i этот терминал a принадлежит FIRST (Y_i) и ε принадлежит всем множествам FIRST (Y₁), …, FIRST (Y_i-1), то есть Y₁, …, Y_i-1 =>*ε. Если ε принадлежит FIRST (Y_j) для всех j =1, 2, …, k, то добавим ε в FIRST (Y).

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

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

Выход. FIRST (w).

Метод. Добавим в FIRST (X₁X₂…X_k) все непустые символы из FIRST (X₁). Затем, если ε принадлежит FIRST (X₁), то добавим все непустые символы из FIRST (X₂), и так далее. Наконец, если для всех j FIRST (X_j) содержит пустой символ, то мы добавим ε в множество FIRST (X₁X₂…X_k).

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

S → B A

A → +B A

A → ε

B → D C

C → * D C

C → ε

D → (S)

D → a

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

FIRST (D) = {(, a}, FIRST (C) = {*, ε }, FIRST (B) = FIRST (D), FIRST (A)={+, ε },

FIRST (S) = {(, a}

LL(k)-грамматика

Определение. Грамматика G = (V_T, V_N, P, S) называется LL(k)-грамматикой, если для любых двух левых выводов

S =>* wAv => wuv =>* wx

S =>* wAv => wu₁v =>* wy,

для которых FIRST_k (x) = FIRST_k (y) верно, что u=u₁.

То есть если для данной цепочки wAv, состоящей из терминальных и нетерминальных символов и k первых символов (если они есть), выводящихся из Av, существует не более одного правила, которое можно применить к A, чтобы получить вывод какой-нибудь терминальной цепочки, начинающейся с w и продолжающейся упомянутыми k терминалами.

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

S → aAS

S → b

A → a

A → bSA

и два вывода

(1) S =>* wSv => wuv =>* wx

(2) S =>* wSv => wu₁v =>* wy

Пусть цепочки x и y начинаются с a. Это означает, что в выводе участвовало правило S→aAS. Следовательно, u = u₁ = aAS. Пусть цепочки x и y начинаются с b. Это означает, что в выводе участвовало правило S→b. Следовательно, u = u₁ = b.

Для выводов

(3) S =>* wAv => wuv =>* wx

(4) S =>* wAv => wu₁v =>* wy

рассуждение аналогично. Таким образом, грамматика обладает свойством LL(1).

Для LL(1)-грамматик может быть построен анализатор методом рекурсивного спуска без возвратов.