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.

widgety

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

Ohodnoťte jako ve škole:

Průměrná známka 2,49

Našli jste v článku chybu?
Zasílat nově přidané názory e-mailem
DigiZone.cz: Jak by měla vypadat sportovní reality show?

Jak by měla vypadat sportovní reality show?

Lupa.cz: Roaming se mění. Co byste o něm měli vědět?

Roaming se mění. Co byste o něm měli vědět?

120na80.cz: Pyly útočí. Braňte se

Pyly útočí. Braňte se

Podnikatel.cz: Poděs, Slibotechna a další. Ty berte obloukem

Poděs, Slibotechna a další. Ty berte obloukem

Podnikatel.cz: Nemocenské pojištění. Chystají se velké změny

Nemocenské pojištění. Chystají se velké změny

Podnikatel.cz: Máte poslední dny na odevzdání přehledů

Máte poslední dny na odevzdání přehledů

Vitalia.cz: Vědci: Svět vegetariánů by byl zdravější a...

Vědci: Svět vegetariánů by byl zdravější a...

Vitalia.cz: Sami nezvládají. Z čeho platit péči o seniora?

Sami nezvládají. Z čeho platit péči o seniora?

Podnikatel.cz: Radši se k podnikání nechají zaměstnat

Radši se k podnikání nechají zaměstnat

Podnikatel.cz: Velká fotogalerie franšíz. Vybírejte v ČR

Velká fotogalerie franšíz. Vybírejte v ČR

Podnikatel.cz: Víte o změnách u sociálního pojištění OSVČ?

Víte o změnách u sociálního pojištění OSVČ?

Vitalia.cz: Jak se žije na kozí farmě

Jak se žije na kozí farmě

Lupa.cz: Jaký je Průvodce světem Arduina?

Jaký je Průvodce světem Arduina?

Podnikatel.cz: Firmu lze trestat za účast na sebevraždě

Firmu lze trestat za účast na sebevraždě

Lupa.cz: Stát chce vytěsnit malé firmy z trhu

Stát chce vytěsnit malé firmy z trhu

Podnikatel.cz: Když si reklamou „zabíjíte“ zákazníky

Když si reklamou „zabíjíte“ zákazníky

Měšec.cz: Má vám zdražit elektřina? Stěžujte si

Má vám zdražit elektřina? Stěžujte si

Vitalia.cz: Proč jsou po vyřazení lepku zdravější?

Proč jsou po vyřazení lepku zdravější?

Vitalia.cz: Byla Nestlé kaše opravdu nebezpečná?

Byla Nestlé kaše opravdu nebezpečná?

Podnikatel.cz: Prodá jen 15 obědů denně. Co dělá špatně?

Prodá jen 15 obědů denně. Co dělá špatně?

Ušetřete