Jak se dělá překladač

Ondřej Holeček 15. 11. 2001

Co je to syntaktická analýza? Jak funguje yacc? Je těžké naprogramovat překladač? Co je to gramatika? Co je to stavový automat? Tento článek (možná na pokračování) by vám měl posloužit jako lehký úvod do tvorby strojových překladačů. Nečekejte však zázraky. Je to složité!

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:

různé gramatiky

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) ;-)

DigiZone.cz: Šlágr TV: pokuta 100 tisíc za on-line

Šlágr TV: pokuta 100 tisíc za on-line

Lupa.cz: Jak EET vidí ajťák aneb Drahá vražda UX

Jak EET vidí ajťák aneb Drahá vražda UX

120na80.cz: Vyzrajte na návaly a pocení v přechodu

Vyzrajte na návaly a pocení v přechodu

Podnikatel.cz: Šizený guláš na pultě. Jako Lidl to nedělejte

Šizený guláš na pultě. Jako Lidl to nedělejte

Vitalia.cz: Co se platí u zubaře

Co se platí u zubaře

120na80.cz: Zjistěte, zda je vaše klíště infikované

Zjistěte, zda je vaše klíště infikované

DigiZone.cz: ČT neskončí s nízkým rozlišením podle plánu

ČT neskončí s nízkým rozlišením podle plánu

Podnikatel.cz: Alza radí e-shopům, jak opustit Heureku

Alza radí e-shopům, jak opustit Heureku

Vitalia.cz: Před, nebo po snídani? Kdy je lepší čistit si zuby

Před, nebo po snídani? Kdy je lepší čistit si zuby

DigiZone.cz: Konec geoblokace online médií?

Konec geoblokace online médií?

Lupa.cz: Nová podoba Instagramu? Katastrofa

Nová podoba Instagramu? Katastrofa

Vitalia.cz: Proč máme prasklý chléb nejraději?

Proč máme prasklý chléb nejraději?

DigiZone.cz: DAB+ versus FM, ČRo a ČRa proti APSV

DAB+ versus FM, ČRo a ČRa proti APSV

Vitalia.cz: Muži kouří 24 cigaret denně, ženy o dost míň

Muži kouří 24 cigaret denně, ženy o dost míň

DigiZone.cz: UPC umí televizi sedm dní nazpět

UPC umí televizi sedm dní nazpět

Vitalia.cz: Ministerstvo: tyto příbory jsou nebezpečné

Ministerstvo: tyto příbory jsou nebezpečné

Podnikatel.cz: Rošáda v živnostech. Týká se vás?

Rošáda v živnostech. Týká se vás?

Vitalia.cz: Taky ji kupujete? Je šizená

Taky ji kupujete? Je šizená

120na80.cz: Jak si udržet zdravou vaginu

Jak si udržet zdravou vaginu

Vitalia.cz: Dnešní patolog o mrtvolu téměř nezavadí

Dnešní patolog o mrtvolu téměř nezavadí