Translyator, kompilyator va interpretator ishlash tamoyillari

Translyator, kompilyatorva interpretator ishlash tamoyillari Kompilyator belgilar katorini tekshirish muammosini, ushbu kator shu tilga tegishli yoki yukligini aniqlash uchun va tegishli bulsa, u holda tugiluvchi grammatika qoidalari terminlarida katorni strukturasini anglashni xal qilishi kerak. Ushbu muammo razbor muammosi sifatida mashxur. Tugiluvchi qoidalar bilan ishlovchi grmmatikani tekshiramiz. (Ye-boshlang'ich belgi). Ye - E+T 5. F- (E) E- T 6. F - x T - T*F 7. F - y 4. T - F Kurinib turibdiki, (x+u)*x kator ushbu tilga tegishli. Xususiy holda, buni kuyidagicha keltirib chiqarish mumkin (xar bir keltirib chiqarish kadami uchun kullanilayotgan qoida rakami ko'rsatilgan): Birinchi chiqishning xar bir bosqichida sententsial formaning eng chap noterminali grammatikaning biron bir tugiluvchi qoidasi yordamida almashtirildi. Shu sababli ushbu chiqish chap tomonli chiqish deyiladi. Xar bir bosqichida eng ung noterminal almashtirilgan ikkinchi chiqish esa ung tomonli chiqish deb ataladi. Shu kabi boshqa chiqishlar xam mavjudki, ular chap tomonli xam, ung tomonli xam hisoblanmaydilar, lekin translyatorlarni ko'rishda ulardan foydalanilmaydi. Gapni chap tomonli razbori chap tomonli chiqishni kullanilgan holda gapni generatsiya qilish uchun tugiluvchi qoidalarning ketma-ketligi sifatida aniklanadi. Ushbu holda chap tomonli razborni kuyidagicha yozish mumkin: 2,3,4,5,1,2,4,6,4,7,6. Gapni ung tomonli razbori ung tomonli chiqishni kullanilgan holda gapni generatsiya qilish uchun tugiluvchi qoidalarning tugiluvchi qoidalarning teskari ketma ketligi hisoblanadi; masalan, yuqorida keltirilgan holda ung tomonli razbor kuyidagicha yoziladi: 6,4,2,7,4,1,5,4,6,3,2. Tugiluvchi qoidalar ketma-ketligining teskari tartibi shu bilan bog'liqki, ung tomonli razbor gapni boshlang'ich belgiga keltirish sifatida karaladi, gapni boshlang'ich belgidan boshlab generatsiya qilish emas (pastdan yuqoriga karab razbor). Shuni takidlash kerakki, xar bir tugiluvchi qoidadan ikkala chiqishda xam bir xil son marta foydalaniladi (razborlarda). Razbor daraxti. chiqish yana sintaksis daraxt (razbor daraxti) nomi bilan mashxur daraxtni ko'rish terminlarida xam ifodalanishi mumkin. (x+u)*x kator xolida sintaksis daraxt quyidagi ko'rinishda bo'ladi: Razbor muammisini quyidagi masalalarga keltirish mumkin. chap tomonli razborni topish ung tomonli razborni topish sintaksis daraxtni ko'rish. Bir xil qiymatga ega bo'lmagan grammatikalar. Kupgina xollarda chap tomonli va ung tomonli razborlar va sintaksis daraxt unikal hisoblanadi. Lekin, quyidagi tugiluvchi qoidali grammatika uchun S S+S| x x+x+x gap ikkita sintaksis daraxtga, ikkita chap (ung) tomonli razborga ega. S S+S S S+S S +S+S x+S x+S+S x+S+S x+x+S x+x+S x+x+x x+x+x Agar grammatikada generatsiya qilingan qandaydir gap, bittadan ortik razbor daraxtiga ega bulsa, bunday grammatika haqida u bir qiymatli emas deyiladi. Ekvivalent shart shunda kurinadiki, gap bittadan ortik chap yoki ung tomonli razborga ega bo'lishi kerak. Grammatikaning bir qiymatli emasligini urnatish masalasi umumiy holda yechimi yuk masaladir, yani kirishda ixtiyoriy grammatikani ...