Chap rekursiv grammatika. Tahlil qilish Chap rekursiyani onlayn o'chirish
Bashoratli tahlilni qo'llashda asosiy qiyinchilik - bu kirish tili uchun grammatikani topish, uni yagona aniqlangan kirishlar bilan tahlil jadvalini yaratish uchun ishlatish mumkin. Ba'zan, ba'zi oddiy o'zgarishlar bilan LL (1) bo'lmagan grammatika ekvivalent LL (1) grammatikaga qisqartirilishi mumkin. Ushbu transformatsiyalar orasida eng samaralisi chap faktorizatsiya va olib tashlashdir chap rekursiya. Bu erda ikkita fikrni ta'kidlash kerak. Birinchidan, bu o'zgarishlardan keyin har bir grammatika LL(1) ga aylanmaydi, ikkinchidan, bunday o'zgarishlardan keyin hosil bo'lgan grammatika tushunarsiz bo'lib qolishi mumkin.
To'g'ridan-to'g'ri chap rekursiyani, ya'ni formaning rekursiyasini quyidagi usulda olib tashlash mumkin. Avval biz A-qoidalarini guruhlaymiz:
bu yerda satrlarning hech biri A bilan boshlanmaydi. Keyin bu qoidalar to'plami bilan almashtiramiz
Bu erda A" yangi terminal bo'lmagan. A noterminalidan siz avvalgidek bir xil zanjirlarni olishingiz mumkin, ammo endi buni qilolmaysiz. chap rekursiya. Ushbu protsedura barcha to'g'ridan-to'g'ri yo'q qiladi chap rekursiyalar, lekin ikki yoki undan ortiq qadamni o'z ichiga olgan chap rekursiya o'chirilmaydi. Quyida berilgan algoritm 4.8 hamma narsani o'chirishga imkon beradi chap rekursiyalar grammatikadan.
Algoritm 4.8. Olib tashlash chap rekursiya.
Kirish. Elektron qoidalarsiz KS-grammatikasi G (A -> e shaklida).
Chiqish. KS-grammatikasi G" holda chap rekursiya, G ga teng.
Usul. 1 va 2-bosqichlarni bajaring.
(1) G grammatikasining noterminallarini istalgan tartibda joylashtiring.
(2) Quyidagi protsedurani bajaring:
Shaklning har qanday qoidasi uchun 2-bosqichda tashqi halqaning (i-1) iteratsiyasidan keyin 
, bu erda k< i, выполняется s >k. Natijada, keyingi iteratsiyada (i tomonidan), ichki halqa (j tomonidan) har qanday qoidada m ning pastki chegarasini ketma-ket oshiradi. 
, m >= i bo'lgunga qadar. Keyin, darhol olib tashlangandan so'ng chap rekursiya A i -qoidalar uchun m i dan katta bo'ladi.
Algoritm 4.8 grammatikada e - qoidalari bo'lmasa qo'llaniladi (A -> e ko'rinishidagi qoidalar). Grammatikada mavjud bo'lgan elektron qoidalar oldindan o'chirilishi mumkin. Olingan grammatika holda chap rekursiya elektron qoidalarga ega bo'lishi mumkin.
Chap faktorizatsiya
Chap faktorizatsiyaning asosiy g'oyasi shundan iboratki, agar ikkita muqobildan qaysi biri noterminal A ni kengaytirish uchun ishlatilishi noma'lum bo'lsa, A qoidalarini o'zgartirish kerak, shunda qaror qabul qilish uchun etarli ma'lumot bo'lmaguncha kechiktiriladi. to'g'ri qaror qabul qiling.
Agar 
- ikkita A -qoidalari va kirish zanjiri bo'sh bo'lmagan qatordan boshlanadi, biz birinchi qoidaga ko'ra yoki ikkinchisiga ko'ra kengaytirishni bilmaymiz. Kengaytirish orqali qarorni kechiktirishingiz mumkin. So'ngra, nimadan chiqarilishi mumkinligini tahlil qilgandan so'ng, siz orqali yoki orqali kengaytirishingiz mumkin. Chap faktorlashtirilgan qoidalar shaklni oladi
Algoritm 4.9. Grammatikaning chap faktorizatsiyasi.
Kirish. KS-grammatikasi G.
Chiqish. Chap faktorli KS-grammatikasi G" ga ekvivalent G.
Usul. Har bir noterminal A uchun uning ikkita yoki undan ortiq muqobillari uchun umumiy bo'lgan eng uzun prefiksni toping. Agar , ya'ni, ahamiyatsiz bo'lmagan umumiy prefiks mavjud bo'lsa, barcha A qoidalarini almashtiring
bu yerda z bilan boshlanmagan barcha muqobillarni bildiradi
Bu yerda A" yangi noterminaldir. Ikkita muqobil umumiy prefiksga ega bo'lmaguncha ushbu transformatsiyani qo'llang.
4.9-misol. dan shartli gaplarning grammatikasini yana bir bor ko'rib chiqamiz misol 4.6:
S -> agar E bo'lsa, S | agar E keyin S boshqa S | a E -> b
Chap faktorizatsiyadan keyin grammatika shaklni oladi
S -> agar E keyin SS" | a S" -> boshqacha S | e E -> b
Afsuski, grammatika noaniq bo'lib qolmoqda va shuning uchun LL(1) grammatikasi emas.
LL(k)-grammatika, agar berilgan satr va dan kelib chiqadigan birinchi k belgilar (agar mavjud bo'lsa) uchun ba'zi bir terminal qatorining chiqishini olish uchun A ga qo'llanilishi mumkin bo'lgan ko'pi bilan bitta qoida mavjud bo'lsa,
Guruch. 4.4.
zikr etilgan k terminallar bilan boshlanadi va davom etadi.
Grammatika ba'zi k uchun LL(k)-grammatik bo'lsa, LL(k)-grammatikasi deyiladi.
4.7-misol. Grammatikani ko'rib chiqing G = ((S, A, B), (0, 1, a, b), P, S), bu erda P qoidalardan iborat
S -> A | B, A -> aAb | 0, B -> aBbb | 1.
Bu yerga . G har qanday k uchun LL (k)-grammatikasi emas. Intuitiv ravishda, agar biz etarlicha uzun a belgilar qatorini o'qishdan boshlasak, 0 yoki 1 ga duch kelmagunimizcha, S -> A va S -> B qoidalaridan qaysi biri birinchi bo'lib qo'llanilganligini bilmaymiz.
LL (k)-grammatikaning aniq ta'rifiga murojaat qilib, biz o'rnatamiz va y = a k 1b 2k . Keyin xulosalar
ta'rifning (1) va (2) xulosalariga mos keladi. x va y satrlarning birinchi k belgilar bir xil. Biroq, xulosa noto'g'ri. Bu erda k o'zboshimchalik bilan tanlanganligi sababli, G LL -grammatikasi emas.
LL(k)-grammatikasiga ta'rif berishning oqibatlari
4.6 teorema. KS-grammatikasi LL(k)-grammatikasi, agar va faqat ikki xil qoida uchun va P chorrahasidan bularning barchasi bilan bo'sh , Nima 
.
Isbot. Zaruriyat. Faraz qilaylik va teorema shartlarini qanoatlantirsin va x ni o'z ichiga oladi. Keyin, BIRINCHI ta'rifiga ko'ra, ba'zi y va z uchun xulosalar mavjud
(E'tibor bering, biz bu erda ko'rib chiqilayotgan barcha grammatikalar uchun taxmin qilinganidek, N tarkibida foydasiz bo'lmagan terminallar mavjud emasligidan foydalandik.) Agar |x|< k ; то y = z = e . Так как , то G не LL (k)- грамматика .
Adekvatlik. Faraz qilaylik, G LL(k)-grammatikasi emas.
Keyin ikkita xulosa bor
x va y zanjirlari birinchi k pozitsiyalarda mos kelishini, lekin . Shuning uchun va P dan va har bir to'plamdan farqli qoidalar 
Va 
BIRINCHI k (x) zanjiri FIRST k (y) bilan mos keladi.
4.8-misol. Ikki qoidadan tashkil topgan G grammatikasi S -> aS | a LL(1)-grammatikasi bo'lmaydi, chunki
BIRINCHI 1 (aS) = BIRINCHI 1 (a) = a.
Intuitiv ravishda buni quyidagicha tushuntirish mumkin: a belgisi bilan boshlangan zanjirni tahlil qilishda faqat shu birinchi belgini ko'rib, S -> aS yoki S -> a qoidalarining qaysi biri S ga qo'llanilishi kerakligini bilmaymiz. Boshqa tomondan, G LL(2)-grammatikasi. Haqiqatan ham, hozirgina keltirilgan teoremaning yozuvida, agar , keyin A = S va. S uchun faqat ikkita ko'rsatilgan qoida berilganligi sababli, u holda . FIRST2(aS) = aa va FIRST2(a) = a bo'lgani uchun oxirgi teorema bo'yicha G LL (2)-grammatik bo'ladi.
Chap rekursiyani olib tashlash
Bashoratli tahlilni qo'llashda asosiy qiyinchilik - bu kirish tili uchun grammatikani topish, uni yagona aniqlangan kirishlar bilan tahlil jadvalini yaratish uchun ishlatish mumkin. Ba'zan, ba'zi oddiy o'zgarishlar bilan LL (1) bo'lmagan grammatika ekvivalent LL (1) grammatikaga qisqartirilishi mumkin. Ushbu transformatsiyalar orasida chap faktorizatsiya va chap rekursiyani olib tashlash eng samarali hisoblanadi. Bu erda ikkita fikrni ta'kidlash kerak. Birinchidan, bu o'zgarishlardan keyin har bir grammatika LL(1) ga aylanmaydi, ikkinchidan, bunday transformatsiyalardan keyin hosil bo'lgan grammatika tushunarsiz bo'lib qolishi mumkin.
To'g'ridan-to'g'ri chap rekursiyani, ya'ni formaning rekursiyasini quyidagi usulda olib tashlash mumkin. Avval biz A-qoidalarini guruhlaymiz:
bu erda hech qanday satr A bilan boshlanmaydi. Keyin ushbu qoidalar to'plamini bilan almashtiramiz
Bu yerda A" yangi noterminaldir. Xuddi shu zanjirlar noterminal Adan oldingi kabi chiqarilishi mumkin, ammo hozir chap rekursiya yo'q. Bu protsedura barcha darhol chap rekursiyalarni olib tashlaydi, lekin ikki yoki undan ortiq bosqichni o'z ichiga olgan chap rekursiyani olib tashlamaydi. Berilgan. quyida algoritm 4.8 grammatikadan barcha chap rekursiyalarni olib tashlash imkonini beradi.
Algoritm 4.8. Chap rekursiyani olib tashlash.
Kirish. Elektron qoidalarsiz KS-grammatikasi G (A -> e shaklida).
Chiqish. KS-grammatikasi G" chap rekursiyasiz, G ga ekvivalent.
Usul. 1 va 2-bosqichlarni bajaring.
(1) G grammatikasining noterminallarini istalgan tartibda joylashtiring.
(2) Quyidagi protsedurani bajaring:
Shaklning istalgan qoidasi uchun 2-bosqichda tashqi halqaning (i-1)-chi iteratsiyasidan keyin 
, bu erda k< i
, выполняется s >k. Natijada, keyingi iteratsiyada (i tomonidan), ichki halqa (j tomonidan) har qanday qoidada m ning pastki chegarasini ketma-ket oshiradi. 
, m >= i bo'lgunga qadar. Keyin, A i -qoidalar uchun darhol chap rekursiyani olib tashlaganingizdan so'ng, m i dan katta bo'ladi.
LL(k)-xususiyat grammatikaga katta cheklovlar qo'yadi. Ba'zan grammatikani shunday o'zgartirish mumkinki, natijada paydo bo'lgan grammatikaga ega bo'ladi mulk LL(1) . Bunday transformatsiya har doim ham muvaffaqiyatli bo'lavermaydi, lekin agar LL(1) grammatikasini olish mumkin bo'lsa, u holda analizatorni qurish uchun siz orqaga qaytishsiz rekursiv tushish usulidan foydalanishingiz mumkin.
Aytaylik, biz quyidagi grammatika bilan yaratilgan til uchun analizator qurishimiz kerak:
E → E + T | E – T | T
T → T * F | T/F | F
F → son | (E)
Bir nechta terminallar BIRINCHI(T) ham to‘plamga tegishli BIRINCHI(E+T), shuning uchun kirish zanjirini tahlil qilishda bajarilishi kerak bo'lgan protsedura chaqiruvlari ketma-ketligini aniq belgilash mumkin emas. Muammo shundaki, terminal bo'lmagan E qoidaning o'ng tomonining birinchi holatida sodir bo'ladi, uning chap tomoni ham E. Bunday vaziyatda noterminal E to'g'ridan-to'g'ri chap rekursiv deyiladi.
Noterminal A KS-grammatikasi G chaqirdi chap rekursiv , grammatikada xulosa bo'lsa A =>* Voy.
Kamida bitta chap rekursiv qoidaga ega grammatika bo'lishi mumkin emas LL(1)-grammatika.
Boshqa tomondan, ma'lumki, har bir CS tili kamida bitta chap bo'lmagan rekursiv grammatika bilan belgilanadi.
Chap rekursivlikni yo'q qilish algoritmi
Mayli G = (N, T, P, S)– KS-grammatikasi va qoidasi A→Aw 1 | Voy 2 | ... | Voy n | v 1 | v 2 | ... | v m dan barcha qoidalarni ifodalaydi P o'z ichiga olgan A chap tomonda, va zanjirlarning hech biri v i noterminal bilan boshlanmaydi A.
Keling, to'plamga qo'shamiz N boshqa terminal bo'lmagan A" va o'z ichiga olgan qoidalarni almashtiring A chap tomonda, quyidagilarga:
A → v 1 | v 2 | ... | v m | v 1 A' | v 2 A' | ... | v m A"
A' → w 1 | w 2 | ... | w n | w 1 A' | w 2 A' | ...| w n A"
Olingan grammatika asl nusxaga teng ekanligini isbotlash mumkin.
Ushbu transformatsiyani arifmetik ifodalarni tavsiflovchi yuqoridagi grammatikaga qo'llash natijasida biz quyidagi grammatikaga ega bo'lamiz:
E → T | T.E."
E" → + T | + T.E."
T → F | F.T."
T"→ * F | * F.T."
F → (E) | son
Olingan grammatika xossaga ega ekanligini ko'rsatish oson LL(1).
Yana bir shunga o'xshash muammo bir xil noterminal uchun ikkita qoida bir xil belgilar bilan boshlanganda yuzaga keladi.
Masalan,
S → agar E bo'lsa, S boshqa S
S → agar E keyin S
Bunday holda, biz ushbu qoidalarning turli oxiriga mos keladigan yana bir terminal bo'lmagan qo'shamiz. Biz quyidagi qoidalarni olamiz:
S → agar E keyin S S’
S" →
S"→ boshqa S
Olingan grammatika uchun rekursiv tushish usulini amalga oshirish mumkin.
9.1.4. Qaytish bilan rekursiv tushish.
Rekursiv tushish usulini qo'llash uchun 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 grammatikani toʻplamlardan iborat shaklga aylantir BIRINCHI kesishmaydi, bu murakkab jarayon, shuning uchun amalda bir texnika deb ataladi qaytish bilan rekursiv tushish .
Buning uchun leksik analizator an'anaviy usullardan tashqari ob'ekt sifatida ifodalanadi skanerlash, Keyingisi va hokazo, nusxa ko'chirish konstruktori ham mavjud. Keyin, noaniqlik paydo bo'lishi mumkin bo'lgan barcha holatlarda, tahlil qilishni boshlashdan oldin, leksik analizatorning hozirgi holatini eslab qolishingiz kerak (ya'ni, leksik analizatorning nusxasini oling) va biz birinchisi bilan shug'ullanayotganimizni hisobga olib, matnni tahlil qilishni davom ettirishingiz kerak. bu vaziyatda mumkin bo'lgan konstruktsiyalar. Agar bu tahlil qilish opsiyasi bajarilmasa, u holda leksik analizator holatini tiklashingiz va keyingi grammatika opsiyasi yordamida yana bir xil fragmentni tahlil qilishga urinib ko'rishingiz kerak va hokazo. Agar barcha tahlil qilish opsiyalari bajarilmasa, xato haqida xabar beriladi.
Ushbu tahlil qilish usuli orqaga qaytishsiz rekursiv tushishdan ko'ra sekinroqdir, ammo bu holda grammatikani asl shaklida saqlab qolish va dasturchi harakatini tejash mumkin.
Rasmiy grammatikalarning o'ziga xos xususiyati shundaki, ular cheksiz qoidalar to'plamidan foydalangan holda tilning cheksiz zanjirlarini aniqlashga imkon beradi (albatta, til zanjirlari to'plami ham chekli bo'lishi mumkin, lekin oddiy real tillar uchun ham. bu shart odatda bajarilmaydi). Yuqoridagi belgili oʻnli butun sonlar uchun grammatik misol 15 ta qoidadan foydalangan holda cheksiz butun sonlar toʻplamini belgilaydi.
Cheklangan qoidalar to'plamidan foydalanish qobiliyatiga rekursiv qoidalar orqali grammatik belgilarning ushbu shaklida erishiladi. Grammatik qoidalardagi rekursiya noterminal belgilardan birining o'zi orqali aniqlanishida ifodalanadi. Rekursiya to'g'ridan-to'g'ri (aniq) bo'lishi mumkin - keyin belgi bir qoidada o'zi orqali aniqlanadi yoki bilvosita (yo'q) - keyin xuddi shu narsa qoidalar zanjiri orqali sodir bo'ladi.
Yuqorida muhokama qilingan G grammatikasida to'g'ridan-to'g'ri rekursiya qoidada mavjud:<чс>-»<чс><цифра>, va uning ekvivalent grammatikasida G" - qoidada: T-VTF.
Rekursiya cheksiz bo'lmasligi uchun, unda ishtirok etuvchi grammatikaning terminal bo'lmagan belgisi uchun ham uni belgilaydigan, o'zini chetlab o'tadigan va cheksiz rekursiv ta'rifdan qochishga imkon beradigan boshqa qoidalar bo'lishi kerak (aks holda bu belgi shunchaki grammatikada kerak emas). Bu qoidalar<чс>-»<цифра>- G va T->F grammatikasida - G grammatikasida».
Rasmiy tillar nazariyasida rekursiya haqida boshqa hech narsa aytish mumkin emas. Ammo rekursiyaning ma'nosini to'liqroq tushunish uchun siz tilning semantikasiga murojaat qilishingiz mumkin - yuqorida muhokama qilingan misolda bu imzolangan o'nli butun sonlar tili. Keling, uning ma'nosini ko'rib chiqaylik.
Grammatikaning ta'rifi. Ekusa-maura shakli "ZO /
Agar siz raqam nima ekanligini aniqlashga harakat qilsangiz, unda har qanday raqamning o'zi raqam ekanligidan boshlashingiz mumkin. Bundan tashqari, siz har qanday ikkita raqam ham raqam ekanligini, keyin esa uchta raqam va hokazo ekanligini ko'rishingiz mumkin. Agar siz ushbu usul yordamida raqamning ta'rifini tuzsangiz, u hech qachon tugallanmaydi (matematikada raqamning raqam sig'imi emas. har qanday narsa bilan cheklangan). Biroq, har safar yangi raqam hosil qilganda, biz shunchaki o'ngga (chapdan o'ngga yozishga odatlanganimiz uchun) allaqachon yozilgan raqamlar qatoriga birlik qo'shayotganimizni sezishingiz mumkin. Va bir raqamdan boshlanadigan bu raqamlar qatori ham sondir. Keyin "raqam" tushunchasining ta'rifi shunday tuzilishi mumkin: "raqam - bu har qanday raqam yoki o'ngga istalgan raqam qo'shiladigan boshqa raqam". Aynan shu narsa G va G grammatikalari qoidalarining asosini tashkil qiladi va qoidalarning ikkinchi qatorida o'z aksini topgan.<чс>-><цифра> [ <чс><цифра>va T->F | TF. Ushbu grammatikadagi boshqa qoidalar raqamga belgi qo'shishga imkon beradi (qoidalarning birinchi qatori) va "raqam" (qoidalarning uchinchi qatori) tushunchasini aniqlash. Ular elementar va tushuntirishni talab qilmaydi.
Rekursiya printsipi (ba'zan "iteratsiya printsipi" deb ataladi, u mohiyatni o'zgartirmaydi) rasmiy grammatika g'oyasidagi muhim tushunchadir. Qanday bo'lmasin, aniq yoki bilvosita rekursiya har qanday haqiqiy dasturlash tillarining grammatikalarida doimo mavjud. Aynan shu narsa cheksiz ko'p til zanjirlarini yaratishga imkon beradi va rekursiya tamoyilini tushunmasdan ularning avlodi haqida gapirish mumkin emas. Odatda haqiqiy tilning grammatikasida? dasturlash bitta emas, balki rekursiya yordamida tuzilgan qoidalar to'plamini o'z ichiga oladi.
Grammatikani o'rnatishning boshqa usullari
Backus-Naur shakli rasmiy nuqtai nazardan qulay, ammo rasmiy grammatikani yozishni tushunish har doim ham oson emas. Rekursiv ta'riflar til satrlarini rasmiy tahlil qilish uchun yaxshi, lekin inson nuqtai nazaridan qulay emas. Masalan, qanday qoidalar<чс>-><цифра> | <чс><цифра>aniq bo'lmagan va qo'shimcha tushuntirishni talab qiladigan bittadan boshlab o'ngdagi istalgan sonni qo'shish orqali raqamni qurish qobiliyatini aks ettiradi.
Lekin dasturlash tilini yaratishda uning grammatikasini nafaqat ushbu til uchun kompilyatorlar yaratadiganlar, balki tildan foydalanuvchilar – bo‘lajak dastur ishlab chiquvchilar ham tushunib olishlari muhim. Shuning uchun, rasmiy grammatika qoidalarini tavsiflashning boshqa usullari mavjud bo'lib, ular insonning ko'proq tushunishiga qaratilgan.
Grammatik qoidalarni yozish
metabelgilardan foydalanish
Metabelgilar yordamida grammatika qoidalarini yozish grammatika qoidalari qatorida maxsus belgilar bo'lishi mumkin, deb taxmin qilinadi - meta-
358 9-bob. Rasmiy tillar va grammatika
Belgilar - alohida ma'noga ega bo'lgan va o'ziga xos tarzda talqin etiladi. Eng ko'p ishlatiladigan metabelgilar () (qavslar), (kvadrat qavslar), () (jingalak qavslar), "," (vergul) va "" (tirnoqlar). Ushbu meta-belgilar quyidagi ma'noga ega:
□ Qavslar ularning ichida sanab o'tilgan barcha zanjirlarni bildiradi
grammatik qoidaning berilgan joyidagi belgilar faqat bitta ce bo'lishi mumkin
kurtak;
□ kvadrat qavslar ularda ko'rsatilgan zanjir paydo bo'lishi mumkinligini anglatadi
grammatika qoidalari ma'lum bir joyda bo'lishi mumkin yoki bo'lmasligi mumkin (ya'ni, ular bo'lishi mumkin
unda bir marta bo'lishi mumkin yoki umuman bo'lmasligi mumkin);
□ jingalak qavslar ularning ichida ko'rsatilgan qator paydo bo'lmasligini bildiradi
grammatik qoidalar ma'lum bir joyda bir necha marta sodir bo'ladi, bir marta sodir bo'ladi
bir marta yoki xohlagancha ko'p marta;
□ vergul tur ichidagi belgilar qatorlarini ajratish uchun ishlatiladi
qavslar;
□ Qo'shtirnoq metabelgilardan biri kerak bo'lgan hollarda qo'llaniladi
zanjirga odatdagi tarzda kiriting - ya'ni qavslardan biri yoki orqasida
beshinchisi til belgilari zanjirida bo'lishi kerak (agar iqtibosning o'zi bo'lsa
belgilar zanjiriga kiritilishi kerak, keyin uni ikki marta takrorlash kerak - bu
printsip dastur ishlab chiquvchilarga tanish).
Yuqorida muhokama qilingan G grammatika qoidalari metabelgilar yordamida yozilgan bo'lsa, shunday bo'lishi kerak:
<число> -» [(+.-)]<цифра>{<цифра>}
<цифра> ->0|1|2|3|4|5|6|7|8|9
Qoidalarning ikkinchi qatori izohlarga muhtoj emas va birinchi qoida quyidagicha: “Raqam bu + yoki - belgilaridan boshlanishi mumkin boʻlgan belgilar zanjiri boʻlib, keyin bitta raqamdan iborat boʻlishi kerak, undan keyin esa bitta raqam boʻlishi kerak. istalgan sonli raqamlar ketma-ketligi." Backus-Naur shaklidan farqli o'laroq, metasimbollardan foydalangan holda yozish shaklida, ko'rib turganingizdek, birinchi navbatda, grammatikada tushunarsiz terminal bo'lmagan belgi olib tashlanadi.<чс>, ikkinchidan, biz rekursiyani butunlay yo'q qilishga muvaffaq bo'ldik. Grammatika oxir-oqibat aniqroq bo'ldi.
Metambollardan foydalangan holda qoidalarni yozish shakli grammatika qoidalarini ifodalashning qulay va tushunarli usulidir. Ko'p hollarda u takrorlash belgisi () (jingalak qavslar) bilan almashtirib, rekursiyadan butunlay xalos bo'lishga imkon beradi. Keyingi materiallardan ma'lum bo'lishicha, bu shakl grammatika turlaridan biri - muntazam grammatika uchun eng keng tarqalgan.
Grammatik qoidalarni grafik shaklda yozib olish
Qoidalarni grafik shaklda yozishda butun grammatika maxsus tuzilgan diagrammalar to'plami shaklida taqdim etiladi. Bu shakl Paskal tili grammatikasini tavsiflashda taklif qilingan va keyinchalik u adabiyotda keng tarqalgan. U barcha grammatika turlari uchun mavjud emas, faqat
Grammatikaning ta'rifi. Backus-Naur shakli 359
Kontekstsiz va muntazam turlar uchun, lekin bu etarli, shuning uchun u taniqli dasturlash tillarining grammatikasini tavsiflash uchun ishlatilishi mumkin.
Belgilanishning bu shaklida grammatikaning har bir terminal bo'lmagan belgisi yo'naltirilgan grafik shaklida tuzilgan diagrammaga mos keladi. Grafikda quyidagi turdagi burchaklar mavjud:
□ kirish nuqtasi (diagrammada hech qanday tarzda ko'rsatilmagan, u erdan boshlanadi)
grafikning kirish yoyi);
□ terminal bo'lmagan belgi (diagrammada to'rtburchaklar bilan belgilanadi, unda
ramz belgisi kiritilgan);
□ terminal belgilar zanjiri (diagrammada oval, doira bilan ko'rsatilgan
yoki dumaloq qirralari bo'lgan to'rtburchaklar, uning ichida yozilgan
kurtak);
□ tugun nuqtasi (diagrammada qalin nuqta yoki soya bilan ko'rsatilgan
doira);
□ chiqish nuqtasi (hech qanday tarzda belgilanmagan, grafikning chiqish yoyi shunchaki unga kiradi).
Har bir diagrammada faqat bitta kirish nuqtasi va bitta chiqish nuqtasi mavjud, ammo qolgan uch turdagi cho'qqilarning istalgan soni. Cho'qqilar bir-biri bilan yo'naltirilgan grafik yoylari (strelkali chiziqlar) bilan bog'langan. Yoylar faqat kirish nuqtasidan chiqishi mumkin va faqat kirish nuqtasiga kirishi mumkin. Yoyning qolgan cho'qqilari ham kirishi, ham chiqishi mumkin (to'g'ri tuzilgan grammatikada har bir tepada kamida bitta kirish va kamida bitta chiqish bo'lishi kerak).
Grammatikaning har qanday terminal bo'lmagan belgisiga mos keladigan belgilar zanjirini qurish uchun siz ushbu belgining diagrammasini ko'rib chiqishingiz kerak. Keyin, kirish nuqtasidan boshlab, diagramma grafigining yoylari bo'ylab har qanday cho'qqilar orqali chiqish nuqtasiga qadar harakat qilishingiz kerak. Bunday holda, terminal bo'lmagan belgi bilan belgilangan tepadan o'tib, ushbu belgi hosil bo'lgan zanjirga joylashtirilishi kerak. Terminal belgilar zanjiri bilan ko'rsatilgan cho'qqidan o'tayotganda, bu belgilar ham hosil bo'lgan zanjirga joylashtirilishi kerak. Diagrammaning tugun nuqtalaridan o'tayotganda, hosil bo'lgan zanjirda hech qanday harakatlar qilish kerak emas. Harakatning mumkin bo'lgan yo'liga qarab, siz diagramma grafigining istalgan cho'qqisidan bir marta emas, bir marta yoki xohlaganingizcha ko'p marta o'tishingiz mumkin. Diagrammaning chiqish nuqtasiga etib borishimiz bilan, hosil bo'lgan zanjirning qurilishi tugallanadi.
Olingan zanjir, o'z navbatida, terminal bo'lmagan belgilarni o'z ichiga olishi mumkin. Ularni terminal belgilari satrlari bilan almashtirish uchun siz yana tegishli diagrammalarni ko'rib chiqishingiz kerak. Va shunga o'xshash zanjirda faqat terminal belgilar qolmaguncha. Shubhasiz, ma'lum bir tilning belgilar zanjirini qurish uchun maqsadli grammatik belgining diagrammasidan ko'rib chiqishni boshlash kerak.
Bu tasvirlar bilan ishlaydigan grammatika qoidalarini tavsiflashning qulay usuli va shuning uchun faqat odamlarga qaratilgan. Hatto bu erda uning asosiy tamoyillarini oddiy taqdim etish ham juda og'ir bo'lib chiqdi, ammo mohiyati
9-bob. Rasmiy tillar va grammatika
Usul juda oddiy. Agar siz shakldagi diagrammalardan foydalangan holda G grammatikasidan "raqam" tushunchasining tavsifiga qarasangiz, buni osongina ko'rish mumkin. 9.1.
Guruch. 9.1. Belgilangan o'nli butun sonlar grammatikasining grafik tasviri: tepada - "son" tushunchasi uchun; quyida - "raqam" tushunchasi uchun
Yuqorida aytib o'tilganidek, bu usul asosan adabiyotlarda dasturlash tillari grammatikasini taqdim etishda qo'llaniladi. Foydalanuvchilar uchun - dastur ishlab chiquvchilari - bu qulay, ammo amaliy qo'llash U kompilyatorlarda hali mavjud emas.
Tillar va grammatikalarning tasnifi
Grammatikaning har xil turlari yuqorida aytib o'tilgan, ammo ular qanday va qanday asosda turlarga bo'linganligi ko'rsatilmagan. Biror kishi uchun tillar oddiy yoki murakkab bo'lishi mumkin, ammo bu ko'pincha odamning shaxsiyatiga bog'liq bo'lgan sof sub'ektiv fikrdir.
Kompilyatorlar uchun tillarni oddiy va murakkabga bo'lish mumkin, ammo bu holda bu bo'linish uchun qat'iy mezonlar mavjud. Quyida ko'rsatilgandek, bu ma'lum bir dasturlash tili qaysi turga tegishli ekanligiga bog'liq.
Rovaniya, bu til uchun tan oluvchining murakkabligi bog'liq. Til qanchalik murakkab bo'lsa, kompilyatorning ushbu tilda yozilgan dastlabki dastur zanjirlarini tahlil qilish uchun hisoblash xarajatlari shunchalik yuqori bo'ladi va shuning uchun kompilyatorning o'zi va uning tuzilishi shunchalik murakkab bo'ladi. Tillarning ayrim turlari uchun cheklangan hisoblash resurslariga asoslangan maqbul vaqt ichida ushbu tillardagi manba matnlarini tahlil qiladigan kompilyatorni yaratish printsipial jihatdan imkonsizdir (shuning uchun tabiiy tillarda dasturlar yaratish hali ham mumkin emas. Masalan, rus yoki ingliz tillarida).
Grammatikalarning tasnifi.
Chap rekursiyani o'z ichiga olgan grammatika LL(1) grammatikasi emas. Keling, qoidalarni ko'rib chiqaylik
A→ Aa(A da chap rekursiya)
A→ a
Bu yerga a ikkala noterminal variant uchun oldingi belgisi A. Xuddi shunday, chap rekursiv tsiklni o'z ichiga olgan grammatika LL(1) grammatikasi bo'la olmaydi, masalan
A→ Miloddan avvalgi
B→ CD
C→ A.E.
Chap rekursiv tsiklni o'z ichiga olgan grammatika faqat to'g'ridan-to'g'ri chap rekursiyani o'z ichiga olgan grammatikaga aylantirilishi mumkin, keyin esa qo'shimcha noterminallarni kiritish orqali chap rekursiyani butunlay yo'q qilish mumkin (haqiqatan ham u o'ng rekursiya bilan almashtiriladi, bu bilan bog'liq muammo emas. LL(1) -xususiyatlar).
Misol tariqasida generativ qoidalarga ega grammatikani ko'rib chiqing
S→ Aa
A→ Bb
B→ Cc
C→ Dd
C→ e
D→ Az
ishtirok etgan chap rekursiv tsiklga ega A B C D. Ushbu tsiklni to'g'ridan-to'g'ri chap rekursiya bilan almashtirish uchun biz noterminallarni quyidagicha buyurtma qilamiz: S, A, B, C, D.
Keling, shaklni yaratishning barcha qoidalarini ko'rib chiqaylik
Xi→ Xj g,
Qayerda Xi Va Xj terminal bo'lmagan va γ - terminal va terminal bo'lmagan belgilar qatori. Qaysi qoidalarga kelsak j ≥ i, hech qanday chora ko'rilmaydi. Biroq, agar chap rekursiv tsikl mavjud bo'lsa, bu tengsizlik barcha qoidalar uchun amal qila olmaydi. Biz tanlagan tartib bilan biz bitta qoida bilan ishlaymiz:
D→ Az
chunki A oldingi D bu tartibda. Endi almashtirishni boshlaylik A, mavjud bo'lgan barcha qoidalardan foydalanish A chap tomonda. Natijada biz olamiz
D→ Bbz
Chunki B oldingi D tartiblashda jarayon takrorlanib, qoidani beradi:
D→ CCbz
Keyin u yana takrorlanadi va ikkita qoida beradi:
D→ ecbz
D→ Ddcbz
O'zgartirilgan grammatika endi quyidagicha ko'rinadi:
S→ Aa
A→ Bb
B→ Cc
C→ Dd
C→ e
D→ Ddcbz
D→ ecbz
Bu hosil qiluvchi qoidalarning barchasi kerakli shaklga ega va chap rekursiv sikl to'g'ridan-to'g'ri chap rekursiya bilan almashtiriladi. To'g'ridan-to'g'ri chap rekursiyani bartaraf qilish uchun biz yangi terminal bo'lmagan belgini kiritamiz Z va qoidalarni o'zgartiring
D→ ecbz
D→ Ddcbz
D→ ecbz
D→ ecbzZ
Z→ dcbz
Z→ dcbzZ
E'tibor bering, transformatsiyadan oldin va keyin D muntazam ifoda hosil qiladi
(ecbz) (dcbz)*
Umumlashtirib, shuni ko'rsatishimiz mumkinki, agar noterminal bo'lsa A chap tomonlarda paydo bo'ladi r+ s qoidalarni ishlab chiqish, r ulardan to'g'ridan-to'g'ri chap rekursiya ishlatiladi va s- yo'q, ya'ni.
A→ Aa 1, A→ Aa 2,..., A→ Aa r
A→ β 1, A→ β 2,..., A→ β s
u holda ushbu qoidalar quyidagi bilan almashtirilishi mumkin:
Norasmiy dalil - bu transformatsiyadan oldin va keyin A muntazam ifoda hosil qiladi ( β 1 | β 2 |... | β s) ( α 1 | α 2 |... | α r) *
Shuni ta'kidlash kerakki, chap rekursiyani (yoki chap rekursiv tsiklni) yo'q qilish orqali biz hali ham LL (1) grammatikasini olmaymiz, chunki Ba'zi noterminallar uchun natijada paydo bo'lgan grammatika qoidalarining chap tomonida bir xil belgilardan boshlab muqobil o'ng tomonlar mavjud. Shuning uchun, chap rekursiyani yo'q qilgandan so'ng, grammatikani LL (1) shakliga aylantirishni davom ettirishimiz kerak.
17.Grammatikalarni LL(1) shakliga aylantirish. Faktorizatsiya.
Faktorizatsiya
Ko'p hollarda LL(1) xususiyatiga ega bo'lmagan grammatikalarni faktorizatsiya jarayonidan foydalanib LL(1) grammatikalariga aylantirish mumkin. Keling, bunday vaziyatning misolini ko'rib chiqaylik.
P→ boshlash D; BILAN oxiri
D→ d, D
D→ d
BILAN→ s; BILAN
BILAN→ s
Faktorizatsiya jarayonida biz chap tomonda bitta noterminal uchun bir nechta qoidalarni almashtiramiz, ularning o'ng tomoni bir xil belgi (belgilar zanjiri) bilan boshlanadi, bu erda o'ng tomonda umumiy boshlanish qo'shimcha ravishda kiritiladi. terminal bo'lmagan. Grammatika, shuningdek, qo'shimcha noterminal uchun qoidalar bilan to'ldiriladi, unga ko'ra qoidaning asl o'ng tomonining turli "qoldiqlari" undan olinadi. Yuqoridagi grammatika uchun bu quyidagi LL(1) grammatikasini beradi:
P→ boshlash D; BILAN oxiri
D→ d X X)
X→ , D(uchun 1-qoidaga muvofiq D uchun original grammatika d kerak D)
X→ ε (uchun 2-qoidaga muvofiq D uchun original grammatika d hech narsa (bo'sh qator))
BILAN→ s Y(qo'shimcha nonterminalni kiriting Y)
Y→ ; BILAN(uchun 1-qoidaga muvofiq C uchun original grammatika s quyidagicha; C)
Y→ ε (uchun 2-qoidaga muvofiq C uchun original grammatika s hech narsa (bo'sh qator))
Xuddi shunday, generativ qoidalar
S→ aSb
S→ aSc
S→ ε
faktorizatsiya orqali qoidalarga aylantirilishi mumkin
S→ aSX
S→ ε
X→ b
X→ c
va natijada grammatika LL(1) dir. Biroq, faktorizatsiya jarayonini umumiy holatga kengaytirish orqali avtomatlashtirish mumkin emas. Quyidagi misol nima bo'lishi mumkinligini ko'rsatadi. Keling, qoidalarni ko'rib chiqaylik
1. P→ Qx
2. P→ Ry
3. Q→ sQm
4. Q→ q
5. R→ sRn
6. R→ r
Ikkita variant uchun yo'l-yo'riq belgilarining ikkala to'plami P o'z ichiga oladi s, va "chidashga harakat qilmoqda s qavsdan tashqarida ", biz almashtiramiz Q Va R 1 va 2-qoidalarning o'ng tomonida:
P→ sQmx
P→ sRny
P→ qx
P→ ry
Ushbu qoidalar quyidagi qoidalar bilan almashtirilishi mumkin:
P→ qx
P→ ry
P→ sP 1
P 1 → Qmx
P 1 → Rny
uchun qoidalar P1 uchun dastlabki qoidalarga o'xshash P va oʻzaro kesishuvchi qoʻllanma belgilar toʻplamiga ega. Biz ushbu qoidalarni qoidalar bilan bir xil tarzda o'zgartirishimiz mumkin P:
P 1 → sQmmx
P 1 → qmx
P 1 → srnny
P 1 → rny
Faktoring, biz olamiz