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

Aba
Бу ерда а нотерминаллар қатори (бўш бўлиши ҳам мумкин).
Ўз-ўзига юклаш.
Агар G грамматикада А нотерминал бор бўлса, унинг учун
Aa₁ A a₂
(бу ерда a₁ ва a₂ терминалларнинг ёки нотерминалларнинг бўш бўлмаган қаторлари ҳисобланиб), у ҳолда бундай грамматика ҳақида ўз-ўзига юкловчи дейилади. Масалан, қуйида келтирилган иккита грамматикалар ўз-ўзига юклашни амалга оширади:
G₁ = ( {S}, {a,b}, P, S) бу ерда Р нинг элементлари:
S  aSb
S 
G₂ = ({S,A},{begin,end,[,]},P,S) бу ерда Р нинг элементлари:
S  begin A end
S 
A [S]
Охирги ҳолда А ва S ҳақида улар ўз-ўзига юклаш хусусиятига эга деб айтилади. Назарий жиҳатдан ихтиёрий ўз-ўзига юклаш хусусиятига эга бўлмаган контекст-озод грамматика регуляр грамматикага эквивалент ва регуляр тилни генерациялайди. Бошқа томондан регуляр грамматика ўз-ўзига юклашга эга бўла олмайди. Ҳақиқатда ўз-ўзига юклаш контекст-озод грамматикани ва регуляр тилларни фарқлашга имкон беради. Иккинчи мисолдан кўриниб турибдики, қавсларни мослашуви ва х.к. лар ўз-ўзига юкловни талаб этади, шунинг учун уларни регуляр грамматика ёрдамида қуриб бўлмайди.
Таҳлил нуқтаи назаридан контекст-озод тил чекли автоматга эквивалент магазин туридаги автоматни англашга ҳақли бўлиб, унга магазин туридаги хотира қўшилганлиги муҳим. Магазин туридаги автоматнинг функцияларига қуйидагилар киради:
а) кирувчи белгини ўқиш, стекнинг юқори белгисини белгилар қаторига ўзгартириш (бўш бўлиши ҳам мумкин) ва ҳолатни ўзгартириш ёки
в) барчаси юқоридагидек, фақат кирувчи белгини ўқимасдан.
Магазин туридаги автоматни қуйидагича қисқача тасаввур қилиш мумкин.
(К, S, Г, δ , S₀ , Z₀ )
бу ерда К – холатларнинг чекли тўплами,
S –кирувчи алфавит,
Г- магазин алфавити,
δ -ўтишлар тўплами,
S₀ –бошланғич холат,
Z₀ магазин белгиси,
бошланғич холатда у стекда жойлашади.
Қуйидагича аниқланган М магазин туридаги автоматни мисол сифатида кўриб чиқамиз:
К= {A}, S₀ ={A},
S={‘(‘,’)’}, Z₀ =I
Г= {O,I},
δ δ ( A,I,’(‘)=(A,IO) каби берилади.
(бу эса А холатда I билан стек чўққисида ‘(‘ ўқишда А холатга ўтиш кераклигини ва I ни IО га ўзгартиришни билдиради.
δ ( A,О,’(‘)=(A,ОO), δ ( A,О,’)‘)=(A, ), δ ( A,I, )=(A, )
М автомат мос қавсларни англайди. Очилган қавслар стекка жойланади ва мос ёпилган қавс учрагунча у ерда сақланиб, мос қавс учрагандан сўнг у ердан кетади. Қавслар қатори, агар барча қатор ўқилгандан сўнг стек бўш қолса, қабул қилинади. Бу усулни яна қаторларни охирги холатлар бўйича қабул қиладиган магазин типидаги автоматлар ҳам аниқлашлари мумкин. Ушбу икки тур эквивалентдирлар.
Юқорида ифодаланган магазин туридаги автомат детерминирлангандир, яъни ҳар бир мумкин бўлган кирувчи белгига бир қийматли ўтиш мавжуд. Чекли автоматлар холига келсак, биз магазин туридаги берилган кириш учун ўтишлар тўпламига, холатига ва стекка эга детерминирланмаган автоматларни худди шундай аниқлашимиз мумкин.
Таҳлил жараёнида мос магазин туридаги автоматни эффектив моделлаштириш амалга оширилади. Баъзи бир контекст-озод тиллар детерминирланган ҳолда таҳлил қилина олмайди (қайтишсиз). Детерминирланган таҳлилга эга тил детерминирланган тил деб аталади, кўпгина дастурлаш тиллари детерминирлангандир, жуда бўлмаса, шунга яқинроқдирлар.
Контекст-озод грамматика ва магазин туридаги автомат ўртасида тўлиқ мослик мавжуд ва автоматнинг детерминирланганлиги тилни генерация қилиш учун қандай грамматикадан фойдаланилаётганлигига боғлиқ. Таҳлил усули детерминирланган (аниқ грамматика учун) ҳисобланади, агар ушбу грамматиканинг таҳлилиида қайтиш талаб этилмаса. Баъзи бир тилларни грамматик таҳлилнинг фақат биргина усули ёрдамида детерминирланган таҳлил этиш мумкин. Хусусий ҳолда, бир қатор тилларни пастдан юқорига, юқоридан пастга эмас, детерминирланган ҳолда таҳлил қилиш мумкин. Бундан кейин биз таҳлилнинг детерминирланган усулларини қараб ўтамиз. Нодетерминирланган усуллар Фортран каби қаторга мўлжалланган тилларга қўлланиши мумкин. Кучли рекурсив тиллар (С++, Паскаль каби) да компиляторнинг жорий қатордагина орқага қайтиши талаб қилинмай, балки дастурнинг каттагина қисмида ҳам талаб қилинса, детерминирланмаган усулларни қўллаш мумкин бўлмайди. Қайтишнинг бошқа камчилиги шундаки, у компиляторнинг синтаксис таҳлил билан параллел олиб бориладиган харакатларини рад этиши мумкин.