Nfx gramatikasidagi tahlil qilish uchun cocco youngeri kssami algaritmi

Информация о документе

Цена	10000UZS
Размер	465.6KB
Покупки	0
Дата загрузки	06 Ноябрь 2026
Расширение	pdf
Раздел	Курсовые работы
Предмет	Педагогика

Nfx gramatikasidagi tahlil qilish uchun cocco youngeri kssami algaritmi

Купить

O’ZBEKISTON RESPUBLIKASI
OLIY VA O’RTA -MAXSUS TA’LIM VAZIRLIGI
SAMARQAND DAVLAT UNIVERSITETI
RAQAMLI TEXNOLOGIYALAR FAKULTETI
KAMPYUTER ILIMLARI VA DASTURLASH TEXNOLOGIYALARI
YO’NALISHI

20 6-GURUH TALABASI
SAYDULLAYEV YAXSHIMURODNING
“ALGORITM VA MA’LUMOTLAR STRUKTURASI ” FANIDAN
“NFX GRAMATIKASIDAGI TAHLIL QILISH
UCHUN COCCO -YOUNGERI -KSSAMI ALGARITMI”
MAVZUSIDA TAYYORLAGAN

TEKSHIRDI: DJABBAROV A.H.

SAMARQAND – 2021

MUNDARIJA .
I.bob Kirish … … … … … … … … … … … … … … … … … … … … … … … … … … … 3
II.bob Asosiy qism: … … … … … … … … … … … … … … … … … … … … … … … … 5
2.1. Kontekstsiz gramatika … … … … … … … … … … … … … … … … … … … … .5
2.2. Chomsyening normal shakli … … … … … … … … … … … … … … … … … ..19
III .bob Xu losa … ..… … … … … … … … … … … … … … … … … … … … … … … … 30
IV .bob Foydalanilgan adabiyotlar … … ... .… … … … … … … … … … … … … … ...31

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 .
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 yozi layotganda
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
top gan 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 tushuna digan 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.) Alg oritmlash 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 mashin a 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 hi soblanadi. C++
dasturlash tili tarkibida bir nechta imkoniyatlar mavjud, ya’ni consol rejimi, forma
ob’yekt rejimi, grafik muhiti va ma’lumotlar bazasi bilan ishlash imkoniyatlari
keng joriy etilgan. Ushbu qo’llanmada keltirilgan misol va masalalarning y echimi
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 u chun 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 )
• - 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.
Rasmiy grammatikaning alohida holati ham kontekstsiz grammatikadir .
KZ -grammatikasi bilan aniqlanishi mumkin bo'lgan til kontekstga bog'liq til yoki
KZ tili deb ataladi .
Algor itm 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 dinam ik 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-ik=I d[ B ] [ i ] [ k ] ∧ d[C] [k+1]
[j] w[i…j] A→BC w[i…k] w[k+1…j]
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 ] =
∑ ∑ d[ B ] [ i ] [ k ] ⋅ d[ C] [ k + 1 ] [ j ]d[ A ] [ i ] [ j ]w [ i ... j ]A j−1
k=i A→BC

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 ikkit a pastki qatorga bo'lingan barcha bo'linishlar uchun tsikl mavjud,
shuning uchun ishlov berish . Natijada, biz yakuniy murakkablikni olamiz .
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
bitta 2 3 4 besh 6
bitta

2
3
4
besh
6
B
bitta 2 3 4 besh 6
bitta
2
3
4
besh
6
C
bitta 2 3 4 besh 6

bitta ●
2
3 ●
4 ●
besh
6
D
bitta 2 3 4 besh 6
bitta
2 ●
3
4
besh ●
6 ●
E

bitta 2 3 4 besh 6
bitta
2 ●
3
4
besh ●
6 ●

.
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 gra mmatikaga 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 b ilan 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'ls a, 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 19 62 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 nom larini 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 nom langan, 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 ye ydi " jumlasini tahlil qiladi:
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
Qadam Doskada xom
tugunlar
Kengashda qayta ishlangan tugunlar Kengashga
qo'shilgan
tugunlar

bitta

U NP , V , Det ,
baliq N , P ,
bir Det ,
sanchqi N
bilan ovqatlanadi
.
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 yeydi
U NP , V yeydi [ baliq ] NP
5, 6 baliq N , P bilan ,
bir Det ,
sanchqi N , VP yeydi ,
[ 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 ] NP
8 sanchqi N , VP yeydi ,
[ baliq ] NP ,
[ vilka ] NP
U NP , V , Det , baliq N ni , P , a Det
bilan ovqatlanadi

to'qqiz VP , [ baliq ] NP ,
[ vilkalar ] NP yeydi
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
Eydi ] S , [ baliqni vilka bilan yeydi ] VP ,
[ vilka bilan ] PP , [ U baliq yeydi ] S
[ U baliqni
vilka bilan
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 qator ning 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 keladiga n 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 uchtag acha
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
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, uni ng 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
bit
ta

Men NP , siz NP , bolal
ar NP , V so'radi , V yor
dam bering
2-
4
Men NP , siz NP , bolalar NP
, 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 , de
b 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'r
adi , 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'ra
di V , yordam V ,
( men , so'radi )
VP , ( sizdan so'r
adi ) VP
[ bolalar
so'radi ] S , ( bolalar s
o'radi ) CP

10
-
12
VP _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ ___ _ _ _ _ _ _ _ _
Men NP , siz NP ,
bolalar NP , so'ra
di V , yordam V ,
( men , so'radi )
VP ,
( siz , so'radi ) V
P ,
( bolalar , so'rad
i ) VP
( Men , yordam ) CP ,
( siz , yordam ) CP ,
( bolalar , yordam ) C
P
13
-
18
CP _____ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Men NP , siz NP ,
bolalar NP , so'ra
di V , yordam V ,
( men , so'radi )
VP , ( sizdan so'r
adi ) VP ,
( bolalar , so'rad
i ) VP , ...

19 ( bolalar , yordam ) CP Men NP , siz NP ,
bolalar NP , so'ra
di 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'ra
di 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 m arta 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'ri nli 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 .
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
all aqachon 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 qolayotgani ni 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 yan gi 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 daraxt i 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 mumk in 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 bel gilashdir, 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'p aytirish 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 b o'lmagan va 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 qidiruv ni 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) : 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] new_prob = sat[ 1] + rule.prob if (chunk no t 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:
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 qismlari terminal va term inal
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 mavj ud - 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
ASC II 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, gram matika quyidagi xususiyatlar bilan belgilanadi:

• — 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
almashtiris h 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.
Grammatik a turlari
Chomskiy ierarxiyasiga ko'ra , grammatika 4 turga bo'linadi, har bir keying isi
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 ha r bir qoidasi shaklga ega
, yoki , ya'ni qoidaning o'ng tomonida noterminalning ko'pi bilan bitta
hodisasi bo'lishi mumkin [2] .
Ilova
• Konteks tsiz grammatikalar grammatik tahlilda grammatik tuzilmani aniqlash
uchun keng qo'llaniladi .
• Muntazam grammatika ( muntazam iboralar shaklida ) matnni qidirish,
qismlarga ajratish va almashtirish uchun sha blon sifatida keng qo'llaniladi, shu
jumladan leksik tahlilda .
Misol sifatida arifmeti k 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 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
Xomskiyning fikricha, formal grammatikalarni to‘rt turga bo‘lish
mumkin. Grammatikani u y oki 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 grammat ika 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 cheklanma gan 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
tuzuvchila rni 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:
• , 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
grammatikal arning 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 turla rga 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 b o'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. Boshqa cha qilib aytganda, bu satrni tahlil qilish algoritmidir
. Algoritm pastdan yuqoriga tahlil q ilishni 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.
CYK ning standart versiyasi faqat oddiy s haklda (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.

X ulosa
Ushbu kurs ish ida NFX gramatkasdagi tahlil qilish uchun coca -younger -
kassami alg oritmi va uning realizatsiya qilish haqida yoz ildi .NFX gramatkasda
tahlil qilish coca -younger -kassami algartmi mavzusida bajargan kurs ishmni
bajarsh davomida kontektsiz gramatka hamda Chomsyening normal
shakli,Algartm haqida keltr ildi .
Kantektsiz gramatka (CS -gramatka, kantektsiz gramatka ) rasmiy tilni tilni
tavsiflash usulini urgandm.bular quydagilardan iborat
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
kontekts iz giramatka hosil bulsa, suz topish.Harqanday KS -gramatkadan NFX ga
qisqartrish mumkin, shuning uchun algartm har qanday KS -gramatsi uchun
unversaldir.

Foydalanilgan adabiyolar

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.co m/ru/post/524/
7) http://www.mkurnosov.net/
8) www.fayllar .org
9) Vikipediya - CYK algoritmi
10) David Rodriges -Velazkes,

Nfx gramatikasidagi tahlil qilish uchun cocco youngeri kssami algaritmi

Купить

Похожие документы
2001-yil sentabr voqealri va uning xalqaro munosabatlarga
1945-1990-yillarda Buyuk Britaniya
1918-1923 yillarda xalqaro munosabatlar, Versal Vashington siyetemasining tuzilishi
Ahmad al-farg‘oniy
Almashlab ekishni loyihalashtirish va joriy etish

Информация о документе

Продавец

Nfx gramatikasidagi tahlil qilish uchun cocco youngeri kssami algaritmi

Похожие документы