Principiul de functionare a programului FLEX

FLEX (Fast LEXical Analyzer Generator) este un generator de analizoare lexicale si constituie unul dintre utilitarele standard ale sistemelor de operare Unix. Se mentioneaza ca prezentul document se bazeaza pe versiunea 2.5.4 a programului FLEX.

Programul FLEX primeste la intrare un fisier continand o specificatie a atomilor pe care urmeaza sa-i recunoasca analizorul generat, precum si a actiunilor semantice de executat. Pe baza acestei specificatii se genereaza un program C ce contine tabelele de analiza, impreuna cu functia de analiza, numita yylex( ). In continuare se compileaza programul obtinut, rezultand astfel analizorul lexical executabil.

Fisierul ce contine specificatia este un fisier text care poate avea orice nume acceptat de sistemul de operare. Din considerente istorice (care tin de versiunile pentru DOS ale programului LEX), se recomanda ca fisierul de specificatie sa aiba extensia .lxi.  

Programul C rezultat este memorat intr-un fisier denumit implicit lex.yy.c (utilizatorul poate solicita explicit un alt nume).  Efectuarea analizei lexicale asupra unui text sursa folosind analizorul generat de FLEX este ilustrata in figura de mai jos.

Lansarea in executie a programului FLEX

Lansarea in executie a programului FLEX se realizeaza cu comanda

In cazul in care nume_fisier_specificatii nu este precizat, FLEX va astepta introducerea specificatiilor de la stdin.
Cateva dintre optiunile liniei de comanda mai des utilizate sunt:

• -d = analizorul generat va functiona in regim "debug", adica la fiecare atom recunoscut se va afisa pe stderr un mesaj care contine numarul liniei din fisierul de specificatii unde apare regula atasata atomului respectiv si secventa de caractere ce compun atomul; se precizeaza ca efectul optiunii -d se obtine cu conditia ca variabila globala yy_flex_debug sa fie setata pe o valoare nenula  (implicit variabila are valoarea 0);

 
• -h = genereaza la stdout un rezumat al optiunilor din linia de comanda (-? si --help au acelasi efect);

 
• -i = analizorul generat va fi case-insensitiv (la identificatorii si cuvintele cheie din textul sursa nu se va face distinctie intre literele mari si cele mici);

 
• -o nume_fisier_iesire = aceasta optiune se foloseste daca se doreste ca fisierul de iesire al generatorului sa aiba alt nume decat lex.yy.c;
• -T = generatorul va lucra in regim "trace", furnizand informatii utile care reflecta mersul procesului de construire a automatelor finite (nedeterminist si determinist);
• -V = la stdout se afiseaza versiunea programului FLEX;
• -+ = analizorul generat va fi in limbajul C++ (implicit el este in ANSI-C).

Structura programului de specificatie
Programul de specificatie contine in principiu expresiile regulate ce descriu atomii limbajului sursa, precum si actiunile pe care analizorul trebuie sa le execute la recunoasterea fiecarui atom.
Structura unui program de specificatie este urmatoarea:

sectiune_definitii
%%
sectiune_reguli
%%
cod utilizator

Sectiunea de definitii

• directive %option
• declaratii de stari de start
• secvente C definite de utilizator

• nume este un cuvant compus din una sau mai multe litere, cifre, '_' sau '-', cu observatia ca primul caracter TREBUIE sa fie litera sau '_' si SA SE AFLE PE PRIMA POZITIE A LINIEI.
• definitie este o expresie regulata si se considera ca incepe cu primul caracter non-spatiu de dupa nume si tine pana la sfarsitul liniei.

Directivele %option permit utilizatorului sa precizeze unele optiuni legate de analizorul generat. Cateva asemenea optiuni sunt:

%option main -- are ca efect generarea unei functii main() care nu face altceva decat sa apeleze functia de analiza yylex();

%option caseless -- are acelasi efect ca si optiunea -i din linia de comanda;

%option debug -- are acelasi efect ca si optiunea -d din linia de comanda;

%option yylineno -- analizorul rezultat va contine cod care actualizeaza variabila globala yylineno cu valoarea curenta a numarului liniei sursa;
%option noyywrap -- aceasta optiune este foarte utila daca se doreste ca la o rulare a analizorului sa se parcurga un singur fisier sursa, asa cum de fapt trebuie sa se intample de cele mai multe ori.
Daca aceasta optiune lipseste, analizorul generat incearca sa prelucreze in lant mai multe fisiere sursa. Trecerea de la un fisier la altul se realizeaza prin apelul de catre analizor a unei functii numite yywrap(), la intalnirea marcajului EOF al fiecarui fisier sursa. Cum functia yywrap() nu exista in mod implicit, ea ar trebui definita de catre utilizator. Rolul acestei functii este sa deschida urmatorul fisier in variabila globala FILE *yyin si sa returneze 0, respectiv sa returneze o valoare nenula daca nu mai exista un fisier urmator.

Secventele C definite de utilizator in sectiunea de definitii

Utilizatorul are posibilitatea de a plasa in sectiunea de definitii secvente proprii de cod C. O modalitate de a introduce aceste secvente C este ca ele sa fie incluse intre perechile de caractere %{ si respectiv %}. Perechile %{ si %} trebuie sa apara pe linii separate si neindentate. 

Codul cuprins intre aceste perechi (exclusiv perechile) va fi copiat ad-literam in analizorul generat, in spatiul de vizibilitate din afara functiei yylex(). Cu alte cuvinte, codul utilizator plasat in sectiunea de definitii va fi considerat ca spatiu de declaratii globale in raport cu functia yylex().

Observatie: intrucat orice linie indentata din sectiunea de definitii este copiata fara modificari in analizorul generat, rezulta ca perechile delimitatoare %{ si %} pot lipsi, cu conditia ca toate liniile de cod ale utilizatorului sa fie scrise indentat. 

Sectiunea de reguli

• sablon este o expresie regulata, al carei prim caracter TREBUIE SA SE AFLE PE PRIMA POZITIE A LINIEI;
• actiune este o secventa formata din 1 sau mai multe instructiuni C care TREBUIE SA INCEAPA PE ACEEASI LINIE CU SABLONUL. Daca secventa e formata din mai multe instructiuni acestea se vor inchide intre acolade. In particular, actiunea poate fi si instructiunea vida.

Daca actiunea este redata prin instructiunea vida, la recunoasterea sirului descris de sablonul in cauza, analizorul nu va executa nimic (de fapt, va trece pur si simplu la delimitarea urmatorului atom). In consecinta, atomii ale caror reguli au actiune vida sunt neglijati (filtrati sau eliminati). Comentariile si spatiile albe sunt exemple de siruri care se preteaza la un asemenea tratament.

Daca o actiune se termina cu instructiunea return, aceasta va insemna iesirea din functia yylex(), altfel aceasta functie trece automat la cautarea urmatoarelor potriviri. In concluzie, daca dorim ca analizorul lexical sa prelucreze cate un singur atom la fiecare apel, va trebui sa prevedem instructiuni return la toate actiunile care corespund unor atomi valizi (nu comentarii sau spatii albe). Acest mod de lucru este potrivit pentru compilatoarele care lucreaza intr-o singura trecere. Pentru compilatoarele care lucreaza in mai multe treceri, analiza lexicala fiind o faza distincta, actiunile se vor termina prin instructiuni de scriere (de exemplu directiva ECHO) a codurilor lexicale intr-un fisier de iesire (care ar putea fi yyout).

Expresii regulate

In continuare, pe baza unor exemple se va descrie sintaxa admisa de FLEX pentru expresiile regulate:
 

In ceea ce priveste actiunile si secventele de cod inserate in sectiunea de reguli, ele pot contine referiri la variabile globale, respectiv apeluri la unele macro-uri si functii utilitare predefinite.
Cateva dintre variabilele utile sunt:

• char *yytext - reprezinta adresa zonei in care se depun caracterele ce compun atomul curent;
• int yyleng - reprezinta lungimea atomului curent;
• FILE *yyin - desemneaza fisierul care contine textul sursa de analizat;
• FILE *yyout - desemneaza fisierul in care se poate scrie cu ajutorul macro-ului ECHO;

• ECHO - realizeaza scrierea continutului zonei yytext in fisierul desemnat prin yyout;
• BEGIN nume_stare_start - realizeaza comutarea analizorului in starea de start specificata;
• REJECT - cauta urmatoarea regula al carei sablon se potriveste cu atomul in curs de prelucrare, sau cu un prefix al acestuia, si executa actiunea asociata regulii gasite;
• YY_START - furnizeaza starea de start curenta (care este o valoarea intreaga);
• yyterminate() - are ca efect terminarea procesului de analiza si returnarea valorii 0 catre apelantul functiei yylex(); yyterminate este un macro si poate fi redefinita de utilizator;
• void yymore() - determina concatenarea urmatorului atom din textul sursa, la atomul existent in yytext (in mod normal urmatorul atom il inlocuieste pe cel precedent);
• void yyless(int n) - lasa in yytext primele n caractere ale atomului curent, restituind in sirul de intrare caracterele de pe pozitiile n+1 pana la sfarsit; actualizeaza apoi valoarea lui yyleng la n (caraterele restituite vor fi analizate ulterior). 

Obs: daca n este 0, inseamna ca intreg atomul este restituit sirului de intrare; acest lucru ar duce la intrarea intr-o bucla infinita a analizorului, deoarece in pasul urmator acealsi atom va fi recunoscut, ajungandu-se la acelasi apel al lui yyless. Argumentul 0 poat fi totusi utilizat cu succes, daca inaintea apelului la yyless, se modifica starea de start (vezi directiva BEGIN);

• void unput(char c) - forteaza plasarea in sirul de intrare a caracterului c, acesta devenind urmatorul caracter analizat. 

Obs: daca se doreste plasarea in sirul de intrare a unui string de caractere, se va apela unput pentru fiecare caracter, incepand de la ultimul pana la primul. Se precizeaza ca argumentul c NU POATE FI CARACTERUL EOF ! Inaintea folosirii functiei unput trebuie facuta o copie a zonei yytext, deoarece continutul ei este alterat incepand cu caracterul cel mai din dreapta.

• int input() - citeste si returneaza urmatorul caracter din sirul de intrare;

Secventele C definite de utilizator in sectiunea de reguli

In sectiunea de reguli, la fel ca in cea de definitii, utilizatorul poate sa plaseze secvente de cod C (altele decat cele care reprezinta actiuni atasate expresiilor regulate). Sintaxa utilizata pentru asemenea secvente este aceeasi ca in cazul sectiunii de definitii.

Codul utilizator din sectiunea de reguli va fi copiat in analizorul generat, in INTERIORUL functiei yylex(). Ca urmare, se recomanda ca secventele C utilizator sa fie plasate inainte de prima regula. De obicei asemenea secvente vor contine declaratii locale in raport cu functia yylex(), respectiv operatii (de exemplu initializari ) care se vor executa la fiecare apel al lui yylex().

Observatie: daca secventele C ale utilizatorului sunt plasate in alte locuri decat inaintea primei reguli, este dificil de anticipat locul din analizorul generat in care vor fi inserate, precum si efectul executiei lor (in caz ca vor ajunge sa fie executate).

Sectiunea de cod utilizator

Acesta sectiune a fisierului de specificatii este optionala (daca lipseste, atunci si separatorul %% care urmeaza dupa sectiunea de reguli poate lipsi). Daca este prezenta, atunci continutul ei, care consta in cod C utilizator, este copiat fara modificari la sfarsitul fisierului lex.yy.c. 

In mod normal, in sectiunea de cod utilizator pot sa apara:

• functia main() care sa contina apel(uri) la yylex(), daca se doreste ca analizorul sa lucreze in mod autonom (de exemplu pentru a-l testa); 
• alte functii apelate din yylex() (de exemplu yywrap() sau functii apelate in cadrul actiunilor); se mentioneaza ca pentru aceste functii trebuie sa avem in codul utilizator din sectiunea de definitii: fie prototipurile, fie directive #include ale header-elor ce contin prototipurile. 

Modul de functionare a analizorului generat de FLEX (functia yylex)

Modul de functionare al analizorului yylex() este guvernat de urmatoarele principii:

• pentru sabloanele recunoscute se aplica actiunile corespunzatoare din specificatie (sectiunea de reguli), care pot genera text specific in fisierul yyout sau pot returna coduri lexicale;
• textul din fisierul sursa care nu se potriveste cu nici un sablon este copiat automat in yyout (in cazul in care yyout nu a fost redefinit, el este implicit stdout);
• daca pentru un text se potrivesc mai multe sabloane, se alege potrivirea cea mai lunga;
• daca pentru un text se potrivesc mai multe sabloane de aceeasi lungime, se alege prima potrivire din specificatie, in ordine textuala;
• textul corespunzator potrivirii este copiat in variabila globala yytext iar lungimea acestuia este memorata in variabila globala yyleng.

Cand analizorul intalneste marcajul EOF, el verifica rezultatul functiei yywrap(). Rezultat fals (zero) inseamna ca analiza trebuie sa continue cu noul fisier desemnat de yyin. Un rezultat nenul al functiei yywrap() determina sfarsitul analizei si returnarea valorii 0 spre apelantul lui yylex().

Absenta functiei yywrap() poate fi suplinita de optiunea %option noyywrap sau prin linkeditare cu optiunea -lfl (ambele variante presupun return 1).

Stari de start

FLEX poate genera analizoare lexicale capabile sa analizeze un fisier sursa in care apar secvente de cod scrise in limbaje diferite (carora le corespund seturi de expresii regulate diferite). Pentru aceasta exista un mecanism care permite activarea dinamica a unui anumit set de reguli, in functie de o asa-numita stare de start.

Starile de start trebuie mai intai declarate in sectiunea de definitii. Declararea se face conform sintaxei:

%s lista_nume_stari_de start_inclusive

sau

%x lista_nume_stari_de_start_exclusive

unde numele din liste sunt separate prin spatii.

In continuare, numele starilor de start vor servi drept etichete atasate anumitor reguli din sectiunea de reguli, precum si ca argumente ale directivelor BEGIN. 

In urma executiei unei directive BEGIN, analizorul trece in starea de start ce apare ca argument al directivei. Din acest moment analizorul va folosi regulile ce corespund conditiei respective:

• daca e vorba de o conditie inclusiva (declarata cu %s), regulile acceptate sunt cele etichetate cu numele conditiei, precum si regulile neetichetate;
• daca e vorba de o conditie exclusiva (declarata cu %x), regulile acceptate sunt doar cele etichetate cu numele conditiei.

Se precizeaza ca o aceeasi regula poate fi etichetata cu una sau mai multe stari de start. Etichetarea se face conform sintaxei:

<lista_nume_stari_de_start>regula

unde numele din lista sunt separate prin virgule. 

Exemplu

In cele ce urmeaza este prezentat un exemplu de fisier de specificatii pentru un subset foarte restrans al limbajului Pascal, care ilustreaza principalele aspecte enuntate in paragrafele de mai sus. Presupunand ca numele acestui fisier este sspas.lxi, comenzile necesare pentru a genera analizorul lexical corespunzator si pentru a-l lansa in executie sunt:

$ flex sspas.lxi

$ gcc lex.yy.c -o alex

$ ./alex nume_fisier_sursa

In ultima comanda nume_fisier_sursa poate lipsi, caz in care se va astepta introducerea textului sursa de la stdin (tastatura).

Observatie: daca se alege aceasta ultima varianta, marcajul de sfarsit de fisier este combinatia Ctrl-D.

La executia analizorului lexical se va putea observa ca prezenta in fisierul sursa a secventelor {+d} si {-d} au ca efect activarea, respectiv dezactivarea in mod dinamic a regimului de lucru "debug".

Fisierul sspas.lxi poate fi accesat aici.

Desfasurarea lucrarii

Se va intocmi o specificatie FLEX continand expresii regulate dintre cele propuse in Anexa A, sau date de conducatorul lucrarii.

Se va utiliza apoi programul FLEX pentru obtinerea unui analizor lexical. Testarea analizorului se va realiza la fel ca si pentru analizorul descris in lucrarea "Proiectarea analizoarelor lexicale".