Ifodalarning sintaktik tahlili

|
Ifodalarning sintaktik tahlili
|
bet | 61/131 | Sana | 16.06.2024 | Hajmi | 1,92 Mb. | | #264063 |
Bog'liq Tiplarni dinamik tarzdaIfodalarning sintaktik tahlili. Sintaktik tahlil deganda joriy qilingan grammatikaga leksemalarning maʻlum ketma-ketligi hosil qilgan tilga tegishli ekanligini belgilovchi jarayondir. Amalda, har qanday grammatikadan parser qurishingiz mumkin, ammo amalda ishlatiladigan grammatikalar maxsus shaklga ega. Masalan, n uzunlikdagi kiruvchi satr uchun murakkabligi O(n3) dan oshmasligi kerak bo‘lgan har qanday kontekst-erkin grammatika uchun analizator (parser) qurish mumkin. Lekin ko‘p hollarda tez ishlaydigan analizator qurish imkonini beradigan berilgan dasturlash tili asosida grammatika qurish mumkin. Amaliyotda tili analizatorlari odatda chiziqli murakkablikka ega. Masalan, dasturda chapdan o‘ngga qarab bitta terminal belgiga (leksik sinf) oldinga qarab ko‘rish orqali erishiladi.
Sintaktik tahlillovchi kirish parametrlari - bu leksema va jadvllar ketma- ketligi, masalan, ichki tasvirlangan jadval, bu jadval sintaktik tahlillovchi uchun chiqish parametrlaridir.
Sintaktik tahlillovchi chiqish parametrlari – jadvallar va tahlil daraxti hisoblanadi, masalan, kompilyatorning keyingi ko‘rishi uchun chiquvchi bo‘lib hisoblangan identifikatorlar jadvali va tiplar jadvali (masalan, tipli nazoratni amalga oshiruvchi ko‘rinish bo‘lishi mumkin).
Leksik va sintaktik tahlil bosqichlarining alohida qarashlarga ajratilishi shart emas. Odatda bu fazalar bir xil ko‘rinishda bir-biri bilan o‘zaro taʻsirlashadi. Bunday ko‘rishning asosiy fazasi ajralish fazasi bo‘lib hisoblanadi va sintaktik analizator leksik analizatorga har safar boshqa terminal belgi kerak bo‘lganda murojaat qiladi.
Sintaktik tahlillovchi sinflari. Juda ko‘p tahlillovchi algoritmlarni quyidagi ikki sinflarning biriga tegishlidir.
top-down algoritmlari (past sathlarga yo‘naltirilgan);
bottom-up algoritmlari (yuqori stahlarga yo‘naltirilgan);
Bu terminlarning kelib chiqishi sintaktik daraxt tugunlarining yaratilish usuli bilan bog‘liq: ildizdan (grammatika aksiomalari) yuqori tugunlargacha (terminal simvollar), yoki yuqori tugunlardan ildizgacha.
Past sathlarga yo‘naltirilgan analizatorlar chiqishni qurish uchun grammatika aksiomadan boshlab va terminal simvollar zanjiri bilan tugaydi. Analizatorlar quyidagi xususiyatlarga ega bo‘lgan LL grammatika bilan bog‘liq:
u natija bermaydigan analizatorlarga ega bo‘lishi mumkin;
birinchi L harfi - kiruvchi zanjirni chapdan o‘nga qarab o‘qilishini bildiradi (left-to-right scan);
ikkinchi L harfi - zanjirning chap chiqishi qurilayotganini bildiradi (leftmost derivation).
Past sathlarga yo‘naltirilgan analizatorlarni yaratish juda qulay bo‘lib hisoblanadi, ularni qo‘lda ham yaratish mumkin, masalan, rekursiv kamayish usuli bilan. LL grammatika bilan ishlash va o‘zgartirish murakkab emas. LL grammatika
bo‘lmagan grammatikalarda analizatorlar uchun rekursiv kamayish usullaridan foydlanish mumkin.
Boshqa tomondan past sathlarga yo‘naltirilgan analizatorlarga qaraganda yuqori sathlarga yo‘naltirilgan analizatorlar ko‘proq ishlatiladi. Chunki ular ko‘proq grammatikalarni tahlil qila oladi. Shuning uchun bu analizatorlar uchun analizatolarni yaratuvchi maxsus dasturlar mavjud. yuqori sathlarga yo‘naltirilgan analizatorlar bilan LR – grammatika bog‘liq. Bundagi L harfi oldingidek, kiruvchi zanjirni chapdan o‘nga qarab o‘qilishini bildiradi (left-to-right scan), R harfi esa - zanjirning o‘ng chiqishi qurilayotganini bildiradi(rightmost derivation). Bugungi kunda LR – grammatikaga asoslangan analizatorlar bilan juda ko‘p dasturlash tillari foydalanmoqda.
|
| |