Kako napraviti parser – alati lex i yacc

9. januara 2019.16. aprila 2019. Mateja Ašanin 0 Komentara bison, flex, lex, parsinranje, yacc

Da li vam je ikada bio potreban parser kako biste utvrdili ispravnost teksta ili fajla? Da li ste se zapitali kako biste napravili kompajler za svoj programski jezik ili programski okvir (framework)? U ovome u velikoj meri mogu da pomognu alati lex i yacc.

Sadržaj

Uvod

Lex i yacc su dva uparena alata pomoću kojih možete napraviti parser za tekst. Lex deli ulazni tok na tokene (reči), dok yacc uzima tokene i sastavlja ih u konstrukciju visokog-nivoa, analognu rečenici. Yacc je dizajniran da radi sa izlaznim tokom lex-a, iako se dodatnim kodom to može zaobići. Međutim, izlazni tok lex-a je dizajniran tako da može poslužiti kao ulazni tok i nekom drugom parseru.

Njihova namena je da čitaju fajlove koji imaju razumljiv strukturirani format. Na primer, programski kod u većini programskih jezika se može pročitati pomoću lex-a i yacc-a. Većina fajlova ima predvidljiv format koji se može pročitati pomoću ovih alata. Lex i yacc se mogu koristiti za jednostavnu i regularnu gramatiku. Prirodni jezici su ipak van njihovog dometa, ali većina računarskih programskih jezika je u okviru njihovih mogućnosti.

Pored lex-a i yacc-a, često ćete se sresti sa terminima kao što su flex i bison. Kako su lex i yacc deo standardnog BSD Unix paketa, flex je napravljen GNU alternativa lex-u, a bison kao GNU alternativa yacc-a.

U nastavku teksta daćemo nekoliko jednostavnih primera primene ovih alata. Tekst je namenjen programerima, i nije neophodno predznanje iz teorije automata.

Instalacija lex-a i yacc-a

Ukoliko želite da instalirate lex i yacc na Debian/Ubuntu sistemu, to možete uraditi sledećom komandom u terminalu:

$ sudo apt-get install byacc flex

Ukoliko koristite Windows, potrebno je sa linka http://gnuwin32.sourceforge.net/packages.html, preuzeti instalacije za flex i bison i instalirati ih. Nakon toga, potrebno je u System Properties -> Enviroment Variables -> Path, dodati putanju do foldera u kom su flex i bison instalirani.

Pokretanje lex i yacc programa

Lex program se piše u fajlu čija je ekstenzija „l“. Da bismo dobili leksički analizator, potrebno je izvršiti sledeću komandu:

$ lex .l

Na taj način smo generisali leksički analizator, koji je smešten u fajlu lex.yy.c.

Sa druge strane, yacc program se piše u fajlu čija je ekstenzija y. Da bi dobili sintakstni analizator, potrebno je izvršiti sledeću komandu:

$ yacc -d .y

Tako ćemo generisani sintakstni analizator, koji se nalazi u datoteci y.tab.c i header fajl y.tab.h. Da bi dobili izvršni fajl, potrebno je pokrenuti sledeću komandu:

$ gcc -o  lex.yy.c y.tab.c -lfl

Ukoliko nam je potreban samo izvršni fajl leksičkog analizatora, to možemo postići na sledeći način:

$ gcc -o  lex.yy.c -lfl

Lex: lexical analyzer generator

Leksički analizator je program koji ulazni tok deli na prepoznatljive delove. Lex prihvata problemski orijentisanu specifikaciju za poklapanje ulaznog toka sa pravilima i proizvodi program na jeziku opšte namene koji prepoznaje regularne izraze. Regularne izraze zadaje korisnik u izvornoj specifikaciji lex-a.

Dalje, Lex pretvara regularne izraze i akcije u generisani program nazvan yylex. Program yylex će prepoznati regularne izraze u ulaznom toku i izvršiti akcije za svako poklapanje sa zadatim pravilima.

Na primer, jednostavan leksički analizator bi mogao da prebroji reči na svom ulaznom toku:

int brojLinija = 0, brojReci = 0;

%%
\n      ++brojLinija;   
[A-Za-z]+   ++brojReci;
.      ;

%%
main() {
    yylex();
    printf("broj linija = %d, broj reci= %d\n", brojLinija, brojReci);
}

Programiranje lex programa

Lex kod se sastoji iz tri celine:

{definicija}
%%
{pravila}
%%
{potprogram}

Definicije namenjene lex-u se zadaju pre prvog %%. Početak sekcije definicija označava se sa %{ a kraj sa %}. Sekcija definicija može sadržati deklaracije lokalnih i globalnih promenljivih, include direktiva i definicija makroa. Sve što se ne nalazi između %{ i %} lex pokušava da definiše kao deklaraciju regularnih izraza. Sa leve strane se postavlja naziv regularnog izraza, a sa desne strane sam regularni izraz. Ime obavezno počinje slovom alfabeta iza koga sledi jedno ili više slova, cifara, donja crta ili gornja crta. Potprogram predstavlja korisnikove rutine, u kojima može učitavati karaktere iz fajla ili standardnog ulaza, ispisivati akcije u fajl ili standardni izlaz , ili prepisati neke funkcije lex-a.

Prvi %% označava početak sekcije pravila, dok je drugi opcioni. Apsolutni minimum Lex programa bi bio samo %%, gde bi se sve sa ulaznog toka preusmerilo na izlazni tok.

Pravila predstavljaju korisnikove kontrolne odluke. Unose se u tabelarnom obliku, gde leva kolona sadrži regularne izraze, dok desna sadrži akcije, tj. delove programa koji se izvršavaju kada se izraz pronađe u ulaznom toku. Razmak ili tab predstavljaju kraj regularnog izraza. Regularni izraz:

[A-Za-z]+     ++brojReci;

traži jedno ili više uzastopnih slova u ulaznom toku i uvećava promenljivu brojReci kad god se pravilo poklapa. Ukoliko akcija zahteva jedan C izraz, može se staviti sa desne strane pravila, a ako je potrebno više njih, onda bi ih trebalo postaviti ih između blok zagrada.

[A-Za-z]+    {
     printf(“Pronadjena rec”);
     brojReci++;
}

Definicija regularnih izraza je veoma slična QED (Quick Editor) regularnim izrazima. Regularni izraz specificira set stringova za poklapanje. Sadrži tekstualne karaktere i operatorske karaktere. Slova alfabeta i brojevi su uvek tekstualni karakteri. Operatorski karakteri su:

“ \ [ ] ^ - ? . * + | ( ) $ / { } % < >

i ako se i oni koriste kao tekstualni karakteri, potrebno je umetnuti i / pre njih. Sve što se nalazi između dva znaka navodnika (“) se uzima kao niz tekstualnih karaktera. Najčešća primena mehanizma navodnika je da se razmak doda u izraz.

Klase karaktera se mogu specificirati u paru []. Konstrukcija [abc] se podudara sa jednim karakterom, koji može biti a, b ili c. U velikim zagradama većina operatora ima ulogu tekstualnih karaktera, dok su samo tri specijalna: \, – i ^. Karakter – označava opseg. Primer:

[A-Za-z]

predstavlja klasu karaktera koja sadrži mala slova i velika slova.

Kada se regularni izraz poklopi, lex izvršava zadate akcije. Postoje uobičajene akcije, koje kopiraju sa ulaza na izlaz. One se izvršavaju na svim stringovima koji nisu poklopljeni sa zadatim regularnim izrazima. Najjednostavnija akcija je ignorisanje ulaza. Primer:

[ \t\n]  ;

koji će ignorisati razmak, tab i novi red. Ukoliko jedno pravilo izvršava istu akciju kao i sledeće, pomoću | se izbegava ponovno pisanje akcije. Na primer:

\n   |
.   f();

Ukoliko se poklopi prvo pravilo, izvršiće se ista akcija koja bi se izvršila za pravilo ispod njega. U većini slučajeva, korisnik želi da zna kako izgleda niz karaktera koji je poklopljen sa regularnim izrazom, pa se to može postići na sledeći način:

[A-Za-z]+    printf(“%s”, yytext);

Promenljiva yytext predstavlja referencu na niz karaktera koje je pravilo poklopilo. Ova akcija je veoma česta, pa se umesto nje može koristiti ECHO:

[A-Za-z]+    ECHO;

Dužina stringa koji se poklapa sa regularnim izrazom smeštena je u promenljivu yyleng.

U primeni lex-a sa yacc-om, yacc-u se na ulaz mogu proslediti tokeni. Na primer, ako imamo definisano pravilo

[a-zA-Z]     return(SLOVO);

za svako slovo iz ulaznog toka, lex će na izlaz proslediti token SLOVO.

Lex ume da rukuje sa višestrukim poklapanjima. Kada je više od jednog regularnog izraza poklopljeno, lex bira pravilo na sledeći način:

Pravilo koje je poklopilo najviše karaktera je pobednik.
Od svih poklopljenih pravila sa istim brojem karaktera, pobednik je prvo navedeno.

Hajde sada da postavimo pravila:

imiblog      slova();
[a-z]+      reg();

Ukoliko je ulaz „imiblogs“, prvo pravilo je poklopilo „imiblog“ (7 karaktera), a drugo pravilo celu reč (8 karaktera), pa će se izvršiti akcija reg(). Ukoliko je ulaz „imiblog“, i prvo i drugo pravilo će poklopiti 7 karaktera, ali pobednik će biti prvo pravilo, i izvršiće se funkcija slova().

Ponekad je korisno da sva pravila koja imaju poklapanje sa ulaznim tokom, izvrše svoju akciju. To se može učiniti pomoću akcije REJECT, koja označava da se prepušta izvršavanje sledeće alternative. Na primer, imamo sledeća pravila:

imi  i++;
imiblog ib++;
\n  |
.   ;

Ukoliko je na ulazu „imiblog”, prednost će uzeti drugo pravilo, zato što je poklopilo najviše karaktera. Promenljiva ibNakon izvršenja komandi, sledećom komandom dobijamo izvršni fajl:

$ gcc -o kalkulator lex.yy.c y.tab.c -lfl

Pokretanjem kalkulator izvršnog fajla startujemo kalkulator:

$ ./kalkulator 1+2 će se uvećati, ali promenljiva i neće. Na sledeći način bismo omogućili da se i pravilo imi poklopi kad god je to moguće:

imi  i++;
imiblog {ib++;REJECT;}
\n  |
.   ;

Yacc: yet another compiler compiler

Pošto smo naučili kako da ulazni tok razbijemo na tokene, sada je potreban način kako da prepoznamo šablone visokog nivoa. Ovde nastupa yacc, pomoću koga je moguće opisati šta zapravo želimo da uradimo sa tokenima.

Yacc pretvara gramatička pravila i akcije u generisani program nazvan yyparse. Program yyparse će prepoznati šablone u ulaznom toku i izvršiti akcije za svako poklapanje sa zadatim gramatičkim pravilima.

Ulazna specifikacija je kolekcija gramatičkih pravila. Svako pravilo opisuje dozvoljenu strukturu i zadaje joj ime. Na primer, jedno gramatičko pravilo bilo bi:

datum: dan ’.’ ’ ’  ime_meseca ’ ’ godina ’.’ ;

Ovde dan, ime_meseca i godina predstavljaju strukture od interesa u ulaznom procesu. Pretpostavimo da su oni definisani. Tačka „.“ je ograničena jednostrukim navodnicima, što označava da se tačka pojavljuje na ulazu, kao i razmak. Sa dobrom definicijom, ulaz „1. Jun 2017.“ bi bio poklopljen sa gore navedenim pravilom. Specifikacije su veoma fleksibilne. Veoma je jednostavno dodati novo pravilo:

datum: dan ’.’ mesec ’.’ godina ’.’ ;

omogućavajući „1.6.2017.“ kao sinonim za „1. Jun 2017.“ U većini slučajeva, novo pravilo se može dodati u radni sistem sa malim naporom, i sa minimalnom opasnošću da se poremeti već postojeći ulaz.

Za ulaz koji se čita postoji mogućnost da se neće poklapati sa specifikacijom. Nekada nam je potrebno da sprečimo obradu loših podataka, ili da nastavimo sa obradom ulaznog toka nakon preskakanja loših podataka.

Programiranje yacc programa

Kao što možete primetiti, i yacc struktura se sastoji iz tri celine:

{deklaracija}
%%
{pravila}
%%
{programi}

Sekcija deklaracije može biti prazna. Međutim, ako sekcija programa ne postoji, drugi %% nije potreban. Znači, najmanja yacc specifikacija izgleda ovako:

%%
{pravila}

Sekcija pravila je napravljena od jednog ili više gramatičkih pravila. Gramatičko pravilo je oblika:

PRAVILO: TELO_PRAVILA ;

PRAVILO predstavlja neterminalno ime, a TELO_PRAVILA predstavlja sekvencu od 0 ili više imena i znakova. Dve tačke i tačka-zarez su yacc-ove interpunkcije, dve tačke označavaju početak tela pravila, a tačka-zarez kraj pravila. Razmaci, tabovi i nove linije se ignoršu, ali se ne mogu uključiti u neko ime. Imena mogu biti proizvoljne dužine, napravljena od slova, tačke, donje crte i brojeva, s tim da prvi simbol mora biti slovo.

Ako postoji više gramatičkih pravila sa istom levom stranom, uspravnom crtom (|) se može zaobići ponovno pisanje leve strane. Tačka zarez se izbacuje pre uspravne crte. Na taj način pravila:

izraz:   izraz '+' izraz ;
izraz:  izraz '-' izraz ;

mogu biti zamenjena sa

izraz:
          izraz '+' izraz
        | izraz '-' izraz ;

Imena koja predstavljaju tokene moraju biti deklarisana, i to se može učiniti sa

%token PROMENLJIVA BROJ

u sekciji deklaracije. Svako ime koje nije definisano u sekciji deklaracije predstavlja neterminalni simbol. Svaki neterminalni simbol mora stajati sa leve strane bar jednog pravila.

Za svako gramatičko pravilo korisnik može dodati akciju koja treba da se izvrši svaki put kada se pravilo poklopi sa ulaznim procesom. Ove akcije mogu da vrate vrednost i mogu da zadrže vredosti koje su vratile prethodne akcije. Takođe, leksički analizator može vratiti vrednost za token, ako je to potrebno.

Akcije mogu biti ulaz, izlaz, poziv potprograma i izmena eksternih nizova i promenljivih. Bilo da je prisutan jedan ili više izraza, akcija se mora naći između vitičastih zagrada.

Da bi se olakšala komunikacija između parsera i akcija, potrebno je malo izmeniti akciju. Da bi pravilo vratilo vrednost, akcija postavlja pseudopromenljivu $$ na neku vrednost. Na primer, akcija koja ima povratnu vrednost 1 je

{ $$ = 1 ; }

Da bi se koristila povratna vrednost prethodnih akcija i leksičkog analizatora, akcije mogu koristiti pseudopromenljive $1, $2, … koje su povezane sa povratnim vrednostima komponenti sa desne strane pravila, redom sleva na desno. Na taj način, na primer, ako je pravilo:

A    :   B C D   ;

povratnoj vrednosti akcije pravila C bismo pristupili sa $2, a $3 bi bila povratna vrednost D.

Korisnik može da definiše i ostale promenljive koje se mogu koristiti u akcijama. Deklaraciju i definiciju je moguće napraviti u sekciji deklaracije, između %{ i %}. Ove deklaracije i defincije su globalne, tako da im mogu pristupiti akcije i leksički analizator. Funkcija leksičkog analizatora yylex ima povratni tip integer, čija vrednost označava broj tokena. Ako je potrebno asocirati i vrednost sa tokenom, neophodno je deklarisati eksternu promenljivu yylval. Podrazumevani tip yylval je integer. Ukoliko se tipovi podataka koji se šalju iz lex-a u yacc razlikuju, potrebno je deklarisati uniju vrednosti koju promenljiva yylval koristi, a to se može postići na sledeći način:

%union {
    int    vrednost;
    char  tekst;
}
%token     BROJ
%type  komentar

gde token BROJ može imati vrednost vrednost iz unije, a neterminalni simbol komentar može imati vrednost tekst.

Ako se yacc poziva sa opcijom -d, deklaracija unije kopira se u y.tab.h kao yystype. Kada je definisano yystype, imena članova unije moraju biti pridružena imenima terminala i neterminala.

Kada kažemo da su gramatička pravila dvosmislena, to znači da ulazni string može biti strukturiran na dva ili više različitih načina. Na primer, pravilo:

izraz :  izraz ’-’ izraz ;

je prirodni način izraziti činjenicu da je jedan način formiranja aritmetičkog izraza da se stave dva druga izraza zajedno sa minusom između njih. Nažalost, ovo gramatičko pravilo ne specificira kompletno način na koji se mogu svi kompleksni ulazi strukturirati. Na primer, ako je ulaz izraz – izraz – izraz pravilo može biti struktuirano kao (izraz – izraz) – izraz ili kao izraz – (izraz – izraz). Da bi se rešio ovaj probem, uvode se pravila prednosti zajedno sa informacijama o levoj i desnoj asocijativnosti. Za označavanje asocijativnosti uvode se oznake %left i %right. Iza navedenih ključnih reči sledi lista tokena. Svi tokeni koji se nalaze u istom redu imaju istu prednost i asocijativnost. Ova podešavanje je potrebno uneti u sekciji deklaracije.

%left ’+’ ’-’
%left ’*’ ’/’

Prvo deklarisano podešavanje ima najmanji prioritet, dok svako sledeće ima veći prioritet od prethodnog. Ukoliko je potrebno da se promeni prednost, koristi se %prec. Na primer, pravilo

izraz : ’-’ izraz %prec ’*’

specificira da unarni minus ima istu prednost kao i operacije množenja.

Obrada grešaka

Obrada grešaka je veoma komplikovano područje, i većina grešaka je semantičke prirode. Prihvatljivo je da se prekinu svi dalji procesi kada se pronađe greška, ali bi bilo korisnije da se nastavi sa skeniranjem ulaza, kako bi se našle i ostale sintaksne greške. Da bismo to omogućili, potrebno je „restartovati“ parser.

Yacc nam pruža token error, rezervisan za obradu grešaka. Ovo ime se može koristiti u gramatičkim pravilima, na mestima gde mogu da se jave greške, kako bi oporavak bio moguć. Parser uzima tokene sa steka sve dok ne dođe do stanja kada je token error važeći. Ukoliko je token error sledeći token, on obavlja akciju koja je zadata. Sledeći token se onda resetuje na token koji je napravio grešku. Ako nema specijalnih pravila za greške, proces se zaustavlja kada se pronađe greška.

Ukoliko se ne poklopi ni jedno pravilo, yacc poziva rutinu yyerror.

Primer: Kalkulator

Hajde sada da napravimo jednostavan kalkulator. Kalkulator će funkcionisati tako što ćemo zadavati izraze preko komandne linije, koje će lex razbijati na tokene i prosleđivati yacc-u, gde će yacc prepoznavati šablone visokog nivoa, izračunavati vrednosti izraza i štampati na standardni izlaz.

Sledeći kod predstavlja lex ulaznu specifikaciju:

%{
    #include 
    #include 
    #include "y.tab.h"
%}
%%
[a-z] {yylval = yytext[0]- 'a'; 
return PROMENLJIVA;}
[0-9]+  { yylval = atoi(yytext); 
      return BROJ;}
[-+()=/*\n] {return yytext[0];}
[ \t]   ;
.   {return yytext[0];}
%%

Leksički analizator šalje yacc-u tokene PROMENLJIVA i BROJ. Promenljiva yylval nam služi da prosledimo yacc-u koju promenljivu i broj smo učitali. Sledeći kod predstavlja yacc ulaznu specifikaciju:

%token BROJ PROMENLJIVA
%left '+' '-'
%left '*' '/'

%{
    #include 
    void yyerror(char *);
    int yylex(void);
    int sym[26];
%}

%%

program:
        program iskaz '\n'
        | 
        ;

iskaz:
        izraz                      { printf("%d\n", $1); }
        | PROMENLJIVA '=' izraz    { sym[$1] = $3; }
        ;

izraz:
        BROJ
        | PROMENLJIVA               { $$ = sym[$1]; }
        | izraz '+' izraz           { $$ = $1 + $3; }
        | izraz '-' izraz           { $$ = $1 - $3; }
        | izraz '*' izraz           { $$ = $1 * $3; }
        | izraz '/' izraz           { $$ = $1 / $3; }
        | '(' izraz ')'             { $$ = $2; }
        ;

%%

void yyerror(char *s) {
    printf("%s\n", s);
}

int main(void) {
    int i;
    for(i = 0; i < 26; i++)
    sym[i]=0;
    yyparse();
    return 0;
}

Izvorne fajlove možete pronaći na sledećem linku, kao i sled komandi koje je potrebno izvršiti kako bi pokrenuli kalkulator. Evo kako funkcioniše:

$ lex kalkulator.l $ yacc -d kalkulator.y

Nakon izvršenja komandi, sledećom komandom dobijamo izvršni fajl:

$ gcc -o kalkulator lex.yy.c y.tab.c -lfl

Pokretanjem kalkulator izvršnog fajla startujemo kalkulator:

$ ./kalkulator 1+2 3 5+8 13 (2+3)*5 25

Zaključak

U ovom članku smo objasnili šta je to lex, a šta yacc, kako se mogu instalirati na različitim operativnim sistemima i kako programirati i pokrenuti lex i yacc programe. Da ponovimo, lex pomoću zadatih regularnih izraza deli ulazni tok na delove, dok yacc, za zadata gramatička pravila, te delove koristi kako bi našao šablone visokog nivoa. Ova dva alata se najčešće koriste kako bi parsirali tekst, i time izvukli neku semantiku ili utvrdili ispravnost teksta.

Ukoliko želite detaljnije da se upoznate sa programiranjem u lex-u i yacc-u, kompletan tutorijal možete pronaći na sledećem linku http://dinosaur.compilertools.net/.

Literatura

Autor: Mateja Ašanin

Student master studija na Prirodno-matematičkom fakultetu u Kragujevcu, softverski inženjer u SmartCat.

Osnovne akademske studije završio sam na Prirodno-matematičkom fakultetu u Kragujevcu 2018. godine, smer Informatika. Tokom studija bio sam polaznik programa praksi u kompanijama Emisia Consulting, Comtrade SE, Technomedia doo i Levi9 IT Services. Školske 2018/19 radio sam kao asistent na fakultetu, na predmetima Operativni Sistemi 2, Klijentske Web Tehnologije i Softverski Inženjering. Od jula 2019. do jula 2020. radio sam kako Java Developer u Levi9 IT Services.

Facebook | Linkedin | Github