|
Belgilar zanjiri. Zanjirlar ustidagi amallar
Ketma- ket yozilgan ihtiyoriy belgilar ketma-ketligi - belgilar zanjiri (satr) deb nomlanadi. Belgi tushinchasi tayanch bo‘lib ta’rifi berilmaydi.
Bunda biz berilgan zanjirlar belgisini grek hariflari bilan yozamiz –α, β, γ.
Misol: α=”a0103s” , β=”aaaa”, γ=”.”. α= β agarda mos zanjirlarda belgilar to‘plami va soni, teng bo‘lib ular bir xil ketma ketlikda tursa.
Zanjirdagi belgilar soni , zanjirning uzunligini bildiradi va quyidagicha yoziladi | α | misol: | α | =6; agar α= β unda | α | = | β | ;
Zanjirlar ustidagi asosiy amal konkatenatsiya ( birlashtirish, ulash, qo‘shish) amalidir. α va β zanjirlarni konkatenatsiyasi αβ ko‘rinishda yoziladi. Natijaviy zanjirda β zanjirning belgilari α ning belgilaridan keyin yoziladi masalan αβ= “a0103saaaa”.
Bu amal kommutativ emas, yani αβ≠βα , lekin assotsiativ α(βγ)=(αβ)γ.
Yana ikkita amalni aytib o‘tmoq kerak:
Zanjirni teskari qilish amali- zanjir belgilarini teskari tartibda yozishdir αR ko‘rinishda yoziladi:
α = “abv”; αR=“vba”; ∀α,β: (α,β)R= βRαR;
Iteratsiya amali:
Agar zanjir birorta belgidan iborat bo‘lmasa, bunday zanjir bo‘sh zanjir deb nomlanadi va u λ yoki ε xarflari bilan belgilanadi. Bo‘sh zanjir quyidagi qoidalarga rioya qiladi:
1. | ε | =0;
2.R=α;
3. ∀ε=ε;
4. ∀n≥0: εn=ε;
5. ∀α: α0= ε;
Tilni elementar belgilaridan tashkil qilingan bo‘linmas konstruksiya leksema deb nomlanadi. Leksema tilni birligi bo‘lib uning asosiy tushunchasi xisoblanadi. Agar leksema bo‘linsa uning til nuqtayi nazariyasidan ma’nosi yo‘qaladi. Tabiiy tillarda leksema bu so‘zni bildiradi. Programmalash tillarda leksema deb identifikator, konstanta, kalit so‘zi, amal belgilari , ajratuvchilar va nishonlar xisoblanadi. Leksik taxlilchi (skaner) kompilyator qismi bo‘lib , boshlang‘ich programm matn o‘qiydi va undagi leksemalarni ketma ket ajratib beradi. Leksik taxlilchi vazifasini sintaktik taxlilchi xam bajarishi mumkin, lekin leksik taxlilchi aloxida bo‘lishini sababi xam bor:
leksik taxlilchini ishlatish natijasida boshlang‘ich matndan leksemalar ajratib beriladi va ortiqcha narsalar olib tashlanadi (probellar, kommentariyalar va xokazo), natijada programma
qisqartiriladi;
leksik taxlil jarayonida sodda va effektiv algoritmlar qo‘llanadi, aksincha sintaktik taxlilchini algoritmlari murakkabdir;
leksik taxlilchi murakkab sintaktik taxlilchini boshlang‘ich matn ustida ishlashni ozod qiladi , va unga tayyor kerakli ko‘rinishda
leksemalarni uzatib beradi;
agar programm tilini kodirovkasi o‘zgarilsa u faqat leksik tahlilchiga ta’sir qiladi.
Leksik va sintaktik taxlil bir-biriga bog‘langan xolda, ikkita usul bilan o‘zaro ishlashi mumkin. Bu ketma ket usuli va parallel usuli.
Birinchi usulda leksik taxlilchi matinni to‘liq ko‘rib chiqib uni biror bir tuzim ko‘rinishda sintaktik taxlilchiga tayyorlab beradi. Bu tizim leksemalar jadvali deb nomlanadi. Jadvalda leksemani ko‘rinishdan tashqari uning turi va maxsus qo‘di saqlanishi mumkin. Bu jadvaldan tashqari yana boshqa jadvallar xosil bo‘lishi mumkin, masalan identifiqatorlar jadvali , konstantalar jadvali va hokazo.
Ikkinchi usulda ishni sintaktik taxlilchi boshlaydi va konstruksiyalarni tekshirish jarayonida leksik taxlilchini chaqirib joriy leksemani talab qiladi, va kutilgan leksema qoydalarga rioya qilsa uni jadvallarga yozadi va keyingi leksemaga o‘tadi.
Birinchi usul ikkinchiga qaraganda ma’quldir.
Leksemalar turlarga bo‘linadi, ko‘pincha kuyidagi turlar ishlatiladi:
Identifikatorlar
Kalit so‘zlar
Konstantalar
Ajratuvchilar(amallar)
Har bir leksema juftlik bilan berilishi mumkin:
( leksema turi, leksema manzili)
Yuqorida ko‘rsatilgan leksemalar regulyar grammatika bilan berilishi mumkin va uni chekli avtomat bilan amalga oshirish mumkin.
Leksik tahlilchi zanjirni tilga kirishini aniqlashdan tashqari yana bir nechta masalalarni yechish kerak:
U o‘zi manba programmadan leksemani ajratib olishi kerak va to‘g‘ri yozilganligini aniqlash kerak.
Leksemani kerakli jadvallarga joylashtirish kerak, yoki jadvalda borligini aniqlash kerak.
Belgilar zanjirni juftlikka qayta ishlash kerak.
Probel, kommentariy va boshqaruv belgilarni olib tashlashi kerak.
Leksik tahlilchi bu translyator, unda kiruvchi zanjir - programm matni, chiquvchi zanjir bu leksemalar ketma ketligi. Bu ketma ketlik leksemalar jadvali deb nomlanadi.
Leksik tahlilni to‘liq bajarish uchun holat diagrammalarga amallar qo‘shamiz.
Bunda ti terminal belgilar, Di bajarish kerak bo‘lgan amallar.
Misol: Bizga ishorasiz o‘nli butun son berilsin va uni qiymatini kvadrati chop etilsin. Uning grammatikasi kuyidagicha bo‘ladi:
S→N⊥
N→0|1|…|9|N0|N1|…|N9 Yechim:
Sonni har bir raqamini o‘qiganda Gorner sxemasi bo‘yicha uning qiymatini hisoblaymiz, ohirgi belgi o‘qilganda kvadratini chop etamiz:
Do'stlaringiz bilan baham: | 
