logo

NFX GRAMATIKASIDAGI TAHLIL QILISH UCHUN COCCO-YOUNGERI-KSSAMI ALGARITMI

Загружено в:

08.08.2023

Скачано:

0

Размер:

216.8076171875 KB
O’ZBEKISTON RESPUBLIKASI 
OLIY VA O’RTA-MAXSUS TA’LIM VAZIRLIGI 
SAMARQAND DAVLAT UNIVERSITETI 
RAQAMLI TEXNOLOGIYALAR FAKULTETI
KAMPYUTER ILIMLARI VA DASTURLASH TEXNOLOGIYALARI
YO’NALISHI
“ ALGORITMLAR VA MA’LUMOTLAR STRUKTURASI ”  FANIDAN
“NFX GRAMATIKASIDAGI TAHLIL QILISH   UCHUN COCCO-
YOUNGERI-KSSAMI ALGARITMI”
 MAVZUSIDA TAYYORLAGAN
KURS ISHI
SAMARQAND – 2021
Reja 
Kirish
Asosiy qism:
1 1. Kontekstsiz gramatika 
2. Chomsyening normal shakli
3. Algoritm
   
KIRISH
             Bu kurs   ishi   binominal  koeffitsientlarni  o’rganish  algoritmini  ko’rib  chiqib
o’rgandim   .Bugungi   kunda   ma’lumotlar   oqimining   ko’pligi   tufayli   ularni   qisqa
vaqt   ichidazmashina   buyruqlarini   o’zida   saqlovchi   assembler   tili   yaratildi.
2 Keyinchalik   FORTRAN,   BASIC,   PASKAL   va   COBOL     singari   yuqori   darajali
tillar   ham   paydo   bo’ldiki,   bu   tillar   yordamida   so’z   va   gaplarning   mantiqiy
konstruksiyasidan   foydalanib  algoritmlash  imkoniyati   yaratildi.  Ular  buyruqlarni
mashina   tiliga   interpretatorlar   va   kompilyatorlar   yordamida   o’tkazar   edi.
Algoritmlash tillari yaratilishi bo’yicha uchta turga ajratiladi: -quyi darajadagi; -
o’rta   darajadagi;   -yuqori   darajadagi.   Ma’lumki,   ma’lum   bir   masalani   yechish
uchun buyruqlar  ketma-  ketligi  ya’ni  algoritm algoritmlash  tilida yozilayotganda
kamroq buyruqlardan foydalanilsa, bunday tillar darajasi  yuqoriroq hisoblanadi.
Quyi darajadagi algoritmlash tillari bevosita kompyuter qurilmalari bilan bog’liq
bo’lib,   buyruqlar   ularning   kodlari   bilan   yoziladi.   Bu   kabi   buyruqlardan   tashkil
topgan algoritmlar katta hajmli bo’lib, ularni taxrirlash katta mehnat talab qiladi.
Dastlabki   kompyuterlar(ENIAK,   MESM   va   boshqalar)   ana   shunday   tillarda
ishlagan. O’rta darajadagi algoritmlash tillari buyruqlarida faqat raqamlar emas,
balki insonlar tushunadigan ba’zi so’zlar ishlatila boshlandi(Assemblaer).   
    Yuqori   darajadagi   algoritmlash   tillari   quyidagicha   bosqichlarga   bo’linadi:
Algoritmik(Basic,   Pascal,   C   va   b.)   Mantiqiy(Prolog,   Lisp   va   b.)   Obyektga
mo‘ljallangan(Object Pascal, C++, Java va b.)   Algoritmlash tillarida yaratilgan
algoritmlar   mashina   tiliga   translyatorlar   yordamida   o’tkaziladi.
Translyator(translator-tarjimon)  biror bir algoritmlash  tilida yozilgan algoritmni
mashina   tiliga   tarjima   qiladi.     Translyatorlar   ikki   turda   bo’ladi:         -
Kompilyatorlar(compiler-yig'uvchi)   biror   bir   algoritmlash   tilida   yozilgan
algoritmni   mashina   tiliga   to’liq   o’qib   olib   tarjima   qiladi;       -
Interpretatorlar(interpreter - izohlovchi, og’zaki tarjimon)   biror bir algoritmlash
tilida   yozilgan   algoritmni   mashina   tiliga   satrma   -   satr   tarjima   qiladi.
Translyatorlarni   bu   ikkala   turi   -   bir   biridan   farq   qiladi.   Komplyatsiya   qilingan
algoritmlar   birmuncha   kam   vaqt   talab   etadi,   ya’ni   tezroq   ishlaydi,   lekin
interpretatsiya   qilingan   algoritmlarni   o’zgartirish   osonroq   hisoblanadi.       C++
dasturlash   tili   tarkibida   bir   nechta   imkoniyatlar   mavjud,   ya’ni   consol   rejimi,
forma   ob’yekt   rejimi,   grafik   muhiti   va   ma’lumotlar   bazasi   bilan   ishlash
3 imkoniyatlari   keng   joriy   etilgan.   Ushbu   qo’llanmada   keltirilgan   misol   va
masalalarning   yechimi   dasturining   int   main   funksiyasi   tarkibini   C++   dasturlash
tilinining   ixtiyoriy   versiyalarida   ishlatib   ko’rish   mumkin.   Qo’llanma   oliy   o’quv
yurtlari   talabalari   va   magistrantlari,   litsey,   kasb-hunar   kollejlari   talabalari
hamda mustaqil o’rganuvchilar uchun qulay manba hisoblanadi.
Kontekstsiz grammatika   (   CS-grammatika   ,   kontekstsiz grammatika   ) - rasmiy 
tilni tavsiflash usuli, bu to'rtta, bu erda:
-   alifbo   , uning elementlari   terminallar   deb ataladi   (Eng.   Terminals   )

- elementlari   noterminallar   deb ataladigan to'plam   (Ingliz.   Nonterminals   )

- grammatikaning boshlang'ich belgisi (inglizcha   Boshlash belgisi   )
4 - xulosa qilish qoidalari to'plami (Eng.   A ishlab chiqarish 
qoidalari   yoki   ishlab chiqarishlar   ) turi   , bu erda   ,   ya'ni qaysi chap tomonda- 
yagona nonterminal, va o'ng - terminallar va nonterminallar ketma-ketligi.
Misol  
Terminallar   .   S   =   {   (   ,   )
Noterminallar   .   N=   {   S}
Pul o'tkazish qoidalari   :   P
S→   e
S→   SS
S→   (   S)
Ushbu grammatika   to'g'ri qavs qatorlari   tilini belgilaydi   .   Masalan, ketma-
ketlik   quyidagicha chiqarilishi mumkin:   (   (   )   (   (   )   )   )
S
⇒   (   S)  	⇒   (   SS)  	⇒   (   (   )   (   S)   )  	⇒   (   (   )   (   (   )   )   )
Chomsky normal shakli .
    Chomskiyning   normal shakli KS-grammatikaning normal shakli bo'lib, unda 
barcha mahsulotlar quyidagi shaklga ega:	

A   →   a   bu erda   terminal   bo'lmagan va   terminal AAaa

A   →   BC  Bu erda   ,   ,   - terminal bo'lmagan va   va   boshlang'ich noterminal emas
ABCBC

S→   e  bu erda   dastlabki noterminal va   bo'sh satr (agar tilda bo'sh qator bo'lsa,
bu ishlab chiqarish kerak) Se	

Har   qanday CS grammatikasini Chomskiyning oddiy shakliga 
tushirish   mumkinligini ko'rsatish   mumkin.
Vikipediyadan, bepul ensiklopediya
Sahifaning joriy versiyasi hali tajribali ishtirokchilar   tomonidan   ko'rib
chiqilmagan va 2016 yil 6 yanvarda ko'rib chiqilgan   versiyadan   sezilarli darajada
farq qilishi mumkin ;   tekshiruvlar   10 ta tahrirni   talab qiladi .
Kontekstga bog'liq grammatika   (   KZ-grammatikasi   ,   kontekst grammatikasi
)   rasmiy grammatikaning   maxsus holatidir (   Xomskiy ierarxiyasi   bo'yicha 1-tur   ),
unda barcha ishlab chiqarishlarning chap va o'ng qismlari terminal va terminal 
bo'lmaganlar bilan o'ralgan bo'lishi mumkin. belgilar.
5 Rasmiy grammatikaning alohida holati ham   kontekstsiz grammatikadir   .
KZ-grammatikasi bilan aniqlanishi mumkin bo'lgan til kontekstga bog'liq til yoki 
KZ tili deb ataladi   .
Algoritm  Algoritm Coca-Younger-Kasami   (Engl.   Cocke-Younger-Kasami 
algorithm   , Engl.   CYK algorithm-   ) - algoritm normal shaklda Chomskian 
oldindan belgilangan kontekstsiz grammatika hosila bo'lsa, so'z topish.   Har 
qanday KS-grammatikani NFH ga qisqartirish mumkin, shuning uchun algoritm 
har qanday KS-grammatikasi uchun universaldir.
Muammoni   dinamik dasturlash   orqali hal qilamiz   .   Bir mag'lubiyatga 
hisobga   hajmi   .   Keling, buning uchun bir uch o'lchovli qator yaratish   hajmi   , 
mantiqiy qiymatlar iborat, va   faqat agar agar   pastki olingan mumkin   bitişte 
bo'lmagan dan   grammar qoidalar 
yordamida   .   wnd|   N|   ×n×d[   A   ]   [   i   ]   [   j   ]   =   true Aw   [i   ...   j   ]
Barcha juftlarni ko'rib chiqing   , bu erda   doimiy va   .   {  ⟨   J   ,   i  	⟩   |   j   -   i   =   m   }<n	

i   =   j.   Biz har qanday satr belgisi chiqadigan barcha noterminallar uchun 
massivni ishga tushiramiz   .   Bunday holda   , grammatikada   qoida 
mavjud   bo'lsa   .   Aks holda
wd[   A   ]   [   i   ]   [   i   ]   =   D true   A→w[i]d[   A   ]   [   i   ]   [   i   ]   =   false

i   ≠   j   Barcha noterminallar va juftliklar uchun qiymatlar   allaqachon 
hisoblab chiqilgan, shuning uchun   .   Bu substring, deb   non-terminal olingan
mumkin   mahsulotlar, bir turdagi bor bo'lsa,   va bo'ladi   pastki deb   kelgan 
Derivable   va SUBSTRING   olingan   .
{  	
⟨ j ', i '	⟩   | j '- i '<   m   } d [   A   ]   [   i   ]   [   j   ]   =V
A→BC   V j-i
k=I  d[   B   ]   [   i   ]   [   k   ]  	∧   d [C] 
[k+1]   [j]  w[i…j] A→BC w[i…k] w[k+1…j]
6   1- RASM  
Ishni tugatgandan so'ng, qiymat   berilgan grammatikada berilgan satr 
chiqarilganmi yoki yo'qmi degan savolga javobni o'z ichiga oladi, bu erda 
grammatikaning   boshlang'ich belgisi.   d[   S]   [   1   ]   [   n   ]S
O'zgartirishlar  
So'zni ko'rsatish usullari soni  
Agar massiv butun sonlarni saqlasa va formula bilan almashtirilsa   , u 
holda   -   noterminaldan   pastki   qatorni   olish usullari soni   .  
d [   A   ]   [   i   ]   [   j   ]   =∑¿A→BC	∑k=i
j−1
d[B][i][k]⋅d[C][k+1][j]d[A][i][j]w[i...	j]A
 So'zni chiqarishning minimal qiymati
Qoidaga ko'ra olib   qo'yish   narxi   bo'lsin   .   Agar formula foydalanish bo'lsangiz,   , 
keyin   bir Fransiyani chiqayotgani minimal qiymati hisoblanadi   a bitişte 
bo'lmagan dan   .   H(A→BC)A   →   BCd[   A   ]   [   i   ]   [   j   ]   =	
min
A→	BC  	
min
k=i
(d [   B   ]   [   i   ]   [   k   ]   + d [   C ]   [   k   +   1   ]   [   j   ]   +   H (   A   →   B   C )   )   d [   A   ]   [   i   ]   [   j   ]  
w   [   i   ...   j   ]A
Shunday qilib, Chomskiyning normal shaklidagi CS grammatikasida xulosa 
chiqarish muammosi kichik segmentdagi dinamik dasturlash muammosining 
alohida holatidir. Asimptotiklar
Ko'rish qoidalari   ichida qayta ishlanadi   .   A→w[i]O   (   n  	
⋅   |   D   |   )  Barcha pastki 
qatorlar ichida takrorlanadi   .   Bitta pastki qatorni qayta ishlashda barcha chiqish 
qoidalari va ikkita pastki qatorga bo'lingan barcha bo'linishlar uchun tsikl 
mavjud, shuning uchun ishlov berish   .   Natijada, biz yakuniy murakkablikni 
olamiz   .  
7 O(n 2
)
O(n⋅ |D|)
O(n 3
⋅
|D|)
Shuning uchun algoritmning umumiy ishlash vaqti   .   Bundan tashqari, 
algoritm   o'lchamli   massiv uchun xotirani talab qiladi   , bu 
erda   grammatikadagi   terminal bo'lmaganlar   soni   .   O   (n 3	
⋅
  |   D   |   )dO   (n 2	⋅
  |   N|   ) N|
Ishga misol  
Chomskiy normal shakldagi   to'g'ri qavs ketma-
ketliklarining   grammatikasi   berilgan.
  DA   →   e   |   B   B   |   C         DB   →   B   B   |   C     DC→   (D   →   B   E   |   )   E→   )  So'z 
berildi   .   w   =   (   )   (   (   )   )
A
bit
ta 2 3 4 be
sh 6
bit
ta
2
3
4
be
sh
6
B
bit
ta 2 3 4 be
sh 6
8 bit
ta
2
3
4
be
sh
6
C
bit
ta 2 3 4 be
sh 6
bit
ta ●
2
3 ●
4 ●
be
sh
6
D
9 bit
ta 2 3 4 be
sh 6
bit
ta
2 ●
3
4
be
sh ●
6 ●
E
bitt
a 2 3 4 bes
h 6
bitt
a
2 ●
3
4
bes
h ●
6 ●
10 .
 Tabiiy tillar uchun tahlil qilish.   2-qism: Kok-Younger-Kasami (CYK) 
algoritmi
Ideal holda, biz matnni chiziqli vaqt va bitta o'tishda tahlil qilishni 
xohlaymiz.   Oddiy iboralar bunga imkon beradi, lekin bu CFG bilan ishlamaydi: 
masalan,     S → A | B; A → a | x A; B → b | x B   u satrni     x…xa   tugunlar 
daraxtiga     A va satrni     x…xb   tugunlar daraxtiga aylantiradi.   B   - va parser 
satrning oxirgi belgisini ko'rmaguncha, u avvalgi barcha belgilar bilan nima 
qilishni bilmaydi.   Shuning uchun, dasturlash tillari uchun grammatikaga 
qo'shimcha cheklovlar qo'yiladi - aslida siz tahlil qilish uchun "oldinga 
qarashingiz" shart emas - bu sizga dastur matnini bir martalik tahlil qilish 
imkonini beradi.   Kompilyatorlar bilan shug'ullangan har bir kishi, ehtimol, LL- va
LR-parsing bilan tanish bo'lishi mumkin va til grammatikasini ma'lum bir tahlil 
qilish algoritmi talablariga "moslashtirish" tajribasiga ega.   Ammo tabiiy tillar 
bilan ishlashda, tahlil qilish qulayligi uchun tilni "to'g'rilash" imkoni yo'q - siz til 
bilan qanday bo'lsa, shunday ishlashingiz kerak.
1960-yillarda ixtiyoriy CFGni tahlil qilish uchun CYK algoritmi ishlab 
chiqilgan.   U birinchi marta nashr etilgan - bir-biridan mustaqil ravishda - 1961 
yilda Mudofaa vazirligining Yaponiya tadqiqot institutidan I. Sakai va 1962 yilda 
Nyu-York universitetidan J. Kok tomonidan nashr etilgan. 1966 yilda xuddi shu 
algoritm nashr etilgan - yana mustaqil ravishda - General Electricdan D. Younger
va Illinoys Universitetidan T. Kasami tomonidan.   Yoshroq o'z nashrida Ko'ka va 
Sakay nomlarini tilga oladi, lekin ularning biron bir aniq asariga ishora qilmaydi:
aftidan, Koka va Sakayning ishi Yoshga - hozir men kabi - mavjud emas 
edi.   Algoritm ixtirochilarining hech biri xafa bo'lmasligi uchun u bir vaqtning 
o'zida uchta odam sharafiga nomlangan, garchi ular bir-birini tanimasa ham.
CYK g'oyasi "pastdan yuqoriga" - terminallardan S gacha - tahlil qilish va qayta 
hisob-kitoblarga yo'l qo'ymaslik uchun dinamik dasturlashdan foydalanishdir: 
birinchidan, biz barcha tugunlarni to'g'ridan-to'g'ri terminallardan tuzamiz va 
ularni "bortga" joylashtiramiz.   Algoritmning har bir bosqichida biz doskadan 
bitta tugunni olamiz, uning ishtirokida barcha mumkin bo'lgan tugunlarni tuzamiz 
va ularni ham doskaga qo'shamiz.   Agar butun matn uchun doskada S paydo 
bo'lsa, unda tahlil muvaffaqiyatli bo'ldi;   agar taxtadagi barcha tugunlar qayta 
ishlansa, lekin S u erda hech qachon paydo bo'lmasa, tahlil qilish muvaffaqiyatsiz 
tugadi.   Misol tariqasida, Vikipediya   quyidagi grammatikaga muvofiq "   U baliqni 
vilka bilan yeydi " jumlasini tahlil qiladi:
11 S → NP VP
VP → VP PP | V NP | V
PP → P NP
NP → Det N | she
V → eats
P → with
N → fish | fork
Det → a | the
Qada
m Doskada xom 
tugunlar Kengashda qayta ishlangan 
tugunlar Kengashga 
qo'shilgan 
tugunlar
bitta U  
NP ,   V   ,  
Det   , 
baliq  
N   ,  
P   , 
bir  
Det   , 
sanchqi  
N 
bilan   ovqatlana
di .
2 U  
NP ,   V   ,  
Det   , 
baliq  
N   ,  
P   , 
bir  
Det   , sanchqi  
N 
bilan   ovqatlanadi .
3 yeydi  
V   , the  
Det   , 
baliq  
N   , bilan  
P   , 
bir  
Det   , sanchqi  
N U  
NP VP   yeydi
4
Det   ,   baliq  
N   ,  
P 
bilan   , bir  
Det   , 
sanchqi  
N   ,  
  VP   yey
di U  
NP ,   V   yeydi [   baliq   ]  
NP
12 5, 6 baliq  
N   ,  
P   bilan , 
bir  
Det   , 
sanchqi  
N   ,  
  VP   yey
di   , [   baliq   ]
  NP U  
NP   , yeb  
V   ,  
Det
7 a  
Det   , 
sanchqi  
N   ,  
  VP   eb  
, [   baliq   ]
  NP U  
NP ,   P   bilan  
V   ,  
Det   , baliq  
N ,   eydi [   vilkalar   ]  
N
P
8 sanchqi  
N   ,  
  VP   yey
di   , [   baliq   ]
  NP   , 
[   vilka   ]
  NP U  
NP ,   V   ,  
Det   , baliq  
N   ni ,  
P   , a  
Det 
bilan   ovqatlanadi
to'qqi
z VP   , [   baliq   ]
  NP   , 
[   vilkalar   ]
  NP   yey
di U  
NP ,   V   ,  
Det   , baliq  
N   ,  
P   , bir  
Det   , 
sanchqi  
N bilan   ovqatlanadi . [   U 
ovqatlanadi   ]  
S
10 [   baliq   ]  
NP   , 
[   sanchqi   ]  
NP   , 
[   u yeydi   ]  
S U  
NP   ,    
V   ,  
Det   , baliq  
N   ,  
P bilan   , 
bir  
Det   , vilka  
N   ,  
VP   yeydi . [   baliq 
yeydi   ]  
VP
o'n 
bir [   sanchqi   ]  
NP   , 
[   u yeydi   ]  
S   , 
[   baliqni 
yeydi   ]  
VP U  
NP   ,  
V   ,  
Det     ,     baliq  
N   ,  
P   bilan   ,    
bir  
Det   , 
vilka  
N   ,  
VP   ,   [   baliq   ]  
NP     yeydi .   [   vilka 
bilan   ]  
PP
12 [   U yeydi   ]  
S   , 
[   baliq 
yeydi   ]  
VP   , 
[   sanchqi 
bilan   ]  
PP U  
NP   ,  
V   ,  
Det     ,     baliq  
N   ,  
P   bilan   , 
bir  
Det   , vilka  
N   ,  
VP   ,   [   baliq   ]  
NP   , 
[   vilka   ]  
NP     yeydi .   [   U baliq 
yeydi   ]  
S
13 [   baliq 
yeydi   ]  
VP   , 
[   sanchqi 
bilan   ]  
PP   , 
[   baliqni yeydi   ]  
S U  
NP   ,  
V   ,  
Det     ,     baliq  
N   ,  
P   bilan   ,  
Det   , vilka  
N   ,  
VP   ,   [   baliq   ]  
NP   , 
[   vilka   ]  
NP,     [   U     yeydi   ]  
S   [   baliqni 
vilka bilan 
yeydi   ]  
VP
14, 15 [   sanchqi bilan   ]   PP   , 
[   U baliq yeydi   ]   S   , 
[   baliqni vilka bilan 
yeydi   ]   VP U   NP   ,   V   ,     Det     ,     baliq   N   ,   P   bilan   ,   Det   , 
sanchqi   N   ,   VP   ,   [   baliq   ]   NP   , 
[   vilka   ]   NP,     [   U Eydi   ]   S   ,   [   baliqni vilka 
bilan yeydi   ]   VP  
16 [   baliqni vilka 
bilan yeydi   ]  
VP U  
NP   ,
  V   ,     Det     ,     baliq  
N   ,
  P   bilan  
,  
Det   , sanchqi  
N   ,  
VP   ,[   baliq   ]
  NP   , 
[   vilka   ]
  NP,     [   U  [   U baliqni 
vilka bilan 
yeydi   ]  
S
13 Eydi  
]   S
  ,   [   baliqni vilka bilan 
yeydi   ]
  VP   , [   vilka bilan   ]
  PP   , [   U 
baliq yeydi   ]
  S  
CFG uchun CYK qiyinligi qanday?   Doskada eng ko'p       tugunlar bo'lishi 
mumkin - har bir terminal bo'lmagan belgi va kiritilgan matnning har bir pastki 
qatori uchun;   shuning uchun taxtani uch o'lchovli massiv sifatida saqlash qulay, 
uning indekslari terminal bo'lmagan, pastki qatorning boshi va pastki qatorning 
oxiri.   Har bir bosqichda doskadan bitta tugun qayta ishlanadi, ya'ni tahlil qilish 
uchun       qadamlar kerak bo'ladi.   Har bir bosqichda barcha grammatika 
qoidalari tekshiriladi va qayta ishlangan tugun o'ng tomonga mos keladigan har 
bir qoida uchun ishlov berilgan tugun bilan birga o'ng tomonda ishtirok etishi 
mumkin bo'lgan kengashning barcha tugunlari tekshiriladi.   Bunday qadamning 
murakkabligini aniqlash uchun qoladi.
Asl CYK algoritmi     Chomsky Normal Form     (CNF) da CFGlar bilan ishlagan - 
har bir xulosa qoidasining o'ng tomonida bitta terminal yoki ikkita terminal 
bo'lmagan terminalga ruxsat berilgan.   Qoida uchun     A → BC   "taxtadan o'ng 
tomonda qayta ishlangan tugun bilan birga ishtirok etishi mumkin bo'lgan barcha 
tugunlar" - bu       indeksli tugunlarning maksimal (C, end  
B   , ?) va/yoki      
indeksli tugunlarning maksimali sifatida.   (B, ?,  
C   boshlang ).   (Agar B=C bo'lsa, 
ikkala variant ham mos keladi.) Ma'lum bo'lishicha, CNF uchun bitta CYK 
qadamining     murakkabligi , butun tahlil qilishning murakkabligi esa     .
Va agar CFG CNFda bo'lmasa?   Qoida uchun     A → BCD   siz ishlov berishingiz 
kerak bo'ladi:
indeksli tugunlarning maksimali sifatida       (C, end  
B   , ?), va ularning 
har biri uchun       indeksli tugunlarning maksimali sifatida (D, end  
C   , ?);

indekslari (B,?, start C   ) va (D, end  
C   ,?) bilan tugunlarning   maksimal       juftligi 
sifatida ;

indeksli tugunlarning maksimali       (C, ?, start  
D   ) va ularning har biri 
uchun       indeksli tugunlarning maksimali (B, ?, start  
C   ).
Bu shuni anglatadiki, agar xulosa qilish qoidasining o'ng tomonida uchtagacha 
terminal bo'lmaganlarga ruxsat berilsa, u holda bitta CYK qadamining    
murakkabligi , butun tahlil qilishning murakkabligi esa bo'ladi    
.   O'zboshimchalik bilan CFG ni umumlashtirgan holda, biz CYK yordamida tahlil 
14 qilishning murakkabligini ko'ramiz ,     bu erda       xulosa qilish 
qoidalarining o'ng qismining maksimal uzunligi («grammatik daraja»).
Endi biz MCFG uchun CYK ni uning markaziy g'oyasini saqlab qolgan holda 
umumlashtiramiz: algoritmning har bir bosqichida biz doskadan bitta tugunni 
olamiz, uning ishtirokida barcha mumkin bo'lgan tugunlarni tuzamiz va ularni 
doskaga qo'shamiz.   Tahlil qilish "   Men sizdan bolalarga yordam berishingizni 
so'radim!   " 1-qismda berilgan va qulaylik uchun bu erda takrorlangan 
grammatikaga ko'ra, shunday bo'ladi:
VP(X,Y) ← NP(X),V(Y)
CP(X,Y) ← VP(X,Y)
VP(X,YZW) ← NP(X),V(Z),CP(Y,W)
S(XYZ) ← NP(X),VP(Y,Z)
NP( я ) ←  ε
NP( тебя ) ←  ε
NP(детям) ← ε
V(просил) ← ε
V(помочь) ← ε
Q
ad
a
m Xom tugunlar Qayta ishlangan
tugunlar Qo'shilgan tugunlar
bi
tt
a Men  
NP   ,   siz  
NP   ,   bolal
ar  
NP   ,  
V   so'radi   ,  
V   yo
rdam bering
2- Men  
NP   ,   siz  
NP   ,   bolalar  
NP  
15 4 ,  
V   so'radi   ,  
V   yordam 
bering
be
sh so'radi  
V   ,   yordam  
V Men  
NP   ,   siz  
NP   ,  
bolalar  
NP (   Men   so'radim   )  
VP   ,  
(   sizdan   so'radi   )  
VP   ,  
(   so'radi   bolalar   )  
VP  
_
6 yordam  
V   , 
(   men   ,   so'radi   )
  VP   , 
(   siz   ,   so'radi   )
  VP   , 
(   bolalar   ,   so'radi   )
  VP Men  
NPman   ,   siz  
N
P   ,   bolalar  
NP   ,   d
eb so'radi  
V (   Men   ,   yordam   )  
VP   , 
(   siz   ,   yordam   )  
VP   , 
(   bolalar   ,   yordam   )  
V
P
7, 
8 (   Men   ,   so'radi   )  
VP   , 
(   siz   ,   so'radi   )  
VP   , 
(   bolalar   ,   so'radi   )  
VP   , 
(   men   ,   yordam   )  
VP   , 
(   siz   ,   yordam   )  
VP   , 
(   bolalar   ,   yordam   )  
VP Men  
NP   ,   siz  
NP   ,  
bolalar  
NP   ,  
V   so'
radi   ,  
V   yordam 
bering (   Men   so'radim   )  
CP   ,  
(   sizdan   so'radim   )  
CP  
_
to'
qq
iz (   bolalar   ,   so'radi   )  
VP   , 
(   men   ,   yordam   )  
VP   , 
(   siz   ,   yordam   )  
VP   , 
(   bolalar   ,   yordam   )  
VP   , 
(   men   ,   so'radi   )  
CP   , 
(   siz   ,   so'radi   )  
CP Men  
NP   ,   siz  
NP   ,  
bolalar  
NP   ,   so'r
adi  
V   ,   yordam  
V  
, 
(   men   ,   so'radi   )  
VP   ,   (   sizdan   so'r
adi   )  
VP [   bolalar 
so'radi   ]  
S   ,   (   bolalar  
so'radi   )  
CP
10
-
12 VP   _   _   _   _  
_   _   _   _   _   _  
_   _  
_   _   _   _  
_   _   _   _   _   _  
_   _   _  
_   _   _  
_   _   ___   _   _  
_   _   _   _  
_  
_ Men  
NP   ,   siz  
NP   ,  
bolalar  
NP   ,   so'r
adi  
V   ,   yordam  
V  
, 
(   men   ,   so'radi   )  
VP   , 
(   siz   ,   so'radi   )  
V
P   , 
(   bolalar   ,   so'ra
di   )  
VP (   Men   ,   yordam   )  
CP   , 
(   siz   ,   yordam   )  
CP   , 
(   bolalar   ,   yordam   )  
C
P
13 CP   _____   _   _   _  
_   _   _   _   _   Men  
NP   ,   siz  
NP   ,  
16 -
18 _  
_   _   _   _  
_   _   _   _   _   _  
_   _   _  
_   _   _  
_   _   _   _   _   _  
_   _   _   _  
_   _  
_ bolalar  
NP   ,   so'r
adi  
V   ,   yordam  
V  
, 
(   men   ,   so'radi   )  
VP   ,   (   sizdan   so'r
adi   )  
VP   , 
(   bolalar   ,   so'ra
di   )  
VP   , ...
19 (   bolalar   ,   yordam   )  
CP Men  
NP   ,   siz  
NP   ,  
bolalar  
NP   ,   so'r
adi  
V   ,   yordam  
V  
, 
(   men   ,   so'radi   )  
VP   , ... (   siz   , [   bolalar 
yordam berishni 
so'rashdi   ])  
VP
yi
gi
r
m
a (   siz   , [   bolalar yordam 
berishni so'rashdi   ])  
VP Men  
NP   ,   siz  
NP   ,  
bolalar  
NP   ,   so'r
adi  
V   ,   yordam  
V  
, 
(   men   ,   so'radi   )  
VP   , ... [   Bolalarga yordam 
berishingizni iltimos 
qildim   ]  
S
Bunday tahlilni qanday amalga oshirish kerak va uning murakkabligi qanday 
bo'ladi?   Uch o'lchovli taxta endi etarli emas: VP va CP kabi 2 o'rinli predikat 
tugunlari kiritilgan matnning har qanday pastki qatorlari uchun mavjud bo'lishi 
mumkin, shuning uchun beshlik bilan indekslash talab qilinadi (terminal 
bo'lmagan, start  
1   , end  
1   , start  
2   , oxiri  
2   ).   Buning o'zi tahlil qilish bosqichlari 
sonini ko'taradi   .   Endi biz bunday besh o'lchovli taxtaning qaysi tugunlari 
ishlov berilayotgan tugun bilan birgalikda xulosa qilish qoidasini qo'llashda 
ishtirok etishi mumkinligini tushunishimiz kerak - masalan,   P(XY,ZW) ← 
P(X,Z),P(Y,W) 1-qismda berilgan ikki marta takrorlangan satrlar tili grammatikasi
qoidalari.   Mos keladigan tugunlar indekslarda (P, end  
X   , ?, end  
Z   , ?) va (P, ?, 
start  
Y ) bo‘ladi. , ?,  
W   boshlang ), shuning uchun   ulardan 1 tasi 
bo'ladi.   "Grammatikaning o'lchami" 2 (ya'ni, eng ko'p ikki o'rinli predikatlar) va 
uning darajasi ham 2 (ya'ni, xulosa qilish qoidalari maksimal ikkita o'zgaruvchi 
sifatida birlashtirishga imkon beradi) deb faraz qilsak, biz murakkablikni olamiz. 
CYK tahlili bo'ladi   .
17 Va agar yuqoridagi grammatikada bo'lgani kabi daraja yuqoriroq bo'lsa, qoida 
qayerda   VP(X,YZW) ← NP(X),V(Z),CP(Y,W) uchta o'zgaruvchini birlashtirishni 
o'z ichiga oladi?   Bunday holda, V uchun mos tugunlar indekslarda joylashgan 
bo'ladi (CP, ?, start  
Z   , end  
Z   , ?) va (NP, ?, ?, ∅ , 	∅ ), shuning uchun 
allaqachon   bo'laklar bo'ladi.   Xuddi shunday, NP uchun mos tugunlar 
indekslar (CP, ?, ?, ?, ?) va (V, end  
Y   , start  
W   , 	
∅ , 	∅ ) bo'yicha joylashadi va  
ularning qismlari ham bo'ladi.   Bosqichlar har biri murakkablik   bilan 
olinadi   .   Tahlil qilish misolida juda ko'p foydasiz qadamlar ham seziladi: 
uchta NP va ikkita V mavjud bo'lgan jumlada ularning har bir juft kombinatsiyasi 
VP va CP tugunlari tomonidan chiqariladi.
Umuman olganda, tahlil qilish algoritmi polinom bo'lib qolayotganini ko'rish 
mumkin, lekin grammatika murakkablashgani sayin ko'rsatkich tez o'sib boradi: 
yuqoridagi fikrni umumlashtirib, biz murakkablikni olamiz   , bu erda      
grammatika o'lchami.   Bu shuni anglatadiki, ikkitadan ortiq o'zgaruvchilarni 
birlashtirishni yangi terminal bo'lmagan, masalan,   VP(X,YZW) ← 
NP(X),V(Z),CP(Y,W) bir juft qoidalar qoidasi bilan almashtirish orqali tahlil 
qilishni sezilarli darajada soddalashtirish mumkin   CP'(Y,ZW) ← V(Z),CP(Y,W); 
VP(X,YZ) ← NP(X),CP'(Y,Z) .   Shu tarzda olingan parse daraxti gap tuzilishining 
nazariy tavsifidan uzoqroq, ammo shunga qaramay, grammatikalarning bunday 
"normalizatsiyasi" keng qo'llaniladi.
1-qismda ta'kidlanganidek, tabiiy tillardagi matnlar ko'pincha bir nechta mumkin 
bo'lgan tahlillarga imkon beradi va bu mumkin bo'lgan tahlillar orasidan eng 
ehtimoliyini tanlash talab qilinadi.   Eng frontal yechim har bir xulosa chiqarish 
qoidasiga (masalan,   VP(X,Y) ← 75% NP(X),V(Y); VP(X,YZW) ← 25% 
NP(X),V(Z),CP(Y,W) bunday ehtimolli grammatika PMCFG deb ataladi) 
ehtimollik belgilashdir, keyin esa tahlil qilish ehtimoli unda qo’llaniladigan 
barcha xulosa chiqarish qoidalarining ehtimolliklari hosilasi 
hisoblanadi.   Ularning logarifmlari bilan ishlash mikroskopik ehtimollarga 
qaraganda ancha qulayroqdir: keyin ehtimolliklarni ko'paytirish ularning 
logarifmlarini qo'shish bilan almashtiriladi.
Xulosa qilib aytganda, men Python-da PMCFG uchun CYK-ni amalga oshirishim 
bilan o'rtoqlashaman, bu amalda qo'llaniladi (5 soniya ichida 10 so'zgacha 
jumlalarni tahlil qilish kerak edi)   , lekin bu cheklovlardan tashqarida 
ishlashga qodir.   Kengash uchun o'lchovli massiv o'rniga   men ikki darajalidan
foydalanaman,   dict unda birinchi darajali kalitlar terminal bo'lmagan, ikkinchisi 
ob'ektlar   Chunk va qiymatlar ehtimollik logarifmlari.   Terminal bo'lmagan va 
18 pastki qatorlar to'plamining har bir kombinatsiyasi uchun faqat bitta nusxa 
bo'lishi mumkin   Chunk , shuning uchun ob'ektlarni solishtirish uchun ularni 
solishtirish kifoya - bu   oddiy yozuvdan (ma'lumotlar klassi) foydalanishga 
nisbatan   id qidiruvni bir necha baravar tezlashtiradi.   dict kalit sifatida.
class   Chunk :
    instances = {}
     def   __new__ (cls, symbol, inputs) :
        key = symbol, tuple(inputs)
        i = cls.instances.get(key)
         if  i:
            return  i
        i = super(Chunk, cls).__new__(cls)
        i.symbol = symbol
        i.inputs = inputs
        cls.instances[key] = i
         return  i
def   parse (grammar, string) :
19     chart = {n: {}  for  n  in  grammar.non_terminals}
    agenda = {Chunk(rule.left.symbol, [(i, i +  1 )]): rule.prob
               for  i  in  range(len(string))  for  rule  in  grammar.rules
               if  rule.terminating  and  rule.left.inputs[ 0 ] == string[i]}
    goal = Chunk(grammar.start, [( 0 , len(string))])
     while  agenda  and  goal  not   in  chart[grammar.start]:
        (best, prob) = max(agenda.items(), key= lambda  x: x[ 1 ])
        chart[best.symbol][best] = prob
         del  agenda[best]
         for  rule  in  grammar.rules:
             if   not  rule.terminating  and  any(best.symbol == prod.symbol  for  prod  in  
rule.right):
                right = list(rule.right)
                 for  perm  in  itertools.product(*(chart[prod.symbol].keys()  for  prod  in  
right)):
                     if  best  in  perm:
                        sat = satisfies(perm, rule.left, right, chart)
                         if  sat  is   not   None :
                            chunk = sat[ 0 ]
20                             new_prob = sat[ 1 ] + rule.prob
                             if  (chunk  not   in  chart[chunk.symbol])  and  \
                               ((chunk  not   in  agenda)  or  (agenda[chunk] != new_prob)):
                                agenda[chunk] = new_prob
     return  chart[grammar.start].get(goal)
def   satisfies (perm, left, right, chart) :
    mapping = {}
    prob =  0
     for  chunk, pred  in  zip(perm, right):
         for  c_i, p_i  in  zip(chunk.inputs, pred.inputs):
            mapping[p_i] = c_i
        prob += chart[chunk.symbol][chunk]
    inputs = []
     for  r  in  left.inputs:
         if  len(r) ==  1 :
21             inputs.append(mapping[r])
         else :
            mapped = [mapping[c]  for  c  in  r]
             for  k  in  range(len(mapped) -  1 ):
                 if  mapped[k][ 1 ] != mapped[k +  1 ][ 0 ]:
                     return   None
            inputs.append((mapped[ 0 ][ 0 ], mapped[ -1 ][ 1 ]))
     if  len(inputs) >  1 :
         for  i  in  range(len(inputs) -  1 ):
             if  inputs[i][ 1 ] > inputs[i +  1 ][ 0 ]:
                 return   None
     return  Chunk(left.symbol, inputs), prob
Ko'proq kuzatuvchilar shuni ta'kidlashadiki, bu amalga oshirish faqat   N(t) ← 
ε CNF ga o'xshash shakl qoidalarida terminallarga ruxsat beradi.   Bu qisman har 
bir so'zni uning ishtirokida sintaktik tuzilmalarni tuzishdan oldin 
turkumlashtirishni buyuradigan an'anaga hurmatdir.
Kontekstga bog'liq grammatika   (   KZ-grammatikasi   ,   kontekst 
grammatikasi )   rasmiy grammatikaning   maxsus holatidir (   Xomskiy 
ierarxiyasi   bo'yicha 1-tur   ), unda barcha ishlab chiqarishlarning chap va o'ng 
22 qismlari terminal va terminal bo'lmaganlar bilan o'ralgan bo'lishi mumkin. 
belgilar.
Rasmiy grammatikaning alohida holati ham   kontekstsiz grammatikadir   .
KZ-grammatikasi bilan aniqlanishi mumkin bo'lgan til kontekstga bog'liq til yoki 
KZ tili deb ataladi   .
Rasmiy grammatika G=(N, T, I, P) kontekstga sezgir bo‘ladi, agar barcha P 
qoidalari quyidagi ko‘rinishd a  bo‘lsa: aAb → ažb
Bu erda A ∈  N (ya'ni bitta terminal bo'lmagan belgi), ō 	∈  (N 	∪  T)   +
  (ya'ni 
terminal va/yoki terminal bo'lmagan   belgilardan iborat bo'sh bo'lmagan qator), a, 
b 	
∈  ( N 	∪  T)* (ya'ni terminal va/yoki terminal bo'lmagan belgilardan iborat har 
qanday satr).	

 so'zlarida bevo  Rasmiy tillar nazariyasida   rasmiy grammatika   yoki 
oddiy   grammatika - bu   rasmiy tilni     tavsiflash usuli, ya'ni   ba'zi 
chekli   alifboning barcha so'zlari   to'plamidan   ma'lum bir 
kichik   to'plamni   tanlash .   Generativ   va   tanib   oluvchi (yoki   analitik   ) 
grammatikalar mavjud   - birinchisi, siz tilning istalgan so'zini yaratishingiz 
mumkin bo'lgan qoidalarni o'rnatasiz, ikkinchisi esa ma'lum bir so'zdan uning 
tilga kiritilgan yoki yo'qligini aniqlashga imkon beradi.   Terminal (terminal 
belgisi)     grammatikaga mos keladigan tilning sita mavjud bo'lgan va o'ziga 
xos, o'zgarmas ma'noga ega bo'lgan ob'ektdir ("harflar" tushunchasining 
umumlashtirilishi).   Kompyuterda ishlatiladigan rasmiy tillarda odatda 
ASCII   standart belgilarining hammasi yoki bir qismi    - lotin harflari, raqamlar
va maxsus belgilar   terminal sifatida qabul qilinadi .

Terminal bo'lmagan (terminal bo'lmagan belgi)     - bu qandaydir til borligini 
bildiruvchi ob'ekt   (   masalan: formula, arifmetik ifoda, buyruq) va o'ziga xos 
ramziy qiymatga ega emas.
Generativ grammatikalar
Grammatika tomonidan berilgan tilning so'zlari chiqish qoidalariga ko'ra 
dastlabki noterminaldan chiqadigan (hosil qilingan) terminallarning barcha 
ketma-ketligidir.
Grammatikani o'rnatish uchun siz terminallar va terminal bo'lmaganlar alifbosini,
xulosa qilish qoidalari to'plamini o'rnatishingiz kerak, shuningdek, terminal 
bo'lmaganlar to'plamida boshlang'ichni tanlashingiz kerak.
Shunday qilib, grammatika quyidagi xususiyatlar bilan belgilanadi:
23 — terminal belgilar     to'plami (   alfavit ).

N - terminal bo'lmagan belgilar   to'plami (   alifbo ).

P - shakl qoidalari to'plami: "chap tomon" "o'ng tomon", bu erda:
o "chap tomon" - kamida bitta terminal bo'lmagan terminallarni o'z ichiga 
olgan bo'sh bo'lmagan terminallar va terminallar ketma-ketligi
o "o'ng tomon" - terminallar va terminal bo'lmagan har qanday ketma-ketlik

S - terminal bo'lmaganlar to'plamidan grammatikaning boshlang'ich (yoki 
boshlang'ich) belgisi.
Xulosa  
Chiqish terminallar va terminal bo'lmaganlardan tashkil topgan qatorlar ketma-
ketligi bo'lib, bunda birinchi qator bitta boshlang'ich noterminaldan iborat bo'lib, 
har bir keyingi qator oldingisidan ba'zi bir pastki qatorni bitta (har qanday) ga 
almashtirish orqali olinadi. qoidalardan.   Yakuniy satr butunlay terminallardan 
tashkil topgan qatordir va shuning uchun tilning so'zidir.
Muayyan so‘z uchun hosila mavjudligi uning berilgan grammatika bilan 
belgilangan tilga tegishliligi mezoni hisoblanadi.
Grammatika turlari  
Chomskiy ierarxiyasiga   ko'ra   , grammatika 4 turga bo'linadi, har bir keyingisi 
avvalgisining cheklangan kichik qismidir (lekin tahlil qilish ham osonroq):

turi 0.   cheksiz grammatika     - har qanday qoidalar mumkin

1   -tur. kontekstga sezgir grammatikalar     - chap qismda "kontekst" bilan 
o'ralgan bitta terminal bo'lmagan (o'ng qismda bir xil shaklda mavjud bo'lgan 
belgilar ketma-ketligi) bo'lishi mumkin;   terminal bo'lmagan o'zi o'ng tomonda 
bo'sh bo'lmagan belgilar ketma-ketligi bilan almashtiriladi.

tip 2.   kontekstsiz grammatikalar     — chap qism bitta terminal bo‘lmagandan 
iborat.

3-tur.   muntazam grammatikalar     soddaroq,   chekli avtomatlarga   ekvivalent .
Bundan tashqari, quyidagilar mavjud:

Qisqartirmaydigan grammatika   .   Bunday grammatikaning har bir qoidasi 
shaklga ega , qayerda .   Qoidaning o'ng tomonining uzunligi chapning 
uzunligidan kam emas   [1]
  .

Chiziqli grammatikalar   .   Bunday grammatikaning har bir qoidasi shaklga ega ,
yoki , ya'ni qoidaning o'ng tomonida noterminalning ko'pi bilan bitta hodisasi 
bo'lishi mumkin   [2]
  .
Ilova  
24 Kontekstsiz   grammatikalar grammatik tahlilda   grammatik tuzilmani aniqlash 
uchun keng qo'llaniladi   .

Muntazam grammatika   (   muntazam iboralar   shaklida ) matnni qidirish, 
qismlarga ajratish va almashtirish uchun shablon sifatida keng qo'llaniladi, 
shu jumladan   leksik tahlilda   .
Misol sifatida arifmetik ifodalar  
Tabiiy sonlar   ,   qavslar   va arifmetik belgilardan   iborat cheklangan arifmetik 
formulalar to'plamini belgilaydigan oddiy tilni ko'rib chiqing .   Shuni ta'kidlash 
kerakki, bu erda har bir qoidada o'qning chap tomonida joylashgan faqat bitta 
terminal bo'lmagan belgi mavjud.   Bunday grammatikalar   kontekstsiz   deb ataladi .
Terminal alifbosi:
= {'0','1','2','3','4','5','6','7','8','9','+','-', '*','/','(',')'}
Terminal bo'lmagan alifbo:
  { FORMULA, BELGI, NUMBER, NUMBER}
Qoidalar:
1. FORMULA
FORMULA BELGI FORMULA                 (formula belgi bilan bog'langan 
ikkita formuladir)
2. FORMULA
NUMBER                                (formula raqam)
3. FORMULA
( FORMULA )                          (formula qavs ichidagi formuladir)
4. BELGI
+ | - | * | /                          (belgisi ortiqcha yoki minus, ko'paytirish yoki 
bo'linish)
5. NUMBER
NUMBER                                  (raqam bu raqam)
6. NUMBER
25 RAQAM DIGITAL                            (raqam bu raqam va raqam)
7. NUMBER
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (raqam 0 yoki 1 yoki ... 9)
Dastlabki terminal bo'lmagan:
FORMULA :
Keltirilgan xulosa qoidalaridan foydalanib   (12+5)   formulani chiqaramiz .   Aniqlik
uchun har bir almashtirishning yon tomonlari juft bo'lib ko'rsatilgan, har bir 
juftlikda almashtirilgan qismning tagiga chizilgan.
FORMULA     (FORMULA)
(   FORMULA   ) (   FORMULA BELGI FORMULA   )
(FORMULA   BELGI   FORMULA) (FORMULA   +   FORMULA)
(FORMULA +   FORMULA   ) ( FORMULA +   RAQAM   )
( FORMULA +   RAQAM   ) ( FORMULA +   RAQAM   )
( FORMULA +   RAQAM   ) (FORMULA +   5   )
(   FORMULA   + 5) (   NUMBER   + 5)
(   NUMBER   + 5) (   RAQAM   + 5)
(   RAQAM   + 5) (   RAQAM   + 5)
(   RAQAM   + 5) (   1   RAQAM + 5)
(1   RAQAM   + 5) (1   2   + 5)
Analitik grammatikalar  
Generativ grammatika grammatikaning yagona turi emas, lekin ular dasturlash 
ilovalarida eng keng tarqalgan.   Generativ grammatikalardan farqli 
o'laroq,   analitik (taniq) grammatika   berilgan so'zning tilga tegishliligini aniqlash 
imkonini beruvchi algoritmni belgilaydi.   Misol uchun, har qanday   oddiy 
tilni        chekli avtomat      grammatikasi yordamida tanib olish mumkin   va kontekstsiz 
har qanday grammatika   stekga asoslangan avtomat   yordamida tan olinishi 
mumkin .   Agar so'z tilga tegishli bo'lsa, unda bunday avtomat o'z chiqishini aniq 
shaklda tuzadi, bu esa   ushbu so'zning   semantikasini tahlil qilish imkonini beradi.   
Grammatikalarning tasnifi
26   Xomskiyning fikricha,   formal grammatikalarni   to‘rt turga bo‘lish 
mumkin.   Grammatikani u yoki bu turga belgilash uchun uning   barcha   qoidalari 
(ishlab chiqarishlari) ma'lum sxemalarga mos kelishi kerak.
0 turi - Cheksiz   [   tahrir   |   kodni tahrirlash   ]
G iborali tuzilishga   ega grammatika   algebraik tuzilma   , tartiblangan to'rtlik (V  
T   ,
V  
N   , P, S), bu erda   [1]
  :
  - terminal belgilar   alifbosi   (to'plami) -   terminallar   ,

  - terminal bo'lmagan belgilar   alifbosi   (to'plami) - 
terminal   bo'lmagan   belgilar ;

  -   lug'at   , bundan tashqari

  grammatikaning cheklangan   ishlab chiqarishlari   (qoidalari) to'plamidir,

  -   boshlang'ich belgi   (   manba   ).
Bu yerda   alifbo ustidagi barcha qatorlar to'plamidir , lekin   — alifbo ustidagi 
bo sh bo lmagan qatorlar to plami	
ʻ ʻ ʻ .
Chomskiy tasnifiga ko'ra, 0-turi   cheklanmagan grammatikalarni   o'z ichiga oladi
-   iboralar tuzilishiga ega grammatika   , ya'ni istisnosiz barcha rasmiy 
grammatikalar.   Qoidalarni quyidagicha yozish mumkin:
qayerda   kamida   bitta   terminal   bo ' lmagan   [2]
  belgini   o ' z   ichiga   olgan   har  
qanday   bo ' sh   bo ' lmagan   satr   va   -  alifbodagi   har   qanday   belgilar   qatori .
Murakkabligi tufayli bunday grammatikalarning amaliy qo'llanilishi yo'q.
1-toifa - kontekstga sezgir  
Bu turga   kontekstga bog'liq (KZ) grammatika   va qisqartirilmaydigan 
grammatikalar kiradi.   Grammatika uchun barcha qoidalar [3]
  ga o'xshaydi   :

, qayerda .   Bunday grammatikalar kontekstga sezgir deb ataladi.

, qayerda .   Bunday grammatikalar qisqartirilmaydiganlar deb tasniflanadi.
Grammatikaning bu sinflari ekvivalentdir.   Ulardan tabiiy tillardagi matnlarni 
tahlil qilishda foydalanish mumkin, lekin ular murakkabligi tufayli 
tuzuvchilarni qurishda amalda qo‘llanilmaydi.   Kontekstga bog'liq bo'lgan 
grammatikalar uchun gap isbotlangan: ba'zi bir algoritm bo'yicha, cheklangan
miqdordagi bosqichlarda, terminal belgilar zanjiri berilgan tilga tegishli yoki 
yo'qligini aniqlash mumkin.
2-toifa - kontekstsiz  
Ushbu tur   kontekstsiz (CS) grammatikalarni   o'z ichiga oladi .   Grammatika 
uchun barcha qoidalar quyidagicha ko'rinadi:
27 , qayerda (qisqartirilmagan CF-grammatikalar uchun) yoki
(qisqartirilganlar uchun), .   Ya'ni, grammatika qoidaning chap tomonida 
faqat   terminal bo'lmagan belgi   paydo bo'lishiga imkon beradi .
COP grammatikalari kompyuter tillari   sintaksisini tavsiflash uchun keng 
qo'llaniladi   (   tahlil qilish   ga qarang ).
Turi 3 - muntaza
Uchinchi turga   oddiy grammatikalar   (avtomatik) kiradi - rasmiy 
grammatikalarning eng soddasi.   Ular kontekstsiz, lekin cheklangan 
funksionallikka ega.
Barcha oddiy grammatikalarni ikkita ekvivalent sinfga bo'lish mumkin, ular III 
turdagi grammatika uchun quyidagi shakldagi qoidalarga ega bo'ladi:

yoki , qayerda (chap chiziqli grammatikalar uchun).

;   yoki , qayerda (o'ng chiziqli grammatikalar uchun).
Oddiy grammatikalar eng oddiy konstruksiyalarni tasvirlash uchun 
ishlatiladi:   identifikatorlar   ,   satrlar   ,   doimiylar   , shuningdek   assembly 
tillari   ,   buyruq protsessorlari   va boshqalar.
TILLARNI TASAINFI
Rasmiy tillar   ularni belgilaydigan grammatika turlariga ko'ra 
tasniflanadi.   Biroq, bir xil tilni har xil turlarga mansub turli grammatikalar 
bilan aniqlash mumkin.   Bunday holda, til ularning eng soddaiga tegishli deb 
hisoblanadi.   Shunday qilib, iboralar tuzilishi, kontekstga sezgir va kontekstsiz 
grammatikaga ega grammatika tomonidan tasvirlangan til kontekstsiz bo'ladi.
Grammatika kabi tilning murakkabligi uning turiga qarab belgilanadi.   Eng 
murakkablari ibora tuzilmasi bo'lgan tillar (bu tabiiy tillarni o'z ichiga oladi), 
so'ngra - KZ-tillari, KS-tillari va eng oddiylari - oddiy tillar.
Cocke   -Younger-     Kasami   algoritmi   ,   CYK   yoki   CKY   algoritmi ,   bu algoritm 
bo'lib, berilgan     kontekstsiz grammatikada     berilgan satrni chiqarish mumkinmi 
yoki yo'qligini aniqlash imkonini beradi   va agar shunday bo'lsa, uning chiqishini 
ta'minlaydi.   Boshqacha qilib aytganda, bu satrni   tahlil 
qilish   algoritmidir .   Algoritm pastdan yuqoriga tahlil qilishni amalga oshiradi 
va   dinamik dasturlash   usuliga asoslangan .   uning kashfiyotchilari: Jon Kok, 
Daniel Yanger, Tadao Kasami va Jeykob T. Shvarts.   Ular pastdan yuqoriga tahlil 
va dinamik dasturlashdan foydalanganlar.
28 CYK ning standart versiyasi faqat oddiy shaklda (CNF) berilgan kontekstsiz 
grammatikalar bilan ishlaydi.   Biroq, har qanday kontekstsiz grammatika 
(konversiyadan keyin) bir xil tilni ifodalovchi CNF grammatikasiga aylantirilishi 
mumkin (   Sipser 1997   ).
Pseudocode
 Pseudocode   da algoritm quyidagicha ko'rinadi   :
CYK algoritmi:
  n  ta belgidan iborat  S  qator  berilgan  :
  a 
1  ...  a 
n  . r  terminal bo'lmagan belgilarni o'z ichiga olgan grammatika  berilgan  R
1  ...  R 
r  .Dastlabki belgilarning
  R 
s  
    kichik to plamini o z ichiga oladi . ʻ ʻ def  massivi  P  [  n  ,  n  ,  r  ] mantiqiy qiymatlar 
False ga ishga tushirildi.
har bir    i  = 1 :  n 
   har bir  ishlab chiqarish uchun  R 
j  ->  a 
i  
    to'plami  P  [  1  ,  i  ,  j ] = Har bir i  = 2  uchun   rost
 :  n  har bir  j  = 1 :  n  -  i uchun interval uzunligi                      
   +1                - har bir  k  = 1  uchun  intervalli boshlash : 
     i  -1                - har bir ishlab chiqarish  uchun  intervalli bo'linish R 
A  ->  R 
B  R 
C  
agar  P  [  k  ,  j  ,  B  ] va  P  [  i  -  k  ,  j  +  k  ,  C  ]
          keyin  P  [  i  ,  j  ,  A  ] = rost
  bo'lsa  tayinlang 
       
          s  to plamdan ba zi 	
ʻ ʼ x uchun P  [n,  1  ,  x  ] = To g ri, 	ʻ ʻ bu yerda  s  barcha  R 
s  
indekslari bo lsa , 	
ʻ S  qaytishi  tilga tegishli bo lsa,	ʻ
  S  qaytarilishi  tilga  tegishli emas.
  
xulosa
Men kurs ishmni NFX gramatkasdagi tahlil qilish uchun coca-younger-kassami
algartmi va uning realizatsiya qilish  haqida yozdim.NFX gramatkasda tahlil 
qilish coca-younger-kassami algartmi mavzusida bajargan kurs ishmni bajarsh
davomida kontektsiz gramatka hamda Chomsyening normal shakli,Algartm 
haqida keltrdim. 
Kantektsiz gramatka (CS-gramatka, kantektsiz gramatka ) rasmiy tilni tilni 
tavsiflash usulini urgandm.bular quydagilardan iborat
29 1.–alifbo , uning elimentlari terminlari deb ataladi (Eng. Terminlash )
2.-elimentlar noterminlar deb ataladgan tuplam ( Ingiliz. Noterminlash )
         Algartm Coca-Younger-Kassami  (Engl. Cocke-Younger-Kasami algartmi,    
Engl  .CYK  algartm -)-algartm normal shaklda Chomiskian oldindan belgilangan 
kontektsiz giramatka hosil bulsa, suz topish.Harqanday KS-gramatkadan NFX ga 
qisqartrish mumkin, shuning uchun algartm har qanday KS-gramatsi uchun 
unversaldir.    
Foydalanilgan adabiyolar
30 1. M.O‘. ASHUROV, SH.A.SATTAROVA, SH.U.USMONQULOV,  
“ALGORITMLAR” ,  «Fan va texnologiya» nashriyoti, 2018.
2. H.To’rayev,“Kombinatorika va graflar nazariyasi”, “Ilm ziyo”, 2009 ,
3. Akbaraliyev B.B., Yusupova Z.Dj.  ,  “MA LUMOTLAR TUZILMASI VA ‟
ALGORITMLAR”, Toshkent 2013
4. Toirov Sh.A., Raximov R.T., Karimov M.M ,” “ALGORITMGA KIRISH” 
fanidan laboratoriya ishlarini bajarish bo’yicha USLUBIY KO’RSATMA”, 
Samarqand 2015,
5. Xayitmatov O’.T., Inogomjonov E.E., Sharipov B.A., Ro’zmetova N., 
Rahimboboeva D,” MA'LUMOTLAR TUZILMASI VA ALGORITMLARI”, 
Toshkent – 2011
Foydalanilgan internet saytlar:
1) https://kursovik.com/programming/320372.html
2) http://aliev.me/runestone/Graphs/PrimsSpanningTreeAlgorithm.html
3) http://www.hpcc.unn.ru/?dir=836
4) https://brestprog.by/topics/mst/
5) wikipedia
6) https://evileg.com/ru/post/524/
7) http://www.mkurnosov.net/
8) www.fayllar .org
9) Vikipediya - CYK algoritmi  
10) David Rodriges-Velazkes,  
31

O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA-MAXSUS TA’LIM VAZIRLIGI SAMARQAND DAVLAT UNIVERSITETI RAQAMLI TEXNOLOGIYALAR FAKULTETI KAMPYUTER ILIMLARI VA DASTURLASH TEXNOLOGIYALARI YO’NALISHI “ ALGORITMLAR VA MA’LUMOTLAR STRUKTURASI ” FANIDAN “NFX GRAMATIKASIDAGI TAHLIL QILISH UCHUN COCCO- YOUNGERI-KSSAMI ALGARITMI” MAVZUSIDA TAYYORLAGAN KURS ISHI SAMARQAND – 2021 Reja Kirish Asosiy qism: 1

1. Kontekstsiz gramatika 2. Chomsyening normal shakli 3. Algoritm KIRISH Bu kurs ishi binominal koeffitsientlarni o’rganish algoritmini ko’rib chiqib o’rgandim .Bugungi kunda ma’lumotlar oqimining ko’pligi tufayli ularni qisqa vaqt ichidazmashina buyruqlarini o’zida saqlovchi assembler tili yaratildi. 2

Keyinchalik FORTRAN, BASIC, PASKAL va COBOL singari yuqori darajali tillar ham paydo bo’ldiki, bu tillar yordamida so’z va gaplarning mantiqiy konstruksiyasidan foydalanib algoritmlash imkoniyati yaratildi. Ular buyruqlarni mashina tiliga interpretatorlar va kompilyatorlar yordamida o’tkazar edi. Algoritmlash tillari yaratilishi bo’yicha uchta turga ajratiladi: -quyi darajadagi; - o’rta darajadagi; -yuqori darajadagi. Ma’lumki, ma’lum bir masalani yechish uchun buyruqlar ketma- ketligi ya’ni algoritm algoritmlash tilida yozilayotganda kamroq buyruqlardan foydalanilsa, bunday tillar darajasi yuqoriroq hisoblanadi. Quyi darajadagi algoritmlash tillari bevosita kompyuter qurilmalari bilan bog’liq bo’lib, buyruqlar ularning kodlari bilan yoziladi. Bu kabi buyruqlardan tashkil topgan algoritmlar katta hajmli bo’lib, ularni taxrirlash katta mehnat talab qiladi. Dastlabki kompyuterlar(ENIAK, MESM va boshqalar) ana shunday tillarda ishlagan. O’rta darajadagi algoritmlash tillari buyruqlarida faqat raqamlar emas, balki insonlar tushunadigan ba’zi so’zlar ishlatila boshlandi(Assemblaer). Yuqori darajadagi algoritmlash tillari quyidagicha bosqichlarga bo’linadi: Algoritmik(Basic, Pascal, C va b.) Mantiqiy(Prolog, Lisp va b.) Obyektga mo‘ljallangan(Object Pascal, C++, Java va b.) Algoritmlash tillarida yaratilgan algoritmlar mashina tiliga translyatorlar yordamida o’tkaziladi. Translyator(translator-tarjimon) biror bir algoritmlash tilida yozilgan algoritmni mashina tiliga tarjima qiladi. Translyatorlar ikki turda bo’ladi: - Kompilyatorlar(compiler-yig'uvchi) biror bir algoritmlash tilida yozilgan algoritmni mashina tiliga to’liq o’qib olib tarjima qiladi; - Interpretatorlar(interpreter - izohlovchi, og’zaki tarjimon) biror bir algoritmlash tilida yozilgan algoritmni mashina tiliga satrma - satr tarjima qiladi. Translyatorlarni bu ikkala turi - bir biridan farq qiladi. Komplyatsiya qilingan algoritmlar birmuncha kam vaqt talab etadi, ya’ni tezroq ishlaydi, lekin interpretatsiya qilingan algoritmlarni o’zgartirish osonroq hisoblanadi. C++ dasturlash tili tarkibida bir nechta imkoniyatlar mavjud, ya’ni consol rejimi, forma ob’yekt rejimi, grafik muhiti va ma’lumotlar bazasi bilan ishlash 3

imkoniyatlari keng joriy etilgan. Ushbu qo’llanmada keltirilgan misol va masalalarning yechimi dasturining int main funksiyasi tarkibini C++ dasturlash tilinining ixtiyoriy versiyalarida ishlatib ko’rish mumkin. Qo’llanma oliy o’quv yurtlari talabalari va magistrantlari, litsey, kasb-hunar kollejlari talabalari hamda mustaqil o’rganuvchilar uchun qulay manba hisoblanadi. Kontekstsiz grammatika ( CS-grammatika , kontekstsiz grammatika ) - rasmiy tilni tavsiflash usuli, bu to'rtta, bu erda: - alifbo , uning elementlari terminallar deb ataladi (Eng. Terminals )  - elementlari noterminallar deb ataladigan to'plam (Ingliz. Nonterminals )  - grammatikaning boshlang'ich belgisi (inglizcha Boshlash belgisi ) 4

- xulosa qilish qoidalari to'plami (Eng. A ishlab chiqarish qoidalari yoki ishlab chiqarishlar ) turi , bu erda , ya'ni qaysi chap tomonda- yagona nonterminal, va o'ng - terminallar va nonterminallar ketma-ketligi. Misol Terminallar . S = { ( , ) Noterminallar . N= { S} Pul o'tkazish qoidalari : P S→ e S→ SS S→ ( S) Ushbu grammatika to'g'ri qavs qatorlari tilini belgilaydi . Masalan, ketma- ketlik quyidagicha chiqarilishi mumkin: ( ( ) ( ( ) ) ) S ⇒ ( S) ⇒ ( SS) ⇒ ( ( ) ( S) ) ⇒ ( ( ) ( ( ) ) ) Chomsky normal shakli . Chomskiyning normal shakli KS-grammatikaning normal shakli bo'lib, unda barcha mahsulotlar quyidagi shaklga ega:  A → a bu erda terminal bo'lmagan va terminal AAaa  A → BC Bu erda , , - terminal bo'lmagan va va boshlang'ich noterminal emas ABCBC  S→ e bu erda dastlabki noterminal va bo'sh satr (agar tilda bo'sh qator bo'lsa, bu ishlab chiqarish kerak) Se  Har qanday CS grammatikasini Chomskiyning oddiy shakliga tushirish mumkinligini ko'rsatish mumkin. Vikipediyadan, bepul ensiklopediya Sahifaning joriy versiyasi hali tajribali ishtirokchilar tomonidan ko'rib chiqilmagan va 2016 yil 6 yanvarda ko'rib chiqilgan versiyadan sezilarli darajada farq qilishi mumkin ; tekshiruvlar 10 ta tahrirni talab qiladi . Kontekstga bog'liq grammatika ( KZ-grammatikasi , kontekst grammatikasi ) rasmiy grammatikaning maxsus holatidir ( Xomskiy ierarxiyasi bo'yicha 1-tur ), unda barcha ishlab chiqarishlarning chap va o'ng qismlari terminal va terminal bo'lmaganlar bilan o'ralgan bo'lishi mumkin. belgilar. 5