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

4. Грамматик тахлилнинг жадвалли-бошқарув дастурини қуриш.

Жадвалли –бошқарилувчи универсал дастурда аниқ грамматикалар таҳлил қилиниши керак бўлган гапларда кирувчи берилганлар кўринишида берилади. Универсал дастур грамматик таҳлилнинг оддий пастдан чиқувчи усулига мос равишда ишлайди, шу сабабли, агар детерминирланган синтаксис графга асосланган бўлса, у соддадир, яъни гапни қайтишсиз битта белгига аввалдан қараб таҳлил этиш мумкин.
Берилган ҳолда грамматика дастурнинг структурасига эмас, балки берилганларнинг мос келувчи структурасига айлантирилади. Графни тасвирлашнинг табиий усули -бу ҳар бир белги учун тугун киритиш ва ушбу тугунларни кҳрсаткичлар орқали боғлашдир. Бундан кўринадики, «жадвал» бу оддий тўплам эмас. Ушбу структуранинг тугунлари бирлашмаларга (union) бирлаштирилган структуралардан (struct) ташкил топади. Бирлашма тугуннинг тоифасини идентификациялайди. Биринчиси терминал белги билан идентификацияланади ва tsum билан белгиланади, иккинчиси берилганлар структурасига кўрсаткич бўлиб нотерминал nsum га мос келади. Бирлашманинг иккала варианти иккита кўрсаткичга эга: биттаси кейинги белгига кўрсатади, кўрсаткич бўйича (suc) , иккинчиси эса мумкин бўлган альтернативлар рўйхати билан боғлиқ (alt). Граф кўринишида тугунни қуйидагича (15-расм) ифодалаш мумкин.

sum
Alt	Suc

15-расм.
Худди шундай яна бўш кетма-кетликни ифодаловчи элемент керак бўлади, «бўш» белги. Уни қуйидаги empty терминал элемент ёрдамида белгилаймиз.
struct node;
tupedef node *pointer;
struct node {
pointer suc;
pointer alt;
int isTerminal;
union {
char tsum;
hpointer nsum;
};
};

Графни берилганлар структурасига айлантириш қоидалари В1-В7 қоидалар билан бир хил.

Графни берилганлар структурасига айлантириш қоидалари:
С1. Мос ўрнига қўйишлар ёрдамида графлар тизимини мумкин қадар кам сонли алоҳида графларга келтириш.
С2. Қуйида келтирилган С3-С5 қоидаларга мос равишда ҳар бир графни берилганлар структурасига айлантириш.
С3. В3 қоидадаги элементлар кетма-кетлиги қуйидаги (16-расм) тугунлар рўйхатига айлантирилади:

S1		→	S2		→…→	Sn
	*			*			Null