Nfx gramatikasidagi tahlil qilish uchun cocco-youngeri-kssami algaritmi

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

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

Nfx gramatikasidagi tahlil qilish uchun cocco-youngeri-kssami algaritmi

Купить

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 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; -
2

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
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.
3

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.
4

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 .
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 .
5

{ ⟨ 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]
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
6

qoidalari va ikkita 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
bit
ta 2 3 4 be
sh 6
bit
ta
2
3
4
be
sh
6
7

B
bit
ta 2 3 4 be
sh 6
bit
ta
2
3
4
be
sh
6
C
bit
ta 2 3 4 be
sh 6
bit
ta ●
2
3 ●
4 ●
be
sh
8

6
D
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
9

bes
h ●
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 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
10

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:
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
11

4
Det , baliq
N ,
P
bilan , bir
Det ,
sanchqi
N ,
VP yey
di U
NP , V yeydi [ baliq ]
NP
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 U NP , V , Det , baliq N , P bilan , Det ,

sanchqi N , VP , [ baliq ] NP ,

[ vilka ] NP, [ U
Eydi ] S , [ baliqni vilka
12

yeydi ] VP 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 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 ).
13

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
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
14

bi
tt
a Men
NP , siz
NP , bolal
ar
NP ,
V so'radi ,
V yo
rdam 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 , 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 ( Men , yordam )
CP ,
( siz , yordam )
CP ,
( bolalar , yordam )
C
P
15

P ,
( bolalar , so'ra
di )
VP
13
-
18 CP _____ _ _ _
_ _ _ _ _
_
_ _ _ _
_ _ _ _ _ _
_ _ _
_ _ _
_ _ _ _ _ _
_ _ _ _
_ _
_ Men
NP , siz
NP ,
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
16

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
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
17

$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 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 18$ $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 : 19$ $chunk = sat[ 0 ] 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: 20$

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
21

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 .
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:
22

— 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
23

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
24

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
25

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:
26

, 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.
27

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
28

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
29

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,
30

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

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