Jazyky a překladače - 3 (syntaxe)

14. 8. 2006 | Michal Vyskočil | Programování | 9742×

Přesuneme se od regulárních výrazů trochu blíže k překladačům. Tématem dnešního dílu budou základy analýzy zdrojového kódu. Navíc přinese ještě méně teorie a více praxe než předchozí díl. Dnešním oblíbeným programovacím jazykem je C.

Obsah

• Princip překladače
• Analýza zdrojového kódu
• Lexikální analýza a program (f)lex
• Zajímavosti
  • Zkratky programu flex
  • Vstup a výstup
  • Generování analyzátorů v C++
• Nevýhody
• Závěr

Princip překladače

Překladač je program, který (velice zjednodušeně řečeno) postupně prochází kód napsaný v nějakém programovacím jazyce a z něj generuje spustitelný soubor. Samotný překlad se sestává z několika fází:

Analýza zdrojového kódu

/* program v C */
int   n = 10;
char* s = "Hello, world!";
if (n == 10) {
	printf("%s\n", s);
}

" program ve Smalltalku "
n := 10.
s := 'Hello, world!'.
[n = 10] if:
	[ Transcript show: n, s; cr. ]

<!-- dokument v XML -->
<servlet>
	<servlet-name>webdav</servlet-name>
	<servlet-class>org.apache.catalina.servlets.WebdavServlet</servlet-class>
	<init-param>
	<param-name>debug</param-name>
	<param-value>0</param-value>
	</init-param>
</servlet>

Nahoře jsou ukázky zdrojového kódu napsaného ve dvou různých programovacích jazycích — C a Smalltalk (Squeak). A navíc příklad dokumentu ve formátu XML (protože syntaxe se netýká jen programovacích jazyků). Na první pohled je vidět jejich syntaktická odlišnost, přestože v konečném výsledku dělají to samé. Pokud vynecháme absenci typování ve Smalltalku, potom vidíme odlišné příkazy pro přiřazení (``='' vs. ``:=''), jiné znaky pro ukončení příkazu (``;'' vs. ``.''), jiné komentáře a podobně. Navíc vidíme další rozdíl. Zatímco řetězec if je v C kódu zvýrazněn, ve Smalltalku ne. Není to překlep při psaní, ale zdůraznění skutečnosti, že if není ve Smalltalku klíčové slovo jazyka, ale normální metoda. Syntaxe tudíž určuje (mimo jiné) tvar základních konstrukcí jazyka a překladač (interpret, parser) je musí nějakým způsobem rozpoznat.

Opět se zaměříme na otázku, jak něco takového naprogramovat. Standardní knihovna jazyka C (ostatní jazyky mají ekvivalentní nástroje) poskytuje funkce pro práci se soubory, které jsou definovány v souboru stdio.h. Pomocí těch nejjednodušších můžeme na zdrojový kód nahlížet jako na jednorozměrné pole znaků — 'i','n','t',' ', ..., případně jako na izolované řádky:

21:  int    n = 10;
22:  char*  s = "Hello world!";

Ovšem funkce jako scanf() už pracují na vyšší úrovni a umožňují zadat formátovací řetězec, podle něhož bude vstup přiřazen do proměnných. Potom můžeme napsat něco jako:

char type[10], name[10];
int value;

scanf("%s %s = %d", &type, &name, &value);
printf("type: %s, name: %s, value: %d\n", type, name, value);
return 0;

a přeložený program vrátí

$ echo "int n = 10;" | ./scanf
type: int, name: n, value: 10

Funkce scanf bohužel neumí dvě věci. Tou první je definovat vlastní parametry (například pro klíčová slova jazyka) a tou druhou je fakt, že jí není možné říct čekej na libovolný ze zadaných vstupů. To, co potřebujeme, je něco, co se dokáže na program podívat asi takto:

(INT int) (IDENTIFIER n) (=) (CONSTANT 10) (;)

Lexikální analýza a program (f)lex

To něco se odborně nazývá lexikální analyzátor. Ten, který dokáže zdrojový program rozdělit na jednotlivé lexémy (tokeny). Lexém je nejmenší logická jednotka v kódu programu, například identifikátor nebo operátory, případně ukončovací znak. Jsou definovány jako regulární výrazy, třeba identifikátor je v C definován takto — [a-zA-Z_][a-zA-Z0-9_]*. Což znamená, že prvním znakem může být libovolný znak latinské abecedy a podtržítko, následovaný libovolným počtem znaků latinské abecedy, arabských číslic a podtržítek. Lexikální analyzátor tedy načítá vstupní text a zkoumá, do které ze zadaných kategorií patří.

Přestože je možné napsat daný parser ručně (například jako velký konečný automat), bývá jednodušší využít generátor analyzátorů. Program lex je dostupný na všech systémech, které splňují normu POSIX, a jeho úkolem je na základě symbolického popisu vygenerovat kód lexikálního analyzátoru. Ve většině linuxových distribucí ovšem naleznete progam flex, což je rozšířená verze lexu, kterou vydalo FSF.

Specifikace skeneru se obecně sestává ze čtyř částí. V té první, ohraničené %{ %}, uvedeme deklarace jazyka C. Například makra, nebo hlavičkové soubory.

%{

#define UNDEFINED   0
#define HCONSTANT   1
#define OCONSTANT   2
#define DCONSTANT   3

%}

Ve druhé části si můžeme nadefinovat užitečné podvýrazy, které nám zpřehlední zápisy v další části.

D           [0-9]
O           [0-7]
H           [a-fA-F0-9]
IS          (u|U|l|L)*

Další část, ohraničená %% %%, slouží k definici lexémů. K nim může být přiřazen kód, který bude vykonán po jeho nalezení. Jak vidíte, lexémy jsou definovány pomocí regulárních výrazů a celý zápis trochu připomíná program awk. Zajímavostí je zápis [ \t\n]+, který nemá přiřazen žádnou akci. Je to z toho důvodu, že bílé znaky (mezera, tabelátor, nový řádek) vynecháváme. Nicméně nástroj make nebo jazyk Python počítají i bílé znaky do syntaxe.

%%
0[xX]{H}+{IS}?   { return HCONSTANT; }
0{O}+{IS}?       { return OCONSTANT; }
{D}+{IS}?        { return DCONSTANT; }
[ \t\n]+
.                { return UNDEFINED; }
%%

Poslední, čtvrtá, část obsahuje již jenom výkonný kód v C, který reaguje na jednotlivé lexémy.

static char name[4][16] = {
	"nezname", "sestnactkove", "osmickove", "desitkove"
};

int main() {
	int token;
	while (token = yylex()) {
	printf("Nalezeno %s cislo\n", name[token]);
	}
}

K dispozici je zdrojový kód integer.l, i ve verzi se zvýrazněnou syntaxí integer.l.html. Nebo si můžete stáhnout celý archív integer.tar.gz, který obsahuje i Makefile.

Překlad se potom provede (pokud jste si nestáhli archív s Makefile) takto:

flex integer.l
gcc -o integer lex.yy.c -lfl

Aplikace potom načítá standardní vstup a analyzuje zadané lexémy:

$ ./integer
123
Nalezeno desitkove cislo
0123
Nalezeno osmickove cislo
0x115
Nalezeno sestnactkove cislo
0X1Ff
Nalezeno sestnactkove cislo
234U
Nalezeno desitkove cislo
12      0x2
	077
Nalezeno desitkove cislo
Nalezeno sestnactkove cislo
Nalezeno osmickove cislo
54,21
Nalezeno desitkove cislo

Po zadání znaku, který nezná ``,'', se program ukončí, protože makro UNDEFINED se expanduje na 0, a tím dojde k ukončení cyklu while. Navíc také úspěšně ignoruje prázdné řádky.

Vygenerovaný program obsahuje několik důležitých funkcí a proměnných:

yylex()	Funkce, která v cyklu spouští akce na základě nalezené masky. Protože ji přerušujeme příkazem return, můžeme ji použít v našem cyklu.
yytext	Pole znaků, které obsahuje nalezený lexém.
yyleng	Délka řetězce v yytext.
yymore()	Načte další lexém do proměnné yytext.
ECHO	Zkopíruje nalezený lexém na standardní výstup.

Zajímavosti

Manuálů k program flex naleznete na internetu mnoho, některé z nich jsou i dole v odkazech, proto nebudu vysvětlovat formáty masek nebo funkce přepínačů, ale přeskočím na zajímavější funkce.

Zkratky programu flex

V předchozím případě bylo nutné definovat podvýraz pro čísla jako D [0-9]. Autoři programu flex do něj zařadili zkratky pro často používané skupiny. Ty se zapisují ve formátu [:zkratka:], což je stejná syntaxe, jako například v programu grep. Podporované zkratky jsou:

alnum, alpha, blank, cntrl, digit, graph, lower, print, punct, space, upper, xdigit

Programátorům v C budou jistě velice povědomé, protože názvy i funkčnost odpovídá funkcím is<zkratka>() ze souboru ctype.h. Výše uvedený příklad potom můžeme zapsat jako D [[:digit:]] (a přiznám se, že teď dostalo slovo zkratka zcela nový význam).

Vstup a výstup

Někdy nám nemusí být po chuti, že analyzátor pracuje jen se standardním vstupem a výstupem. Jsou definovány dvě proměnné:

FILE *yyin  = stdin;
FILE *yyout = stdout;

Pokud v naší funkci main() napíšeme

yyin  = fopen("input", 'r');
yylex();

Při tom je důležité vědět, že existuje funkce yywrap() z knihovny libfl, která se používá k rozhodování, zda je analyzátor na konci. Můžete si ovšem napsat vlastní verzi této funkce, která bude nastavovat proměnnou yyin na základě nějakého seznamu, a tím zajistíte zpracování více než jednoho souboru (což je výchozí chování).

Generování analyzátorů v C++

Časy se mění a tak i do tradičních vod unixových nástrojů pronikl jazyk C++. Zároveň s tím se objevil požadavek na generátor analyzátorů pro tento jazyk. Dalo by se říct, že flex podporuje dva způsoby, jak toho dosáhnout.

Prvním a ne zcela čistým způsobem je napsat kód v C++, soubor vygenerovat a nakonec doufat, že půjde přeložit překladačem C++. Přitom je nutné mít na paměti, že řetězce jsou pouze pole znaků, nebo že yyin není proud z C++, ale klasický soubor z C. Nicméně v dobách, kdy překladače (a standardní knihovna C++) nestály za nic, toto bylo asi rozumné řešení.

Dnes je lepší použít přepínač -+ (případně wrapper flex++), který vygeneruje čistokrevný C++ kód. Důležité je potom rozhraní dvou tříd definované v souboru FlexLexer.h — FlexLexer a jeho potomek yyFlexLexer. Funkce a globální proměnné, které jsme používali v C verzi, se potom změní na metody jedné z těchto dvou tříd. Bohužel řetězce jsou pořád definovány jako pole znaků a ne jako std::string. Funkce main() potom může vypadat přibližně takto:

int main()
{
	FlexLexer* lexer = new yyFlexLexer;
	while(lexer->yylex() != 0);
	return 0;
}

Nevýhody

Nevýhoda je jedna: vygenerovaný analyzátor je pomalejší a náročnější na strojové prostředky než ručně napsaný protějšek. Navíc s pomocí konečného automatu není napsání analyzátoru nic těžkého. Na druhou stranu je definice analyzátoru kompaktnější a snadněji udržovatelná. Velice pěkně to ilustruje příklad na wikipedii (Lexical analysis), kde je ručně napsaný analyzátor jazyka PL/0 (který stvořil Niclaus Wirth, takže odpůrci Pascalu byli varováni) a jeho protějšek v lexu. Asi 100 řádků ručně napsaného kódu oproti 50 řádkům v lexu, které se ovšem rozgenerují na asi 1700 řádků v C (nebo 1500 v C++).

Závěr

Dnes jsme se stručně seznámili s klasickým unixovým nástrojem (f)lex, který slouží ke generování lexikálních analyzátorů. Programů, které rozpoznávají kousky (lexémy, tokeny) syntaxe programovacího jazyka. Poznali jsme jeho výhody (rychlost tvorby, snadná udržovatelnost), ale i nevýhody (malý výkon, větší spotřeba systémových prostředků). Dnešní díl byl zaměřen na programátory v C (a trochu v C++) a aby to ostatním nebylo líto, přidám odkazy na obdobné nástroje pro ostatní jazyky.

JLex	Generátor analyzátorů pro Javu.
JFlex	Rychlý generátor analyzátorů pro Javu.
shlex	Modul pro psaní jednoduchých analyzátorů v Pythonu.
Plex	Generátor analyzátorů pro Python.
Cslex	Generátor pro C#.
Parse::Lex	Modul pro jazyk Perl.
lexer	Balíček lexer pro Common Lisp.

       

Komentáře

[Tom.š Ze.le.in]

Nějak jsem nenašel onen seznam fází, který bych čekal za dvojtečkou :)

Samotný překlad se sestává z několika fází:

Ale jinak vcelku přehledný článek. I když možná, když už byl na konci Lisp zmíněn, by neuškodila poznámka o tom, že některé jazyky (CL, Forth, ale do určité míry i třeba TeX) syntaxi mohou předefinovávat za chodu a obecný lexer nesvázaný s jazykem (byť pro parsování základní syntaxe sexpů téměř triviální) se ve flexu (ale i jako konečný automat) píše špatně.

Popravdě řečeno, docela se na další díly těším - už proto, že jsem zvědavý, jestli se autorovi podaří napsat text dostatečně obecně, aby byl platný i pro exotičtější jazyky...

[Michal Vyskočil]

Nějak jsem nenašel onen seznam fází, který bych čekal za dvojtečkou :)

Nakonec jsem se rozhodl ty fáze uvádět postupně v dalších dílech

Ale jinak vcelku přehledný článek. I když možná, když už byl na konci Lisp zmíněn, by neuškodila poznámka o tom, že některé jazyky (CL, Forth, ale do určité míry i třeba TeX) ...

Common Lisp se momentálně učím, ale bohužel to má poměrně malou důležitost a tak to jde pomalu . Ale pokusím se ho nevynechat, protože se mi ten jazyk líbí, i když jsem odkojený imperativními jazyky.

[deda.jabko]

pokud mate zajem o lisp a nechce se vam moc ucit, doporucuji jeho dialekt scheme. specifikace celeho jazyka se vleze ve srovnani s clispem na par stranek, vystaci si asi s desitkou primitiv, zbytek konstrukci jazyka jde odvodit, takze implementace jde nacpat do 1000 radku v cecku. ...sice byl puvodne navrzen jako vyukovy jazyk, ale jde bez problemu pouzit i v praxi. (bez problemu myslim, ze vas vsichni budou povazovat za exota)

[Marek Bernát]

To máte síce pravdu, ale pochopiť Lisp ako taký a naučiť sa v ňom myslieť trvá určite dlho v každom dialekte. Alebo nie? Rád si nechám poradiť, pretože tiež sa práve učím Common Lisp a nevidím v tom problém, okrem toho, že to bude trvať zopár rokov, ale tak to proste je so všetkým

[deda.jabko]

souhlasim s vami, naucit a pochopit jsou dve naprosto odlisne kategorie. (i kdyz nekteri moji kolegove jsou schopni mezi to dat rovnitko a ridit se tim) a tak mozna by bylo lepsi rikat naucit se clisp a pochopit funkcionalni programovani.

btw. ono to je stejne jedno, protoze po case prace s lispem, budete i v cecku psat rekurze misto cyklu a makra na desitky radek. ;-]

[Marek Bernát]

Ale na druhej strane, je funkcionálne programovanie a funkcionálne programovanie. V Haskelli sa mi funkcionálne robilo oveľa pohodlnejšie ako v Lispe. Lisp dáva skôr možnosť oveľa väčších abstrakcií, presahuje hranice funkcionálnych jazykov. Aspoň mi to tak pripadá. A všade aj tvrdia, že Lisp nie je funkcionálny jazyk, ale jazyk podporujúci túto paradigmu.

Hehe, ja som sa už teraz po relatívne krátkej dobe s Lispom pristihol, že píšem viac makier v C++, hoci som ich kedysi odsudzoval, kvôli tomu, že robia kód nečitateľným a nebezpečným. Ale podľa mňa je to tak správne, pretože začiatočníci robia desné makrá, lebo nechápu ich podstatu. Chce to čas, hovorím ja

[Lukáš Zapletal]

ANTLR - kvalitní a stabilní lexikální analyzátor pro Javu (a nejen to).

[Michal Vyskočil]

Vím, ale seznam obsahuje pouze generátory analyzátorů. Na parsery dojde řada v příštích dílech.

[Pavel Křivánek]

Ve Smalltalku metoda jménem if: standardně neexistuje, správně se jmenuje ifTrue:

Do seznamu generátorů překladačů bych ještě doplnil geniální SmaCC právě pro Smalltalk.

[mikro]

perfektny clanok. trochu som sa bal po predoslych dieloch (a to som spominanu problematiku mal aj na VS), ale teraz ste mi otvorili oci. flex je fakt spica nastroj.