Bison - generator automat de analizoare sintactice

BISON – Generator de analizoare sintactice (parsere)

LUCRARE DE LABORATOR

1. Studiul generatoarelor automate de analizoare sintactice: a. Se va citi materialul “Despre bison” b. Se va citi materialul prezentat in referat

2. Se vor studia si implementa exemplele prezentate in referat

Bison - generator automat de analizoare sintactice (parsere)

1. Prezentare generala Bison este un generator de analizoare sintactice pentru gramatici LALR(1) si constituie unul dintre utilitarele standard ale sistemelor de operare Unix. Programul Bison poate genera un “translator” in modul urmator: primeste la intrare un fisier continand o specificatie (specificatiile sintactice si unele semantice) a gramaticii pe care urmeaza sa o recunoasca si genereaza un program C ce contine codul de analiza sintactica, cod care implementeaza metoda de analiza sintactica LALR(1): - Sintaxa de specificare a gramaticii – din fis. de intrare - este o varianta a formei BNF

(Backus-Naur Form). Fisierul ce contine specificatia gramaticii este un fisier text care poate avea orice nume acceptat de sistemul de operare. Din considerente istorice se recomanda ca fisierul de specificatie sa aiba extensia .y (bison este succesorul utilitarului yacc).

- Functia de analiza din programul C generat se numeste yyparse( ). Programul C rezultat este memorat intr-un fisier care are implicit acelasi nume cu fisierul de specificare (mai putin extensia .y) la care se adauga sufixul .tab.c (utilizatorul poate solicita explicit un alt nume).

o In afara de codul generat automat, utilizatorul mai trebuie sa prevada cel putin trei functii C:

• functia main( ) din care se va apela yyparse( ); • functia yylex( ) care va furniza atomii lexicali (este apelata de yyparse); • functia yyerror( char *s ) pentru afisarea mesajelor de eroare (este apelata de

yyparse). In continuare se compileaza programul obtinut, rezultand astfel analizorul sintactic executabil.

• Intrare Bison: Gramatica Iesire Bison: Fisier sursa C, care compilat, constituie parser LALR ptr. gramatica data.

• Bison – folosit si in verificarea erorilor (prin producerea tuturor starilor unui automat finit, se pot depista erorile deplaseaza/reduce sau reduce/reduce).

• Permite completarea cu actiunile posibile in vederea depanarii. • Permite definirea actiunilor semantice si atribuirea de valori simbolurilor gramaticii.

Lansarea in executie a programului Bison Lansarea in executie a programului Bison se realizeaza cu comanda

bison [optiuni] [nume_fisier_specificatii] Cateva dintre optiunile liniei de comanda mai des utilizate sunt:

• -d sau --defines = se genereaza un fisier de iesire suplimentar ce contine macrodefinitii pentru:

o codurile atomilor lexicali definiti in gramatica

1


o tipul asociat atributelor atomilor lexicali YYSTYPE o declaratiile variabilelor externe

Fisierul astfel obtinut are acelasi nume ca si fisierul cu cod C generat, dar cu extensia .h si poate fi inclus in specificatia pentru Flex;

• -h sau --help = afiseaza la stdout un rezumat al optiunilor din linia de comanda;

• -t sau --debug = se genereaza cod pentru macroul YYDEBUG. Activarea regimului "debug" se realizeaza atribuind variabilei globale yydebug o valoare nenula (implicit variabila are valoarea 0);

• -v sau --verbose = se genereaza un fisier de iesire suplimentar ce contine o descriere detaliata a starilor analizorului si a actiunilor preconizate pentru fiecare atom din sirul de intrare. Tot aici sunt descrise si conflictele (rezolvate si nerezolvate) depistate la generarea analizorului. Numele fisierului este acelasi ca nume fisierului cu cod C generat, dar cu extensia .output in loc de .tab.c;

• -o nume_fisier_iesire= aceasta optiune se foloseste daca se doreste ca fisierul de iesire al generatorului sa aiba alt nume decat cel implicit;

• -V sau --version = la stdout se afiseaza versiunea programului Bison; 2. Structura unui fişier sursa bison (yacc): Programul de specificatie, de obicei cu extensia .y, (fisierul sablon pe baza caruia bison-ul genereaza programul C care reprezinta parser-ul) este format din patru mari sectiuni:

%{ declaratii C: declaratii globale si definitii %}

definiţii Bison %% reguli (specificarea gramaticii) %% cod C utilizator Sectiunea de declaratii C este opţională şi poate cuprinde două secţiuni. Sectiunea de definitii bison este asemănătoare cu cea din flex. Astfel este permisă introducerea de cod C între %{ si %}. Tot în secţiunea de definiţii trebuie specificate terminalele pe care analizorul sintactic se asteapta să le primeasca de la analizorul lexical . 1. O primă secţiune cuprinde între delimitatorii %{ şi %} declaraţii în limbajul C pentru

variabilele care se utilizează în regulile de traducere sau în procedurile din cea de-a treia parte a fişierului. Aşadar, textul cuprins între %{ şi %} se copie nealterat în fişierul C produs de bison. Daca nu este nevoie de declaratii C, atunci intreaga sectiune poate lipsi (inclusiv delimitatorii "%{" si "%}").

2. A doua secţiune a acestei prime părţi conţine declaraţii ale unităţilor lexicale ale gramaticii, declaraţii de asociativitate şi precedenţă a operatorilor, declaraţii ale tipurilor de date si declaratii de functii si variabile care sunt folosite in actiunile semantice din regulile gramaticii. Aceste declaratii sunt copiate la inceputul codului generat, inainte de definitia functiei yyparse. Aici se declara atomii lexicali (simbolurile terminale), tipurile asociate atributelor simbolurilor terminale si neterminale, precedenta si asociativitetea operatorilor, etc.

2


Principalele declaratii Bison din aceasta a doua sectiune sunt: • %token pentru declararea simbolurilor terminale ale gramaticii • %union {....} pentru declararea unei multimi de valori posibile

utilizate in actiunile semantice. • %left pentru asociativitate stânga a operatorilor • %right pentru asociativitate dreapta a operatorilor • %nonassoc pentru declaraţiile de neasociativitate • %prec pentru precizarea precedenţei operatorilor • %type pentru definirea tipului simb-lor neterminale

Tot în această secţiune se poate introduce simbolul de start al gramaticii, în cazul în care acesta nu este partea stângă a primei reguli sintactice:

start <nume _simbol _de _start>

%token Simbolurile terminale ale gramaticii – unităţile lexicale – cu excepţia celor formate dintr-un singur caracter (precum +, * etc.), trebuiesc declarate. Aceste simboluri sunt reprezentate în bison prin nişte coduri numerice; funcţia yylex transmite codul unităţii respective funcţiei yyparse. Programatorul nu trebuie să ştie aceste coduri numerice, ele sunt generate automat folosind opţiunea –d la lansarea lui bison şi sunt trecute într-un fişier nume.tab.h (sau yytab.h sub DOS). Unităţile lexicale se definesc prin linii de forma:

% token <nume _unitate _lexicală> şi pot fi utilizate în celelalte două părţi ale fişierului de intrare. Numele de terminale nu au nici o semnificatie pentru bison, ele fiind doar niste denumiri de constante. Totuşi, prin conventie, numele alese pentru terminale conţin numai majuscule, iar toate celelalte nume sunt formate cu minuscule. Se pot utiliza trei tipuri de declaratii bison: • %token [VAL] <nume_atom>: declararea unui atom sau simbol terminal, cu specificarea unei valori (optional). • %token <<VAL>> <SYMBOL>: declararea unui simbol al gramaticii care are valoarea semantica VAL. OBS: <VAL> trebuie inclusa intre < si >. Simbolurile gramaticii pot avea valori semantice1, atribute. În mod implicit, aceste valori sunt întregi si sunt specificate în YYSTYPE. Pentru a specifica alt tip, în partea de declaraţii C se adaugă o directivă define pentru YYSTYPE:

#define YYSTYPE <nume tip> declară tipul valorilor semantice (atributelor) pentru simbolurile gramaticii ca fiind <nume tip>. Utilizarea de tipuri diferite pentru simboluri diferite se realizează prin specificarea acestor tipuri într-o declaraţie union (specifică bison), iar declararea tipului simbolurilor cu type.

Exemplul 1: %union {

int intval; double doubleval; symrec *tptr;

}

1 Vezi si paragrafele Descrierea regulilor semantice in bison si Valorile simbolurilor si actiuni ale regulilor.

3


%type <intval> INT %type <doubleval> REAL %type <tptr> ID Prin aceste declaraţii se specifică tipul valorilor pentru token-urile INT, REAL, ID ca fiind respectiv int, double, pointer la symrec (pointer în tabela de simboluri). %{ /*sectiunea de declaratii dintr-un fis. De specificatii bison ptr. generarea unui analizor de expresii aritmetice */ #include <stdio.h> #include <string.h> #define MAX_SIZE 100 char *_finalstr; %} %token SEMICOLON %token MULT %token DIV %token PLUS %token MINUS %token RPAREN %token LPAREN %token <num> NUMBER %union{ double num; char *str; } %type <str> exprlist %type <num> expr %type <num> addexpr %type <num> multexpr %type <num> unaryexpr %type <num> simpleexpr Exemplul 1-1: %right '=' %left '-' '+' %left '*' '/' %right '^' %nonassoc '(' ')' Declaratia %left arata ca operatorii declarati prezinta asociativitate stanga. De exemplu pentru operatia de adunare: x+y+z=(x+y)+z . Pentru asociativitate dreapta se foloseste %right . Termenul nonassoc exprima faptul ca operatorul nu este asociativ. Ordinea de declarare a operatorilor, permite stabilirea precedentei operatiilor. Operatiile declarate la inceput sunt cele mai putin prioritare, iar cele declarate la sfarsit sunt cele mai prioritare .

Sectiunea de reguli gramaticale este obligatorie si contine regulile gramaticale care descriu sintaxa pe care trebuie sa o verifice analizorul lexical generat cu bison. In aceasta sectiune se specifica productiile gramaticii si actiunile de realizat sunt specificate.

Fiecare regulă conţine:

4


- partea stângă (un neterminal al gramaticii GIC); - partea dreaptă (şirul format din terminali şi neterminali, corespunzător unei reguli din GIC);

o Cele două părţi sunt despărţite prin “:” (două puncte). - partea de acţiune, cuprinsă între{ şi }, conţine cod C care va fi inclus în analizor şi

reprezintă operaţiile care se execută atunci când analizorul realizează o reducere cu regula specificată. Analizorul sintactic executa acţiunea de la sfarşitul unei producţii imediat ce aceasta se potriveste pe datele de la intrare.

O regulă se termină prin “;” (punct virgulă). Dacă sunt mai multe reguli care au aceeaşi parte stângă, acestea se scriu o singură dată şi părţile drepte se despart prin “|’’. Sintaxa de scriere a regulilor gramaticale este urmatoarea: rezultat: alternativa1 | alternativa2 ... ; unde

• rezultat este o un simbol neterminal pentru care se descriu regulile de derivare; • alternativele sunt secvente de simboluri terminale si nerminale grupate conform

productiilor gramaticii. Fiecare producţie conţine de la stanga la dreapta, un simbol neterminal, caracterul : şi o lista de simboluri şi acţiuni. Cu ajutorul caracterului ; se marchează sfarşitul producţiei .

Exemplul 2: Regulile gramaticii care descrie expresiile aritmetice: expr : NUMAR

| expr ‘+’ expr | expr ‘-’ expr | expr ‘*’ expr | expr ‘/’ expr | ‘(‘ expr’)’ ;

Aici, expr este numele neterminalului care defineşte expresia aritmetică, terminalii +, -, *, /, (, ) se pun între apostrof, iar NUMAR reprezintă token-ul (unitatea lexicală) număr (ce trebuie declarat în secţiunea declaraţii). Dacă dorim ca analizorul pe care-l construim să realizeze şi acţiuni semantice2, de pildă să evalueze expresiile (pentru şirul 25+15, pe lângă faptul că verifică sintaxa, raportează şi rezultatul adunării, valoarea 40), se adaugă la reguli partea de acţiune. Pentru fiecare productie se ataseaza intre acolade actiunea de urmat. In cadrul acesteia, $1, $2, $3, .... identifica tokenii din dreapta productiei (capatul recunoscut pe vf. stivei cu valorile respective), iar $$ identifica valoarea pe care o primeste neterminalul care este introdus in stiva in locul celor redusi. expr : NUMAR {$$ = $1;}

| expr ‘+’ expr {$$ = $1+$3;} | expr ‘-’ expr {$$ = $1-$3;} | expr ‘*’ expr {$$ = $1*$3;} | expr ‘/’ expr {$$ = $1/$3;}

2 Vezi si paragraful Descrierea regulilor semantice in bison si Modul de functionare a analizorului sintactic

5


| ‘(‘ expr’)’ {$$ = $2;} ;

În partea de acţiune se scriu instrucţiuni în limbajul C. Aici, $$ reprezintă valoarea unui atribut al neterminalului expr din stânga regulii sintactice, iar $i reprezintă valoarea atributului celui de-al i-lea simbol din partea stângă a regulii.

Implicit, prima regula din sectiune este cea care descrie derivarile posibile pentru simbolul de start al gramaticii (prima producţie se considera cea de nivel cel mai înalt). Expresia din partea dreapta a unei producţii conţine 0 sau mai multe simboluri . Un exemplu de producţie foarte simpla este cea care conţine în partea dreapta un singur simbol. Dupa ce apare în stanga unei producţii, un simbol poate fi folosit în producţii ulterioare în partea dreapta . Caracterul | citit ca "sau" introduce o regula având aceeaşi parte stanga ca regula anterioara . Exemplul 3 (specificarea regulilor pentru un parser al unui text in limbaj natural: propoziţie : prop_simpla {printf("\n Propoziţie simpla");} | prop_compusa {printf("\n Propoziţie compusa");} ; prop_simpla:subiect verb complement ; prop_compusa:prop_simpla CONJ prop_simpla |prop_compusă CONJ prop_simpla ; subiect : SUBST | PRON | ADJ subiect ; verb :VERB |ADV VERB |verb VERB ; complement:SUBST |ADJ complement ;

Dacă datele de intrare nu corespund nici unei reguli (Exemplu subiect, subiect) atunci se apelează funcţia yyerror( ) definita în secţiunea de rutine, şi apoi se aplica productia speciala error. Se poate introduce facilitatea de revenire din eroare, modificând codul pentru yyerror( ). Exemplul 4 (specificarea regulilor pentru parser-ul de expresii aritmetice din exemplul 1): exprlist: exprlist expr | expr ; expr: addexpr SEMICOLON | SEMICOLON ; addexpr: addexpr PLUS multexpr | addexpr MINUS multexpr | multexpr

6


; multexpr: multexpr MULT unaryexpr | multexpr DIV unaryexpr | unaryexpr ; unaryexpr: MINUS unaryexpr | simpleexpr ; Simpleexpr:LPAREN expr RPAREN | NUMBER ; Secţiunea de cod utilizator conţine cod C definit de utilizator, cod care este copiat ca atare în analizorul sintactic generat (la sfarsitul fisierului in care se afla codul generat automat); conţine rutine scrise în limbaj C care se includ nealterate în analizorul generat cu bison. În această sectiune trebuie furnizat un analizor lexical, adică o funcţie yylex() precum şi apelul (în programul principal) la funcţia yyparse() pe care o creează bison-ul.Aici este locul potrivit pentru definirea functiilor main, yyerror si eventual yylex. Cea mai importanta funcţie din aceasta secţiune este funcţia main(), care cheama în mod repetat funcţia yyparse() până când datele de la intrare se termina. Funcţia yyparse() reprezinta analizorul sintactic generat de bison, deci programul încearca în mod repetat să analizeze propoziţii până când se termina datele de la intrare. Terminarea datelor de la intrare este semnalata de analizorul lexical prin întoarcerea valorii 0. Exemplu de secţiune cod utilizator: extern yyin; /* variabila yyin este o variabila globala generata de flex în codul analizorului lexical , fiind implicit iniţializata la intrarea standard*/ main ( ) { while( !feof(yyin)) {yyparse( );} } yyerror(char *s) { fprintf(stderr,"%s\n",s); } Modul de funcţionare al analizorului sintactic (analiza sintactica LR sau de tip deplasare - reducere ) Un analizor sintactic generat cu bison lucrează detectând reglile de producţie care s-ar putea aplica utilizând terminalele citite deja. Pentru a realiza acest lucru el crează o mulţime de stări, fiecare reprezentând o poziţie posibila în una sau mai multe reguli de producţie partial analizate. La citirea unui terminal de la intrare, analizorul poate acţiona în doua feluri:

• Dacă prin citirea terminalului nu se ajunge la sfarşitul nici unei reguli de producţie partial analizate, terminalul este introdus într-o stiva interna iar analizorul trece într-o stare care să reflecte noua poziţie în regulile partial analizate. Aceasta operatie se numeste deplasare.

• Când analizorul a detectat toate simbolurile, terminale sau neterminale, care formează partea dreapta a unei reguli, el extrage simbolii ce formează partea dreapta de pe stiva

7


interna, introduce simbolul aflat în stanga producţiei şi intra într-o noua stare care să corespunda noului simbol introdus. Aceasta operatie se numeste reducere .

Fie gramatica expresiilor aritmetice şi şirul de intrare a * (a + a). (1) E → E + T (2) E → T (3) T → T * F (4) T → F (5) F → (E) (6) F → a Pentru acelaşi şir se obţine secventa de miscări: (q, a * (a + a), $, l) |- (q, * (a + a), $a, l) |- (q, * (a + a), $F, 6) |- (q, * (a + a), $T, 64) |- (q, (a + a), $T *, 64) |- (q, a + a), $T * (, 64) |- (q, + a), $T * (a, 64) |- (q, + a), $T * (F, 646) |- (q, + a), $T * (T, 6464) |- (q, + a), $T * (E, 64642) |- (q, a), $T * (E +, 64642) |- (q, ), $T * (E + a, 64642) |- (q, ), $T * (E + F, 646426) |- (q, ), $T * (E + T, 6464264) |- (q, ), $T * (E, 64642641) |- (q, l, $T * (E), 64642641) |- (q, l, $T * F, 646426415) |- (q, l, $T, 6464264153) |- (q, l, $Î, 64642641532) |- (q, l, l, 64642641532) Sa consideram urmatorul exemplu: gramatica (simplificata) a expresiilor aritmetice:

(r1) E → E + E (r2) E → E * E (r3) E → id

O succesiune de derivari (dreapta) pentru a obtine propozitia x+y*z este:

E E * E E * z E + E * z E + y * z x + y * z 2

→3

→1

→3

→3

→Pentru a analiza sintactic propozitia (programul sursa) trebuie construita derivarea in sens invers (de la frunze catre simbolul de start: vom reduce propozitia x + y * z la simbolul de start (E)). Acest tip de analiza sintactica este este numit bottom-up sau shift-reduce parsing si foloseste o stiva pentru stocarea formelor propozitionale intermediare. Iata aceeasi derivare, dar in ordine inversa:

(1) . x + y * z shift (2) x . + y * z reduce (r3) (3) E . + y * z shift (4) E + . E * z shift (5) E + y . * z reduce (r3) (6) E + E . * z shift (7) E + E * . z shift

8


(8) E + E * z . reduce (r3) (9) E + E * E . reduce (r2) efectueaza inmultirea (10) E + E . reduce (r1) efectueaza adunarea (11) E . acceptare

Termenii din stanga punctului sunt introdusi in stiva, cei din dreapta punctului urmand sa fie cititi de pe banda de intrare. Cand vf. stivei coincide cu partea dreapta a unei productii, atunci atomii din vf. acesteia se inlocuiesc cu partea stanga a productiei recunoscute. Intuitiv, atomii recunoscuti sunt scosi din stiva (pop) – a avut loc recunoasterea unui capat - iar partea stanga a productiei este introdusa (push) - reducerea. Grupul de atomi recunoscutti este numit capat (handle), iar operatia consta in reducerea capatului recunoscut cu partea stanga a productiei. Procesul continua pana cand toti atomii (tokenii) de la intrare sunt “shiftati” pe stiva, iar stiva nu contine decat simbolul de start.

La pasul 1 se shfteaza x pe stiva. La pasul 2 se aplica o reducere pentru regula r3 (se schimba x in E), etc, pana cand in stiva ramane doar simbolul de start. La pasii 9 si 10, cand se reduc r2, respectiv r1, se emit instructiunile de inmultire, respectiv adunare. Inmultirea are prioritate mai mare fata de adunare. Totusi, sa analizam ce se intampla la pasul 6: operatia de deplasare (shiftare): aici, in loc sa realizam o deplasare, am fi putut reduce vf. stivei (E + E) cu r1. Aceasta ar fi fost corecta daca adunarea avea prioritate mai mare ca inmultirea. In mod normal, bison nu stie ce operatie (deplasare sau reducere) dorim sa aplicam: este o situatie in care apare un conflict deplasare-reducere.Astfel de situatie se rezolva fie rescriind gramatica (eliminam ambiguitatea), fie semnaland bison-ului care este prioritatea operatorilor implicati. Valorile simbolurilor şi acţiuni ale regulilor.Orice simbol într-un analizor generat de yacc are o valoare, care furnizeaza informaţii suplimentare despre o anumita apariţie a simbolului. Dacă simbolul reprezinta un număr, atunci valoarea va fi numărul respectiv, dacă este un şir, valoarea va fi un pointer catre zona în care este memorat şirul, iar dacă este un identificator, valoarea este un pointer catre o intrare în tabela de simboluri. Unele terminale nu au nici o valoare utila . De exemplu, pentru paranteze nu avem nevoie de valoare, pentru ca doua apariţii ale acestui simbol nu difera prin nimic. Simbolurile neterminale pot avea orice valoare, stabilita în codul specificat în programul bison(yacc). În specificaţiile mai complicate, simboluri diferite folosesc tipuri de date diferite. De exemplu, int şi double pentru numere, char* pentru şiruri şi pointeri catre structuri pentru simboluri de nivel mai înalt. Dacă se folosesc mai multe tipuri de valori, ele trebuie listate astfel încât yacc să poata genera un tip union, cu numele YYSTYPE, care să le conţina. În mod implicit, yacc considera ca toate valorile sunt de tip int. De fiecare data când analizorul reduce o regula, executa codul asociat cu acea regula, cod denumit acţiune. Acţiunea apare între acolade, la sfarşitul regulii înainte de | sau ; . Codul din acţiune se poate referi la valorile simbolurilor (yylval corespunzător) din partea dreapta a regulii prin $1,$2,… şi poate seta valoarea simbolului din stanga , folosind $$. Exemplu: expresie : expresie '+' număr {$$=$1+$3} | expresie '-' număr {$$=$1-$3} | număr {$$=$1} ;

9


Tratarea erorilor in bison Analizorul sintactic generat de Bison sesizeaza, implicit, o eroare sintactica, atunci cand atomul lexical care urmeaza nu poate fi prelucrat conform regulilor sintactice si in contextul creat (continutul stivei analizorului). Utilizatorul poate genera o situatie de eroare sintactica si in mod explicit, in cadrul unei actiuni, prin invocarea macroului YYERROR. Semnalarea erorii se realizeaza prin apelarea functiei yyerror() cu un argument reprezentand mesajul de eroare. Apelul functiei yyerror() se face fie automat, din functia yyparse(), fie imediat inainte de invocarea lui YYERROR. Mesajul implicit, in cazul erorilor sintactice depistate automat, este “parse error”, dar utilizatorul poate obtine si mesaje “mult mai sugestive” daca defineste simbolul YYERROR_VERBOSE in sectiunea de declaratii (nu conteaza valoarea asociata acestuia).

Revenirea din erori Dupa revenirea din functia yyerror(), in functia yyparse(), analizorul sintactic va incerca “revenirea din eroare”. Revenirea din eroare si continuarea compilarii este posibila doar daca in sectiunea de reguli sunt prevazute si productii de eroare corespunzatoare. In absenta acestor productii de eroare, analizorul sintactic isi termina executia si genereaza un cod de retur diferit de zero. Productii de eroare

In tentativa de revenire din eroare, analizorul sintactic introduce, in mod fortat, in sirul de intrare un simbol special cu numele error. Simbolul error este predefinit in limbajul recunoscut de Bison si este considerat simbol terminal (token, atom) cu destinatie speciala pentru tratarea erorilor. Utilizatorul poate prevedea cateva reguli speciale, numite productii de eroare, in sectiunea de reguli, care sa contina pseudo-atomul error. Daca una din aceste reguli speciale se “potriveste” cu situatia nou creata (prin introducerea fortata a lui error in sirul de intrare), procesul de analza (functia yyparse) poate continua. “Potrivirea” regulilor, care reprezinta productii de eroare, este interpretata de catre Bison intr-o maniera foarte larga, in sensul ca daca “potrivirea stricta” nu este aplicabila, atunci se fac noi tentative de “aranjara a unei potriviri” dupa cum urmeaza. Mai intai se deruleaza inapoi contextele, prin scoaterea succesiva a starilor din stiva analizorului, pana cand se ajunge intr-o stare care sa permita deplasarea simbolului error. In continuare se incearca deplasarea, conform regulii date de productia de eroare, a atomului aflat in sirul de intrare la momentul sesizarii erorii (atomul care a declansat eroarea). Daca acest lucru nu este posibil, se abandoneaza atomul si se citesc noi atomi pana cand se va realiza potrivirea cu regula. Atomii care nu s-au potrivit regulii sunt si ei abandonati.

Modul de construire a productiilor de eroare determina, in final, strategia de revenire din erori. O strategie simpla si eficienta este ca simbolul error sa apara la sfarsitul productiilor de eroare, intercalat intre doua simboluri terminale. Astfel se incerca reducerea intregii constructii sintactice, in care apare eroarea, fara a mai semnala alte erori in lant. Binenteles, aceasta schema functioneaza doar daca atomul care incheie constructia apare corect in textul sursa. In caz contrar revenirea din eroare va trebui sa se faca cu o alta productie de eroare, la un nivel mai sus in ierarhia regulilor sintactice (mai aproape de simbolui de start al gramaticii). Totusi, pentru a preveni semnalarea erorilor sintactice in lant, cauzate de o singura gresala in textul sursa, analizorul generat de Bison emite un mesaj de eroare dupa care suspenda emiterea celorlalte mesaje. Reluarea semnalarii mesajelor de eroare se realizeaza fie prin apelul macroului yyerrok (in cadrul unei actiuni semantice asociate unei reguli), fie in mod automat dupa prelucrarea cu succes a trei atomi consecutivi.

10


Descrierea regulilor semantice in Bison Semantica limbajului este data de actiunile pe care le executa compilatorul in momentul in care recunoaste anumite constructii sintactice. Rezultatul actiunilor semantice depinde in mare masura de valorile care intra in calcul si care, de regula, reprezinta atributele asociate simbolurilor (terminale sau neterminale). Pentru aceasta, programul Bison permite atasarea la oricare simbol al gramaticii a unei valori semantice, pe post de atribut. Tipul implicit pentru atribute este int. Pentru a preciza alt tip pentru atributele tuturor simbolurilor se introduce definitia: #define YYSTYPE tip_explicit in sectiunea de declaratii. Pentru a preciza tipuri distincte pentru atributele diferitelor simboluri sunt necesare doua etape: - descrierea tuturor tipurilor preconizate pentru atribute in declaratia %union. - precizarea explicita a tipului atributului pentru fiecare simbol (terminal sau neterminal) a

carui valoare semantica se utilizeaza. Pentru simbolurile terminale precizarea tipului se realizeaza in cadrul declaratiei %token, iar pentru simbolurile neterminale in cadrul declaratiei %type.

Actiunile semantice se pot intercala printre simbolurile productiilor din sectiunea de reguli si au forma:

{ instructiuni C} De regula, productiile au o singura actiune semantica plasata la sfarsitul productiei. Actiunea tipica este cea care calculeaza valoarea atributului pentru simbolul rezultat (din partea stanga a productiei) in functie de atributele simbolurilor care compun alternativa regulii sintactice (din partea dreapta a productiei). Codul C din cadrul actiunii semantice poate referi atributul pentru simbolul rezultat prin constructia $$ iar atributele simbolurilor care compun alternativa prin constructii de forma $n, unde n este numarul de ordine al simbolului din cadrul alternativei (eventualele actiuni semantice intercalate printre simboluri intra si ele la numar). Exemplul 4: /* Exemplu de fisier intrare bison, exemplul4.y */ %{ int yylex(void); void yyerror(char* s); %} %token ID %token WHILE %token BEGIN %token END %token DO %token IF %token THEN %token ELSE %token SEMI %token ASSIGN %start prog %% prog: stmlist

; stm: ID ASSIGN ID

| WHILE ID DO stm | BEGIN stmlist END | IF ID THEN stm | IF ID THEN stm ELSE stm

11


; stmlist: stm

| stmlist SEMI stm ;

%% Dacă se compilează acest fişier cu bison, acesta construieşte automatul LALR(1) pentru gramatica descrisă în secţiunea Reguli. Această gramatică are 3 neterminali: prog (simbolul de start al gramaticii), stm şi stmlist. Terminalii sunt declaraţi prin directiva %token. Bison raportează conflictele de deplasare – reducere şi cele de reducere-reducere dacă există. Aceste conflicte sunt rezolvate de către bison astfel: • conflictul de deplasare-reducere este rezolvat în favoarea deplasării; • conflictul de reducere-reducere este rezolvat în favoarea reducerii cu regula care apare prima în lista de reguli Pentru descrierea precedentă este raportat un singur conflict de deplasare reducere (este obţinut datorită celor două forme ale instrucţiunii IF). Automatul LALR(1) obţinut este vizibil dacă se lanseaza bison – ul cu opţiunea –v (pentru a afla ce opţiuni pot fi folosite lansaţi bison –h). Iată cum se descrie automatul în exemplul dat (exemplul4.output, generat datorita optiunii -v) - LALR PARSING TABLE: State 20 conflicts: 1 shift/reduce Grammar 0 $accept: prog $end 1 prog: stmlist 2 stm: ID ASSIGN ID 3 | WHILE ID DO stm 4 | BEGIN stmlist END 5 | IF ID THEN stm 6 | IF ID THEN stm ELSE stm 7 stmlist: stm 8 | stmlist SEMI stm Terminals, with rules where they appear $end (0) 0 error (256) ID (258) 2 3 5 6 WHILE (259) 3 BEGIN (260) 4 END (261) 4 DO (262) 3 IF (263) 5 6 THEN (264) 5 6 ELSE (265) 6 SEMI (266) 8 ASSIGN (267) 2 Nonterminals, with rules where they appear $accept (13) on left: 0 prog (14) on left: 1, on right: 0 stm (15) on left: 2 3 4 5 6, on right: 3 5 6 7 8 stmlist (16) on left: 7 8, on right: 1 4 8

12


state 0 0 $accept: . prog $end ID shift, and go to state 1 WHILE shift, and go to state 2 BEGIN shift, and go to state 3 IF shift, and go to state 4 prog go to state 5 stm go to state 6 stmlist go to state 7 state 1 2 stm: ID . ASSIGN ID ASSIGN shift, and go to state 8 state 2 3 stm: WHILE . ID DO stm ID shift, and go to state 9 state 3 4 stm: BEGIN . stmlist END ID shift, and go to state 1 WHILE shift, and go to state 2 BEGIN shift, and go to state 3 IF shift, and go to state 4 stm go to state 6 stmlist go to state 10 state 4 5 stm: IF . ID THEN stm 6 | IF . ID THEN stm ELSE stm ID shift, and go to state 11 state 5 0 $accept: prog . $end $end shift, and go to state 12 state 6 7 stmlist: stm . $default reduce using rule 7 (stmlist) state 7 1 prog: stmlist . 8 stmlist: stmlist . SEMI stm SEMI shift, and go to state 13 $default reduce using rule 1 (prog) state 8 2 stm: ID ASSIGN . ID ID shift, and go to state 14 state 9 3 stm: WHILE ID . DO stm DO shift, and go to state 15 state 10 4 stm: BEGIN stmlist . END 8 stmlist: stmlist . SEMI stm END shift, and go to state 16 SEMI shift, and go to state 13 state 11

13


5 stm: IF ID . THEN stm 6 | IF ID . THEN stm ELSE stm THEN shift, and go to state 17 state 12 0 $accept: prog $end . $default accept state 13 8 stmlist: stmlist SEMI . stm ID shift, and go to state 1 WHILE shift, and go to state 2 BEGIN shift, and go to state 3 IF shift, and go to state 4 stm go to state 18 state 14 2 stm: ID ASSIGN ID . $default reduce using rule 2 (stm) state 15 3 stm: WHILE ID DO . stm ID shift, and go to state 1 WHILE shift, and go to state 2 BEGIN shift, and go to state 3 IF shift, and go to state 4 stm go to state 19 state 16 4 stm: BEGIN stmlist END . $default reduce using rule 4 (stm) state 17 5 stm: IF ID THEN . stm 6 | IF ID THEN . stm ELSE stm ID shift, and go to state 1 WHILE shift, and go to state 2 BEGIN shift, and go to state 3 IF shift, and go to state 4 stm go to state 20 state 18 8 stmlist: stmlist SEMI stm . $default reduce using rule 8 (stmlist) state 19 3 stm: WHILE ID DO stm . $default reduce using rule 3 (stm) state 20 5 stm: IF ID THEN stm . 6 | IF ID THEN stm . ELSE stm ELSE shift, and go to state 21 ELSE [reduce using rule 5 (stm)] $default reduce using rule 5 (stm) state 21 6 stm: IF ID THEN stm ELSE . stm ID shift, and go to state 1 WHILE shift, and go to state 2 BEGIN shift, and go to state 3

14


IF shift, and go to state 4 stm go to state 22 state 22 6 stm: IF ID THEN stm ELSE stm . $default reduce using rule 6 (stm) Exemplul 5: /* Intrare bison pentru expresii aritmetice de forma a*(a+a) */ %{ #define QUIT ((double) 101010) void prompt( void ){ printf("READY> "); } %} %start S %% S: { prompt(); }

| S '\n' { prompt(); } | S E '\n' {

if ($2 == QUIT) { return(0);}

else { printf("Expresia este corecta.\n"); prompt();}

} ;

E : E '+' T {printf(" E->E+T\n");} | E '-' T {printf(" E->E-T\n");} | T {printf(" E->T\n");} ;

T : T '*' F {printf(" T->T*F\n");}

| T '/' F {printf(" T->T/F\n");} | F {printf(" T->F\n");} ;

F : '(' E ')' {printf(" F->(E)\n");}

| 'a' {printf(" F->a\n");} ;

%% #include <stdio.h> #include <ctype.h> int main(){ printf("\n**********************************************\n"); printf("** **\n"); printf("** Parser pentru expresii aritmetice **\n"); printf("** cu operanzi a si operatori +,-,*,/,( ) **\n"); printf("** La promterul READY> **\n"); printf("** Introduceti o expresie. Ex. a*(a+a)-a **\n"); printf("** Pentru iesire tastati quit **\n"); printf("** **\n");

15


printf("\n**********************************************\n"); yyparse(); } yyerror(s){ printf("Expresia este incorecta\n"); } yylex(){ int c; while ((c=getchar()) == ' ' || c == '\t' ); if(c==EOF)

return 0; if (c == 'Q' || c == 'q')

if ((c=getchar()) == 'U' || c == 'u') if ((c=getchar()) == 'I' || c == 'i')

if ((c=getchar()) == 'T' || c == 't') { yylval = QUIT;

return( EOF ); } else return '?'; return c; }

OBSERVATII FINALE BISON poate fi folosit pentru proiectarea de aplicaţii diverse. Dezvoltarea unui proiect cu ajutorul BISON - ului presupune parcurgerea următoarelor etape: 1. Identificarea problemei. Acest lucru presupune o viziune de ansamblu asupra proiectului stabilindu-se arhitectura sistemului ce urmează a fi proiectat, descompunerea sistemului în funcţiile componente, etc; 2. Definirea limbajului sursă. Obiectul acestui pas este specificarea limbajului care urmează a fi tradus. Cel mai adecvat mecanism pentru această specificare este gramatica independentă de context pentru că se poate descrie această gramatică direct în limbajul BISON; 3. Scrierea programului de descriere a gramaticii în fişierul de intrare pentru BISON; 4. Scrierea codului auxiliar. În acest pas se stabilesc şi se scriu acţiunile ataşate regulilor sintactice, funcţiile necesare lansării aplicaţiei (main(), yylex(), yyerror()) precum şi alte instrucţiuni C care urmează a fi încorporate în programul generat de BISON; 5. Obţinerea funcţiei yyparse(). Odată creat fişierul de intrare, se lansează BISON pentru acesta şi se obţine programul sursă C. Dacă sunt necesare şi alte funcţii C, acestea se pot incorpora în programul obţinut de BISON; 6. Compilarea textului obţinut şi obţinerea programului executabil.

16

Bison - generator automat de analizoare sintactice

Documents

Transcript of Bison - generator automat de analizoare sintactice