Jak se dělá překladač 2

Dnešní článek vám rozhodně nevysvětlí všechno. Pojal jsem ho jako čistě praktickou ukázku a jeho cílem není ani tak vysvětlit, jak se to dělá, ale spíš, jak to funguje. Do jednoho článku na roota se to všechno prostě nevejde, takže když už nic jiného, berte to alespoň jako zajímavé čtení, případně jako inspiraci pro vaše vlastní programy.

Neznám žádné nástroje, které by konstruovaly analyzátory LL/SLL, a myslím, že to možná ani není potřeba. Jejich konstrukce je velmi jednoduchá a lze ji celkem snadno zvládnout na papíře. Aby nedošlo ke zmatení, bude vhodné poznamenat, že yacc vytváří analyzátory LALR(1), které se od LL liší přímo ve své podstatě. Kdysi jsem trávil dlouhé chvíle nad zdrojákem, který mi yacc vygeneroval, a snažil se pochopit, jak vlastně pracuje, v domnění, že se jedná o LL analyzátor. Musím vás ujistit, že nejedná. Třeba si ho zde jednou rozebereme :-).

Jak jsem již naznačil, dnešní článek bude vlastně jeden velký příklad použití jednoduché překladové gramatiky.

Co budeme programovat: Možná jste si už setkali s problémem, kdy potřebujete efektivně pomocí scriptu vytvořit určitou větvenou adresářovou strukturu, v určitých adresářích soubory a do souborů zapsat určitá data. Náš jazyk bude dělat právě to.

Syntax našeho vymyšleného jazyka: Do vstupního souboru se napíše seznam všech souborů a adresářů, které chceme vytvářet. Soubory se od adresářů budou lišit tím, že se před jejich jméno napíše znak %, před adresář to bude znak $. Za jméno souboru se zapíše do { kudrnatých závorek } řetězec, který si budeme přát do souboru uložit. Bude-li řetězec obsahovat mezery, uzavřeme ho do uvozovek ", bude-li jméno souboru/adresáře obsahovat mezery, můžeme s ním udělat totéž (uzavřít ho do uvozovek). Adresář, jak už jsem naznačil, se od souboru bude odlišovat tím, že jeho jméno bude začínat na $. Za jménem adresáře budou následovat opět { kudrnaté závorky }, ve kterých bude tímto způsobem popsán obsah (podadresáře a obsažené soubory). Příklad, jak takový jazyk bude vypadat, si můžete prohlédnout zde.

Výstup překladu: Jako výstup dostaneme seznam akcí, které když provedeme, vytvoříme tak žádanou adresářovou strukturu. Akce mohou být tyto:

1) MKDIR(jméno adresáře); = vytvoří adresář
2) CD(jméno adresáře); = přejde do adresáře (klasické cd)
3) CDDOTDOT(); = jde o úroveň výš (klasické cd ..)
4) CREATEFILE(jméno souboru, data); = vytvoří soubor a do
   něj zapíše data

Přeložíte-li výše uvedený příklad, dostanete tento výsledek.

Lexikální analyzátor: Tato věcička bude předzpracovávat vstup před tím, než se na něj vrhne syntaktický analyzátor. Úkolem Lexikálního analyzátoru je rozsekání vstupního souboru na tzv. tokeny. Jako vhodný příklad si můžete představit třeba program bc(1). Tento program na svém vstupu očekává matematický výraz, dejme tomu 123+357. Kdyby však program měl tento výraz zpracovávat znak po znaku, (1, 2, 3, +, 3, 5, 7), asi by to nebylo to pravé ořechové. Proto se nejprve vytvoří tzn. lexikální analyzátor, který bude číst text a vracet správně uspořádané skupiny znaků tak, aby dávaly smysl. Tedy (123, +, 357). S tím už se pak syntaktickému analyzátoru bude pracovat mnohem lépe.

Co to je token, pochopíte v našem příkladu nejlépe, podíváte-li se na seznam tokenů k předchozímu příkladu. Podívejte se ještě jednou na předchozí příklad a porovnejte ho se seznamem. V tuto chvíli je doufám pojem token jasný. Ještě pro přesnost bych měl poznamenat, že token string samozřejmě musí obsahovat samotný řetězec. Proto se ještě podívejte na tento výstup lexikálního analyzátoru. Jestliže jste stále na vážkách, podívejte sa na tento výstup. Jak se programuje lexikálni analyzátor, se můžete podívat sem.

Gramatika: Jak jistě tušíte, abychom mohli sestavit syntaktický analyzátor, musíme nejprve vymyslet gramatiku, která generuje náš jazyk. Taková gramatika může vypadat například takto:

 (0) START -> ITEM eof
 (1) ITEM  -> FILE  ITEM
 (2) ITEM  -> DIR  ITEM
 (3) ITEM  ->
 (4) FILE  -> % string { string }
 (5) DIR   -> $ string { ITEM }

 Terminály = %, $, string, }, {, eof
 Neterminály = FILE, ITEM, DIR
 Kořen gramatiky = START

Jak jsem vymyslel gramatiku: Myslím, že není složité vymyslet gramatiku, která generuje požadovaný jazyk. Horší je to však s konstrukcí gramatiky, která je SLL (resp. ke které lze sestrojit patřičný SLL-analyzátor). Ne každá gramatika je totiž SLL, ne ke každému jazyku lze takovou gramatiku sestavit. Gramatika, kterou jsem vám zde předhodil, je SLL(1) a prozatím to berte jako fakt.

Syntaktický analyzátor: Bylo by dobré si ujasnit, že celou tabulku, která představuje samotný analyzátor, jsem sestavil z gramatiky. Postup není zas až tak úplně triviální, proto vám dnes udělám jen lehký nástin a o samotném sestavení analyzátoru se rozepíšu až v dalším pokračování.

Celý analyzátor vypadá asi takto:

Jak jsem tu tabulku sestrojil? Podíváte-li se na pravé strany gramatiky a intuitivně si zkusíte vypočítat pro každé pravidlo všechny terminály, na které můžou jednotlivé pravé strany po libovolném počtu přepisování začínat, mnohé by se vám mělo objasnit. Podrobněji bych se o tom měl rozepsat v některém z příštích dílů, v tom dnešním mi na to nezbude místo.

Funkčnost analyzátoru je celkem snadná. Stěžejní datovou strukturou, se kterou pracuje analyzátor, je zásobník (tedy klasická konstrukce typu FIRST IN LAST OUT). V počátečním stavu zásovník obsahuje na svém dně jediný prvek „START“. Při analýze se nejprve načte pomocí lexikálního analyzátoru jeden token. Tento token určuje sloupec v tabulce (jsou to ty zelené buňky). Dále se analyzátor podívá na vrchol zásobníku a tento symbol určí řádku (modré buňky). Na průsečíku se pak určí akce.

Akce je možná vlastně jenom jedna. Je to náhrada vrcholu zásobníku za něco jiného. Červeně jsou v tabulce označeny speciální akce. Err znamená, že při analýze došlo k chybě, a překladač by měl oznámit syntax-error. Další červená položka může být Red, což značí prosté odebrání jednoho symbolu z vrcholu zásobníku a načtení dalšího tokenu. Světle šedé akce se provedou tak, že se odebere vrchol zásobníku a místo něj se uloží šedé symboly. Čárkou oddělená čísla, která se vyskytují v šedě vyplněných buňkách tabulky, značí číslo pravidla. Budete-li si tato čísla zapisovat v pořadí, jak je celé slovo postupně analyzováno, získáte tak vlastně seznam pravidel, která derivují právě ono vstupní slovo.

Aby to bylo všechno jasné, vyzkoušíme si analyzovat část vstupu našeho výše uvedeného příkladu.

Jak jsem již zmiňoval, analýza začíná s prvkem START na dně zásobníku. Načte se první token, tedy $. Podíváme se na vrchol zásobníku (tam je START) a v tabulce proto na souřadnice [$, START], kde se nachází ITEM EOF. START tedy odebereme ze zásobníku a uložíme ITEM EOF. Načtený symbol je stále $, na vrcholu zásobníku je ITEM. Podíváme se do tabulky na souřadnice [$, ITEM], tam je

DIR ITEM. ITEM tedy odebereme a vložíme DIR ITEM. Na vrcholu zásobníku je nyní DIR a načtený token je stále $. Koukneme se na [$, DIR], tam se nachází $ string { ITEM } Odebereme tedy DIR a vložíme $ string { ITEM }. Na zásobníku je teď $ string { ITEM } ITEM EOF. Koukneme na souřadnice [$, $], tam je červené

Red. Proto odebereme $ ze zásobníku a načteme další token (string). Na zásobníku je teď string { ITEM } ITEM. Koukneme na [string, string], tam je Red, takže odebereme string ze zásobníku a načteme další token…

To by bylo pro dnešek vše.

A co bude příště?

Rekurzivní sestup: Kromě výše popsaného postupu zásobníkem je možné LL-analyzátor programovat velmi rychle a jednoduše takzvaným rekurzivním sestupem. A právě touto metodou je naprogramován náš příklad, na který se můžete podívat již dnes. Na výsledný program se můžete podívat sem a jen pro motivaci si všiměte nápadně podobných jmen céčkových funkcí, neterminálů v gramatice a tabulky syntaktického analyzátoru. Více si o tom povíme příště.