2
Topshiriq sharti:
1. Berilgan variant bo‘yicha sintaktik tahlil daraxtini qurilsin.
2. Bajarilgan ish bo‘yicha hisobot shakllantirilsin.
Nazariy qism
Sintaktik tahlil daraxtlari tabiiy tildagi jumlalar yoki matematik
ifodalar kabi real hayotdagi konstruksiyalarni ifodalash uchun ishlatilishi
mumkin. 1-rasmda sodda gapning ierarxik tuzilishi ko'rsatilgan. Bu tasvir
bizga qism daraxtlar yordamida uning alohida bo‘laklari
bilan ishlash
imkonini beradi.
1-rasm. Sodda gapning sintaktik tahlil
daraxti
Bundan tashqari,
\(((7 + 3) * (5 - 2))\)
kabi matematik ifodalarni sintaktik tahlil daraxti shaklida aks ettirish
mumkin (2-rasm).
3
2-rasm: \(((7+3)*(5-2))\) ifodasi uchun sintaktik tahlil daraxti
Ko'paytirish amali qo'shish va ayirish amalidan ko’ra yuqori
ustuvorlikka egadir. Biroq, qavslar tufayli,
bu yerda birinchi navbatda
yig'indi va ayirma hisoblanishi kerak. Daraxt ierarxiyasi ifodani hisoblash
tartibini yaxshiroq tushunishga yordam beradi.
Daraxtning eng yuqori qismida joylashgan ko‘paytmani topishdan
oldin, qism daraxtlarda qo'shish va ayirish amallar bajarilishi kerak.
Birinchi jarayon - chap qism daraxt natijasi - 10 ni, ikkinchisi - o’ng qism
daraxt natijasi – 3 ni beradi. Ierarxik tuzilish xususiyatidan foydalanib,
har bir qism daraxtni topilgan natijani o'z ichiga olgan tugun bilan
almashtirish mumkin. Ushbu protsedura 3-rasmda ko'rsatilgan
soddalashtirilgan daraxtni hosil qiladi.
3-rasm: \(((7+3)*(5-2))\) ifoda uchun soddalashtirilgan tahlil daraxti
Quyidagilarni ko'rib chiqamiz:
To'liq qavslar bilan matematik ifoda uchun tahlil daraxtini qanday
qurish mumkin.
Tahlil daraxtida saqlangan ifodani qanday baholash mumkin.
Tahlil daraxtidan asl matematik ifodani qanday yozish kerak.
Sintaktik tahlil daraxtini qurishda birinchi
qadam ifoda qatorini
tokenlar ro'yxatiga ajratib chiqishdir. Bu misolda tokenlar ro'yxati to'rt xil
bo‘lishi mumkin: chap qavs, o'ng qavs, operator va operand. Ma’lumki,
Sintaktik tahlilchi tomonidan o'qilgan chap qavs har doim yangi
ifodaning
boshlanishini anglatadi va shuning uchun u bilan bog'langan quyi qism
daraxt hosil qilish kerak. Aksincha, o'ngdagi qavsni o'qish ifodaning
tugashini bildiradi. Bundan tashqari, operandlar ularning operatorlarining
4
barglari va avlodlari bo'lishi ham ma'lum. Nihoyat, ma’lumki, har bir
operatorning ikkala avlodi (farzandi) ham bor.
Yuqoridagi ma'lumotlardan foydalanib,
biz quyidagi qoidalarni
aniqlaymiz:
1) Agar '(' belgisi o'qilgan bo'lsa, joriy tugunning chap avlodi
sifatida yangi tugunni qo’shiladi va unga o‘tiladi.
2) Agar ushbu ['+','-','/','*'] ro'yxatdagi elementlaridan biri o'qilgan
bo'lsa, u holda joriy tugunning qiymatini ushbu tokendagi operatorga
tenglashtiriladi. Joriy tugunning o’ng
avlodi tomoniga yangi tugun
qo’shiladi va o’ng qismdaraxtga tushiladi.
3) Agar o'qilgan token raqam bo'lsa, u holda joriy tugun qiymati
ushbu raqamga tenglashtiriladi va ushbu joriy tugunning ajdodiga
qaytiladi.
4) Agar ')' belgisi o'qilgan bo'lsa, joriy tugunning ajdodiga o’tiladi.
Amalda yuqoridagi qoidalarni ko'rib chiqamiz. Biz