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

4. Грамматикаларни LL(1) кўринишга айлантириш.

Кўпгина дастурлаш тиллари учун «кўриниб турган» грамматика бу LL(1) грамматика эмас. Лекин, кўпинча дастурлаш тилининг жуда катта сонли контекст-озод воситаларини LL(1) грамматика орқали ифодалаш мумкин. Муаммо шундаки, LL(1) грамматика белгиларига эга бўлмаган грамматикага эга бўлган ҳолда, унга тенг кучли бўлган LL(1) грамматикани топиш керак. Ихтиёрий контекст-озод грамматикани LL(1) кўринишга айлантиришнинг умумий алгоритми мавжуд эмас. Лекин кўпгина хусусий ҳолларда бундай айлантиришларни бажарувчи қатор усуллар мавжуд.
Чап рекурсияни йўқотиш.
Чап рекурсияга эга грамматика LL(1) грамматика ҳисобланмайди. Қуйидаги қоидаларни кўриб чиқамиз:
А  Аа (А да чап рекурсия)
А  а
Бу ерда а белги-ҳамрох А нотерминалнинг иккала варианти учун.
Худди шунингдек чап рекурсив циклга эга грамматика ҳам LL(1) грамматика ҳисобланмайди, масалан

А ВС

В СД
С АЕ
Чап рекурсив циклга эга грамматикани фақат тўғри чап рекурсияга эга грамматикага айлантириш мумкин ва кейинчалик қўшимча нотерминаллар киритиш йўли билан чап рекурсияни тўлиқлигича олиб ташлаш мумкин бўлади (ҳақиқатда эса у ўнг рекурсия билан алмаштирилади. Ўнг рекурсия эса LL(1)- хусусиятларига нисбатан муаммо ҳосил қилмайди).
Мисол сифатида қуйидаги туғилувчи қоидаларга ва чап рекурсив циклга эга бўлиб A,B,C,D ларни ўзига олувчи грамматикани қараб чиқамиз:
S  Aa C  Dd
A Bb C  e
B Cc D  Az
Ушбу циклни тўғри чап рекурсияга ўзгартириш учун нотерминалларни қуйидагича тартибга соламиз: S, A,B,C,D.
Барча қуйидаги кўринишдаги туғилувчи қоидаларни қараймиз:
Xi  Xjy,
Бу ерда Xi ва Xj нотерминаллар, y эса терминал ва нотерминал белгилар қатори. j >=i бўлган қоидалар учун ҳеч қандай харакат бажарилмайди. Лекин бу тенгсизлик чап рекурсив циклга эга барча қоидалар учун ҳам мос келавермайди. Юқоридаги биз танлаган тартибда қуйидаги ягона қоида билан ишлаймиз.
D  Az
чунки бу тартибда А D дан кейин келмоқда. Энди А ни чап томондаги барча мавжуд қоидалардан фойдаланиб алмаштирамиз. Натижада
D  Bbz ни оламиз.
Тартибда B D дан кейин келаётганлиги сабабли, жараён такрорланади, буни эса қуйидаги қоида беради:
D Ccbz
Сунгра у яна такрорланади ва иккита қоидани беради:
D  ecbz
D  Ddcbz
Энди келтириб чиқарилган грамматика қуйидагича бўлади:
S  Aa C  e
A  Bb D  Ddcbz
B Cc D  ecbz
C Dd
Барча ушбу туғилувчи қоидалар талаб қилинган кўринишга эга, чап рекурсив цикл эса тўғри чап рекурсия билан алмаштирилган. Тўғри чап рекурсияни йўқотиш учун янги нотерминал белги Z киритамиз ва қоидаларни алмаштирамиз:
D  ecbz
D  Ddcbz
ларни
D  ecbz Z dcbz
D  ecbzZ Z dcbzZ
D айлантиришгача ва ундан сўнг қуйидаги регуляр ифодани генерациялайди
(ecbz) (dcbz)*
Умумлаштирган ҳолда, шуни кўрсатиш мумкинки, агар А нотерминал r+s туғилувчи қоидаларнинг чап қисмида учраса, r булардан тўғри чап рекурсиядан фойдаланса, s эса фойдаланмаса, яъни
A  A ₁, A A ₂ ,…., A A _r
A  ₁, A  ₂ , …., A _s
у ҳолда бу қоидаларни қуйидагиларга алмаштириш мумкин:
L i s L i r
Ноформал исбот шуни кўрсатадики, A айлантиришгача ва ундан сўнг қуйидаги регуляр ифодани генерациялайди:
( ₁ | ₂| … | _s) ( ₁| ₂| ….| _r)*
Шуни таъкидлаш лозимки, чап рекурсияни (ёки чап рекурсив циклни) йўқотиш натижасида LL(1) грамматикага эга бўламиз, шундай қилиб, олинган грамматика қоидаларининг чап қисмидаги баъзи бир нотерминалларга альтернатив ўнг қисмлар мавжуд бўлиб, улар бир хил белгилардан бошланадилар. Шунинг учун чап рекурсияни йўқотилгандан кейин грамматикани LL(1) кўринишгача айлантиришни давом эттириш керак.