л, записаних в три рядки. Початковий символ граматики -.
У граматиці можна змінити назви нетермінальних символів без якоїсь зміни мови, заданого нею. Термінальні символи змінювати не можна, так як вони відповідають алфавітом задаваемого мови.
Формальні граматики визначають нескінченна безліч ланцюжків мови за допомогою кінцевого набору правил. Це стає можливим завдяки використанню рекурсивних правил, в яких нетермінальний символ висловлюється сам через себе. Рекурсія при цьому може бути безпосередньою (явною), коли символ визначається сам через себе в одному правилі; або непрямої (неявній), коли таке перевизначення відбувається через ланцюжок правил.
У граматиках і явна рекурсія присутній у другій частині другого правила
,.
Щоб рекурсія була нескінченною, що бере участь в ній нетермінальний символ повинен обов'язково бути присутнім в лівій частині іншого правила, де він визначається, минаючи самого себе. У граматиках і це досягається в першій частині другого правила
,.
Явно або неявно, рекурсія завжди присутня в граматиках будь-яких реальних мов програмування. Як правило, в граматиках реального мови програмування присутня не одне, а безліч правил, побудованих за допомогою рекурсії.
4.4 Класифікація граматик за Хомським
Формальні граматики класифікуються за структурою їх правил. Якщо всі без винятку правила граматики задовольняють деякій структурі, то її відносять до заданого типу. Якщо хоча б одне правило граматики не задовольняє вимогам структури, то вона не потрапляє в заданий тип.
Нехай граматика позначена як
У відповідності з ієрархією Хомського виділяють чотири типи граматик.
Тип 0 - граматики з фразової структурою, або без обмежень. На структуру їх правил не накладається ніяких обмежень, тобто правила мають вигляд
де,. Це найбільш загальний тип граматик. Граматики, які відносяться тільки до цього і не можуть бути віднесені ні до якого іншого типу, є найскладнішими за структурою.
Тип 1 - контекстно-залежні і неукорачівающіе граматики. До цього типу належать два основні класи граматик.
Контекстно-залежні граматики мають правила виду
, де,,.
Неукорачівающіе граматики мають правила вид
де,.
У контекстно-залежних граматиках при побудові речень заданого мови один і той же нетермінальний символ може бути замінений різними термінальними ланцюжками в залежності від контексту, в якому він зустрічається. Ланцюжки і в правилах позначають контекст: - лівий контекст, - правий контекст. У загальному випадку вони можуть бути порожніми.
В не укорочують граматиках при побудові речень мови ланцюжок символів замінюється на ланцюжок неменшою довжини.
Ці два класи граматик еквівалентні.
При побудові компіляторів такі граматики не застосовуються, оскільки мови програмування мають більш просту структуру і можуть бути побудовані за допомогою граматик інших типів.
Тип 2 - контекстно-вільні граматики. Контекстно-вільні граматики мають правила виду, де,. У правій частині у них варто завжди хоча б один символ.
Такі граматики ще називають неукорачівающімі контекстно-вільними граматиками. Існує майже еквівалентний їм клас укорочують контекстно-вільних граматик, відмінність якого в тому, що він допускає, порожню ланцюжок, тобто правила мають вигляд, де,. Надалі, якщо можливість наявності в мові порожній ланцюжка не має принципового значення, будемо говорити просто про контекстно-вільних граматиках.
Контекстно-вільні граматики широко використовуються при описі синтаксичних конструкцій мов програмування.
Тип 3 - регулярні граматики. До цього типу відносяться два еквівалентних класу граматик: леволінейние і праволінейние.
Леволінейние граматики можуть мати правила двох видів
, або
де,.
Праволінейние граматики мають правила теж двох видів
, або,
де,
Регулярні граматики використовуються при описі найпростіших конструкцій мов програмування: ідентифікаторів, констант, рядків, коментарів тощо На основі будуються функції лексичного аналізу вхідної мови.
З визначення типів видно, що будь-яка регулярна граматика є т...
