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

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

Условия использования метода рекурсивного спуска.

Метод рекурсивного спуска без возвратов можно использовать только для грамматик, правила которых удовлетворяют следующему условию: первого символа каждого правила должно быть достаточно для того, чтобы определить, какое правило применимо в данном случае.

Более точно это условие можно формализовать путем определения множества FIRST.

Определение. Для КС-грамматики G и цепочки w, состоящей из терминальных и нетерминальных символов, определим множество FIRST_k(w) следующим образом:

FIRST_k (w) = {x | w =>* xv, |x| = k или w =>* x, |x| < k}

где k – натуральное число.

Иными словами, множество FIRST_k(w) состоит из всех терминальных префиксов длины k терминальных цепочек, выводимых из w.

Например, рассмотрим грамматику, порождающую подмножество типов языка Pascal.

type → simple

type → ^id

type → array [simple] of type

simple → integer

simple → char

simple → num.. num

Для этой грамматики имеем:

FIRST₁(simple) = {integer, char, num}

FIRST₁(^id) = {^}

FIRST₁(array [simple] of type) = {array}

Если цепочка w состоит только из терминалов, то FIRST_k(w) – это первые k символов цепочки w, если |w| ≥ k, или это – сама цепочка w, если |w| < k.

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

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

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

· если 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).

2. Формулировка алгоритма построения множества 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}

Грамматика 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

и два вывода

S =>* wSv => wuv =>* wx

S =>* wSv => wu₁v =>* wy

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

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

Для выводов

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

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

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

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

Дата добавления: 2014-01-11