Виключення ланцюгових правил

записується в скороченому виді так:
(s₁,a ₁, g ₁) |--* ( s_n, a _n,g _n ).

Інший клас граматик, що породжують детерміновані мови, називається слаборозділеними граматиками. Цей клас відрізняється від класу розділених граматик тим, що він допускає використання анулюючих правил у схемі граматики. Однак, не всяка розділена граматика з анулюючими правилами відноситься до класу слаборозділених граматик. Щоб сформулювати визначення, що дозволяє пізнавати слаборозделені і LL(1) граматики, нам будуть потрібні нові поняття: множина ВИБІР, функції ПЕРВ і СЛІД.

Множина ВИБІР будується для кожного правила і включає ті термінальні символи, з появою яких під читаючою голівкою розпізнавач повинний застосовувати це правило.
Для визначення множини ВИБІР використовуються функції ПЕРВ і СЛІД. Аргументом функції ПЕРВ може бути будь-як ланцюжок повного словника µ, а значенням функції ПЕРВ(µ) є множина термінальних символів, що можуть стояти на першому місці в ланцюжках, виведених з ланцюжка µ.

7.2.2.Побудова функції ПЕРВ(µ).

Значення функції ПЕРВ(m) можна визначити користаючись наступними правилами: 1) Якщо ланцюжок µ починається термінальним символом і має вид m®bm’

ПЕРВ(m®bm’) = {b},

2) Якщо ланцюжок µ є порожнім ланцюжком,µ ® $, то функція

ПЕРВ(µ ® $) = $,

3) Якщо ланцюжокµ починається нетермінальним символом B і має вид m®Bµ', а в схемі граматики є n правил, у будь-якій частині яких знаходиться символ B:

B ® a₁ | a₂ | ... | a_n ,

і, якщо не існує виводу B ® $, то функція ПЕРВ(m®Bµ') являє собою об'єднання множин:

ПЕРВ(m®Bµ') = ПЕРВ(a₁) È ПЕРВ (a₂) È...ÈПЕРВ(a_n),

4) Якщо ланцюжок µ починається нетермінальним символом і має вид m® Bµ', в схему граматики входять n правил виду

B ® a₁ | a₂ | ... | a_n ,

і B є нетерміналом, що анулює, тобто існує B ® $, то функція

ПЕРВ(m®Bµ')=ПЕРВ(µ') È ПЕРВ(a ₁₎È ПЕРВ(a ₂₎ È...È ПЕРВ(a _n).

Як приклад виконаємо обчислення функції ПЕРВ для правил наступної граматики:

Г1:

R = { (1) A ® BCc,

(2) A ® gDB,
(3) B ® $,
(4) B ® bCDE,
(5) C ® DaB,
(6) C ® ca,
(7) D ® $,
(8) D ® dD,
(9) E ® gAf,
(10) E ® c }.

Спочатку знайдемо значення функції для правих частин правил (2), (4), (6), (8), (9) , (10) , що починаються термінальними символами:

ПЕРВ(gDB) = {g}
ПЕРВ(bCDE) = {b}
ПЕРВ(ca) = {c}
ПЕРВ(dD) = {d}
ПЕРВ(gAf) {g}
ПЕРВ(c) = {c}

Потім обчислимо функцію для правил (5) і (6) :

ПЕРВ (C) = ПЕРВ (DaB) È ПЕРВ (ca).

З огляду на те, що D є нетерміналом, що анулює, одержуємо:

ПЕРВ(C) = ПЕРВ(aB) ÈПЕРВ(D) È{c} = {a}È{d}È{c}={a, d, c}.

При обчисленні функції для правил (1) і (2) також необхідно врахувати те, що B є терміналом, що анулює, тому маємо:

ПЕРВ(A) = ПЕРВ(BCc) È ПЕРВ(gDB) =
ПЕРВ(Cc) È ПЕРВ(B) È ПЕРВ(gDB) =

{a,d,c} È {b} È{g} = {a,b,c,d,g}.

7.2.3. Побудова функції СЛІД(µ).

Аргументом функції СЛІД є нетермінальний символ, наприклад B, а значення функції СЛІД(B) являє собою множина терміналів, що можуть випливати безпосередньо за нетерміналом B у ланцюжках, виведених з початкового символу граматики.
Обчислення значення функції СЛІД(B) повинне виконуватися за наступними правилами:
1) Якщо в схемі граматики маються правила виду

X₁ ® µ₁Ba₁, X₂ ® µ₂Ba₂, ... , X_n ® µ_nBa_n,

і не існує правил a _i ® $ , то

СЛІД(B) = ПЕРВ(a ₁₎ È ПЕРВ(a ₂₎ È ... È ПЕРВ(a _n).

2) Якщо ж серед приведених вище правил існує хоча б один ланцюжок a_i ® $, наприклад нехай a₁ ® $, то функція обчислюється так:

СЛІД(B) = СЛІД(X₁) È ПЕРВ(a ₂₎ È ... È ПЕРВ(a _n).

Виконаємо обчислення функції СЛІД для нетерміналів граматики Г1. Спочатку визначимо функцію для нетермінала <A>, що зустрічається в правій частині правила (9).

СЛІД(A) = ПЕРВ(f) = {f}.
Нетермінал C входить у праві частини правил (1) і (4), з огляду на те, що нетермінал D є анулюючим, одержуємо:

СЛІД(C) = ПЕРВ(D) È ПЕРВ(E) ÈПЕРВ(c) = {c,d,g}.

Нетермінал <B> входить у праві частини правил (1), (2), (5), тому маємо:

СЛІД(B) =ПЕРВ(Cc) È СЛІД(A) È СЛІД(C),

підставляючи в отримане вираження значення функцій, що входять у праву частину, одержуємо:

СЛІД(B) = { a, c, d, }È { f } È { c, d, g, } = { a, c, d, g, f }.

Для нетермінала D , що входить у правила (2), (4) , (5) і (8), врахувати те, що нетермінал B є анулюючим, одержуємо:

СЛІД(D) =ПЕРВ(B) È СЛІД(A) È ПЕРВ(E) È ПЕРВ(aB),

з огляду на те, що, для нетермінала E, який входить у правило (4)
СЛІД(E) = СЛІД(B) = {a,d,c,g,f},
остаточно маємо:
СЛІД(D) = ПЕРВ(B)È СЛІД(A) ÈПЕРВ(E) È {a} =

= {b}È {f} È {c,g} È {a} = {a,b,c,g,f}.

7.2.4. Побудова функції ВИБІР(m).

Множину ВИБІР, яка буде потрібна нам для побудови переходів магазинних автоматів, можна визначити за допомогою функцій ПЕРВ і СЛІД у такий спосіб:

1) Якщо правило граматики має вид B®aіaне є анулюючим ланцюжком, іншими словами не існує виводу a ®$, то

ВИБІР(B ® a ) = ПЕРВ( a ).

2) Для правил граматики, що анулюють, виду B ®$, множина вибору визначається так

ВИБІР(B ® $) = СЛІД(B).

3) Якщо правило граматики має вид B ® µі µ є анулюючим ланцюжком то

ВИБІР(B ® µ) = ПЕРВ(µ) È СЛІД(B).

Для розглянутої граматики множина ВИБІР для кожного з правил, побудовані описаним вище способом, мають вид:

ВИБІР(A ® BCc) = ПЕРВ(BCc) = {a,b,c,d},
ВИБІР(A ® gDB) = ПЕРВ(gDB) = {g},
ВИБІР(B ® $) = ПЕРВ($) È СЛІД(B) = {a,c,d,g,f},
ВИБІР(B ® bCDE) = ПЕРВ(bCDE) = {b},
ВИБІР(C ® DaB) = ПЕРВ(DaB) = {a,d},
ВИБІР(C ® ca) = ПЕРВ(ca) = {с},
ВИБІР(D ® $) = ПЕРВ($) È СЛІД(D) = {a,b,c,g,f},
ВИБІР(D ® dD) = ПЕРВ(dD) = {d},
ВИБІР(E ® gAf) = ПЕРВ(gAf) = {g},
ВИБІР(E ® c) = ПЕРВ(c) = {c}.

7.3. Слаборозділені граматики

Використовуючи введені поняття, можна дати визначення слаборозділеної граматики.

КВ-граматика називається слаборозділеною, якщо виконуються наступні три умови:

· права частина кожного правила являє собою або порожній ланцюжок $, або починається з термінального символу;

· якщо два правила мають однакові ліві частини, то праві частини правил повинні починатися різними символами;

· множина ВИБІР, побудована для правил з однаковою лівою частиною, не містять однакових елементів.