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.
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,... |
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).
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 | ||
| ... | ||
- 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 (); | |||
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 |
|