Jak se dělá překladač

Než se začneme bavit o teorii překladačů, rozhodně nebude na škodu si objasnit, co to vlastně takový strojový překlad je. Překlad jako takový chápeme obecně jako převod nesrozumitelné formy informace na srozumitelnou. Může se jednat jak o překlad z jazyka nám neznámého do češtiny, tak o překlad vyššího programovacího jazyka do strojového kódu (v tomto případě se jedná o překlad informace, které nerozumí počítač). Nemusíme však nutně překládat programovací jazyky, celá věda o překladačích je velmi rozsáhlá. Spadá do ní vše od prostého vyhledávání řetězců v rozsáhlých souborech a regulárních výrazů, důkazu řešitelnosti/ne­řešitelnosti některých klíčových problémů až po zmiňované překlady vyšších programovacích jazyků.

Proto platí, že nemusíte zrovna psát překladač jazyka C, abyste využili znalosti o strojovém překladu. Každý, kdo jednou naprogramoval alespoň trochu složitější program, stanul v určité fázi vývoje před problémem načítání konfiguračního souboru.

V tzv. „okenním prostředí“ je to snadné. Vytvoříte pár tupých dialogových oken, spoustu klikátek, zaškrtávátek, šoupátek a podobných opičáren. Všechno to uložíte do rozvětvené struktury, a tu pak po poklepání na tlačítko „OK“ na disk. V unixových systémech se s něčím podobným setkáme jen velmi zřídka. Konfigurační soubory jsou textově orientované, klikátka se nekonají, program musí být natolik chytrý, aby si takový konfigurační soubor uměl načíst.

Tímto článkem bych chtěl lehce nakousnout problematiku překladu a vůbec parsování textově orientovaných souborů. Celá problematika překladačů je však značně složitá a rozsáhlá. Ne všechny pasáže, jako třeba některé matematické důkazy, jsou zajímavé. Není snadné vměstnat 150-ti stránková skripta do jednoho krátkého článku. Proto tento článek berte pouze jako krátký úvod do seriálu, jehož pokračování je (podle ohlasu) ve vašich rukou.

Abych vůbec mohl začít něco vysvětlovat, musíme si zadefinovat několik jednoduchých pojmů. Nejedná se o nic složitého a myslím, že to všichni velmi rychle pochopíte:

Jazyk: Jazyk není nic jiného než množina slov.
Slovo: Slovo je posloupnost písmen.
Abeceda: Množina písmen, ze kterých se můžou skládat slova.
Konečný jazyk: Jazyk, který obsahuje konečné množství slov.
Nekonečný jazyk: Jazyk, který obsahuje nekonečně mnoho slov.
Prázdný jazyk: Jazyk, který neobsahuje žádné slovo.

Z toho vyplývá, že budeme-li za písmeno považovat i mezeru, tečku, čárku, otazník a vykřičník, může se slovo českého jazyka rovnat jakékoli větě nebo uskupení vět, které dávají smysl. Slovo programovacího jazyka C můžeme chápat jako libovolný korektně zapsaný program.

Příklady jazyka:

1. Nekonečný jazyk: Množina všech možných slov sestavených z jednoho písmene „a“. Tedy {a, aa, aaa, aaaa, … }
2. Konečný jazyk: Množina slov { aa, bb, cc}
3. Regulární jazyk: Všechna slova vyhovující regulárnímu výrazu ab. Tedy {aaaa, aaa, abbbb, aaabbbbb, aaaaabb…}, prostě všechna slova, která začínají libovolným počtem „a-ček“ a pokračují libovolným počtem „b-ček“.

Nyní se začneme zabývat tím, jak takový jazyk vysvětlit počítači. Jedná-li se o jazyk konečný, není se v podstatě o čem bavit. Stačí udělat seznam všech slov, která do jazyka patří, a jsme hotovi. Jedná-li se však o jazyk nekonečný, nemáme na uložení do paměti počítače dostatečně velkou kapacitu a musíme si poradit jinak. :-)

Obecně existují dvě možnosti, gramatiky a automaty. Automat si můžeme představit jako černou krabici, do které z jedné strany strčíme na papírku napsané slovo a z druhé strany krabice vypadne lísteček, na kterém bude napsáno buď „ANO-slovo do jazyka patří“, nebo „NE-slovo do jazyka nepatří“.

Takovým obecným automatem může být například překladač jazyka C. Na vstupu se mu vloží text, a dojde-li při překladu k chybě, slovo (resp. program) do jazyka nepatří, v opačném případě patří.

Další možná představa automatu může být například „Céčkovská“ funce bool automat(char *s);. Jako parametr je slovo a výstup funkce je logická hodnota, která nám říká, zda slovo do jazyka patří, či nikoli.

Naproti tomu gramatiky se od automatu liší pouze tím, že ona pomyslná krabice má pouze jeden otvor. Krabici uchopíme a třeseme s ní tak dlouho, dokud z ní nevypadne nějaké slovo. Slova, která se nám podaří z krabice vytřást, tvoří jazyk.

Na první pohled se může zdát, že gramatika a automat jsou naprosto totožné pojmy. Zdání však klame. Chápeme-li automat jako program resp. algoritmus, uvidíme, že ne pro každou gramatiku lze sestavit automat, který generuje stejný jazyk jako tato gramatika. Bude-li zájem, mohu zde předvést neformální důkaz. (Upozorňuji, že zabere minimálně dva další články :-)))

Abyste získali lepší představu o tom, co to vlastně taková gramatika je, podívejte se na následující obrázek, kde jsou znázorněny ukázky tří různých gramatik:

Každá gramatika v tomto příkladu obsahuje několik pravidel, pomocí kterých se tvoří jednotlivá slova jazyka. Asi nejlépe si to ukážeme na příkladu, konkrétně na gramatice G1 (Gramatik G2 a G3 si zatím nevšímejte). Uchopíme tedy krabici a začneme třást:

S -> CAC -> CAab -> cBAab -> cbbAab ->  cbbAab -> cbbaab

Z krabice (gramatiky) vypadlo slovo „cbbaab“ a můžeme o něm tedy říci, že patří do jazyka generovaného touto gramatikou.

Pokud jste to ještě nepochopili, třesení probíhalo takto:

Počáteční „neterminál“ se v gramatikách obvykle značí písmenem velké S. Terminál od neterminálu poznáte celkem snadno. Neterminál je každý znak, který se nachází vlevo od šipky, a pro přehlednost jsou všechny tyto neterminály značeny velkým písmem. U gramatiky G1 je tedy množina neterminálů = { S, A, B, C }. Terminál je pak všechno ostatní. Tedy množina terminálů = { a, b, c }, u G3 je to { n }. Jak jsem již nakousnul, počáteční neterminál je v této gramatice S. Podíváme se na pravidla příslušející k tomuto neterminálu a jedno si vybereme. Na výběr máme: S->aBAb, S->ACa, S->CAC. V gramatice jsou pravidla pro jednoduchost oddělena znakem ‚|‘, aby se nemuselo neustále opisovat S->… V příkladu jsem si vybral pravidlo S->CAC. V řetězci CAC si opět vyberu jeden neterminál a aplikuji na něj další libovolné pravidlo. V příkladu to bylo pravidlo C->ab a aplikoval jsem ho na nejlevější Céčko. Získal jsem tak CAab. Tak pokračujeme do té toby, než získáme řetězec složený ze samých terminálů (resp. složený z písmen abecedy).

Doufám, že jste to všichni pochopili! :-)

Nyní se asi ptáte, k čemu je to dobré? Čím nás to tu krmí? K tomuto účelu tu pro vás mám nachystanou gramatiku G3. Tato gramatika generuje všechny matematické výrazy typu „n*(n+n)+n“. Tvoříme-li například program typu bc(1), může nám podobná gramatika pomoci. Podaří-li se nám sestavit program, který pozná, ze kterých pravidel se matematický výraz vytvářel, zjistíme, že nebude problém ho spočítat. Jen pro ilustraci, zmiňovaný výraz by vzniknul z gramatiky G3 asi takto:

S -> A -> A*A -> n*A -> n*A+A -> n*(A)+A -> n*(A+A)+A ->
n*(n+A)+A -> n*(n+n)+A -> n*(n+n)+n

Celá věda o překladačích spočívá ve vymýšlení postupů, jak algoritmicky (programem) co nejefektivneji určit, jak se z určité gramatiky dostalo určité slovo. Nemáte-li však zájem na studiu těchto postupů, existují nástroje, které všechno udělají za vás. V Unixu-Linuxu je to například yacc, kterému jako vstup zadáme popis gramatiky resp. jejích pravidel a yacc nám program sestaví sám. Myslím, že jedna kapitolka v seriálu by se mohla věnovat právě yaccu a můžeme si vyzkoušet použití třeba hned gramatiky G3 :-).

Ještě pro zajímavost se podívejte na gramatiku G2. Tato gramatika se od ostatních liší především posledním pravidlem CBA->BBCC|C|CCdAC. Levá strana tohoto pravidla obsahuje hned tři neterminály. Jedná se o tzn. gramatiky typu 0 a v tomto ani v příštím článku se jimi nebudeme zabývat. Uvádím ji zde pouze jako příklad pro hloubavé hlavinky. Platí totiž následující tvrzení: Nelze sestavit algoritmus/program takový, který pro libovolnou gramatiku typu 0 určí, zda lze z této gramatiky vytřást určité slovo. Nelze sestavit algoritmus, který určí, zda je jazyk generovaný gramatikou typu 0 neprázdný.

A to by bylo pro dnešek vše. V dalším článku bych chtěl vysvětlit pojmy stavový automat, regulární výraz, souvislost mezi automatem a regulárním jazykem a jejich funkci v překladači.

Zajímavé odkazy:

www.lysator.li­u.se/c/ANSI-C-grammar-y.html – Gramatika, která popisuje programovací jazyk C podle normy ANSI
www.fi.muni.cz/zkus­to/ – Zde můžete najít mnoho zjímavých informací (nejen k překladačům) ;-)