Compilatoare

lex este un generator de analizoare lexicale n limbajul C lex genereaz codul surs al analizorului lexical (fiierul lex.yy.c) pornind de la un fiier tokdef.l care definete sintaxa atomilor lexicali din limbaj, cu ajutorul expresiilor regulate i a aciunilor semantice asociate fiecrei clase de atomi astfel definit. lex.yy.c conine codul funciei yylex() Fiecrei definiii a unui atom lexical i este asociat o aciune. mpreun (definiia + aciunea asociat) formeaz o regul. n mod implicit o aciune se ncheie cu returnarea tipului de atom lexical identificat, pentru a putea fi folosit n continuare de ctre analizorul sintactic. lex tokdef.l ==> lex.yy.c

Structura fiierului de definiie a atomilor lexicali (fiierul .l) este: %{ define and include directives of cpp %} definitions %% rules %% user defined routines

%{ int charcount=0,linecount=0; %} %% . charcount++; \n {linecount++; charcount++;} %% int main() { yylex(); printf("There were %d characters in %d lines\n,charcount,linecount); return 0; }

ntreg codul din fiierul de intrare dintre %{ i %} este inclus ca atare la nceputul fiierului surs a analizorului lexical generat. Regulile sunt formate din definiiile atomului lexical (expresii regulate) i aciuni corespunztoare. Cele dou componente ale unei reguli sunt desprite printr-un spaiu. La scrierea regulilor este obligatoriu s se nceap de pe prima coloan a fiecrei linii. Aciunea asociat unei definiii a unui atom lexical se scrie n limbajul de programare C. Dac ea este format din mai multe instruciuni, acestea trebuie scrise ntre paranteze acolade.

Partea user defined routines poate conine definiii de funcii. Componenta de baz este funcia main care conine apelul funciei yylex(), funcie care reprezint de fapt analizorul lexical generat. Dac aceast parte este goal, (f)lex va aduga n mod automat o funcie main implicit, de forma: int main(int argc, char *argv[]) { }yylex(); return 0;

1. Scrierea fiierului de intrare pentru (f)lex, de exemplu tokdef.l 2. Generarea fiierului surs a analizorului lexical, lex.yy.c. 3. Compilarea fiierului surs a analizorului lexical i generarea executabilului. 4. Lansarea n execuie ./alex cc lex.yy.c o alex ll cc lex.yy.c o alex -lfl lex tokdef.l flex tokdef.l

Expresiile regulate sunt translatate de ctre lex ntr-un program care mimeaz modul de lucru al unui automat finit determinist. Pe baza strii curente i a valorii urmtorului caracter de la intrare, se determin noua stare prin indexarea ntr-o tabel a strilor generat de ctre program.

int yylex() {... new_symbol: switch (c = getchar();) { case a: case Z: return identifierOrKeyword(); case 0: case 9: return number(); case (: case ): return specSymbol(); case \: return characterOrString(); case EOF: return YYEOF; default: error(INVALID_TOKEN); goto new_symbol; }

Poate s conin: 1. Cod C Codul dintre %{ i %} va fi copiat ca atare la nceputul fiierului lex.yy.c. Poate conine: directive ctre preprocesor (include, define, .a.), definiii de variabile, prototipurile funciilor care vor fi definite n a treia seciune. 2. Definiii Definiiile elementelor de limbaj care vor fi folosite n regulile din a doua seciune letter [a-zA-Z] digit [0-9] punct [,.:;!?] nonblank [ \t]

3. Definiii de stri: Atunci cnd o regul depinde de context, se pot defini stri care s permit identificarea corespunztoare a atomilor lexicali. Definirea unei stri se face astfel: Exist o stare predefinit i anume starea INITIAL. %s NUMESTARE

Conine o serie de perechi definiie-aciune pentru cte o clas de atomi lexicali Definiiile claselor de atomi lexicali sunt expresii regulate scrise i pe baza definiiilor elementelor de limbaj din prima seciune. Aciunile asociate sunt o instruciune C sau mai multe instruciuni C ntre paranteze acolade. ntre definiie i aciunea asociat trebuie s fie cel puin un spaiu. Acest spaiu poate fi unul sau mai multe blanc-uri, unul sau mai multe taburi, dar nu poate fi sfritul de linie. Adic aciunea asociat unei definiii este obligatoriu s nceap de pe aceeai linie cu aceasta.

Scrierea unei reguli trebuie s nceap de pe prima coloan a liniei. Orice text din seciunea de reguli care nu ncepe de pe prima coloan a unei linii este copiat ca atare n fiierul surs generat lex.yy.c. Dac mai multe definiii se potrivesc textului de intrare, se va lua acea definiie care potrivete textul cel mai lung. Dac mai multe definiii potrivesc un text de aceeai lungime, va fi luat prima n ordinea n care au fost scrise n seciunea de reguli.

. Match any character except newlines. \n A newline character. \t A tab character. The beginning of the line. $ The end of the line. * Zero or more occurences of the expression. + One or more occurences of the expression. ? Zero or one occurence of the expression. (|) One expression or another. [] A set of character or ranges, such as [a-zA-Z]. [] The complement of the set, for instance [ \t]. a+b Literal a+b; C escapes still work!

Expression Matches abc abc abc* ab abc abcc abccc ... abc+ abc abcc abccc ... a(bc)+ abc abcbc abcbcbc ... a(bc)? a abc [abc] one of: a, b, c [a-z] any letter, a-z [a\-z] one of: a, -, z [-az] one of: -, a, z [A-Za-z0-9]+ one or more alphanumeric characters [ \t\n]+ whitespace [^ab] anything except: a, b [a^b] one of: a, ^, b [a|b] one of: a, |, b a|b one of: a, b

Dac pentru anumite succesiuni de caractere nu a fost prevzut nici o regul, atunci acestora li se aplic regula implicit (f)lex i anume: potrivirea i copierea caracter cu caracter la ieire. Ex: Cel mai scurt fiier de definiii pentru (f)lex este: Aciunea: Intrarea este copiat n ieire, caracter cu caracter. %

se potriveste definiiei curente int yyleng lungimea succesiunii de caractere din intrare care se potrivete definiiei curente (n fapt lungimea irului de caractere din yytext) Ex: %{ int charcount=0,linecount=0,wordcount=0; %} letter [ \t\n] %% {letter}+ {wordcount++; charcount+=yyleng;} . charcount++; \n {linecount++; charcount++;}

char* yytext succesiunea de caractere din intrare care

Funcia yylex() citete textul de analizat prin intermediul variabilei yyin, i scrie ieirea prin variabila yyout. n mod implicit yyin are valoarea stdin, adic standard input, adic tastatura. n mod implicit yyout are valoarea stdout, adic standard output, adic monitorul. Adic, n mod implicit analizorul lexical generat va analiza textul introdus de la tastatur i va scrie ieirea pe monitor.

FILE *yyout FILE *yyin

output file input file

%{ int yylineno; %} %% ^(.*)\n printf("%4d\t%s", ++yylineno, yytext); %% int main(int argc, char *argv[]) {

yyin = fopen(argv[1], "r"); yyout = fopen(argv[2], w");yylex(); }

fclose(yyin); fclose(yyout);

int yywrap(void) n momentul n care intrarea se termin (adic yylex, citind din yyin ajunge la EOF End Of File) se apeleaz automat funcia yywrap(). yywrap() returneaz 1 dac nu mai exist intrare de analizat, sau 0 dac mai exist. Deci funcia yywrap() mpreun cu yyin i yyout poate fi folosit pentru a analiza consecutiv mai multe fiiere de intrare i respectiv pentru a scrie consecutiv n mai multe fiiere de ieire.

%{ int second_file = 0; %} %% . \n %% int main(int argc, char *argv[]) { yyin = fopen(argv[1], "r"); yyout = fopen(argv[3], w"); yylex(); fclose(yyin); fclose(yyout); }

int yywrap() {

else }

if(second_file == 0) { yyin = fopen(argv[2], "r"); second_file = 1; return 0; } return 1;

int yymore(void) - append the next token to yytext int yyless(int n) - truncate the current token to ncharachers input

int input(void) - extract the next symbol from input void unput(int c) - return the symbol c back to the

Codul generat de ctre (f)lex n lex.yy.c conine i instruciunii de depanare. Acestea pot fi activate prin specificarea parametrului d la etapa de generare a fiierului surs a analizorului lexical. Adic: 2. Generarea fiierului surs a analizorului lexical, lex.yy.c i activarea depanrii. lex d tokdef.l flex d tokdef.l

Dac aplicarea unei reguli depinde de context, atunci analizorul lexical generat trebuie s fie n msur s fac o analiz n funcie de context. Prin context nelegem locaia n cadrul codului surs care trebuie analizat a succesiunii de caractere la care se refer regula respectiv. Pentru a trata astfel de operaii, (f)lex permite utilizarea strii (state), i anume: 1. right state: o regul depinde de ceea ce urmeaz dup succesiunea de caractere 2. left state: regula depinde de ceea ce a fost naintea succesiunii de caractere

Ex: Trebuie s generm un analizor lexical care s modifice numele claselor, metodelor i variabilelor conform conveniei Java de denumire: numele claselor ncep cu liter mare, iar numele variabilelor i ale metodelor ncep cu liter mic. Atomii lexicali corespunztori celor trei tipuri de identificatori au aceeai definiie, i anume: [a-zA-Z][a-zA-Z0-9]* Aciunea asociat definiiilor trebuie ns s fie diferit: - pentru numele de clase trebuie capitalizat prima liter; - pentru numele de variabile i de metode, prima liter trebuie s fie transformat n liter mic.

Dac gndim problema ca fiind o problem de dependen de context de tip stnga, atunci: - dac nainte de identificator a fost cuvntul cheie class urmat de cel puin un spaiu, atunci identificatorul este un nume de clas i trebuie capitalizat primul lui caracter. - dac nainte de identificator a fost orice altceva, atunci el este un nume de variabil sau de metod, i primul su caracter trebuie transformat n liter mic.

Dac gndim problema ca fiind o problem de dependen de context de tip dreapta, atunci: - dac dup identificator urmeaz cel puin un spaiu i apoi o parantez acolad deschis, atunci identificatorul este un nume de clas i trebuie capitalizat primul lui caracter. - dac dup identificator urmeaz orice altceva, atunci el este un nume de variabil sau de metod i primul su caracter trebuie transformat n liter mic.

Specificarea contextului se face cu ajutorul caracterului /. Regula respectiv va avea forma: definiie_atom_lexical/context aciune Ex: [a-zA-Z][a-zA-Z0-9]*/[ \t\n]+[{] { //capitalizm prima liter a lui yytext i scriem yytext la ieire} [a-zA-Z][a-zA-Z0-9]* {//transformm primul caracter din yytext n liter mic i scriem yytext la ieire}

Trebuie avut n vedere c succesiunea de caractere care definete contextul rmne n irul de intrare i va fi analizat n continuare de ctre analizorul lexical.

Regula este prefixat cu numele unei stri, sub forma: definiie_atom_lexical aciune Ceea ce nseamn c regula va fi evaluat numai dac analizorul lexical se afl n starea . Schimbarea strii analizorului lexical se poate face n partea de aciuni a unei reguli cu ajutorul macroului BEGIN, astfel: definiie_atom_lexical { aciuni; BEGIN NUME_ALTA_STARE; } Toate strile trebuie definite n seciunea de definiii a primei pri a fiierului de intrare printr-o instruciune de forma: %s NUME_STARE Starea iniial a analizorului lexical este INITIAL

%{ %} %s CLASSDEF %% [a-zA-Z][a-zA-Z0-9]* { //transformm primul caracter din yytext n liter mic i scriem yytext la ieire } class[ ]+ { BEGIN CLASSDEF; } [a-zA-Z][a-zA-Z0-9]* { //capitalizm prima liter a lui yytext i scriem yytext la ieire; BEGIN INITIAL; } ... %%

punct [,.;:!?] text [a-zA-Z] %% ")"" "+/{punct} ")"/{text} {text}+" "+/")" ({punct}|{text}+)/"(" "("" "+/{text} {text}+" "+/{punct} " "+ " "+ . \n/\n\n \n {printf(")");} {printf(") ");} {while (yytext[yyleng-1]== ) yyleng--; ECHO;} {ECHO; printf(" ");} {while (yytext[yyleng-1]== ) yyleng--; ECHO;} {while (yytext[yyleng-1]== ) yyleng--; ECHO;} ; {printf(" ");} {ECHO;} ; {ECHO;}

punct [,.;:!?] text [a-zA-Z] %s OPEN %s CLOSE %s TEXT %s PUNCT %%

" "+ "(" "(" "(" ")" {text}+ {text}+ {text}+ {text}+ {text}+ {punct}+ \n %%

; {ECHO; BEGIN OPEN;} {printf(" "); ECHO; BEGIN {printf(" "); ECHO; BEGIN {ECHO ; BEGIN CLOSE;} {ECHO; BEGIN TEXT;} {ECHO; BEGIN TEXT;} {printf(" "); ECHO; BEGIN {printf(" "); ECHO; BEGIN {printf(" "); ECHO; BEGIN {ECHO; BEGIN PUNCT;} {ECHO; BEGIN INITIAL;}

OPEN;} OPEN;}

TEXT;} TEXT;} TEXT;}

S folosim:

{letter}({letter}|{digit})* { int i; if ((i = resWord(yytext)) != 0) return (i); yylval.id = symLookup(yytext); return (IDENTIFIER); }

Utilizarea (f)lex pentru a implementa un analizor lexical pentru un limbaj de programare: - definirea claselor de atomi lexicali - definirea tabelelor necesare: de identificatori, de constante, de cuvinte rezervate, .a. - implementarea operaiilor cu tabelele - .a.

Ex:

Provin din modul n care este implementat: prin automate finite deterministe. Consecin: (f)lex are numai stri i tranziii ntre stri. De exemplu, (f)lex nu poate fi utilizat pentru a recunoate structuri mbricate, cum ar fi parantezele. Tratarea structurilor mbricate cu ajutorul lui (f)lex se poate face numai prin utilizarea unei stive (implementat i gestionat de ctre programator).

http://www.cs.rug.nl/~jjan/vb/lextut.pdf http://epaperpress.com/lexandyacc/downloa d/lexyacc.pdf http://tldp.org/HOWTO/pdf/Lex-YACCHOWTO.pdf