Un calculator de birou

Un calculator de birou

Instructiunile si expresiile se introduc prin prezentarea programului calculatorului de birou care furnizeaza cele patru operatii aritmetice standard ca operatori infix asupra numerelor flotante. Utilizatorul poate, de asemenea, defini variabile. De exemplu, dindu-se intrarea:

r = 2.5

area = pi * r * r

(pi este predefinit), programul calculator va scrie:

2.5

19.635

unde 2.5 este rezultatul primei linii de intrare, iar 19.635 este rezultatul celei de a doua.

Calculatorul consta din patru parti principale: un analizor, o functie de intrare, o tabela de simboluri si un driver. In realitate este un compilator miniatura cu un analizor care face analiza sintactica, functia de intrare realizind intrarea si analiza lexicala, tabela de simboluri pastrind informatia permanenta, iar driverul facind initializarea, iesirea si tratind erorile. Exista multe facilitati care pot fi adaugate la acest calculator pentru a-l face mai util, dar codul este destul de lung intrucit a 19519e410t re 200 de linii si cele mai multe facilitati noi ar adauga cod fara a furniza aspecte noi in utilizarea lui C++.

3.1.1. Analizorul

Iata o gramatica pentru limbajul acceptat de calculator:

program:

END //END este sfirsitul intrarii

expr_list END

expr_list:

expression PRINT //PRINT este '\n' sau ;

expresion PRINT expr_list

expression:

expression + term

expression - term

term

term:

term / primary

term * primary

primary

primary:

NUMBER //numar in flotanta din C++

NAME //nume din C++ fara subliniat

NAME = expression

_primary

(expression)

Cu alte cuvinte, un program este un sir de linii. Fiecare linie consta din una sau mai multe expresii separate prin punct- virgula. Unitatile de baza ale unei expresii sint numere, nume si operatorii *, /, +, - (atit unar cit si binar) si =. Numele nu trebuie sa fie declarate inainte sa fie utilizate.

Stilul analizei sintactice utilizate este de obicei numit analiza descendenta recursiva. Este o tehnica top-down directa. Intr-un limbaj cum este C++ in care apelurile de functii sint relativ ieftine, aceasta este o tehnica eficienta. Pentru fiecare productie din gramatica exista o functie care apeleaza alte functii. Simbolurile terminale (de exemplu END, NUMBER, + si -) se recunosc prin analizorul lexical, get_token(), iar simbolurile neterminale sint recunoscute prin functiile analizorului sintac­tic expr(), term() si prim(). De indata ce ambii operanzi ai unei (sub)expresii sint cunoscuti, ei se evalueaza. Intr-un compilator real se genereaza codul in acest punct.

Analizorul utilizeaza o functie get_token() pentru a obtine o intrare. Valoarea ultimului apel a lui get_token() poate fi gasita in variabila curr_tok. Aceasta este o valoare de enumerare de tip token_value:

enum token_value;

token_value curr_tok;

Fiecare functie a analizorului presupune ca get_token() a fost apelat astfel incit curr_tok sa pastreaze tokenul (lexicul) urmator de analizat. Aceasta permite analizorului sa vada un lexic inainte si obliga fiecare functie a analizorului sa citeas­ca totdeauna un lexic in plus fata de cele pe care le utilizeaza productia pe care o trateaza ea. Fiecare functie a analizorului evalueaza expresia ei si returneaza o valoare. Functia expr() trateaza adunarea si scaderea. Ea consta dintr-un singur ciclu care cauta termeni de adunat sau scazut:

double expr()

}

Aceasta functie in realitate nu face ea insasi foarte mult. Intr-o maniera tipica pentru functii de nivel mai inalt dintr-un program mare, ea apeleaza alte functii pentru a face "greul". Sa observam ca o expresie de forma 2 - 3 + 4 se evalueaza ca (2 - 3) + 4, asa cum se specifica in gramatica.

Notatia curioasa for(;;) este modul standard de a specifica un ciclu infinit. O alternativa este while(1). Instructiunea switch se executa repetat pina cind nu se mai gaseste + sau - si in acest caz se executa instructiunea return din default.

Operatorii += si -= se utilizeaza pentru a trata adunarea si scaderea.

left = left + term();

left = left - term();

ar putea fi utilizate fara a schimba intelesul programului. Cu toate acestea

left += term();

left -= term();

sint nu numai mai scurte, dar exprima direct operatia intentionata. Pentru un operator binar @, o expresie x @= y inseamna x = x @ y si se aplica la operatorii binari:

+ - * / % & | ^ << >>

asa ca sint posibili urmatorii operatori de atribuire:

= += -= *= /= %= &= |= ^= <<= >>=

Fiecare este un lexic separat, asa ca a + = 1; este o eroare din cauza spatiului dintre + si =. (% este modulo sau restul impar­tirii, &, |, ^ sint operatorii logici pe biti and, or si xor, << si >> sint deplasari stinga si dreapta).

Functiile term() si get_token() trebuie sa fie declarate inainte de expr().

Capitolul patru discuta cum sa se organizeze un program ca un set de fisiere. Cu o singura exceptie, declaratiile pentru acest exemplu de calculator de birou pot fi ordonate in asa fel incit fiecare este declarata exact o data inainte de a fi utili­zata. Exceptie face expr(), care apeleaza term(), care apeleaza prim(), care la rindul ei apeleaza expr(). Acest ciclu trebuie sa fie intrerupt cumva. O declaratie:

double expr();

inaintea definitiei lui prim() va fi nimerita.

Functia term() trateaza inmultirea si impartirea:

double term() //inmultire si impartire

}

Testul pentru a ne asigura ca nu se face impartirea prin zero este necesar deoarece rezultatul in acest caz nu este definit. Functia error(char*) este descrisa mai tirziu. Variabila d este introdusa in program acolo unde este nevoie de ea si este initializata imediat. In multe limbaje, o declaratie poate apare numai in antetul unui bloc. Aceasta restrictie poate conduce la erori. Foarte frecvent o variabila locala neinitializata este pur si simplu o indicatie de un stil rau. Exceptii sint variabilele care se initializeaza prin operatii de intrare si variabilele de tip vector sau structura care nu pot fi initializate convenabil printr-o atribuire simpla. Sa observam ca = este operatorul de asignare, iar == este operatorul de comparare.

Functia prim() trateaza un primar; deoarece este la un nivel mai inferior in ierarhia de apeluri, ea face un pic mai multa "munca" si nu mai este necesar sa cicleze.

double prim()

return look(name_string)->value;

case MINUS : get_token(); //minus unar

return _prim();

case LP : get_token();

double e = expr();

if(curr_tok != RP)

return error(") expected");

get_token();

return e;

case END : return 1;

default : return error("primary expected");

}

}

Cind se gaseste un NUMBER (adica o constanta flotanta), se returneaza valoarea ei. Rutina de intrare get_token() plaseaza valoarea in variabila globala number_value. Utilizarea unei variabile globale intr-un program indica adesea ca structura nu este cit se poate de "curata", ca un anumit fel de optimizare a fost aplicat. Asa este aici; un lexic in mod tipic consta din doua parti: o valoare care specifica tipul lexicului (token_value in acest program) si (cind este nevoie) valoarea lexicului. Aici exista numai o singura variabila simpla curr_tok, asa ca este nevoie de variabila globala number_value pentru a pastra valoarea ultimului NUMBER citit. Aceasta functioneaza deoarece calculato­rul totdeauna utilizeaza un numar in calcul inainte de a citi un alt numar de intrare.

In acelasi mod in care valoarea ultimului NUMBER intilnit este tinut in number_value, reprezentarea sirului de caractere a ultimului NAME intilnit este tinut in name_string. Inainte de a face ceva unui nume, inainte calculatorul trebuie sa vada daca el este asignat sau numai utilizat. In ambele cazuri se consulta tabela de simboluri. Tabela este prezentata in &3.1.3. Aici trebuie sa observam ca ea contine intrari de forma:

struct name;

unde next se utilizeaza numai de functiile care mentin tabela:

name* look(char*);

name* insert(char*);

Ambele returneaza un pointer la un nume care corespunde la parametrul sir de caractere. Functia look() semnaleaza daca numele nu a fost definit. Aceasta inseamna ca in calculator un nume poate fi utilizat fara o declaratie prealabila, dar prima lui utilizare trebuie sa fie partea stinga a unei atribuiri.

3.1.2. Functia de intrare

Citirea intrarii este adesea cea mai incurcata parte a unui program. Motivul este faptul ca daca un program trebuie sa comu­nice cu o persoana, el trebuie sa invinga capriciile, conventiile si erorile unei persoane sau a mai multora. Incercarea de a forta persoana sa se comporte intr-o maniera mai convenabila pentru masina este adesea, pe drept cuvint, considerata ofensiva. Sarci­na unei rutine de intrare de nivel inferior este de a citi carac­tere unul dupa altul si sa compuna unitati de nivel mai inalt. Aici intrarea de nivel inferior se face cu get_token().

Regulile pentru intrarile in calculator au fost deliberat alese asa ca sa fie ceva incomod pentru sirul de functii care le manevreaza. Modificari neimportante in definitiile unitatilor ar face pe get_token() foarte simpla.

Prima problema este aceea ca, caracterul newline '\n' este semnificativ pentru calculator, dar sirul de functii de intrare il considera un caracter whitespace. Adica, pentru acele functii, '\n' este un terminator de unitate lexicala. Pentru a invinge aceasta trebuie examinate spatiile albe (spaces, tab, etc):

char ch;

dowhile(ch!='\n' && isspace(ch));

Apelul cin.get(ch) citeste un singur caracter din sirul de la intrarea standard in ch. Testul if(!cin.get(ch)) esueaza daca nici un caracter nu poate fi citit de la intrare (din cin). In acest caz se returneaza END pentru a termina sesiunea de calcul. Operatorul ! (not) se utilizeaza intrucit get() returneaza o valoare nenula in caz de succes. Functia isspace() din <ctype.h> furnizeaza testul standard pentru spatiu alb (&8.4.1). Functia isspace(c) returneaza o valoare nenula daca c este un caracter alb, zero altfel. Testul este implementat ca o tabela de cautare, astfel, utilizind isspace este mai rapid decit daca s-ar testa individual caracterele spatiu alb. Acelasi lucru se aplica la functiile isalpha(), isdigit() si isalnum() utilizate in get_token().

Dupa ce s-a facut avans peste caracterele albe, se utilizea­za caracterul urmator pentru a determina ce fel de unitate lexi­cala incepe in sirul de intrare. Sa ne oprim la niste cazuri separate inainte de a prezenta functia completa. Expresiile terminatoare '\n' si ';' sint tratate astfel:

switch(ch)

Saltul peste caractere albe (din nou) nu este necesar, dar daca ar trebui s-ar repeta apeluri ale lui get_token().

WS este un obiect de spatiu alb declarat in <stream.h>. El este utilizat numai pentru a indeparta spatiile albe. O eroare la intrare sau la sfirsitul intrarii nu va fi detectata pina la apelul urmator a lui get_token().

Sa observam modul in care diferite etichete ale lui case pot fi utilizate pentru un singur sir de instructiuni care trateaza acele cazuri. Se returneaza unitatea PRINT si se pune in curr_tok in ambele cazuri. Numerele se trateaza astfel:

case '0': case '1': case '2': case '3': case '4':

case '5': case '6': case '7': case '8': case '9':

case '.': cin.putback(ch);

cin >> number_value;

return curr_tok = NUMBER;

Scrierea etichetelor orizontal in loc de vertical, in general, nu este o idee buna deoarece este mai greu de citit, dar nu este nimerit in cazul de fata sa avem o linie pentru fiecare cifra. Deoarece operatorul >> este deja definit pentru a citi constante in virgula flotanta dubla precizie, codul este trivial. Intii caracterul initial (o cifra sau un punct) se pune inapoi in cin si apoi constanta poate fi citita in number_value.

Un nume, care este un lexic de tip NAME, este definit ca o litera care este posibil sa fie urmata de litere sau cifre:

if(isalpha(ch))

Aceasta construieste un sir terminat cu zero in name_string. Functiile isalpha() si isalnum() sint furnizate in <ctype.h>, isalnum(c) este diferit de zero daca c este o litera sau o cifra si zero altfel.

Iata in final functia de intrare completa:

token_value get_token()

while(ch != '\n' && isspace(ch));

switch(ch)

error("bad token");

return curr_tok = PRINT;

}

}

Intrucit token_value al unui operator a fost definit prin valoarea intreaga a operatorului, toate alternativele (case) pentru operator se trateaza trivial.

3.1.3. Tabela de simboluri

O singura functie are acces la tabela de simboluri:

name* look(char* p, int ins = 0);

Cel de al doilea argument indica daca sirul de caractere presupus trebuie sa fie in prealabil inserat sau nu.

Folosirea argumentului implicit da pentru look posibilitatea convenabila de a scrie look("sqrt2") in loc de look("sqrt2", 0), adica se doreste cautare, nu inserare. Pentru a obtine notatii convenabile pentru inserare se defineste o a doua functie:

inline name* insert(char* s)

Asa cum s-a mentionat inainte, intrarile in tabela sint de forma:

struct name;

Elementul next se utilizeaza pentru a face inlantuirea numerelor in tabela.

Tabela insasi este pur si simplu un vector de pointeri spre obiecte de tip nume:

const TBLSZ = 23;

name* table[TBLSZ];

Deoarece toate obiectele statice sint implicit initializate cu zero, aceasta declaratie triviala a lui table asigura de asemenea si initializarea.

Pentru a gasi o intrare pentru un nume din tabela, look() utilizeaza un cod hash simplu (numele cu acelasi cod hash se inlantuie):

int ii = 0;

char* pp = p;

while(*pp)

ii = ii << 1 ^ *p++;

if(ii < 0)

ii = -ii;

ii %= TBLSZ;

Fiecare caracter din sirul de intrare p este "adaugat" la ii ("suma" caracterelor precedente) printr-un sau exclusiv. Un bit din x^y este setat daca si numai daca bitii corespunzatori din operanzii x si y sint diferiti. Inainte de a face un sau exclu­siv, ii se deplaseaza cu un bit in stinga pentru a elimina utili­zarea numai a unui octet din el. Aceasta se poate exprima astfel:

ii <<= 1;

ii ^= *pp++;

Utilizarea lui ^ este mai rapida decit a lui +. Deplasarea este esentiala pentru a obtine un cod hash rezonabil in ambele cazuri. Instructiunile:

if(ii < 0)

ii = -ii;

ii %= TBLSZ;

asigura ca ii sa fie in domeniul 0 ... TBLSZ - 1, (% este opera­ torul modulo, numit si rest).

Iata functia completa:

extern int strlen(const char*);

extern int strcmp(const char*, const char*);

extern char* strcpy(const char*, const char*);

name* look(char* p, int ins = 0)

Dupa ce codul hash a fost calculat in ii, numele este gasit printr-o cautare simpla prin intermediul cimpurilor next. Fiecare nume este verificat folosind functia strcmp() de comparare a sirurilor. Daca este gasit, se returneaza numele lui; altfel se adauga un nume nou.

Adaugarea unui nume implica crearea unui obiect cu numele nou intr-o zona de memorie libera folosind operatorul new (vezi &3.2.6), initializarea si adaugarea lui la lista de nume. Adauga­rea se face punind noul nume in capul listei deoarece aceasta se poate face fara a testa daca exista sau nu o lista. Sirul de caractere care alcatuieste numele trebuie si el pastrat intr-o zona libera. Functia strlen() se foloseste pentru a gasi cit de multa memorie este necesara, operatorul new pentru a aloca memorie, iar functia strcpy() pentru a copia sirul in zona respecti­va.

3.1.4. Tratarea erorilor

Intrucit programul este atit de simplu, tratarea erorilor nu este o preocupare majora. Functia eroare pur si simplu numara erorile, scrie un mesaj de eroare si returneaza:

int no_of_errors;

double error(char* s)

Motivul pentru care se returneaza o valoare este faptul ca erorile de obicei apar in mijlocul evaluarii unei expresii, asa ca ar trebui sau sa se faca un abandon al acelei evaluari sau sa se returneze o valoare care in continuare sa fie putin probabil sa cauzeze erori. Ultima varianta este adecvata pentru acest calculator simplu. Daca get_token() ar tine numerele de linie, error() ar putea informa utilizatorul aproximativ asupra locului unde a aparut eroarea. Aceasta ar fi util la o folosire interac­tiva a calculatorului.

Adesea un program trebuie sa fie terminat dupa o eroare deoarece nu exista o cale adecvata care sa permita continuarea executiei. Acest lucru se poate face apelind functia exit(), care la inceput videaza lucrurile de tipul fisierelor de iesire (&8.3.2) dupa care se termina programul iar valoarea returnata de el este argumentul lui exit(). Un mod mai drastic de terminare a programului este apelul lui abort() care termina imediat sau imediat dupa pastrarea undeva a informatiei pentru debugger (vidaj de memorie).

3.1.5. Driverul

Cu toate bucatile programului construite noi avem nevoie numai de un driver care sa initializeze si sa porneasca tot procesul. In acest exemplu simplu functia main() poate fi con­struita astfel:

int main() //insereaza nume predefinite

return no_of_errors;

}

Prin conventie, main() returneaza zero daca programul se termina normal si altfel, o valoare diferita de zero, asa ca returnarea numarului de erori se potriveste bine cu aceasta conventie.

Aici singurele initializari sint numerele predefinite pentru "pi" si "e" care se insereaza in tabela de simboluri.

Sarcina primordiala a ciclului principal este sa citeasca expresii si sa scrie raspunsul. Aceasta se obtine prin linia:

cout << expr() << "\n";

Testind pe cin la fiecare pas al ciclului se asigura ca programul sa se termine daca ceva merge rau in sirul de intrare iar testul pentru END asigura ca ciclul sa se termine corect cind get_token() intilneste sfirsitul de fisier. O instructiune break provoaca iesirea din instructiunea switch sau din ciclul care o contine (adica o instructiune for, while sau do). Testul pentru PRINT (adica pentru '\n' si ';') elibereaza pe expr() de necesi­tatea de a prelucra expresii vide. O instructiune continue este echivalenta cu trecerea la sfirsitul ciclului, asa ca in acest caz:

while(cin)

este echivalent cu :

while(cin)

(ciclurile se descriu in detaliu in &r9).

3.1.6. Argumentele liniei de comanda

Dupa ce programul a fost scris si testat, am observat ca tastarea expresiilor la intrarea standard a fost adesea mai mult decit necesar, deoarece in mod frecvent a trebuit sa se evalueze o singura expresie. Daca este posibil ca aceasta expresie sa fie prezentata ca un argument al liniei de comanda, atunci multe accese cheie ar fi fost eliminate.

Asa cum s-a mentionat in prealabil, un program incepe prin apelul lui main(). Cind aceasta s-a facut, main() primeste doua argumente, care specifica numarul de argumente si care de obicei se numeste argc si un vector de argumente, care de obicei se numeste argv. Argumentele sint siruri de caractere, asa ca tipul lui argv este char *[argc]. Numele unui program (intrucit el apare pe linia de comanda) se paseaza ca argv[0], asa ca argc este intotdeauna cel putin 1. De exemplu, pentru comanda:

dc 150/1.1934

argumentele au aceste valori:

argc 2

argv[0] "dc"

argv[1] "150/1.1934"

Nu este dificil sa fie pastrata linia de comanda ca argu­ment. Problema este cum sa se foloseasca fara a face reprogra­mare. In acest caz, este trivial intrucit un sir de intrare poate fi limitat la un sir de caractere in loc de un fisier (&8.5). De exemplu, cin poate fi facut sa citeasca caractere dintr-un sir in loc de intrarea standard:

int main(int argc, char* argv[])

// ca inainte

}

Programul este neschimbat exceptind adaugarea argumentelor la main() si utilizarea lor in instructiunea switch.

S-ar putea usor modifica main() pentru a accepta diferite argumente in linia de comanda, dar acest lucru nu este necesar, deoarece diferite expresii pot fi pasate ca un singur argument:

dc "rate=1.1934;150/rate;19.75/rate217/rate"

Ghilimelele sint necesare aici din cauza ca ';' este separa­tor de comenzi in sistemul UNIX.