NFX GRAMATIKASIDAGI TAHLIL QILISH UCHUN COCCO-YOUNGERI-KSSAMI ALGARITMI
![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](/data/documents/13bded2e-1edb-46bc-9e35-4e77a4985401/page_6.png)
![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](/data/documents/13bded2e-1edb-46bc-9e35-4e77a4985401/page_7.png)
![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](/data/documents/13bded2e-1edb-46bc-9e35-4e77a4985401/page_12.png)
![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](/data/documents/13bded2e-1edb-46bc-9e35-4e77a4985401/page_13.png)
![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](/data/documents/13bded2e-1edb-46bc-9e35-4e77a4985401/page_14.png)
![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](/data/documents/13bded2e-1edb-46bc-9e35-4e77a4985401/page_16.png)
![-
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](/data/documents/13bded2e-1edb-46bc-9e35-4e77a4985401/page_17.png)
![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](/data/documents/13bded2e-1edb-46bc-9e35-4e77a4985401/page_19.png)
![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](/data/documents/13bded2e-1edb-46bc-9e35-4e77a4985401/page_20.png)
![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](/data/documents/13bded2e-1edb-46bc-9e35-4e77a4985401/page_21.png)
![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](/data/documents/13bded2e-1edb-46bc-9e35-4e77a4985401/page_22.png)
![— 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](/data/documents/13bded2e-1edb-46bc-9e35-4e77a4985401/page_24.png)
![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](/data/documents/13bded2e-1edb-46bc-9e35-4e77a4985401/page_27.png)
![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](/data/documents/13bded2e-1edb-46bc-9e35-4e77a4985401/page_29.png)
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