1. Úvod

Za dobu, kdy se člověk potýká s problémem, jak zaznamenat a předat informaci, vyzkoušel již mnoho způsobů. Pokud bychom ve svých představách putovali časem, mohli bychom pozorovat, jak člověk opustil obrázkové písmo, zkusil různé možnosti (a mnoho slepých uliček) a po různých peripetiích dospěl až k mnohem mocnějšímu nástroji - jazyku a písmu tak, jak je známe dnes.

Na svém monitoru však dnes můžeme - zcela paradoxně - pozorovat vývoj opačný. Od mocných nástrojů k obrázkovému písmu.

Předchozí příměr bychom mohli mávnutím ruky odsoudit jako bonmot. Možná až příliš zjednodušoval, snad málo odlišil samotný jazyk a písmo - způsob, kterým je zaznamenán. Snad si nevšiml, že i při myšoklikání na ikonky používáme určitý "jazyk" - byť jazyk "primitivní" a pouze velmi mlhavě definovaný.

Chtěl bych právě tomuto tématu věnoval svůj referát. Byl bych rád, pokud byste po přečtení následujících stránek získali pocit, že na aplikaci s dobře definovaným vstupem není nic divného - a při použití zde popisovaných nástrojů ani nic těžkého. Naučíte se, jak zacházet s nástroji flex a bison, jak napsat jednoduchou kalkulačku a poznáte, jak jednoduché je zpracovat jazyk podobný například jazyku C.

Můj referát je pouhým úvodem do problematiky - zaměřím se spíš na způsob práce s jednotlivými nástroji než na teorii a použité algoritmy. Jelikož vím, že mnoho lidí raději "píše programy" než hloubá nad teoretickými otázkami, pokusím se nevyděsit odbornými termíny, teorie se dotknu pouze lehce - a odborníci odpustí - často ji i zjednoduším.

1.1 Co si počít se vstupem programu?

Textový vstup vašeho programu může mít mnoho podob - od matematických výrazů až po mnohem složitější jazyky. Představme si následující věty a výrazy:

((x - 50) * 37) / y
Pes jitrničku sežral, docela maličkou,...

1.1.1 Flex a lexikální analýza

V první části zpracování vstupu se pokusíme podle určitých pravidel spojit jednotlivé vstupní znaky do slov - tak zvaných tokenů. Tokenem je v prvním výrazu například levá závorka '(', písmeno 'x', číslice '57' nebo operátory '-', '*', '/'. V druhém příkladu odpovídají tokeny slovům z lidského jazyka: 'pes', 'jitrničku',...

Této části rozboru se říká lexikální analýza textu. Existuje mnoho nástrojů, které vám s tímto problémem pomohou, v našem referátu se budeme věnovat tradičnímu UNIXovému nástroji lex a jeho GNU inkarnaci flex (fast lexical analyzer generator).

1.1.2 Bison a syntaktická analýza

Přestože je analýza skutečného lidského jazyka problém mnohem složitější (než například analýza matematických výrazů), chvíli ještě u tohoto přirovnání zůstaneme. Pokud s jistou dávkou básnické licence řekneme o lexikální analýze, že se zabývá znaky a slovy, pak část druhá - syntaktická analýza - se zabývá slovy a větami, podle pravidel gramatiky jazyka skládá slova do vět.

Z hodin českého jazyka na základní škole si jistě pamatujete na větný rozbor. Jistě jsem si nevybavil pravidla dobře, myslím však, že i takto zjednodušená pravidla nám pro demonstraci gramatiky zcela postačí:

věta ---> věta holá
věta rozvitá
souvětí
...
věta holá ---> podmět přísudek
podmět ---> podstatné jméno
zájmeno
...
podstatné jméno ---> pes
jitrnička
...

Věta může být buď holá nebo rozvitá, holá věta se skládá z podmětu a přísudku, podmětem může být podstatné jméno či zájmeno a 'pes' nebo 'jitrnička' může posloužit jako příklad podstatného jména. Obdobně pro jednoduché matematické výrazy (dobře si všimněte rekurzivnosti celé definice):

výraz ---> číslo
'(' výraz ')'
výraz '+' výraz
výraz '*' výraz
...

1.1.3 Flex a bison jsou generátory kódu

- co to však znamená? Ve zdrojových souborech popíšete pravidla, kterými se ze vstupních znaků vytvářejí tokeny (respektive pravidla gramatiky), flex (bison) takový soubor zpracuje a vytvoří kód v jazyce C, který provádí lexikální (syntaktickou) analýzu. Funkce yylex a yyparse jsou takřka ušity na míru vámi specifikovaného jazyka.

file.l ---> flex ---> lex.yy.c
popis tokenů int yylex ();
file.y ---> bison ---> file.tab.c
gramatika jazyka int yyparse ();

1.2 Odkazy

Na starších UNIXOVých systémech se možná ještě setkáte s předchůdci obou programů - s programy lex a yacc. Flex a bison jsou programy napsané v rámci projektu GNU's Not Unix, a distribuované pod GNU General Public License.

Pokud byste se chtěli zahloubat do originálního manuálu, prohlédnout si zdrojové soubory či přeložit a nainstalovat si oba nástroje, zdrojové soubory si můžete kdykoliv stáhnout z 'mirror' ftp GNU projektu, ve vodách českého internetu je to nejblíže na ftp://sunsite.mff.cuni.cz/GNU/packages/. Verse obou nástrojů pro DOS naleznete na ftp://ftp.vse.cz/.

Všem zájemcům, kteří by rádi prošli všechna temná zákoutí, bych rád doporučil výtečnou dokumentaci, které oba nástroje doprovází a ze které můj referát vydatně čerpal. Dále pak přednášku Automaty a gramatiky a ostré zuby, až se budou prokousávat knihami popisující algoritmy použité ve flexu a bisonovi.

[Obsah] [Následující kapitola: Flex]


© 1999 0rfelyus Emacs