Bison a flex

God made machine language; all the rest is the work of man.

-- zdroj neznßm²

Programy Bison a Flex jsou neoceniteln²m pomocnφkem ka╛dΘho programßtora, kter² pot°ebuje n∞jak²m zp∙sobem zpracovßvat text. Dokß╛φ vygenerovat funkce v C pro velkΘ mno╛stvφ problΘm∙ od jednoduch²ch filtr∙ pro ·pravu textu a Φtenφ jednoduch²ch konfiguraΦnφch soubor∙, p°es kalkulaΦky a interprety makrojazyk∙ a╛ po rozpoznßvaΦe slo╛it²ch programovacφch jazyk∙ jako je C++. Nejsiln∞j╣φ jsou, pokud pracujφ dohromady, ale v n∞kter²ch p°φpadech mß smysl je pou╛φvat i odd∞len∞.

Jejich kompletnφ popis by byl dlouh² (a najdete jej v dokumentaci dodßvanΘ s programem) a proto jsem se rozhodl pouze demonstrovat jejich mo╛nosti na jednoduchΘm problΘmu a to je vyhodnocovaΦ v²raz∙ s up°ednost≥ovßnφm. Tedy program, kter² pro vstup 2 + 3 * 3 odpovφ 11.

flex

Flex generuje programy, kterΘ dokß╛φ ve svΘm vstupu rozpoznat urΦitΘ "obrazce". T∞mito obrazci mohou b²t klφΦovß slova programu, Φφslice, nebo podobnΘ jednoduchΘ Φßsti textu.

V na╣em p°φpad∞ bude ·kolem flexu vyrobit funkci p°evßd∞jφcφ vstupnφ °et∞zec (1 + 120/9*5) na informaci: LEVA_ZAVORKA CISLO(1) PLUS CISLO(120) LOMENO CISLO(9) KRAT CISLO(5) PRAVA_ZAVORKA. Takovou informaci je mnohem jednodu╣╣φ zpracovat a vyu╛ije ji funkce vygenerovanß programem Bison.

Vstupem pro flex je jednoduch² popis v nßsledujφcφm formßtu:

	%{·vodnφ k≤d v jazyce C, kter² se zkopφruje do v²stupu%} zkratky %% pravidla %% koncov² k≤d v jazyce C, kter² se zkopφruje do v²stupu

P°iΦem╛ v╣echny Φßsti vyjma prost°ednφ jsou nepovinnΘ.

Nejd∙le╛it∞j╣φ jsou pravidla. Ty se sklßdajφ ze dvou Φßstφ. Prvnφ je vzor popisujφcφ, co se mß hledat, a druhß Φßst je k≤d v jazyce C, kter² se provede pokud se v²raz najde. Vzorem m∙╛e b²t hledan² °et∞zec a proto nap°φklad nßsledujφcφ program bude vyhledßvat slovo "ahoj" a nahrazovat jej slovem "nazdar":

	%% ahoj printf("nazdar");

Po kompilaci programem flex:

	flex test.f

dostaneme v²stupnφ soubor jmΘnem lex.yy.c, kter² je funkΦnφ program v jazyce C a staΦφ jej jen zkompilovat a slinkovat se specißlnφ knihovnou fl:

	gcc -O2 lex.yy.c -lfl

V²sledn² program se jmenuje "a.exe" (v UnixovΘm sv∞t∞ "a.out") a po spu╣t∞nφ bude Φekat na vstup a ten kopφrovat na v²stup s nahrazen²m "ahoj" za "nazdar".

Hlavnφ sφla flexu spoΦφvß v tom, ╛e nemusφte za vzor psßt pouze jednoduch² °et∞zec, ale pou╛φvßte tzv. regulßrnφ v²razy (se kter²mi se setkßte i v mnoha jin²ch GNU programech), kde n∞kterß pφsmena majφ specißlnφ v²znam. Takov²ch specißlnφch v²znam∙ je mnoho, ale pro na╣e ·Φely postaΦφ:

"\"

Ru╣φ specißlnφ v²znam nßsledujφcφho znaku

"."

Libovoln² znak

"*"

P°edchozφ znak se m∙╛e nula a vφce-krßt opakovat

"+"

P°edchozφ znak se m∙╛e jednou a vφce-krßt opakovat

"[]"

V hranat²ch zßvorkßch lze vyjmenovat jednotlivΘ znaky, kterΘ mohou b²t na danΘ pozici v °et∞zci. Lze napsat i interval pomocφ znaku "-". Tedy nap°φklad "[0-9]" znamenß libovolnou Φφslici a "[abc]" prvnφ t°i pφsmena abecedy.

	%{ #include <math.h> #include <stdio.h> #define YYSTYPE double #include "bison.tab.h" %} %% [0-9]+\.*[0-9]* { /* Desetinnß Φφsla */ yylval=atof(yytext); return NUM; } [-+*/^()\n] { /* Operßtory, zßvorky a konec °ßdky majφ specißlnφ v²znam */ return yytext[0]; } [ \t]* { /* Mezery se a tabulßtor vynechßvajφ. */ } . { fprintf (stderr,"Nepovolen² znak '%s'. Ignoruji\n",yytext); /* V╣e ostatnφ je chyba ve vstupu. */ } %%

V²sledkem na╣eho sna╛enφ je nynφ funkce jmΘnem yylex (jmΘno funkce lze samoz°ejm∞ zm∞nit dle libosti). Vlastnφ funkce main se u╛ nevygeneruje, proto╛e program obsahuje poslednφ %% a flex tedy nepou╛ije svoji standardnφ ukonΦovacφ sekci.

Funkce nynφ po zavolßnφ p°eΦte Φßst standardnφho vstupu (toto je takΘ pouze standardnφ volba a flex nßm umo╛≥uje nadefinovat funkci, kterß Φtenφ provßdφ). Pokud v tΘto Φßsti rozpoznß Φφslo, vrßtφ konstantu NUM a hodnotu prom∞nnΘ yyval nastavφ na p°eΦtenΘ Φφslo. Pokud najde operßtor, vrßtφ p°φmo hodnotu znaku a jinak vypφ╣e chybovΘ hlß╣enφ.

Bison

• ╚φslo je v²raz
• Je-li x v²raz, jsou i "-x" a "(x)" v²razy.
• Jsou-li x a y v²razy, jsou v²razy i "x+y", "x-y", "x*y", "x/y" a "x^y" v²razy.

Tyto pravidla jdou snadno p°epsat do stroje pracujφcφho s °et∞zcem pφsmen, kter² v ka╛dΘm kroku provßdφ jedno z nßsledujφcφch nahrazenφ:

• "E" -> "N"
• "E" -> "-E"
• "E" -> "(E)"
• "E" -> "E+E"
• "E" -> "E-E"
• "E" -> "E*E"
• "E" -> "E/E"
• "E" -> "E^E"

Nap°φklad v²raz "(N+N/N)" vznikne takto:

	E (poΦßteΦnφ stav) (E) (pravidlo E -> (E)) (E+E) (pravidlo E -> E+E) (E+E/E) (pravidlo E -> E/E) (N+E/E) (pravidlo E -> N) (N+N/E) (pravidlo E -> N) (N+N/N) (pravidlo E -> N)

V╣imn∞te si, ╛e pokud provedete postup odzadu a poka╛dΘ budete urΦovat hodnotu vzniklΘho pφsmena, vyhodnotφte tak cel² v²raz. To je p°esn∞ princip funkce Bisona. Pravidla p°epsanß do jeho jazyka vypadajφ takto:

	exp: NUM { $$ = $1; } exp: exp '+' exp { $$ = $1 + $3; } exp: exp '-' exp { $$ = $1 - $3; } exp: exp '*' exp { $$ = $1 * $3; } exp: exp '/' exp { $$ = $1 / $3; } exp: '-' exp { $$ = -$2; } exp: exp '^' exp { $$ = pow ($1, $3); } exp: '(' exp ')' { $$ = $2; }

Kde "exp" mß funkci pφsmene E a ":" ╣ipky. Ve slo╛en²ch zßvorkßch je k≤d v jazyce C, kter² urΦuje, jak poΦφtat hodnotu celkovΘho v²razu pomocφ hodnot jeho podv²raz∙.

Celkov² program musφ je╣t∞ urΦit n∞kolik dal╣φch v∞cφ. Nap°φklad prioritu operßtor∙ a jejich asociativitu (jestli 1+2+3 znamenß (1+2)+3, nebo 1+(2+3)). Kompletnφ rozpoznßvaΦ v²raz∙ vypadß takto:

	%{ #include <math.h> #include <stdio.h> /* Typ hodnoty v²razu */ #define YYSTYPE double int yyerror (char *); %} /* Deklarace. Priorita operßtor∙ je urΦena jejich po°adφm. Asociativita pomocφ slov "left" a "right" */ %token NUM %left '-' '+' %left '*' '/' %left NEG /* unßrnφ mφnus */ %right '^' /* mocn∞nφ */ /* Gramatika */ %% /* Toto je trik jak vyjßd°it, ╛e vstup se sklßdß z libovolnΘho mno╛stvφ °ßdek. */ input: /* prßzdn² °etezec */ input: input line ; /* ╪ßdka je bu∩ prßzdnß, nebo obsahuje v²raz. */ line: '\n' line: exp '\n' { printf ("\t%.10g\n", $1); } ; exp: NUM { $$ = $1; } exp: exp '+' exp { $$ = $1 + $3; } exp: exp '-' exp { $$ = $1 - $3; } exp: exp '*' exp { $$ = $1 * $3; } exp: exp '/' exp { $$ = $1 / $3; } exp: '-' exp %prec NEG { $$ = -$2; } exp: exp '^' exp { $$ = pow ($1, $3); } exp: '(' exp ')' { $$ = $2; } ; %% /* Funkce se zavolß v p°φpad∞ chyby. */ int yyerror (s) char *s; { fputs (s, stderr); return 1; } /* V²sledkem je funkce yyparse, kterou musφme zavolat. */ void main (int argc, char **argv) { yyparse (); return 0; }

Nynφ staΦφ program p°elo╛it:

	bison -d bison.y (vytvo°φ soubor bison.tab.h s hodnotou konstanty NUM) flex flex.f bison bison.y gcc lex.yy.c bison.tab.c -lm -lfl

A zjistφte, ╛e dokß╛e p∞kn∞ poΦφtat. Pokud srovnßte dΘlku tohoto programu s b∞╛n²m programem na vyhodnocovßnφ v²raz∙, asi budete p°φjemn∞ p°ekvapeni. Navφc roz╣φ°enφ tohoto programu o dal╣φ vymo╛enosti (prom∞nnΘ, funkce apod.), je u╛ otßzkou n∞kolika mßlo dal╣φch °ßdek.