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.
A zde je slíbený rozpoznávač čísel a operátorů:


%{
#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

Nyní je čas porozumět vlastnímu výrazu. To už není práce programu flex a přichází na řadu Bison. Ten umožňuje popsat jazyk, který chceme rozpoznat v podobě jednoduchého stroje na generování všech možných vstupů (výrazů). Nejlépe to bude asi jasné na našem příkladu. Výraz lze popsat pomocí následujících pravidel:

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í:

Tyto přepisy jsou pouze jinak zapsaná pravidla. Písmeno "E" zde znamená výraz a písmeno "N" libovolné číslo. Stroj pak začíná s jedním písmenem "E" a provádí změny náhodně dokud se nějaká "E" v řetězci vyskytují. Tak mohou vzniknou všechny výrazy.

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.