Ovqat resepti

2-mavzu. Matematik ifodalar translyatorlarini yaratish

Har bir dasturlash tili uchun nafaqat ushbu tilda dastur matnini tuzish, balki mavjud matn ushbu tilga tegishli yoki yo'qligini aniqlash ham muhimdir. Aynan shu vazifani kompilyator boshqa vazifalar orasida hal qiladi (tuzuvchi nafaqat dastlabki dasturni tanibgina qolmay, balki unga teng keladigan dasturni ham yaratishi kerak). Dastlabki dasturga nisbatan kompilyator tanuvchi vazifasini bajaradi, ba'zi dasturlash tilida dasturni yaratgan kishi ushbu tilning zanjir generatori vazifasini bajaradi.

Grammatika va tanib olish bu ikki mustaqil usul bo'lib, ular aslida tilni aniqlashda ishlatilishi mumkin. Shu bilan birga, ma'lum bir dasturlash tili uchun kompilyatorni yaratishda, tillarni aniqlashning ushbu usullarini bir-biriga bog'lashni talab qiladigan muammo paydo bo'ladi. Tuzuvchi dasturchilar asosan dasturlash tillarining sintaksis tuzilishiga qiziqishmoqda. Ushbu inshootlar uchun ularni tahlil qilish muammosi hal qilinishi isbotlangan. Bundan tashqari, ular uchun uni hal qilishning rasmiy usullari topildi. Dasturlash tillari sof rasmiy tillar emasligi va ba'zi bir ma'nolarga ega ekanligi (semantika), haqiqiy kompilyatorlar yaratish uchun tahlil qilish vazifasi sof rasmiy tillar uchun tuzilganidan ko'ra bir oz kengroq tushuniladi. Tuzuvchi nafaqat kirish belgilarining satri berilgan tilga tegishli ekanligini aniqlashi kerak, balki uning semantik yukini ham aniqlab olishi kerak. Buning uchun zanjir asosida qurilgan o'sha grammatika qoidalarini aniqlash kerak.

Agar kiritish belgilarining satri belgilangan tilga tegishli bo'lmasa - asl dasturda xato mavjud - dastur ishlab chiqaruvchisi xatoning o'zi faktini aniqlashdan manfaatdor emas. Bunday holda, tahlil qilish vazifasi ham kengayib bormoqda: kompilyatordagi tanib oluvchi nafaqat kirish dasturida xatoning mavjudligini aniqlabgina qolmay, balki iloji bo'lsa, xato turi va uning paydo bo'lgan belgilar qatoridagi o'rnini aniqlashi kerak.
Tahlil va rekursiya ko’rinishi. Qoida quyidagicha berilgan bo’lsin:
1) T-> T * A
2) T-> A * T
Ular navbati bilan chap-rekursiv va o'ng-rekursiv deb nomlanadi.

Kirish dasturining tahlili pastga yoki yuqoriga bo'lishi mumkin. Pastga tushirilgan tahlilda, qoidalarda chap burilish qabul qilinishi mumkin emas, chunki bu cheksiz pastadir. Chap rekursiya quyidagi kabi teng huquqli rekursiv shaklga o'tkazilishi mumkin:

T-> AM
M-> * A | M

Yuqoriga qarab tahlil qilishda qoidalarda o'ng tomonga qaytarilish mumkin emas. Xuddi shunday, o'ng rekursiya bilan qoidalar chap rekursiya bilan qoidalarga o'zgartiriladi.

Til va grammatikani tasnifi. Dasturlash tili qanchalik murakkab bo'lsa, ushbu tilda yozilgan original dastur zanjirlarini tahlil qilish uchun kompilyatorning hisoblash xarajatlari shunchalik yuqori bo'ladi va shuning uchun kompilyator va uning tuzilishi murakkabroq. Ba'zi bir til turlari uchun, qoida tariqasida, cheklangan hisoblash manbalari asosida maqbul vaqt oralig'ida ushbu tillardagi manba matnlarini tahlil qiladigan kompilyatorni qurish mumkin emas (shuning uchun tabiiy tillarda, masalan, rus yoki ingliz tillarida dasturlarni yaratish hali ham mumkin emas).
Translyatorlar. Translyatorning rasmiy ta'rifi
Translyator - bu dasturni manba (kirish) tilida olingan (chiqish) tilidagi ekvivalent dasturiga aylantiradigan dastur.
Kirish tilidagi jumlalarni chiqish tilining ekvivalenti jumlalariga aylantirish nuqtai nazaridan, tarjimon tarjimon vazifasini bajaradi.
Translyatorning natijasi natijada paydo bo'ladigan dastur bo'ladi, faqat boshlang'ich dasturning matni to'g'ri bo'lsa - unda kirish tilining sintaksisi va semantikasi nuqtai nazaridan xatolar bo'lmaydi. Agar boshlang'ich dastur noto'g'ri bo'lsa (kamida bitta xato bo'lsa), tarjimonning natijasi xato xabari bo'ladi.
Translyator bosqichlari. Translyatorning umumiy sxemasi
Shaklda 2.1 kompilyatorning umumiy sxemasini taqdim etadi. Bundan ko'rinib turibdiki, umuman olganda, kompilyatsiya jarayoni ikki asosiy bosqichdan iborat - tahlil va sintez. Tahlil bosqichida dastlabki dastur matnini aniqlash, identifikator jadvallarini yaratish va to'ldirish amalga oshiriladi. Uning ishining natijasi - bu kompilyator tushunadigan dasturning o'ziga xos ichki namoyishi. Sintez bosqichida dasturning ichki namoyishi va identifikator jadvalidagi ma'lumotlarga asoslanib, natijada paydo bo'lgan dasturning matni yaratiladi. Ushbu bosqichning natijasi ob'ekt kodidir. Bundan tashqari, kompilyator xatolarni tahlil qilish va tuzatish uchun javob beradigan qismni o'z ichiga oladi, agar dasturiy ta'minotda xato bo'lsa, foydalanuvchiga xatoning turi va uning paydo bo'lishi joyi to'g'risida to'liq ma'lumot berishi kerak. Eng yaxshi holatda kompilyator foydalanuvchiga xatoni tuzatish imkoniyatini taklif qilishi mumkin.
Ushbu bosqichlar, o'z navbatida, kompilyatsiya fazalari deb ataladigan kichik bosqichlardan iborat. Shakllanish fazalarining tarkibi sek. 2.1 eng umumiy ko'rinishida taqdim etilgan, ularning aniq bajarilishi va o'zaro ta'sir qilish jarayoni, albatta kompilyator versiyasiga qarab farq qilishi mumkin.

Tuzuvchi umuman rasmiy tillar nazariyasi nuqtai nazaridan ikkita asosiy funktsiyani bajaradi:

- boshlang'ich dasturning tilini tan olish

- natijada olingan tilni ma'lum tilda yaratish.

Quyida kompilyatsiyaning asosiy bosqichlari (qismlari) ro'yxati va ularning funktsiyalari qisqacha tavsifi keltirilgan.

Leksik analizator (skaner) bu dasturning harflarini manba tilida o'qiydigan va ulardan manbaning tilidagi so'zlarni (tokenlarni) tuzadigan kompilyator qismidir. Leksik analizatorning kirishi boshlang'ich dasturning matnini oladi va olingan ma'lumotlar sintaktik bosqichda kompilyator tomonidan keyingi ishlov berish uchun uzatiladi. Nazariy nuqtai nazardan, leksik analizator kompilyatorning zaruriy, zaruriy qismi emas. Ammo deyarli barcha kompilyatorlarda uning mavjudligini aniqlaydigan sabablar mavjud.

Sintaktik tahlil bosqichida kompilyatorning asosiy qismi. Leksik analizator tomonidan ishlov berilgan manba dasturi matnida sintaktik tuzilmalarni tanlashni amalga oshiradi. Xuddi shu kompilyatsiya bosqichida dasturning sintaktik to'g'riligi tekshiriladi. Parsing kirish dasturlash tilining matnni tanib oluvchi rolini o'ynaydi.

Semantik analizator - bu kiruvchi tilning semantikasi nuqtai nazaridan dastlabki dastur matnining to'g'riligini tekshiradigan kompilyatorning bir qismi. To'g'ridan-to'g'ri tekshirishga qo'shimcha ravishda, semantik tahlil kirish tilining semantikasi tomonidan talab qilinadigan matnli o'zgarishlarni amalga oshirishi kerak (masalan, konversiya tipini o'zgartirish funktsiyalari kabi). Turli xil kompilyatorlarni amalga oshirishda semantik tahlil qisman tahlil qilish fazasiga, qisman kodlarni yaratishga tayyorgarlik bosqichiga kirishi mumkin.

Kod yaratishga tayyorgarlik - bu kompilyator natijada paydo bo'lgan dasturning matnini sintezi bilan bevosita bog'liq bo'lgan, ammo chiqadigan tilda matn yaratilishiga olib kelmaydigan dastlabki harakatlarni bajaradigan bosqich. Odatda, ushbu bosqich til elementlarini aniqlash, xotira ajratish va hk

Kod yaratish bu chiqish tilining jumlalarini va umuman, natijada paydo bo'lgan dasturning matnini tashkil etadigan buyruqlar avlodiga bevosita bog'liq bo'lgan faza. Natijada paydo bo'lgan dasturning sintez bosqichidagi asosiy bosqich. Olingan dasturning matnini to'g'ridan-to'g'ri yaratishdan tashqari, generatsiya odatda optimallashtirishni, allaqachon yaratilgan matnni qayta ishlash bilan bog'liq jarayonni ham o'z ichiga oladi. Ba'zan optimallashtirish alohida kompilyatsiya bosqichiga ajratiladi, chunki bu dasturning sifati va samaradorligiga sezilarli ta'sir qiladi.

Translayotor orqali o'tish - bu kompilyator tomonidan xotiradan ma'lumotlarni ketma-ket o'qish, qayta ishlash va natijani xotirada saqlash jarayoni. Kompilyatorda bir nechta o'tishlarni amalga oshirish mumkin, masalan, leksik va sintaktik passlar. Ba'zi hollarda, o'tish joylari bitta o'tish joyiga birlashtirilishi mumkin.
Interpretatorlar - dastlabki dasturni kirish (manba) tilida idrok etadigan va uni bajaradigan dastur.
Translyator kabi, interpretator ham asl dasturning matnini tahlil qiladi, lekin natijada hosil bo'lgan dasturni yaratmaydi, lekin tilining semantikasini hisobga olgan holda, asl dasturni darhol uning ma'nosiga muvofiq bajaradi.

C++ dasturlash tilida matematik ifodalarning translyatori

#include

#include
#include
#include
#include
#include "stack.cpp"
class TFStack
{
private:
long double num[1000];
int inum;
public:
TFStack () { inum=0; };
~TFStack () {};
void push (long double &);
long double pop ();
long double peek ();
int nonEmpty () { return inum; };
};
void TFStack::push (long double &x)
{
num[inum++]=x;
}
long double TFStack::pop ()
{
if (inum>0) return num[--inum]; else return 0;
}
long double TFStack::peek ()
{
if (inum>0) return num[inum-1]; else return 0;
}
class TCStack
{
private:
int tok[1000], itok;
public:
TCStack () { itok=0; };
~TCStack () {};
void push (char &);
char pop ();
char peek ();
int nonEmpty () { return itok; };
};
void TCStack::push (char &x)
{
tok[itok++]=x;
}
char TCStack::pop ()
{
if (itok>0) return tok[--itok]; else return 0;
}
char TCStack::peek ()
{
if (itok>0) return tok[itok-1]; else return 0;
}
enum token_val {
NUMBER,
ADD='+', SUB='-', MUL='*', DIV='/', EXP='^',
BIG='>', SML='<', EQU='=', MOD='%', AND='&',
OR ='|', FAC='!', LBR='(', RBR=')', END='~'
};
token_val cur_tok;
enum { false, true };
int flDigit, flOp, flAlpha, flLB, flRB, flUSub;
// Синтаксический разбор выражения
int Err (int num, int pos)
{ char *e;
for (int i=0; i
(e+i++)=' '); *(e+pos)='\0';
cout << e << " ^ - ";
switch (num)
{
case 1: cout << "Пропущена операция, либо ошибочная переменная!\n";
break;
case 2: cout << "Пропущена операция!\n";
break;
case 3: cout << "Пропущена переменная / число!\n";
break;
case 4: cout << "Отсутствует выражение!\n";
break;
case 5: cout << "Неверная лексема!\n";
break;
case 6: cout << "Пропущена парная закрывающая скобка!\n";
break;
case 7: cout << "Лишняя закрывающая скобка!\n";
break;
case 8: cout << "Пропущена операция, либо лишняя закрывающая скобка!\n";
break;
};
return 1;
}
void SetFlags (char ch)
{
switch (ch)
{
case LBR:
flDigit=true; flOp=false; flAlpha=true;
flLB =true; flRB=false; flUSub =true; break;
case RBR:
flDigit=false; flOp=true; flAlpha=false;
flLB =false; flRB=true; flUSub =false; break;
case '0': case '1':case '2':case '3': case '4':
case '5': case '6':case '7':case '8': case '9':
flDigit=true; flOp=true; flAlpha=false;
flLB =false; flRB=true; flUSub =false; break;
case EXP: case MUL: case DIV: case ADD: case SUB:
case BIG: case SML: case EQU: case MOD: case AND:
case OR :
flDigit=true; flOp=false; flAlpha=true;
flLB =true; flRB=false; flUSub =false; break;
case FAC:
flDigit=false; flOp=true; flAlpha=false;
flLB =false; flRB=true; flUSub =false; break;
default:
if (isalpha (ch))
{
flDigit=true; flOp=true; flAlpha=true;
flLB =false; flRB=true; flUSub =false;
};
}
}
int DetectSintax (char *Str)
{ char ch, pch;
int CB=0;
flDigit=true; flOp=false; flAlpha=true;
flLB =true; flRB=false; flUSub =true;
for (int i=0; (ch=*(Str+i))!='\0'; i++)
{
switch (ch)
{
case '0': case '1':case '2':case '3': case '4':
case '5': case '6':case '7':case '8': case '9': case '.':
if (flDigit) SetFlags (ch); else { Err (2, i); return 0; }
break;
case EXP: case MUL: case DIV: case ADD: case SUB:
case BIG: case SML: case EQU: case MOD: case AND:
case OR : case FAC:
if (flUSub) SetFlags (ch);
else if (flOp) SetFlags (ch);
else { Err (3, i); return 0; };
break;
case LBR:
if (flLB) { SetFlags (ch); CB++; }
else if (isdigit (pch)||isalpha (pch)) { Err (2, i); return 0; }
else { Err (8, i); return 0; }
break;
case RBR:
if (flRB) { SetFlags (ch); CB--; }
else if (pch==LBR) { Err (4, i); return 0; }
else if (pch==EXP||pch==MUL||pch==DIV||pch==ADD||pch==SUB||
pch==BIG||pch==SML||pch==EQU||pch==MOD||pch==AND||
pch==OR||pch==FAC) { Err (3, i); return 0; }
break;
default:
if (isalpha (ch))
{
if (flAlpha) SetFlags (ch);
else if (isdigit (pch)) { Err (1, i); return 0; }
else if (pch==RBR) { Err (2, i); return 0; }
}
else { Err (5, i); return 0; }
} pch=ch;
};
if (((ch=*(Str+i-1))!=RBR)&&(!isalpha (ch))&&
(!isdigit (ch))&&(ch!=FAC)) { Err (3, i); return 0; }
else if (ch==FAC&&i==1) { Err (3, 0); return 0; }
else if (CB>0) { Err (6, i); return 0; }
else if (CB<0) { Err (7, i-1); return 0; }
return 1;
}
// Непосредственно вычисление выражения
token_val get_token (double *arg, FILE *f)
{ char ch, *var;
do
if (((ch=fgetc (f))==EOF)||(ch=='\n')||(ch==0)) return END;
while ((ch!='\n') && (isspace (ch)));
switch (ch)
{
case EXP: case MUL: case DIV: case ADD: case SUB:
case BIG: case SML: case EQU: case MOD: case AND:
case OR : case FAC: case LBR: case RBR:
return cur_tok=(token_val) ch;
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
ungetc (ch, f); *arg=0;
fscanf (f,"%lf", arg);
return cur_tok=NUMBER;
default:
int i=0;
*(var+i++)=ch;
while (isalpha (ch=fgetc (f))||isdigit (ch)) *(var+i++)=ch;
*(var+i)='\0'; ungetc (ch, f);
cout << var << "="; cin >> *arg;
return cur_tok=NUMBER;
};
}
long double fop (char op, double a, double b)
{
switch (op)
{
case EXP: return pow (a, b);
case MUL: return a*b;
case DIV: if (b!=0) return a/b; else return 0;
case ADD: return a+b;
case SUB: return a-b;
case BIG: return a>b;
case SML: return acase EQU: return a==b;
case MOD: return (int)a%(int)b;
case AND: return (int)a&(int)b;
case OR : return (int)a|(int)b;
case FAC: long double f=1;
for (int i=1; i<=(int)a; f*=i++);
return f;
default : return 0;
}
}
int prty (token_val t)
{
switch (t)
{
case FAC: return 4;
case EXP: return 3;
case MUL: case DIV: return 2;
case ADD: case SUB: case BIG: case SML:
case EQU: case MOD: case AND: case OR: return 1;
default: return 0;
}
}
long double Exec ()
{ TCStack st_op;
TFStack st_num;
token_val t;
double x;
while ((t=get_token (&x, f))!=END)
{
switch (t)
{
case NUMBER:
st_num.push (x); break;
case LBR:
st_op.push (t); break;
case RBR:
while (st_op.peek ()!=LBR)
st_num.push (fop (st_op.pop (), st_num.pop (), st_num.pop ()));
st_op.pop (); break;
case MUL: case DIV: case ADD: case SUB:
case EXP: case BIG: case SML: case EQU:
case MOD: case AND:case OR:
while ((st_op.nonEmpty ())&&
(prty (t)<=prty ((token_val) st_op.peek ())))
st_num.push (fop (st_op.pop (), st_num.pop (), st_num.pop ()));
st_op.push (t); break;
case FAC:
st_num.push (fop (t, st_num.pop (), 0));
break;
}
}
while (st_op.nonEmpty ())
st_num.push (fop (st_op.pop (), st_num.pop (), st_num.pop ()));
return st_num.pop ();
}
void main ()
{ char str[100]="\x0";
clrscr ();
do
{
cout << ">> "; cin >> str;
if (str[0]=='q') break;
if (str[0]=='c') clrscr ();
else
{
if (DetectSintax (str)) cout << Exec () << "\n";
}; } while (1);}