Page 10 - 4761

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

1.4 Класифікація мов

Мови класифікуються відповідно до типів граматик, за допомогою яких вони
задані. Причому одна і та сама мова може бути задана декількома типами граматик. Тому
для класифікації вибирається граматика з найвищим номером.
Складність мови зменшується зі зростанням кваліфікаційного номера.
Згідно класифікації граматик є чотири типи мов:
Тип 0: мови з фазовою структурою.
Це самі складні мови, які можуть бути задані граматикою типу 0. Для розпізнання
ланцюгів символів необхідні обчислювальні рівні по потужності машини Тьюрінга. Тому,
можна сказати, що якщо мова типу 0 , то для неї неможливо побудувати компілятор, який

8