O’zbekiston respublikasi oliy va o`rta maxsus ta’lim vazirligi

2.2.2 Formalizmlar
Sintaktik tahlil jarayonida kontekstdan xoli (KX) grammatikadan foydalanish.
KX grammatika tillar nazariyasining muhim tushunchasi bo’lgan hosil qiluvchi grammatika ga asoslanadi.
Ta’rif: Hosil qiluvchi grammatika (0- tipli grammatika , generative grammar, rewrite grammar) deb shunday G= (N, , P, S) to’rtlikka aytiladiki, u quyidagi shartlarni bajaradi:
N,  - chekli alfavitlar va N   = 
P  (N  )*N(N  )*  (N  )*
S  N
Bu joyda:
N- noterminal simvollar alfaviti;
- terminal simvollar alfaviti;
P- qoidalar(produksiyalar) to’plami
S- bosh noterminal deb ataladi.[2,255]
Kontekstdan xoli grammatika
Ko’pchilik dasturlash tillarining asosiy sintaktik tushunchalari tavsifi shunday grammatika bilan beriladiki, bu grammatika qoidalari to’plamidagi har bir qoidaning chap tomonida faqat bitta noterminal ishlatiladi. Bunday hosil qiluvchi grammatika – kontekstdan xoli grammatika, u aniqlaydigan til esa kontekstdan xoli til deb ataladi. KX grammatika formal quyidagicha ta’riflanadi :
Ta’rif : KX grammatika (kontekstsiz, 2-tipli grammatika , context-free grammar) deb shunday hosil qiluvchi grammatika ga aytiladiki, undagi  qoida A→в ko’rinishida bo’lib, AN, va в(N)* bo’ladi.[2,260]
Misol 1 : G=({S,A,T,U,V},{a,b},P,S), qaysiki
P={
SASTA, ATUT,
SAbA, UTUV,
Aa, UVTV,
bTbb, TVTA
}
hosil qiluvchi, ammo kontekstdan xoli grammatika emas, chunki oxitgi beshta qoida kontekstdan xolilik shartini bajarmaydi.
Ta’rif : Agar satr chiqarishda doimo eng chap tomondagi noterminal almashtirilsa bunday chiqarish chap chiqarish deb ataladi. Agar doimo eng o’ng tomondagi noterminal simvol almashtirilsa bunday chiqarish – o’ng chiqarish deb ataladi.
Misol2: G = ({S,A,B},{a,b}, {S→AB, A→aA|a, B→bB|b}, S) grammatika dagi aaab satr uchun SABaABaaABaaaBaaab – chap chiqarish, SABAbaAbaaAbaaab – o’ng chiqaruv.