Reja Amaliy dasturlash xaqda

[abc] ifodasi misol sifatida ko'rsatib berilganida, boshqa modellalarni bajarishda kerak bo'lgan natija variantlarini ifodalaydi. Bu [abc] ifodasi a, b, yoki c harflaridan birini qabul qilish uchun foydalaniladi.

Dasturlash Tillari

• 
  Dasturlash tillarining bir qismi, birinchi harakatni bajarishda qanday variantni tanlash uchun nedeterministik modellalardan foydalanadi. Misol uchun, bir dasturda birinchi holatda qanday amalni bajarmoqchi bo'lganligini ifodalovchi ifodalar.
  

Lexerlar va Parserlar

• 
  Lexerlar (tushuncha bo'yicha qismlar) va parserlar (tahlil qilish qismlar) quyidagilarga misol bo'lib, lexerlar bir matn bo'yicha tokenlarni aniqlashda va parserlar sintaksisni tahlil qilishda nedeterministik modellalardan foydalanadi.
  

Avtomatik tizimlar

• 
  Otomatlarda, qaysi yo'l tanlash maqsadida nedeterministiklikdan foydalaniladi. Finite avtomatlar, pushdown avtomatlar, va Turing mashinalari, har bir amalni bajarishda bir nechta variantlarni ifodalayadigan nedeterministik modellalardir.
  

Algoritmlar

• 
  Bir nechta algoritmlarda, har bir amal uchun bir nechta yo'l yoki qo'llashlarni aniqlash uchun nedeterministik modellalardan foydalaniladi. Bu, ma'lum bir natijaga yetishish uchun eng optimal yo'l yoki variantni aniqlashda foydalaniladi.
  

Nedeterministik modellalar, dasturlash sohasida ko'p joyda ishlatiladi va dasturlar yozishda, matematik modellalarni tushunishda, shuningdek, yuqori darajada sifatli va qulay variantlarini aniqlashda o'z vazifasini bajaradi.

7-Mavzu: Mavhum mashina

Reja

1. Mavhum mashina xaqida

2. Mavhum mashina xaqida tushunch

3. Mavhum mashina dasturlash tillarida

"Mavhum mashina" ("virtual machine") dasturlash sohasida juda mashhur va amaliyotda ko'p joyda ishlatiladigan bir mazmuniy (abstract) kontseptdir. Bu termin boshqa turdagi mashinalarning o'zidan boshqasidagi o'qimlar orqali xizmat qiladigan emulyator yoki interpretator sifatida ham ta'riflanadi. Mavhum mashina, bir tilda yozilgan dasturni boshqa tilda yoki qurilma dasturlash yuzasidan boshqarish uchun ishlatiladi.
Quyidagi mavhum mashinalar dasturlash sohasida keng qo'llaniladi:

1. 
   Java Virtual Machine (JVM)
   
   • 
     Java dasturlarini bajarish uchun ishlatiladi. Java tili platforma-mavhum (platform-neutral) tilda yozilgan tilda yaratilgan dasturlarni boshqa platformalarda (masalan, Windows, Linux, va boshqalar) ham ishga tushirish imkonini beradi. Java kodlari, Java bytecode deb nomlanuvchi virtual mashina uchun yaratiladi va u Java dasturini boshqa tilda yoki platformada ishga tushiradi.
     
2. 
   Common Language Runtime (CLR)
   
   • 
     CLR, .NET platformasi uchun dasturlarni boshqa tilda yozilgan tilda ishga tushirish va bajarish uchun ishlatiladi. .NET tilida yozilgan dasturlar CIL (Common Intermediate Language) deb nomlangan mavhum mashina uchun yaratiladi.
     
3. 
   Python Virtual Machine (PVM)
   
   • 
     Python dasturlarini bajarish uchun ishlatiladi. Python kodlari Python bytecode deb nomlanuvchi mavhum mashina uchun yaratiladi. PVM, Python dasturlarini boshqa platformalarda (masalan, Windows, Linux) ishga tushirish imkonini beradi.
     
4. 
   Parrot Virtual Machine
   
   • 
     Parrot, oddiy maqsadli yozilgan dasturlarni bajarish uchun keng qo'llaniladi. Bu mavhum mashina, boshqa tilda yozilgan kodni o'qib, tushunish va bajarish uchun ishlatiladi.
     
5. 
   Erlang Virtual Machine (BEAM)
   
   • 
     Erlang tilidagi dasturlarni bajarish uchun ishlatiladi. BEAM, Erlang dasturlarini yaxshi bajarish, distributiv va tartib qo'yishni qo'llab-quvvatlash, va paytli (concurrent) amallarni yozishga qaratilgan.
     

Mavhum mashinalar, dasturlash tilini boshqa tilda interprete etish yoki emulyatsiya qilishda yordam beradi va muhiti standartlashtirilgan bir o'qim (instruction set) orqali faoliyat ko'rsatadi. Bu, dasturlarni boshqa tilda yozilgan tilda ishga tushirish va ishlatishni osonlashtiradi.

1. 
   Kompilyatsiya jarayonining xususiyatlari hatto juda murakkab oddiy tillar, shuning uchun kompilyatsiya natijasining spetsifikatsiyasi tez-tez uchraydi tilga yo'naltirilgan abstrakt mashinalar (lar) nuqtai nazaridan berilgan. AM buyruqlar tizimi BSni amalga oshirish bilan to'ldiriladi parametrlarni uzatish va hududlarni himoya qilish bo'yicha bir qator tizimli harakatlar yap tomonidan nazarda tutilgan, ammo sintaktik bo'lmagan harakatlar
   

taqdimotlar. Bunday ta'rif mashinadan mustaqil bo'lishi mumkin va portativ. odatda quyidagi buyruq toifalarini ajratib turadi:
- qiymatlarni xotiradan stackga yuborish;
- ishlov berish paytida stekdagi nomlanmagan operandlar ustida hisoblash iboralar;
- lokalizatsiyani hisobga olgan holda qiymatlarni stekdan xotiraga yuborish;
- filiallar va tsikllarni tashkil etish;
- protseduralar va funktsiyalarga qo'ng'iroqlarni tashkil qilish
kontekstni saqlash/tiklash. Boshqa toifadagi jamoalar ham bo'lishi mumkin. Imperativ va funktsional yondashuvlarni taqqoslashda dasturlash, P. J. Landin maxsus taklif qildi
LISP semantikasining mashinaga bog'liq jihatlarini tavsiflash uchun qulay bo'lgan mavhum secd mashinasi. Ushbu mashinaning batafsil tavsifi Xendersonning funktsional dasturlash kitobida topish mumkin SECD mashinasi to'rtta registrda ishlaydi: Stack uchun
oraliq natijalar, nomlangan joylashtirish uchun kontekst qiymatlar, hisob-kitoblarni boshqarish dasturi, zaxira xotira (Stack, Environment, Control list, Dump). Registrlar saqlash uchun moslashtirilgan atomlar yoki ro'yxatlar ko'rinishidagi iboralar. Mashinaning holati to'liq
ushbu registrlarning mazmuni bilan belgilanadi. Shuning uchun ishlash mashinalarni o'zgarish nuqtai nazaridan aniq ta'riflash mumkin buyruqlar bajarilganda registrlar tarkibi, bu ifodalanadi quyidagicha: eski holatdan yangi holatga o'tish. Tarjimon yadrosiga o'rnatilgan operatsiyalar mos kelishi kerak parametrlarga kirish va ishlab chiqilganlarni joylashtirishning standart qoidalari natija. Kompilyatsiya qilingan kod ham xuddi shu qoidalarga bo'ysunishi kerak. Bu sizga rasmiy ravishda o'rnatilgan va teng huquqli deb hisoblash imkonini beradi
dasturlashtiriladigan funktsiyalar. Dasturning manba matni bo'yicha kompilyator matnga teng dastur kodini yaratadi. O'rnatilgan tarjimon buyruqlari va natijasini tavsiflash uchun
asosiy Lisp dasturlarini kompilyatsiya qilish uchun sizga quyidagi buyruqlar kerak bo'ladi:
Ld-berilgan kontekstni stekka kiritish;
LDC-dasturdan stekka doimiy kiritish;
LDF-funktsiya ta'rifini stekka kiritish;
AP-ta'rifi allaqachon stakanda bo'lgan funktsiyani qo'llash;
RTN-funktsiya ta'rifidan uni keltirib chiqargan dasturga qaytish;
RAP-rekursiv funktsiyani qo'llash
Dum-rekursiv argumentlarni saqlash uchun xotirani zaxiralash xususiyatlari. Sel-stekning faol (yuqori) qiymatiga qarab dallanma; Join-filialdan keyin umumiy nuqtaga o'tish; CAR-faol Stack qiymatining birinchi elementi; CDR-birinchi elementsiz faol Stack qiymati;
CONS-ikkita yuqori Stack qiymatida tugunni shakllantirish; ATOM-stekning yuqori elementining bo'linmasligi (atomikligi) ; EQ-ikkita yuqori Stack qiymatlarining tengligi;
STOP-to'xtash. Stek an'anaviy ravishda "birinchi kelgan, oxirgi ketgan"sxemasi bo'yicha tashkil etilgan. Stack hajmi cheklanmagan. Mavhum mashinaning har bir jamoasi "biladi"
uning ishida ishlatiladigan Stack elementlarining soni, ularni olib tashlaydi Stack va ularning o'rniga ishlab chiqilgan natijani joylashtiradi. Ijro etiladi buyruqlar navbat bilan, boshqaruv dasturining registridagi birinchi buyruqdan boshlanadi. "To'xtatish" buyrug'ini bajarayotganda mashina ishlashni to'xtatadi, bu rasmiy ravishda mashina holatida o'zgarishlarning yo'qligi bilan tavsiflanadi: s e (STOP ) d → s e (STOP ) d Xendersonga ergashib, ishlov beriladigan elementlarni aniq ajratish uchun ro'yxatning qolgan qismidan biz quyidagi yozuvlardan foydalanamiz: Endi biz sanab o'tilganlarning barchasini metodik ravishda tasvirlashimiz mumkin buyruqlar ustida. Predikat uchun biz qaysi holatlarda qiymat ishlab chiqilishini belgilaymiz "haqiqat".
Haqiqat " T " - mos keladigan ko'rsatkichlar uchun, mos kelmaydiganlar uchun-NIL,
ya'ni yolg'on.
Kontekstda joylashgan qiymatlarga kirish uchun quyidagilar mumkin
ro'yxatdan elementni ajratib turadigan maxsus n-th funktsiyasini aniqlang
berilgan raqam n ro'yxatning uzunligi oshib ketadi degan taxminda
berilgan manzil:
Filiallar join to'ldiruvchisi bilan pastki ro'yxatlarga joylashtirilgan, shundan so'ng
hisoblashning umumiy qismi keladi. Vaqt o'tishi bilan ko'proq ishonchlilik uchun
filialning bajarilishi umumiy qism axlatxonada saqlanadi-zaxira xotirasi va
filial tugagandan so'ng-boshqaruv registrida tiklanadi
dasturlar: Protseduralarni chaqirishni tashkil qilish kontekstni mahalliylardan himoya qilishni talab qiladi ta'rif tanasini talqin qilishda sodir bo'ladigan o'zgarishlar. Buning uchun
funktsiya ta'rifini stekka kiritishda maxsus tuzilma yaratiladi, funktsiyani aniqlash kodi va joriy holat nusxasini o'z ichiga olgan kontekst. Bungacha stekda haqiqiy stek joylashtirilishi kerak jarayon parametrlari. Jarayon RTN buyrug'i bilan yakunlanadi, registrlarni tiklash va protsedura natijasini stakka joylashtirish: f-ta'rif tanasi, funktsiya chaqirilganda EF konteksti,
vf-funktsiyani chaqirish uchun haqiqiy parametrlar, x-funktsiya natijasi. Rekursiv funktsiya qo'ng'iroqlari uchun xotirani zaxiralash kerak haqiqiy dalillarning turli avlodlariga noyob havolalar bunga "ω" xayoliy ob'ektni joylashtirish orqali erishiladi funktsiya rplaca, istisno tariqasida, haqiqiy ma'lumotlarni almashtiradi:
SECD uchun yadroni amalga oshirish yopilishi o'z natijasini joylashtiradigan rplaca va rplacd funktsiyalarini tizimli ravishda buzishni o'z ichiga oladi to'g'ridan-to'g'ri ikkinchi argument xotirasida. Bu talab qiladi sintaksis va tarjimon ta'riflaridagi tegishli filiallar qo'shma korxonani targ'ib qilish bosqichi deb hisoblash mumkin.
Paskal va Oberon tillari uchun shunga o'xshash mashinada quyidagilar mavjud
jamoalar:
Ld-berilgan kontekstdan oraliq qiymatlar to'plamiga kiritish;
LDC-dasturdan stekka doimiy kiritish;
LDP-protsedura ta'rifini kiritish;
LDW - raqamni xotiradan stackga kiritish;
STW-global xotirada qiymatni saqlash;
STE-mahalliy kontekstda qiymatni saqlash;
Ret-protseduradan uni keltirib chiqargan dasturga qaytish;
If-stekning faol (yuqori) qiymatiga qarab dallanish;
EQ-ikkita yuqori Stack qiymatlarining tengligi;
Lt-stekdagi yuqori qiymat ikkinchisiga qaraganda kamroq;
INC-raqamni 1 ga oshirish;
DEC-raqamni 1 ga kamaytirish;
Yuqori Stack elementidan sub-ayirish;
Qo'shish-stekning yuqori elementiga qo'shish;
MUL-ikkita sonning ko'paytmasi;
DIV - stekning yuqori elementini ikkinchi elementga bo'lishning qismi;
BR-mutlaq manzil bo'yicha boshqaruvni shartsiz o'tkazish;
AP-stekda joylashgan argumentlarga protsedurani qo'llash;
STOP-to'xtash.
Secm mashinasi, SECD singari, to'rtta registrda ishlaydi: Stack oraliq qiymatlar uchun argumentlarni joylashtirish uchun kontekst, o'zgaruvchilarning mahalliy qiymatlari va qaytish registri, boshqarish hisoblash dasturi, xotira (Stack, Environment, Control program, Memory). Registrlar ma'lumotlarni vektor shaklida saqlash uchun moslangan yoki haqiqiy manzillarda bir-biriga mos kelmaydigan ro'yxatlar. Holati mashinalar ushbu registrlarning mazmuni bilan to'liq belgilanadi. Shuning uchun mashinaning ishlashini aniq ma'noda ta'riflash mumkin
buyruqlar bajarilganda registrlar tarkibidagi o'zgarishlar, bu ifodalanadi quyidagicha:
s e c m → s' e' C' m ' – eski holatdan yangi holatga o'tish.
Endi biz sanab o'tilganlarning barchasini metodik ravishda tasvirlashimiz mumkin
buyruqlar ustida.
s e (LDC q . c)m → (q . s) e c m
(a . s) e (INC . c)m → (a+1 . s) e c m
Mavhum mashina" ("virtual machine") dasturlash sohasida juda mashhur va amaliyotda ko'p joyda ishlatiladigan bir mazmuniy (abstract) kontseptdir. Bu termin boshqa turdagi mashinalarning o'zidan boshqasidagi o'qimlar orqali xizmat qiladigan emulyator yoki interpretator sifatida ham ta'riflanadi. Mavhum mashina, bir tilda yozilgan dasturni boshqa tilda yoki qurilma dasturlash yuzasidan boshqarish uchun ishlatiladi.

2. 
   Quyidagi mavhum mashinalar dasturlash sohasida keng qo'llaniladi:
   

1. 
   Java Virtual Machine (JVM)
   
   • 
     Java dasturlarini bajarish uchun ishlatiladi. Java tili platforma-mavhum (platform-neutral) tilda yozilgan tilda yaratilgan dasturlarni boshqa platformalarda (masalan, Windows, Linux, va boshqalar) ham ishga tushirish imkonini beradi. Java kodlari, Java bytecode deb nomlanuvchi virtual mashina uchun yaratiladi va u Java dasturini boshqa tilda yoki platformada ishga tushiradi.
     
2. 
   Common Language Runtime (CLR)
   
   • 
     CLR, .NET platformasi uchun dasturlarni boshqa tilda yozilgan tilda ishga tushirish va bajarish uchun ishlatiladi. .NET tilida yozilgan dasturlar CIL (Common Intermediate Language) deb nomlangan mavhum mashina uchun yaratiladi.
     
3. 
   Python Virtual Machine (PVM)
   
   • 
     Python dasturlarini bajarish uchun ishlatiladi. Python kodlari Python bytecode deb nomlanuvchi mavhum mashina uchun yaratiladi. PVM, Python dasturlarini boshqa platformalarda (masalan, Windows, Linux) ishga tushirish imkonini beradi.
     
4. 
   Parrot Virtual Machine
   
   • 
     Parrot, oddiy maqsadli yozilgan dasturlarni bajarish uchun keng qo'llaniladi. Bu mavhum mashina, boshqa tilda yozilgan kodni o'qib, tushunish va bajarish uchun ishlatiladi.
     
5. 
   Erlang Virtual Machine (BEAM)
   
   • 
     Erlang tilidagi dasturlarni bajarish uchun ishlatiladi. BEAM, Erlang dasturlarini yaxshi bajarish, distributiv va tartib qo'yishni qo'llab-quvvatlash, va paytli (concurrent) amallarni yozishga qaratilgan.
     

Mavhum mashinalar, dasturlash tilini boshqa tilda interprete etish yoki emulyatsiya qilishda yordam beradi va muhiti standartlashtirilgan bir o'qim (instruction set) orqali faoliyat ko'rsatadi. Bu, dasturlarni boshqa tilda yozilgan tilda ishga tushirish va ishlatishni osonlashtirad