Page 9 - 4761

Любий опис мови програмування, як правило, складається з 2-ох частин: спершу
формально викладаються правила побудови синтаксичних конструкцій, а потім на звичній
мові дається опис семантичних правил.
’
Мову, задану граматикою G, позначимо L(G). Дві граматики G і G називаються
еквівалентними, якщо вони визначають одну і ту ж мову: L(G)=L(G’). Дві граматики
називаються майже еквівалентними, якщо задані ними мови відрізняються не більше ніж
на пустий ланцюг символів: (GL )     (GL ) '   
Формально граматика G – це четвірка G (VT, VN, P, S), де
VT – множина термінальних символів, або алфавіт термінальних символів;
VN – множина нетермінальних символів, або алфавіт нетермінальних символів;
 *
P – множина правил граматики, виду    , де  VN  VT  ,  VN  VT  ;
S – початковий символ граматики SVN.
Алфавіти термінальних і нетермінальних символів граматики не пересікаються:
VN  VT  O . Це означає, що кожен символ в граматиці не може бути термінальним і
нетермінальним одночасно. Початковий символ – це завжди нетермінальний символ.
Множина термінальних символів містить символи, які входять в алфавіт мови, що
породжується граматикою. Як правило, символи з множини VT зустрічаються тільки в
ланцюгах правих частин правил. Множина VN містить символи, які визначають слова,
поняття, конструкції мови (G і в лівій і в правій частині, але обов’язково має бути хоча б
один раз в лівій частині хоча б одного правила)
Правила граматики зазвичай будуються так, щоб в лівій частині кожного правила
був хоча б один нетермінальний символ.
Мови програмування займають проміжне положення між формальними і
природними мовами. З формальними мовами їх об’єднують строгі синтаксичні правила,
на основі яких будують речення мови. Від мов природного спілкування в мови
програмування перейшли лексичні одиниці, які представляють основні ключові слова.

1.3 Класифікація граматик

Як для людини, так і для компіляторів можна розділити мови на прості і складні.
Чим складніша мова, тим більші обчислювальні затрати компілятора на аналіз ланцюгів
вихідної програми, а відповідно, складніший сам компілятор і його структура.
Формальні граматики класифікуються по структурі їхніх правил. Якщо всі без
виключення правила граматики задовольняють деяку задану структуру, то її відносять до
визначеного типу. Достатньо мати в граматиці одне правило, яке не задовольняє вимогам
структури правил, і вона вже не попадає в заданий тип.
Є чотири типи граматик по Хомському:
Тип 0: граматики з фазовою структурою.
На структуру їхніх правил не накладається ніяких обмежень: для граматики виду

G(VT,VN,P,S) , V=VN  VT правила мають вигляд: α→β, де α  V *, β  V* . Це самий
загальний тип граматики. В нього попадають всі без виключення формальні граматики,
проте частину з них можна віднести і до інших типів. Граматики, що відносяться тільки до
типу Ø , і до інших типів не можуть бути віднесені, є самими складними по своїй
структурі.
Практичного значення граматики, що відносяться тільки до типу Ø не мають.
Тип 1: контекстно-залежні (КЗ) і граматики, що не скорочуються.
До цього типу входять два основні класи граматик:
 контекстно-залежні граматики G(VT, VN, P, S), V=VN  VT, які мають
+
правила виду: α 1Аα 2→α 1βα 2, де α 1α 2  V* , A VN , β  V ;
 граматики, що не скорочуються G(VT, VN, P, S), V=VN  VT, які мають

правила виду: α→β, де α, β  V * , |α|≤|β|.

7