“NFX GRAMATIKASIDAGI TAHLIL QILISH UCHUN COCCO- YOUNGERI-KSSAMI ALGARITMI” Reja Kirish Asosiy qism: 1. Kontekstsiz gramatika 2. Chomsyening normal shakli 3. Algoritm 1

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