7-mavzu. Sintaktik tahlil

Rekursiv kamayish usuli. Eng oddiy va juda ko‘p foydalanilgan past sathlarga yo‘naltirilgan analizatorlarni qurish usuli rekursiv kamayish usulidir (recursive descent method).
Rekursiv kamayish usuli asosiy tamoyillarini o‘rganish uchun arifmetik ifodalarni bajarilish masalasini qaraymiz. Ularga binar amallari qo‘shish (+), ayrish (-), ko‘pytirish (*), butun bo‘lish (/) va qavslar amallari kirsin. Odatdagidek, ko‘paytirish va bo‘lish amallarining ustivorligi teng va ularning ustivorligi qo‘shish va ayirish amallarining ustivorligidan katta bo‘lib, bu amallarning ustivorligi ham tengdir. Qo‘shish turidagi amallarga (+) va (-) - amallarini, ko‘paytirish turidagi amallarga esa (*) va (/) - amallari qilib belgilaymiz. Qavslar amali standari tartibini o‘zgartirish uchun ishlatiladi. Vazifamiz ifoda qiymatini hisoblovchi dastur yozishdan iborat.
Qaralayotgan ifodani quyidagi ko‘rinishda bo‘lsin
T₁ +T₂ +…+T_n
Bunda T_i - F_1i *F_2i *…*F_mi ko‘rinishidagi ifoda. SHuningdek, F_ji – bu son yoki qavs ichidagi ifoda.
Berilgan ifodani hisoblash jarayonini o‘ylab ko‘ramiz, bunda birinchi galda F₁₁ hisoblanadi va F₁₁ dan keyin qaysi amal turganini aniqlanadi. Agar bu ko‘paytirish amali bo‘lsa, chap operandini bilib, o‘ng operandini aniqlaymiz va amalni bajaramiz. SHunday qilib, ko‘paytirish amali uchun chap operandani aniqlaymiz. F₁*F₂*…*F_n amallar ketma ketligini hisoblab bo‘lgandan keyin, keyingi amal sifatida bo‘lish amalini kelsa, buni ham yuqoridagi jarayon bo‘yicha hisoblaymiz.
Ifodalarni hisoblashda barcha hisoblashlarni quyidagi sinflarga ajratish mumkin:

1. 
   Oddiy ifoda, sonlar va qavslar bilan berilgan chiziqli ifodalar, masalan, 28, (128-25+16);
   
2. 
   Ifoda, ko‘paytirish tipidagi amallari bo‘lgan ifoda, ko‘paytirish va bo‘lish amallari kiradi, maslan, 2*15, 28*(15/3)+3;
   
3. 
   Ifoda, qo‘shish tipidagi amallari bo‘lgan ifoda, qo‘shish va ayirish amallari kiradi, masalan, 5-3, (5*3)/10-2;
   

Bular asosida hisoblash jarayonini tasavur qilishimiz mumkin va quyidagi formula bilan ifodalaymiz.

Expression (Term (Factor ()));

Bunda Factor – oddiy ifodani hisoblash protsedurasi bo‘lib, son, qavslarga ega chiziqli ifoda, Term - ko‘paytirish amali tipidagi amallarni saqlovchi ifoda qiymatini hisoblash protsedurasi, Expression - qo‘shish amali tipidagi amallarni saqlovchi ifoda qiymatini hisoblash protsedurasi.
Oddiy ifodani hisoblash protsedurasi:

int Factor () { char ch = getChar(); if (isDigit (ch)) return getValue(ch); if (ch == '(') { int result = Formula(); if (getChar() == ')') return result; error ("kutilmagan belgi yoki amal"); return 0; } return error ("kutilmagan belgi yoki amal"); }

Dastur ko‘paytirish tipiga oid amallarni hisoblash uchun ifodani tahlil qiladi. Ko‘paytirish tipiga oid amallarni hisoblash uchun ifodani hisoblashning umumiy formulasi quyidagicha:
F₁*F₂*…*F_n
Aniq tushunishimiz keraki, hisoblash bajarilayotgan amallar faqat ko‘paytirish yoki bo‘lishi amali bo‘ladi. Bunday amallarni hisoblash uchun Term protsedurasini yaratish mumkin. Bu protseduraning parametrlari butun sonili qiymatlar bo‘lishi kerak. Bunda chap operandani tanlashimiz va kerakli amalni bajarish uchun son yoki oddiy ifodadan iborat o‘ng operandani aniqlashimiz lozim, so‘ng esa amalni bajarish mumkin. Buni quyidagi dastur fragmenti asosida amalga oshirishsh mumkin.

int Term (int left) { char ch = getChar(); int right; if (ch != '*' && ch !='/') { /* navbatdagi amal kutilmagan bo`lsa, uni qaytarishmiz kerak*/ returnChar(); /*kutimagan belgini qaytarish */ return left; /*kutilmagan qimatni qaytarish */ } /* Hammasi yaxshi bo`lsa, o`ng operandni aniqlah kerak*/ right = Factor(); if (ch == '*') { return Term(left * right); /* bu hisoblashni bajarishni aniqlaydi */ } if (right == 0) return error ("Nolga bo`linish"); return Term(left / right); }

Dastur qo‘shish tipiga oid amallarni hisoblash uchun ifodani tahlil qiladi. Qo‘shish tipiga oid amallarni hisoblash uchun ifodani hisoblashning umumiy formulasi quyidagicha:
T₁ +T₂ +…+T_n
Aniq tushunishimiz keraki, hisoblash bajarilayotgan amallar faqat qo‘shish yoki ayirish amali bo‘ladi. Bunday amallarni hisoblash uchun Expression protsedurasini yaratish mumkin. Bu protseduraning parametrlari butun sonili qiymatlar bo‘lishi kerak. Bunda chap operandani tanlashimiz va kerakli amalni bajarish uchun son yoki oddiy ifodadan iborat o‘ng operandani aniqlashimiz lozim, so‘ng esa amalni bajarish mumkin. Buni quyidagi dastur fragmenti asosida amalga oshirishsh mumkin.

int Expression (int left) { char ch = getChar (); int right; if (ch != '+' && ch != '-') { /* navbatdagi amal kutilmagan bo`lsa, uni qaytarishmiz kerak*/ returnChar(); /*kutimagan belgini qaytarish */ return left; /*kutilmagan qimatni qaytarish */ } /* Hammasi yaxshi bo`lsa, o`ng operandni aniqlah kerak*/ right = Term (Factor()); if (ch == '+') { return Expression(left + right); /* bu hisoblashni bajarishni aniqlaydi */ } return Expression(left - right); }

YUqoridagi protseduralar ishlashi uchun quyidagi usullarni mustaqil ishlab chiqish kerak. Umuman olganda rekursiv kamayish usuli qiziqtirgan edi, o‘ylaymizki, quyidagi fragmentlarni yaratsangiz bunga ishonch hosil qilasiz.

1. 
   Kirish oqimidan navbatdagi belgini kutuvchi, getChar parametrsiz usuli.
   
2. 
   Kutilmagan belgini kirish oqimiga chiqarib berish returnChar usuli.
   
3. 
   isDigit i getValue usullarni ham yozish shartmas. Agar parametri son bo‘lsa, birinchi usul true qaytaradi. Ikkinchi usul esa parametr sifatida kirish oqimidan berilan satrdan sonlarni ajratib oladi va butun qiymatlarni hisoblaydi.
   
4. 
   Error usuli xatolar haqidagi xabarlarni chiqarish uchun ishlatiladi.
   

Bu usullarni mustaqil hal qilish mumkin, ammo .NET standart sinflar usullari asosida ba’zalarini modifikatsiyalab yaratish mumkin. Bu dasturlar fragmentini shakllantirishda qiymat qaytarish asosidagi rekursiv kamayish usulidan foydalanildi (recursive descent with backtracking). Qiymat qaytarmaslik asosidagi rekursiv kamayish usuli bilan chegaralanib qolmaganimizni ko‘rib chiqamiz.