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

2.Грамматикалар классификацияси
Нол тур: Фраза структурали грамматика. Коидалар структурасига хеч кандай чегаралар куйилмайди: α→β, бу ерда αєV_­­­⁺, βєV^* - жуфт барчаси грамматикани чикармаган холда. Амалиётда кулланилмайди, V=VTUVN, G(VN,VV,P,S).
Биринчи тур: контекст-боглик: а)кискартирувчи: α₁Aα₂→ α₁βα₂, бу ерда α₁ ва α₂ є V^*, A є VN, β є V⁺. G(VT,VV,P,S) б) кискартирилмайдиган грам: α→β, бу ерда α ва β єV_­­­⁺, |β|>=|α|. Контекс –боглик грамматика коидалари структураси ушбу тил гапларини куриш жараёнида битта нотерминал белги у ёки бу занжирга контексга боглик холда кушилган булиши мумкин ва унда у учрайди: α₁Aα₂→(ёки α₁ , ёки α₂ нолга тенг). Кискартирилмайдиган грамматика: худди шундай структурага эга, лекин A ва β занжирлар узунлиги бир хил. Компиляторларни куриш жараёнида ушбу грамматикадан фойдаланилмайди.
Иккинчи тур: контекст-озод граматика: А→β, бу ерда AєV_­N, βєV⁺(кискартирилмайдиган КБ грам). Кискартириладиган КО: А→β, бу ерда AєV_­N, βєV^*. Коиданинг унг кисмида буш белгилар занжири булиши мумкин.К-О грамматика дастурлаш тилларининг синтаксис конструкцияларини ифодалашда фойдаланилади.
Учинчи тур:Регуляр грамматика: чап чизикли : А→Bγ, А→γ ,бу ерда A ва B єV_­N, γ єVT^*, унг -чизикли: А→γB, А→γ, бу ерда A ва B єV_­N, γ єVT^*. Регуляр грамматика дастурлаш тилларининг оддий конструкцияларини ифодалашда фойдаланилади. Компиляторда унинг асосида кирувчи тилнинг лексик тахлил функциялари курилади.
Энг мураккаб грамматика бу нол грамматикадир. Энг содда 3 тур грамматикасидир.


3.Тиллар классификацияси.
Тур 0: фраза структурали тиллар: 0 грамматика оркали берилган энг мураккаб тилдир. Чекланган захираларда, куп вакт давомида тилнинг гапларини разборини бажара оладиган компиляторни куриш мумкин эмас.Табиий тил компиляторини куриш мумкин эмас.
Тур 1: контекст-боглик тиллар: 1 тур грамматикаси оркали берилади, тилнинг гапларини англаш вакти белгилар занжирининг узунлигига экспоненциал боглик. Матнни таабиий тилга тахлили ва угиришда фойдаланилади.
Тур 2: контекст-озод тиллар: 2 тур грамматикаси оркали берилади, замонавий дастурлаш тиллари синтаксис конструкцияси асосида ётади. Тилни англаш вакти кирувчи занжирнинг узунлигидан полиномиал боглик. Квадратик ёки кубик богликлик булиши мумкин. КО-тиллар дастурлаш тилларнинг синтаксис конструкциялари асосида ётади.
Тур 3: регуляр тиллар: энг оддий, англаш вакти кирувчи занжирнинг узунлигидан чизикли боглик. Дастурлаш тилларининг оддий конструкциялари асосида ётади.