Класифікація граматик В.Ковтунець Математична логіка і формальні системи

Формальна породжувальна граматика G=(V,T,S,P) – впорядкована четвірка обєктів: V – алфавіт або словник T – підмножина основних (термінальних) символів S - початковий символ P – скінченна множина продукцій (правил перетворення) вигляду ξη (ξ і η – ланцюжки над алфавітом).

Приклад 1 V={a,b,A,B,S} T={a,b} S = (початковий символ) P={SABa, ABB, Bab, ABb}. Можна вивести ланцюжки Aaba, Baba, Bababa, abababa.

Приклад 2 V={a,b,A,S} T={a,b} S = (початковий символ) P={SaA, Sb, Aaa}. Можна вивести лише ланцюжки b, aaa. Мова: L(G)={b, aaa}.

Приклад 3 V={0,1,S} T={0,1} S = (початковий символ) P={S11S, S0}. Мова: L(G)={0, 110, 11110,…}. Мова нескінченна.

Приклад 4 Побудова мови L(G)={0 m 1 m, m=0,1, 2,…}. V={0,1,S} T={0,1} S = (початковий символ) P={S0S1, S }.

Приклад 5 Побудова мови L(G)={0 m 1 n, m, n=0,1, 2,…}. V={0,1,S} T={0,1} S = (початковий символ) P={S0S, SS1, S }.

Приклад 6 V={S, a,b,c,,,, (, )} T={a,b,c,,,, (, )} S = (початковий символ) P={S(S S), S(S S), S S, Sa, Sb, Sc}. Породжує формули алгебри висловлень зі змінними a,b,c (булеві формули).

Приклад 7 V={S, a,b,c,+,-,*,/, (, )} T={a,b,c,+,-,*, /, (, )} S = (початковий символ) P={S(S + S), S(S - S), S(S * S), S(S / S), Sa, Sb, Sc}. Породжує формули алгебри арифметичних виразів зі змінними a,b,c.

Типи граматик. Ієрархія Хомскі (N.Chomsky) Тип граматики Обмеження на продукції 0Без обмежень 1, або = 2 =A (нетермінальний символ) 3 =A, =aB або =a, або S

Контекстно вільні граматики Означення. Граматика типу 2, тобто, всі продукції якої виводяться лише з нетермінальних символів, називається контекстно вільною. Приклади 7 та 8.

Контекстно залежні граматики Означення. Граматика, яка не є контекстно вільною, називається контекстно залежною. Така граматика містить хоча б одну продукцію типу Приклад. Мова L(G)={0 m 1 m 2 m, m=0,1, 2,…}.

Регулярні граматики Означення. Граматика типу 3, тобто, всі продукції якої виводяться лише з нетермінальних символів, і при цьому виводяться лише ланцюжки вигляду =aB або =a, або порожній, називається регулярною граматикою. Приклади 4 та 5.

Дерево виведення (синтаксичного розбору) S C A c a B b b P=(SAB, ACa, BBa, B Cb, B b, C c, C b} V={a,b,c,A,B,C,S}, T={a,b,c} Чи виводиться cbab? S AB Ab Cab cbab

Формули Бекуса-Наура Ще один спосіб описання контекстно вільних граматик. Обєднуються в один вираз усі продукції з однаковими символами ліворуч. Символ замінюють на ::=. Наприклад, три продукції A Aa,A a, A AB можна замінити однією ::= a |a|.

Приклади форм Бекуса-Наура ::=( )| + | * | ; ::=x|y. В цій граматиці виводиться ланцюжок (x * y ) + x.