Sintaktik analizatorni yaratish. Odatda, mashina tilidagi matn gaplar, gap- gaplar ostidan, gap osti esa, o‘z navbatida, gaplar ostidan va shu kabi belgilardan hosil bo‘ladi. Masalan, XML hujjatda boshlanish tegi, qiymat, yopish teglari mavjud. Boshlanish tegi [<] belgisi, teg nomi va qanday atribut va qiymatlari, [>] belgisidan iborat. Yopish tegi esa, []belgisi bilan tugaydi. Atribut esa nomi, [=], [“], belgilar to‘plami va yana [“] belgisidan iborat va takrorlanishi mumkin. Qiymat esa qandaydir belgilar to‘plami yoki qandaydir elementlardan (gap, gap osti, ifoda) iborat. Tahlil natijasida tahlil daraxtini hosil qilish mumkin.
Bunday tillarni har bir terminal bo‘lmagan tilning maʻlum bir jumlasiga mos keladigan Backus-Naur shakli (BNSh) yordamida tasvirlash qulay. Dasturlarni yozganda, odatda ularni funksiyalarga va funksiya ostilarga ajratamiz va sietatik tahlillovchi yozmoqchi bo‘lganimiz uchun, har bir BNSh terminal bo‘lmagan sintatik tahlillovchimizning bitta funksiyasiga mos kelsin va har bir bunday funksiya:
ushbu jumlani berilgan pozitsiyadan ajratishga harakat qilish;
bu ishni bajardimi yo‘qmi natijasini qaytarish;
tahlil tugagani yoki xato sodir bo‘lgan pozitsiyani qaytarish;
tahlil natijasida olish kerak bo‘lgan baʻzi qo‘shimcha maʻlumotlarni qaytarish;
Masalan, BNSh ko‘rinishida expr ::= expr1 expr2 expr3 funksiyani yozamiz:
-
bool read_expr(char *& p, ){
if(!read_expr1(p, ))
return false;
// read_expr1() fuksiyasi expr1 tahlil tugaga pozitsiyada p qoʻyadi
// bu pozitsiyada p bilan hech qanday amal bajarilmaydi. if(!read_expr2(p, ))
return false; if(!read_expr3(p, ))
return false; return true;
}
|
Davomi sifatida, BNSh ko‘rinishida expr ::= expr1|expr2|expr3 funksiyani yozamiz:
-
bool read_expr(const char *& p, ){
const char * l = p; if(read_expr1(p, ))
return true;
// expr1 tahlil jarayonida p xato boʻlgan joyni koʻrsatadi p = l;
if(read_expr2(p, ))
return true;
p = l;
if(read_expr3(p, ))
return true; return false;}
|
Bu sintatik tahlillash qiymat qaytarish asosidagi rekursiv kamayish usuliga asoslangan.
Ixtiyoriy matnni BNSh ko‘rinishida keltirish mumkin. Masalan, XML tilidagi quyidagicha yozish mumkin:
element ::= '<'identifier'>'some_data''
Agar identifikatorlari mos kelsa bu haqiqattan ham to‘g‘ri keladi. Bunday amallarni sintaktik tahlillovchiga qo‘shish muammo emas. Masalan, terminal funksiyalar quyidagicha bo‘lishi mumkin:
-
bool read_fix_char(const char *& it, char c){ if(!*it) return false; // satr oxiri
if(*it!=c) return false;// boshqa simvol
// xato boʻlganda joyiga qolish bajariladi
it++; // keyingisiga oʻtish return true;
}
bool read_fix_str(const char * & it, const ch_t * s){ while(*it)// satr tugamagancha
if(!*s)
return true; else if(*it!=*s)
return false;
// xato boʻlganda joyiga qolish bajariladi
else
it++, C++;
if(!*s) return true; return false;
}
|
Satrni sintaktik tahlil qilganimizda yuqoridagi funksiyalarning barcha tiplari uchun forward iteratorlar yetarli ekanligini biling.
forward iteratorlarni taqdim etadigan va faylni butunlay emas, fayl o‘rniga kichik qismlarga xotirada saqlaydigan sinf oqimni yaratishni qaraymiz. Agar shablonlar asosida tahlillovchi funksiyani yaratishni xoxlasak, ularni satrlar va/yoki oqimlardan foydalanish mumkin (base_parse.h kutubxonasi terminal funksiyalari uchun, bu sinfni diskdagi mavzuga oid papkaga qarang). Birinchi navbatda unix «barcha fayllar bor»: ideyalogiyasiga baʻzi aniqliklarni kiritib olamiz: Shunday fayllar bo‘ladiki, ular disk bo‘yicha joylashgan va ularni ixtiyoriy pozitsiyasidan bir necha marta o‘qish mumkin(ularni random-access fayllar deb aytiladi), shunday oqimlar bo‘ladiki, tarmoqdan, klaviaturadan, boshqa ilovalardan yo‘naltirilgan (bularni forward oqimlar deb aytiladi). Bunday oqimlarni bir martaga o‘qish kerak. Shuning uchun, unisi va bunisi bilan ishlash uchun bir yondashuvda faylni o‘qiydigan, forward iteratorlarni qo‘llab quvvatlaydigan, xotirada faylni to‘liq emas, balki maʻlum bir bo‘lagini saqlaydigan sinf-oqimni yaratish maqsadga muvofiq.
Bunday oqimlar Input iteratorlar uchun ancha oldin yaratilgan, maqsadi faqat ularda Input iteratorlar, bu iterator harakatlanishi uchun bitta bufer bo‘ladi. Qachonki, bufer oxiriga kelganda buferga faylning keyingi bo‘lagi yuklanadi hamda iterator bo‘shatilgan bufer boshidan harakatlanishni boshlaydi (7.1-rasmga qarang).
7.1-rasm. Input iteratorlardan foydalanish.
Forward iteratorlarning input iteratrlardan farqi ularni nusxalash mumkinligidir. Bunday masalada oqimlarda forward iteratorlardan foydalanish uchun buferlar ro‘yxatini hosil qilish orqali echiladi. Qandaydir iterator birinchi buferga murojaati bilan ro‘yxatga yangi bufer qo‘shiladi va fayldagi blok maʻlumotlar bilan to‘ldiriladi. Ammo bu usulda fayl to‘liq xotiraga yuklanadi,bu holat kerakmas. Shunday qilamizki, buferning chap tomonidagi joylashgan oxirgi chap iterator joylangan barcha buferlari o‘chirilsin. Lekin, unga joylashgan buffer ro‘yxati bilan har bir iterator mos bo‘lmaydi, lekin faqat ularning sonini mos bo‘ladi (hisoblovchi iteratorlari). Biror bir bufer 0 iterator qolganini va u eng chap ekanligini bilsa, u barcha undan o‘ng buferdagi barcha qo‘shnilari o‘chiriladi. Chunki ular ham 0 iteratorga ega bo‘ladi(7.2-rasmga qarang).
7.2-rasm. Forward iteratorlardan foydalanish.
Bunday kelib chiqadiki, har bir iterator quyidagilarni o‘z ichiga olishi kerak:
belgiga ko‘rsatkich(qayta nomlanishda qaytariladigan qiymat);
bufergadagi belgilar massivning oxiriga ko‘rsatkich iterator harakatlanganda taqqoslash amalga oshiriladi);
bufer ro‘yxati bo‘yicha iteratorlar (bufer maʻlumotlariga murojjat uchun va ular orqali butun oqim maʻlumotlariga murojjat).
Iterator bufer chegarasiga etganda, u keyingi buferlar ro‘yxatda borligini tekshiradi, bo‘lmasa - uni yuklaydi, oldingi bufer iteratorlar sonini kamaytiradi va keyingisini sonini oshiradi. Agar oldingi buferda 0 ta iterator qolgan bo‘lsa, u o‘chiriladi. Agar iterator faylning oxirigacha kelgan bo‘lsa, u faqat oldingi buferdan chaqiriladi va "faylning oxiri" holatiga o‘tadi. Bir iteratorning nusxasini olganda – joriy buferda iteratorlarning soni bittaga ko‘payadi, iteratorning destruktori ishlaganda bittaga kammayadi, va, yana 0 bufer bor bo‘lsa qolgan iteratorlar, u va o‘ngda undan keyingi buferlar, shuningdek 0 iteratori borlari o‘chiriladi. Amalga oshirish uchun diskdagi mavzuga oid papkadagi forward_stream.h ga qarang.
Bunday iteratorlar anʻanaviy iteratorlardan ularni ajratib turadigan baʻzi xususiyatlarga ega. Masalan, bir oqimni (buferlar va baʻzi qo‘shimcha maʻlumotlar ro‘yxatini saqlaydigan) o‘chirish oldin (destruktor tomonidan), barcha iteratorlar o‘chirilgan bo‘lishi kerak, ularni o‘chirish vaqtida o‘zlariga bog‘liq bo‘lmagan holda buferlarga o‘z navbatida o‘chirilganligini aniqlash murojaat qiladi. Agar begin() usulini chaqirish (birinchi buferni yaratish) natijasida birinchi iteratorni bir marta olsak va u shu paytgacha birinchi bufer allaqachon o‘chirib tashlangan bo‘lsa, yana begin() usuli yordamida iteratorni ololmaymiz. Bundan tashqari oqimning end() usuli yo‘q. Natijada, oqimda ichki iterator yaratish kerak bo‘ladi, yaʻni barcha oqimlar yaratilayotganda yaratiladigan va mos yozuvlar iter() usuli yordamida olinishi mumkin. Bundan tashqari, algoritmlarni ishlatganda, iteratorlaran tez-tez nusxalash kerak emas, chunki xotira chapdan o‘nggacha bo‘lgan iteratorda buferlarni saqlaydi. Katta fayllar uchun bu katta xotira talab qilishiga olib keladi.
Yordam sifatida har xil turdagi buferlar mavjud: oddiy (basic_simple_buffer), qator-ustunli iteratorni (basic_adressed_buffer). Bular yordamida hisoblash uchun turli kodlashlar orasida qayta kodlashni bajaruvchi bufer qilish mumkin. Shu munosabat bilan oqim buferning tipi bilan parametrlashtiriladi.
Buyruqlar satrining oxiri null belgi bilan belgilanadi. Bu shuni anglatadiki, uning oxirini topish uchun satr orqali harakat qilsak, ko‘rsatgichni boshqa ko‘rsatgich bilan solishtirishimiz shart emas (STLda anʻanaviy tarzda amalga oshiriladi), aksincha, ko‘rsatgichimiz tomonidan ko‘rsatilgan qiymatni tekshirish kerak. Fayllar bilan bog‘liq vaziyat ham shunday. Belgili kiritishda belgilar asosida sonlarni olamiz va ular katta qiymatlar satriga ega bo‘lgani uchun yana har bir belgini EOF() funksiya bilan taqqoslanadi. Real vaqtda keladigan forward oqimlar uchun faylning oxiri holati oldindan nomaʻlum.
Bu muammoni satrli ko‘rsatgichlar uchun atend(it) funksiyasini tuzish orqali umumlashtirish mumkin:
-
bool atend(const char * p)
{ return !*p; }
|
Agar iterator faylning oxirini ko‘rsatsa, oqim bo‘yicha iteratorlarga true qiymat qaytaradi.
Foydalanuvchi bilan interaktiv hamkorlik qilish uchun (stdin orqali) blokli buferlash amalga oshirilmaydi, chunki blokda odatda bir nechta satr joylashtiriladi va bitta satr kiritilgandan so‘ng, dastur foydalanuvchidan kirishni kutishni davom etadi, chunki blok hali to‘lmagan. Satrning oxirigacha bo‘lgan belgilar buferni to‘ldiradi va buning uchun satrli buferlash kerak. Ushbu kutubxonada oqim ishga tushirilganda fayl tipini tanlab buferlash turini tanlashingiz mumkin (basic_block_file_on_FILE yoki string_file_on_FILE).
strin – stdin orqali satrli buferlash uchun buferning ichki iteratoridir. Interaktiv bo‘lmagan fayllar uchun oqim yaratishda birinchi belgiga ishora qiluvchi iterator yaratiladi, yaʻni birinchi bufer yuklanadi. Bunga strin uchun ruxsat berilmaydi, chunki dasturchi satr rejimidan kiritishni kutishdan oldin biror bir narsa amalga oshirish yoki ekranga chiqarigi mumkin.
Shu sababli birinchi buferni to‘ldirishda satrli fayllari ishlatilganda belgili buyruq ‘\nʻ dan foydalaniladi. Uni o‘qish uchun, start_read_line (it) funksiyasi mavjud, shundan so‘ng satrni tahlil qilish uchun dastur satrni kiritishni kutish rejimiga keladi va keyingi belgi ‘\nʻ tashqarida chiqishda iterator bu satrni ajratib oladi.
Agar bundan keyin yana foydalanuvchidan maʻlumotlar kerak bo‘lsa, dasturchi yana ekranda biror narsani chiqarishni xohlashi mumkin va uni olishdan oldin yana start_read_line(strin) dfn foydalanish mumkin. Bunda quyidagicha takrorlanish hosil qilinadi:
Albatta, bu fragment faqat qayta nomlash vaqtida buferni yuklashda iterator talab qilish mumkin, lekin bu qayta nomlash qachon qo‘shimcha tekshirishlar olib kelishi va butun tizimini murakkablashtirishi mumkin.Sintatik tahlillovchilarning bazaviy funksiyalari. Har safar terminal funksiyalarni yozish dasturchilarga noqulaylik keltirmasligi uchun
«base_parse.h» sinfida tayyorlab qo‘yilgan. Hozirda u umumiy ko‘rinishda (xaqiqiy sonlardan tashqari) tayyorlangan va kelajakda satr bo‘yicha ko‘rsatkichlar va oqim bo‘yicha iteratorlar uchun satrli fuknsiyalar (strcmp, strstr, strchr, strspn, strcspn kabi) ishlaydigan qismini tuzish rejalashtirilgan. Shuningdek bu faylning oxiri haqida o‘ylashi kerak emas, faqat fragmentni to‘g‘ri yozsa bo‘ladi.
Quyida parsingning bazaviy funksiyalari qisqacha keltirilgan va ikki test parserni amalga oshirish paytida ularning foydalanish statistikasi va natijaviy qiymatlari faytaradigan dastur keltirilgan.
-
size_t n
ch_t c
ch_t * s
func_obj bool is(c) // bool isspace(c)
|
span spn
bispan bspn
func_obj err pf(it*) // int read_spc(it*) func_obj err pf(it*, rez*)
|
Len – belgilar soni, *pstr ga qo‘shilgan, satr oxiri yoki oxiri emasligi aniqlovchi statistika va qiymatlari qaytaradi.
-
int read_until_eof (it&) .*$ 0 0 1 OK
|
int read_until_eof (it&, pstr*) .*$ len len OK
|
int read_fix_length (it&, n) .{n} -1 0 OK
|
int read_fix_length (it&, n, pstr*) .{n} -(1+len) 0 2 OK
|
int read_fix_str (it&, s) str -(1+len) 0 ili (1+len) 9 OK
|
int read_fix_char (it&, c) c -1 0 yoki 1 11 OK
|
int read_charclass (it&, is) [ ] -1 0 yoki 1 OK
|
int read_charclass (it&, spn) [ ] -1 0 yoki 1 OK
|
int read_charclass (it&, bspn) [ ] -1 0 yoki 1 OK
|
int read_charclass_s (it&, is, pstr*) [ ] -1 0 yoki 1 OK
|
int read_charclass_s (it&, spn, pstr*) [ ] -1 0 yoki 1 1 OK
|
int read_charclass_s (it&, bspn, pstr*) [ ] -1 0 yoki 1 5 OK
|
int read_charclass_c (it&, is, ch*) [ ] -1 0 yoki 1 OK
|
int read_charclass_c (it&, spn, ch*) [ ] -1 0 yoki 1 1 OK
|
int read_charclass_c (it&, bspn, ch*) [ ] -1 0 yoki 1 OK
|
int read_c (it&, ch*) . -1 0 5 OK
|
int read_while_charclass (it&, is) [ ]* -(1+len) len OK
|
int read_while_charclass (it&, spn) [ ]* -(1+len) len 2 OK
|
int read_while_charclass (it&, bspn) [ ]* -(1+len) len OK
|
int read_while_charclass (it&, is, pstr*) [ ]* -(1+len) len OK
|
int read_while_charclass (it&, spn, pstr*) [ ]* -(1+len) len OK
|
int read_while_charclass (it&, bspn, pstr*) [ ]* -(1+len) len 1 OK
|
int read_until_charclass (it&, is) .*[ ]<- -(1+len) len OK
|
int read_until_charclass (it&, spn) .*[ ]<- -(1+len) len 1 OK
|
int read_until_charclass (it&, bspn) .*[ ]<- -(1+len) len OK
|
int read_until_charclass (it&, is, pstr*) .*[ ]<- -(1+len) len OK
|
int read_until_charclass (it&, spn, pstr*) .*[ ]<- -(1+len) len 2 OK
|
int read_until_charclass (it&, bspn, pstr*) .*[ ]<- -(1+len) len OK
|
int read_until_char (it&, c) .*c -(1+len) len OK
|
int read_until_char (it&, c, pstr*) .*c -(1+len) len OK
|
Oxirgi belgini o‘qigandan so‘ng, iterator undan keyin emas, balki unga qaratilgan.
Funksiya nomidan foydalanib, xato kodini yoki xato xabarini qaytarish qulay, shuning uchun parserlar matni yanada aniqroq ko‘rinadi, maxsus makroslar keltiramiz:
-
#define r_if(expr) if((expr)==0) #define r_while(expr) while((expr)==0) #define r_ifnot(expr) if(expr) #define r_whilenot(expr) while(expr)
#define rm_if(expr) if((expr)>=0) #define rm_while(expr) while((expr)>=0) #define rm_ifnot(expr) if((expr)<0) #define rm_whilenot(expr) while((expr)<0) #define rp_if(expr) if((expr)>0) #define rp_while(expr) while((expr)>0) #define rp_ifnot(expr) if((expr)<=0) #define rp_whilenot(expr) while((expr)<=0)
|
Bu maʻlumotlarni saqlash va bool tipiga mos akslantirish bo‘lsada baʻzi sinfni qilish uchun juda muhim.
Umuman, o‘zgarmas bo‘lgan havolalarga qarshiman, funksiyasi o‘zgartirish kerak argumentlar ko‘rsatgichlari bilan emas, balki bir ko‘rsatkich orqali unga o‘tgan bo‘lishi kerak
Ushbu funksiyalardan foydalanishning ikkita misol keltiramiz: 7.2-dastur. Arifmetik ifodalarni hisoblash.
-
#define ONE_SOURCE //strin.cpp
#include "../strin.h"
using namespace str; using std::cout; using std::endl;
#define ifnot(expr) if(!(expr)) #define r_if(expr) if((expr)==0) #define r_while(expr) while((expr)==0) #define r_ifnot(expr) if(expr)
#define r_whilenot(expr) while(expr)
|
template void dump(it_t tmp, mes_t mes){
string s; read_fix_length(tmp,50,&s);
std::cerr <}
template
const char * read_sum(it_t & it, double * prez);
template
const char * read_expr(it_t & it, double * prez){ const char * err; if(read_s_fix_char(it,'(')){
r_ifnot(err = read_sum(it,prez)) return err;
ifnot(read_s_fix_char(it,')')) return "qavsni yoping";
return 0;
}
int x; ifnot(read_dec(it,&x)){
return "son";
}
*prez = x; return 0;
}
DEF_STRING(md,"*/")
template
const char * read_mul(it_t & it, double * prez){ typedef char_type ch_t;
const char * err;
r_ifnot(err = read_expr(it,prez)) return err;
while(true){
ch_t zn; ifnot(read_s_charclass_c(it,make_span(md().s),&zn))
return 0; double x;
r_ifnot(err=read_expr(it,&x))
|
-
return err; if(zn==(ch_t)'*') *prez *= x;
else *prez /= x;
}
return 0;
}
DEF_STRING(pm,"+-")
template
const char * read_sum(it_t & it, double * prez){ typedef char_type ch_t;
const char * err;
r_ifnot(err = read_mul(it,prez)) return err;
while(true){
ch_t zn; ifnot(read_s_charclass_c(it,make_span(pm().s),&zn))
return 0; double x;
r_ifnot(err = read_mul(it,&x)) return err;
if(zn==(ch_t)'+') *prez += x;
else *prez -= x;
}
return 0;
}
int main()
{
using namespace std; if(0)
{
string str_expression_1 = "5+84/(51)"; string str_expression_2 = "15 + (16 /6 *4)"; string str_expression_3 = "7 + ( 4* 4)"; string str_expression = str_expression_3;
cout <<"hisoblash ifodasi:" <const char * err; double rez;
r_ifnot(err=read_sum(p,&rez)){
int pos=p-str_expression.c_str(); for(int i=1; i
|
-
cout <<' '; cout <<'^' <cout <<"Xatolik: " <}
cout << "natija: " << rez << endl; cout <<"================" << endl;
}
if(1)
{
try{
while(!atend(strin)){
cout <<"arifmetik ifoda kiriting va 'end' bilan tugating "
<read_start_line(strin); const char * err; double rez=0;
err=read_sum(strin,&rez); linecol lc=get_linecol(strin); read_until_str(strin,"end"); r_if(err)
cout << "natija: " << rez << endl;
else{
cout <<" zanjir " <}
}
}
catch(const char * mes){
cerr << "xatolik: " << mes << endl; return -1;
}
catch(string & mes){
cerr << "xatolik: " << mes << endl; return -1;
}
catch(stream_exception & mes){
cerr << "xatolik: " << mes.what() << endl; return -1;
}
catch(...){
cerr << "noaniq [atolik" << endl;
}}
return 0;
}
|
Bugungi kunda dasturchilar uchun maxsus sintaktik tahlillovchilar yaratish ko‘p hollarda shart emas. Chunki bu mashaqqatli va ko‘p vaqt talab qiladi. Umuman olganda qandaydir dasturiy taʻminotlarni, axborot tizimlarining lingvistik taʻminoti yaratilsa, shu taʻminot uchun analizator yaratish kerak bo‘lishi mumkin. Dunyoda dasturlash tillarini ishlab chiqaruvchilar bu sohada juda oldilab ketgan. Shuning uchun sintatik tahlillovchilar bo‘yicha nazariy tushunchaga ega bo‘lish yetarlidi. Ammo ayrim matematik yangi sonli sinflar uchun ishlab chiqish mumkin.
|
