Ўзбекистон республикаси алоқА, ахборотлаштириш ва телекоммуникация технологиялари давлат қЎмитаси тошкент ахборот технологиялари университети

4.Контекст-озод грамматикалар.
3-тур грамматикалар лексик таҳлил вақтида ташкил этиладиган белгиларни генерация қилиш учун қулай, лекин улар юқори даража тилларини гапларида бу белгиларни бирлаштириш усулларини ифодалаш учун ноқулай. Масалан, юқорида айтилганидек, 3 тур грамматикаси орқали қавсларни мослаштиришни амалга ошириб бўлмайди. Контекст-озод грамматикалар (2 тур) эса типик дастурлаш тилларининг барча хусусиятларини амалга ошира олмасалар ҳам, универсал ҳисобланадилар ва компиляциянинг синтаксис таҳлил фазаси учун асос сифатида фойдалидирлар.
Контекст-озод грамматикалар компиляциянинг синтаксис таҳлил фазаси учун асос сифатида хизмат қиладилар. Агар қандайдир дастурлаш тилини контекст-озод грамматика ёрдамида генерация қилиш мумкин бўлмаса, у ҳолда шундай контекст-озод грамматикани топиш мумкинки, у ўзига берилган тил дастурини киритувчи тил усти тўпламини генерация қилади.
Синтаксис таҳлил учун бундай грамматикани қўллаш реал тилдаги қатор чегаралар (масалан, дастурдаги барча идентификаторларни эълон қилинишини шартлиги) таҳлилчи орқали текширилмаслигини англатади.
Лекин компиляторда берилган дастурдаги зарур текширувларни бажарилиши билан боғлиқ харакатларни қараб чиқиш қийин эмас (масалан, белгилар жадвалини қўллаш ҳисобига).
Контекст-озод грамматика таърифидан кўринадики, контекст-озод грамматикалар синфи, регуляр грамматикага кўра, жуда қудратли бўлиб (яъни кўп тилларни генерация қилиш мумкин), контекст-боғлиқ грамматикалар синфига нисбатан кучсизроқдир.
{aⁿ bⁿ | n 0} тил контекст-озод ҳисобланади, лекин регуляр эмас. У қуйидаги қоидаларни туғдирувчи грамматика орқали генерацияланади:
S aSb |
Бошқа томондан {aⁿ bⁿ cⁿ | n 0} тил контекст-боғлиқ ҳисобланади, контекст-озод эмас.
2. Хомскийнинг нормал формаси.
Контекст-озод грамматикалар бир қатор характеристикаларга эга бўлиб, улар учун қуйидаги холатлар тўғридир:
Каноник форма
а) Ҳар бир контекст-озод грамматика нормал формада Хомский грамматикасига барча қуйидаги кўринишдаги туғилувчи қоидалари билан терминал ва нотерминалларга тегишли оддий ҳолларда эквивалентдир.
АВС| a
3. Грейбахнинг нормал формаси.
б) Ҳар бир контекст-озод грамматика нормал формада Грейбах грамматикасига барча қуйидаги кўринишдаги туғилувчи қоидалари билан эквивалентдир.