3. Bison

Bison generuje zdrojový program v jazyce C - tak zvaný parser, který provádí syntaktickou analýzu vstupu podle vámi specifikované gramatiky jazyka.

%{
   Deklarace v jazyce C
%}

   Deklarace pro bison
%%

   pravidla gramatiky
%%

   libovolný C kód

Naštěstí se autoři nesnažili přijít se zcela novým a originálním řešením, a jak sami vidíte, uspořádání souboru specifikujícího pravidla gramatiky je velmi podobné uspořádání souboru pro flex. Jelikož jsou základní postupy podobné, můžeme se nyní věnovat poněkud systematičtějšímu výkladu.

3.1 Gramatika

V tomto odstavci bych rád vyložil zjednodušené základy gramatik. Jak jsem slíbil v úvodu, nebudeme se potápět do hlubin této teorie, spíš se pouze lehce namočíme, tudíž zdatní plavci mohou tento paragraf přeskočit.

Každá gramatika se skládá ze dvou druhů symbolů: z terminálů (též tokenů) a non-terminálů. Dále gramatiku určují tak zvaná přepisovací pravidla a počáteční non-terminál.

Přepisovací pravidla určují, jak nahradit non-terminál posloupností non-terminálů a terminálů (terminály - již podle jména - nelze dále přepisovat). V Bisonu se pravidla zapisují v tak zvané Backus-Naur Formě (zkráceně BNF), non-terminály tradičně zapisujeme malými písmeny, terminály velkými (navíc Bison umožňuje zapsat jednoznakové terminály jako znaky v jazyce C - uvozené do apostrofů).

Raději než zdlouhavým slovním popisem, předvedeme si BNF v krátkém příkladu demonstrujícím popis jednoduchých matematických výrazů ...

Příklad 6.
Terminály:			ČÍSLO, '+', '(', ')', '-', '*', '/'
Non-terminály:			start, výraz
Počáteční non-terminál:		start

start:
	výraz
;

výraz:
	ČÍSLO
      | '(' výraz ')'
      | výraz '+' výraz
      | výraz '-' výraz
      | výraz '*' výraz
      | výraz '/' výraz
;




 1 
   
   
   
 2 
 3 
 4 
 5 
 6 
 7 

... a způsob, kterým z pravidel výrazy vznikají:

Příklad 7.
start
výraz
výraz * výraz
výraz * ( výraz )
výraz * ( výraz + výraz )
výraz * ( 10 + výraz )
výraz * ( 10 + 20 )
( výraz ) * ( 10 + 20 )
( výraz - výraz )  * ( 10 + 20 )
( výraz - 4 )  * ( 10 + 20 )
( 15 - 4 )  * ( 10 + 20 )

 1 
 6 
 3 
 4 
 2 
 2 
 3 
 5 
 2 
 2 

Každý matematický výraz náležející do jazyka, který popisuje výše uvedená gramatika, lze zkonstruovat následujícím způsobem. Začneme symbolem (non-terminálem) start a postupně aplikujeme různá přepisovací pravidla na non-terminály, dokud nedostaneme text složený pouze z terminálů.

Parser vygenerovaný programem bison pracuje v jistém smyslu obráceně. Snaží se tokeny (terminály) ze vstupního souboru spojovat do non-terminálů... až by nakonec měl dojít k počátečnímu non-terminálu.

Rozlišujeme více druhů jazyků s rozličnými vlastnostmi. Má-li bison vygenerovat parser pro daný jazyk, je třeba, aby jazyk splňoval určitá kriteria - musí se jednat o LALR(1) bezkontextový jazyk (context-free language). Naštěstí jazyky generované gramatikami v BNF jsou bezkontextové, LALR(1) znamená (zjednodušeně), že text je možné parsovat pouze s pohledem o jeden token dopředu.

3.2 Sémantická hodnota

Jistě jste si všimli, že v sedmém příkladu jsem lehce podváděl. Přestože jsem v pravidlech gramatiky uvedl jako terminály pouze operátory a token ČÍSLO, v odvozování jsem použil čísla konkrétní. Každý token (a též každý non-terminál) může totiž mít svoji sémantickou hodnotu. V příkladu 7 měl token ČÍSLO hodnoty 15, 4, 10 a 20.

Bison vám samozřejmě umožní přiřadit ke každému terminálu i non-terminálu hodnotu, dokonce si můžete zvolit typ (ve smyslu typu v jazyce C) takové hodnoty. Typ hodnoty reprezentuje makro YYSTYPE a v první části souboru jej lze změnit dvěma způsoby:

%{
#define YYSTYPE double
%}

%%

Často není jednoduchý typ dostatečný pro komplikovanější parsery. Mocnější druhý způsob umožňuje deklarovat YYSTYPE jako union několika typů a později u jednotlivých terminálů a non-terminálů specifikovat, jakého typu je jejich hodnota:

%union {
  int		 ivalue;
  char		*svalue;
}

%%

3.3 Deklarace tokenů

Každé jméno tokenu je vnitřně reprezentováno jako číslo - integer (jednoznakové tokeny již čísla mají - například '+'), všechna jména tokenů je nutné v první části souboru deklarovat, aby bylo možné jim tato čísla přiřadit. Můžeme tak například učinit pomocí slova %token:


%token ČÍSLO

	/* pokud jsme použili %union, můžeme též určit 
	 * typ hodnoty daného tokenu. 
	 *
         * Například v následujícím příkladu je každý
	 * token STRING doprovázen hodnotou typu char* 
	 */

%token <svalue> STRING

Tokeny operátorů mohou být též zleva či zprava asociativní - pak místo konstrukce %token můžeme použít:

%left 		'+', '-'
%left 		'*', '/' '%'
%right 		'^'
%nonassoc	'@'
(a + b + c) == ((a + b) + c)

(a ^ b ^ c) == (a ^ (b ^ c))
(a @ b @ c) je chyba

V tomto příkladu též pořadí operátorů určilo jejich prioritu. Nejvyšší prioritu má operátor '@', následovaný umocněním '^',... - čím je operátor uveden v souboru dříve, tím nižší má prioritu.

Non-terminály není třeba deklarovat - pokud však chceme explicitně určit typ jejich hodnoty, můžeme tak učinit pomocí příkazu type. Lze též určit, který non-terminál bude počáteční (implicitně první mezi pravidly v druhé části):

%type <ivalue> výraz

%start start

3.4 Pravidla a akce

Jak jsem již napsal výše, pravidla gramatiky začínají jménem non-terminálu, který přepisujeme, následovaný dvojtečkou. Za ní uvedeme jednotlivé komponenty pravidla - posloupnost terminálů a non-terminálů, kterými non-terminál "přepisujeme" (mluvíme-li o pravidlech gramatiky jako o přepisovacích pravidlech) - či které do non-terminálu "sdružujeme" (díváme-li se z pohledu parseru, jenž sdružuje terminály a non-terminály do větších celků).

Za seznamem komponent následuje akce, kterou parser spustí, pokud se mu podaří aplikovat toto pravidlo. Na rozdíl od nástroje flex, v bisonu se musí všechny akce obalit složenými závorkami, na druhou stranu není třeba psát pravidla na jeden řádek - je možné je rozepsat na víc řádek.

Celé pravidlo zakončíme středníkem. Pokud se je možné non-terminál přepsat podle více pravidel, lze tato pravidla sdružit a oddělit znakem '|'. Následující dva zápisy jsou ekvivalentní:


statement: RETURN expr ';'
		{ zpracuj_return (); }
;

statement: IDENTIFIER '=' expr ';'
		{ zpracuj_přiřazení (); }
;

statement: 
   RETURN expr ';' { zpracuj_return (); }
 | IDENTIFIER '=' expr ';' 
		{ zpracuj_přiřazení (); }
;

Pokud používáme pro typ hodnoty symbolu jednoduchý typ a nebo jsme deklarovali pro symbol jeden z typů uvedených v konstrukci %union{}, můžeme v akci pracovat též s hodnotami symbolů - terminálů i non-terminálů. V kódu akce můžeme navíc kromě běžných konstrukcí jazyka C navíc použít proměnné $N a $$, které reprezentují hodnotu N-té komponenty pravidla, respektive výsledku pravidla:

%{
#define YYSTYPE	double
%}

...

%%

...

výraz:
	  výraz '+' výraz	{ $$ = $1 + $3; }
	| výraz '-' výraz	{ $$ = $1 - $3; }
	| SIN '(' výraz ')'	{ $$ = sin ($3); }

...

$$ i $N mají typ odpovídající typu deklarovanému pro daný symbol. Na vlastní nebezpečí můžeme typ předefinovat a přiřadit například do celého čísla řetězec (krajní případ: $<svalue>$ = "Ahoj" + 2 * $<ivalue>1).

Jistě jste si všimli, že pravidla gramatiky bývají často rekursivní - už náš jednoduchý příklad matematických výrazů takový byl. Rekurse může být někdy ošemetná a způsob, kterým ji zapíšete, bude mít vliv na rychlost a paměťové nároky vygenerovaného parseru:

Levá rekurse.
expression_list:
	  expression
	| expression_list ',' expression
Pravá rekurse.
expression_list:
	  expression
	| expression ',' expression_list

Přestože jsou obě definice listu výrazu ekvivalentní, parser pro pravou rekursi bude paměťově mnohem náročnější, neboť aby bylo pravidlo alespoň jednou aplikováno, musí být (na rozdíl od levé rekurse) všechna data vázající se ke všem non-terminálům typu expression v paměti.

Poslední věcí, kterou bych v souvislosti s akcemi rád zmínil, jsou akce uprostřed pravidla - mid-rule actions:

statement:
	LET '(' variable ')'
	  { deklaruj_proměnnou ($3) }
	statement
	  { $$ = $6; zruš_proměnnou ($3); }

[Obsah] [Předchozí kapitola: Flex] [Následující kapitola: Propojení]


© 1999 0rfelyus Emacs