Hlavní navigace

Jak se dělá překladač 2

Ondřej Holeček

I když jsem v minulém článku sliboval pokračování o stavových automatech, nakonec jsem se rozhodl podle vašich ohlasů trochu jinak. Dnes si uděláme jednoduchý příklad překladu pomocí SLL(1) gramatiky. Jedná se o druh syntaktické analýzy, která se příliš nehodí pro složité jazyky, jako je třeba programovací jazyk C, je však vhodná pro ručně psané parsery konfiguračních souborů, případně jednoduchých skriptovacích jazyků.

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:

Tabulka č. 280
% $ } { string eof
START ITEM eof, 0 ITEM eof, 0 Err Err Err ITEM eof, 0
FILE % string { string }, 4 Err Err Err Err Err
DIR Err $ string { ITEM }, 5 Err Err Err Err
ITEM FILE ITEM, 1 DIR ITEM, 2

, 3

Err Err , 3
% Red Err

Err

Err Err Err
$ Err Red

Err

Err Err Err
} Err Err

Red

Err Err Err
{ Err Err

Err

Red Err Err
string Err Err

Err

Err Red Err
eof Err Err

Err

Err Err Red

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ě.

Našli jste v článku chybu?

17. 10. 2008 16:41

Zly Pes (neregistrovaný)
heh..teraz Ti to uz asi nepomoze...kazdopadne pochybujem, ze tata gramatika generuje regularny jazyk (cize FA nezostrojis)...a keby generovala..silne pochybujem, ze by sa na preklad pouzival potom SLL analyzator ked by to islo oby automatom. bezkontextovy jazyk su schopne akceptovat zasobnikove automaty.

4. 5. 2006 13:39

rej (neregistrovaný)
v clanku se pise:

"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)...."

..kde jsou videt ony modre a cervene bunky??? Mam firefox i IEcko a nidke nic nevidim.

dik





120na80.cz: Rovnátka, která nejsou vidět

Rovnátka, která nejsou vidět

Vitalia.cz: To nejhorší při horečce u dětí: Febrilní křeče

To nejhorší při horečce u dětí: Febrilní křeče

DigiZone.cz: R2B2 a Hybrid uzavřely partnerství

R2B2 a Hybrid uzavřely partnerství

120na80.cz: Boreliózu nelze žádným testem prokázat

Boreliózu nelze žádným testem prokázat

DigiZone.cz: V Plzni odstartovalo Radio 1

V Plzni odstartovalo Radio 1

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

120na80.cz: Co všechno ovlivňuje ženskou plodnost?

Co všechno ovlivňuje ženskou plodnost?

Vitalia.cz: Jak vybrat ořechy do cukroví a kde mají levné

Jak vybrat ořechy do cukroví a kde mají levné

120na80.cz: Horní cesty dýchací. Zkuste fytofarmaka

Horní cesty dýchací. Zkuste fytofarmaka

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Podnikatel.cz: Vládu obejde, kvůli EET rovnou do sněmovny

Vládu obejde, kvůli EET rovnou do sněmovny

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

Podnikatel.cz: E-Ježíšek si zařádí: nákupy od 2 do 5 tisíc

E-Ježíšek si zařádí: nákupy od 2 do 5 tisíc

Root.cz: Certifikáty zadarmo jsou horší než za peníze?

Certifikáty zadarmo jsou horší než za peníze?

Měšec.cz: Za palivo zaplatíte mobilem (TEST)

Za palivo zaplatíte mobilem (TEST)

Podnikatel.cz: Chtějte údaje k dani z nemovitostí do mailu

Chtějte údaje k dani z nemovitostí do mailu

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

Podnikatel.cz: Udávání a účtenková loterie, hloupá komedie

Udávání a účtenková loterie, hloupá komedie

Vitalia.cz: Pamlsková vyhláška bude platit jen na základkách

Pamlsková vyhláška bude platit jen na základkách

Měšec.cz: Exekuční poradna: ptejte se online

Exekuční poradna: ptejte se online