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 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čí:
\
"
.
"
*
"
+
"
[]
"
-
". 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í.
-x
"
a "(x)
" výrazy.
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.
Několik dalších příkladů najdete v anglické dokumentaci dodávané s programem.