ADE: Bison 1.25

Jak jste poznali z článku předchozího čísla, program Flex je určený pro rozpoznávání jednotlivých symbolů (většinou slov) ve vstupu. Tato slova často tvoří ještě nějakou konstrukci a tu je schopna identifikovat rutina, kterou si snadno vytvoříte pomocí programu Bison.

Bison je generátorem obecně použitelných parserů; Bison konvertuje popis LALR(1) gramatiky do zdrojového kódu v jazyce C, který je schopen popsanou gramatiku rozparsovat. Programátoři zkušení s používáním Bisona jsou schopni snadno vyvíjet širokou škálu parserů různých jazyků, počínaje jednoduchou kalkulačkou a konče složitými programovacími jazyky.
Aby byl Bison schopen vygenerovat parser rozpoznávající požadovaný jazyk, je potřeba tento jazyk popsat tzv. bezkontextovou gramatikou. To stručně znamená, že je potřeba specifikovat jedno nebo více uskupení jazykových prvků podle syntaxe jazyka a definování pravidel pro jejich konstrukci z různých částí. Například v programovacím jazyce C se jedno z takovýchto uskupení nazývá „výraz“. Jedním z pravidel pro konstrukci je „výraz může být složen ze znaménka minus následovaného jiným výrazem“; dalším může být „výraz může být integerovým číslem“. Jak vidíte, pravidla mohou být rekurzivní, ale musí existovat alespoň jedno pravidlo, které rekurz ukončuje.
Ne všechny jazyky umí Bison rozpoznat - vstupem Bisona je jakási gramatika popisující jazyk a Bison umí rozpoznat pouze LALR(1) gramatiky. Stručně vysvětleno to znamená, že musí být jasné, jak zpracovávat další část vstupu již podle prvního tokenu na vstupu (toto pravidlo je opět rekurzivní). Tato definice je obecným popisem LR(1) gramatik, LALR(1) gramatiky přidávají další omezení, která není jednoduché stručně popsat; v praxi se ovšem gramatiky, které jsou LR(1) a nejsou LALR(1) vyskytují velice zřídka.
V gramatickém popisu jazyka se každá syntaktická jednotka nebo seskupení nazve symbolem. Symboly, které jsou tvořeny seskupením menších konstruktů podle pravidel gramatiky, se nazývají neterminální symboly (např.: výraz). Symboly, které již není možné dělit, jsou pak nazývány terminálními symboly (např.: znaménko minus nebo integerové číslo). V Bisonu se terminálním symbolům říká tokeny a neterminálním seskupení.
Pro každé seskupení musí gramatika uvést pravidlo, jak ho složit z jednodušších konstruktů. Například jednou z konstrukcí jazyka C je „return“ konstrukce. Gramatika to popíše takto: „konstrukce“ může být složena z klíčového slova „return“, z „výrazu“ a „středníku“. V tomto pravidle jsou klíčové slovo „return“ a terminátor „středník“ tokeny, kdežto „výraz“ je jiným seskupením. V gramatice bude existovat pochopitelně více pravidel pro seskupení „konstrukce“.
Jedno seskupení musí být označeno jako speciální a musí definovat komplexní strukturu jazyka. Toto seskupení bývá nazýváno startovacím symbolem. Například v jazyce C je takovýmto symbolem „seznam definic a deklarací“.
Parser vygenerovaný Bisonem čte sekvenci tokenů ze vstupu a tyto tokeny pak spojuje do seskupení podle zadaných pravidel. Pokud je vstup v pořádku, musí nakonec dojít ke seskupení do startovacího symbolu; pokud tomu tak není, parser nahlásí syntaktickou chybu.
Nyní se podívejme na to, jak je gramatika v Bisonu popsána. Každý neterminální symbol (seskupení) je popsán identifikátorem; konvence doporučuje pro seskupení používat malá písmena. Takže jako identifikátory bychom mohli mít „výraz“, „deklarace“ apod.
Terminální symboly (tokeny) jsou v Bisonu také popsány identifikátory a pro snadné odlišení od seskupení se používají velká písmena. Například tedy „INTEGER“, „IF“ nebo „RETURN“. Terminální symbol „error“ je rezervován pro zadání pravidla ošetřujícího chybu. Tokeny mohou být také reprezentovány znakem, což bývá použito pro veškeré jednoznakové tokeny (znak vyjadřující token v jazyce ho zároveň popisuje v gramatice; příkladem mohou být závorky či znaménko plus). Poslední možností je popsat token standardním řetězcem jazyka C.
Pravidla gramatiky je nutné ve vstupu Bisona specifikovat. Zde je příklad pravidla, které vyjadřuje return konstrukci jazyka C. Středník uzavřený do apostrofů reprezentuje token pravidla, kdežto „nahý“ středník ukončuje definici pravidla.

konstrukce: RETURN výraz ;
;

Dané seskupení může mít více pravidel - ta je pak možné specifikovat odděleně, nebo je vyjádřit v jednom pravidle pomocí znaku |. Do zápisu pravidla je také možné uvést kód v jazyce C, který bude vykonán, když je dané pravidlo rozpoznáno; tento kód je v zápise uzavřen do složených závorek a většinou slouží k výpočtu nějaké sémantické hodnoty. K danému pravidlu většinou bývá uveden jeden kód až za pravidlem, je však možné kód uvést vícekrát do jakéhokoliv místa popisu pravidla, tento kód je pak proveden v momentu, kdy je rozpoznána část pravidla předcházející tomuto kódu.
Sémantické hodnoty pravidla jsou většinou počítány z sémantických hodnot prvků, z kterého je seskupení tvořeno. Sémantická hodnota n-tého prvku pravidla se specifikuje znakem $ a číslem tohoto prvku, hodnota celého pravidla pak dvojznakem $$. Pokud je kód vložen doprostřed pravidla, je možné použít pouze sémantické hodnoty prvků vlevo od kódu. Uveďme si příklad: v jednoduché kalkulačce by mohlo pravidlo vypadat takto:

výraz: výraz + výraz
{$$=$1+$3}
;

Bison tedy funguje tak, že načte nějakou specifikaci gramatiky a vygeneruje požadovaný parser. Specifikace gramatiky je pochopitelně uložena v souboru a má podobnou formu jako specifikace lexikálních symbolů u programu Flex. První část tvoří deklarace Bisona, kde deklarujeme tokeny a seskupení a některé další údaje. Mezi ty mohou patřit priority později použité u pravidel (lze například zadat, že pravidlo vyjadřující násobení bude mít vyšší prioritu než pravidlo vyjadřující sčítání a tedy násobení bude vypočítáno dříve), asociativitu (zda se má pravidlo vyhodnocovat zleva nebo zprava např. zleva se vyhodnocuje v céčku sčítání, kdežto zprava se vyhodnocuje operátor přiřazení). Dále je zde možné deklarovat například typ použitý pro výpočet sémantických hodnot apod.
Další část odděluje dvojznak %% a za ním jsou uvedena pravidla spolu s akcemi. Musí být zadefinováno alespoň jedno pravidlo (startovní pravidlo). Třetí nepovinná část je opět oddělena dvojznakem %% a za ním je možno uvést libovolný kód v jazyce C, který bude překopírován do výsledného sou boru. Kód v jazyce C je také možné uvést do částí s deklaracemi, je ho však nutné uzavřít do dvojice dvojznaků %{ a %}. Tento kód je pak umístěn před funkci realizující parser a je do něho např. vhodné uvést hlavičky funkcí z kódu za funkcí, pokud jsou z funkce realizující parser volány.
Parser vygenerovaný Bisonem pak funguje následujícím způsobem: ve vygenerovaném souboru pro jazyk C je funkce yyparse(), která realizuje parser. Tato funkce pravidelně volá jinou funkci realizující lexikální scanner a podle lexikálních symbolů (tokenů pro parser) se snaží hledat odpovídající pravidla. Pokud je dané pravidlo nalezeno, je vykonán (v příslušném místě) odpovídající kód v jazyce C.
Předpokládané jméno funkce realizující lexikální scanner je yylex(). Při generování souboru realizujícího parser může Bison vygenerovat také hlavičkový soubor, v němž jsou uvedeny definice jednotlivých tokenů, a to již v odpovídající podobě v jazyce C (tedy např. #define INTEGER 258). Tento hlavičkový soubor je pak velice vhodné načíst funkcí realizující lexikální scanner a vracet hodnoty definované podle tohoto souboru. Vzhledem k tomu, že standardním jménem funkce realizující lexikální scanner generované programem Flex, se přímo propojení programů Flex a Bison nabízí.
Bison zatím nenabízí generování parserů jako tříd pro jazyk C++, což znemožňuje vytváření reentrantních parserů. Předpokládám ale, že to je přesně ta věc, na které se nyní pracuje, jelikož v programu Flex je generování výstupu pro jazyk C++ docela novinkou. Možnost mít v programu více parserů (aby navzájem nekolidovaly stejná jména funkcí a globálních proměnných) je umožněna parametrem P prefix, který změní standardní prefix yy na vámi specifikovaný (tzn. místo yyparse třeba cparse, místo yylex clex atd.). Tento prefix lze specifikovat i u programu Flex.
Bison je zpětně kompatibilní s programem yacc (yet another compiler compiler). Všechny parsery napsané pro yacc by měly bez sebemenší úpravy pracovat i v Bisonu. Každý programátor, který umí pracovat s yaccem, by měl být schopen pracovat s Bisonem bez sebemenších potíží.
K programu Bison je obsáhlá dokumentace (217kB). Je velice dobrá, obsahuje i příklady jednoduchých kalkulátorů (postfixového a infixového).
Bison je skvělým pomocníkem při psaní analýzy vstupu. Bude se vám hodit jednak chcete-li napsat portovatelný program, který bude mít například v nějakém vstupu zadané preference (a tedy kvůli portovatelnosti nebudete moci použít Amigáckou funkci ReadArgs()), případně pokud vstup bude mít trochu složitější strukturu - například v něm budou moci být definovány menu a jejich submenu. Pochopitelně je neocenitelný, pokud si budete chtít napsat vlastní překladač ať už si vymyslíte vlastní jazyk anebo se rozhodnete třeba konkurovat Storm céčku. Bison by pochopitelně měli mít na harddisku i ti, kteří v něm programovat nechtějí, ale chtějí si občas na své Amize pomocí ADE distribuce zkompilovat nějaký program z Unixu, Bison (či yacc) je často používaným nástrojem.

Vytlačiť článok

Pozn.: články boli naskenované ako text a preto obsahujú aj zopár chýb. Taktiež neručíme za zdrojové kódy (Asm, C, Arexx, AmigaGuide, Html) a odkazy na web. Dúfame, že napriek tomu vám táto databáza dobre poslúži.

Žiadna časť nesmie byť reprodukovaná alebo inak šírená bez písomného povolenia vydavatela © ATLANTIDA Publishing

AMIGA REVIEW

ATLANTIDA NEWS