|
Chap rekursiv grammatikalar
|
| bet | 64/131 | | Sana | 16.06.2024 | | Hajmi | 1,92 Mb. | | #264063 |
Bog'liq Tiplarni dinamik tarzdaChap rekursiv grammatikalar. LL (k) – xususityalari grammatika uchun kuchli cheklovlar yuklaydi. Natijada grammatika LL(1) xususiyatiga ega bo‘lishi uchun baʻzan grammatikani o‘zgartirish mumkin. Buni amalga oshirish uchun har doim ham muvaffaqiyatli bo‘lmaydi, lekin bir LL(1) grammatika olish imkoniyatiga ega bo‘ldi, keyin rekursiv kamayish usuli asosida analizator qurishda foydalanishingiz mumkin. Faraz qilaylik, quyidagi grammatika asosida tahlillovchi qurish kerak bo‘lsin.
E → E + T|E-T|T
T → T * F|T/F|F
F → num|(E)
FIRST(T)to‘plamning terminallari FIRST(E+T) to‘plamga tegishli bo‘lsin. Bu holda protseduralarning ketma – ket chaqirish bir qiymatli aniqlab bilmaymiz, chunki kirish zanjiridagilarni tahlil qilishmiz kerak.
Muammo shundaki, terminal bo‘lmagan E ning o‘ng pozitsiyasida qoidaning o‘ng tomoni, chap qismi ham Eda bo‘ladi. Bunday holatlarda terminal bo‘lmagan E – chap rekursiv deb aytiladi.
Taʻrif. Agar grammatikada A =>* Aw chiqish mavjud bo‘lsa, A terminal bo‘lmagan KS grammatika G chap rekursiv deb aytiladi.
Bitta bo‘lsa ham chap rekursiv qoidaga ega bo‘lgan grammatika LL(1)- grammatika bo‘la olmaydi. Ikkinchi tomondan bilamizki, KS til bitta bo‘lsa ham chap rekursiv bo‘lmagan grammatika bilan aniqlanadi.
Chap rekursivlikni bartaraf etish algoritmi. To‘g‘ridan-to‘g‘ri chap rekursivlikni bartaraf etish algoritmini keltiramiz.
G = (N, T, P, S)- KS grammatika va A → Aω1|Aω2|…|Aωn|ν1|ν2|…|νm qoidalar P dagi barcha qoidalarni ifodalasin, A ning chap qismini saqlamaydi, chunki biror bir zanjir νi - A terminal bo‘lmagan bilan boshlanmaydi. N to‘plamga yana bir taerminal bo‘lmagan Aʻ qo‘shamiz va A da chap tomondagi bo‘lgan qoidalarni o‘zgartiramiz. Quyidagi qoidalarni olamiz.
A → ν1|ν2|…|νm | ν1Aʻ|ν2 Aʻ|…|νm Aʻ|
Aʻ → ω1| ω2|…| ωm | ω1Aʻ| ω2 Aʻ|…| ωm Aʻ|
Olingan grammatika oldingisiga ekvivalet ekanligini ko‘rsatish mumkin. Yuqorida keltirilgan grammatikaga bu akslantirishni qo‘yib, arifmetik amallarni yozish uchun quyidagicha grammatikani olamiz:
E → T|TEʻ
Eʻ →+T|+TEʻ T → F|FTʻ
Tʻ → *F|*FTʻ F → (E)|num
Tuzilgan grammatika LL(1) xususiyatlariga ega ekanligini ko‘rsatish mumkin.
Agar ikkita qoida ham terminal bo‘lmagan bir xil belgi bilan bo‘lsa, aniq muammoni vaziyatga keltiradi, masalan,
S → if E then S else S S → if E then S
Bunday hollarda yana bir terminal bo‘lmagan qoida qo‘shamiz, qaysiki yuqoridagi vaziyatga oydinlik kiritib, farqli qoidalarni keltirib chiqaradi va quyidagi qoidani olishimiz mumkin:
S → if E then S Sʻ Sʻ →
Sʻ → else S
Olingan grammatika rekursiv kamayish usuli bilan amalga oshirilishi mumkin.
|
| |
