Kompiler - Část 1 , Lexical Scanner |  |
Pokrok :) Hotový projekt Z obrázku se asi dá pochopit že v téhle lekci vytvoříme první část kompileru jejíž název zní líp v angličtině než v čestině, čili budu používat anglický název. Co tento modul má za úkol už jsem říkal v teorii, ale pro ty co ji nečetli připomenu, že má za úkol rozdělit posloupnost znaků/symbolů na klíčová/povolená slova. I když posloupnost znaků může znít jako namakaný pojem, myslí se tím jen nějaký text. Pro počítač to ale nic jiného než posloupnost znaků není. To je důležité vědět. On nemá páru o tom že soubor který jsme mu dali zpracova obsahuje nějaký skript. Mohl by to klidně být nějaký román. Počítači to bude jedno, proto musíme skript převést do reprezentace pomocí čísel, přesně řečeno datových struktur, kterým už bude počítač lépe rozumět a se kterými se bude lépe pracovat. Také jsem říkal, že psát takový modul od začátku by si vyžádalo spoustu času na vychytání všech chyb. Naštestí tvorbou kompileru se lidé zabývají od počítačového pravěku a tak za tu dobu vznikly nějaké prográmky, které tento proces ulehčují a automatizují úlohy které jsou pro každý kompiler stejné, jako je právě tato část. Prográmek který nám vygeneruje lexikální skener se jmenuje flex a je většinou standartní součástí vývojářských balíků většiny linuxových distribucí. Pro Windows je nutné si ho stáhnout ze netu nebo ze sekce Ke stažení. Ačkoliv je počítačový software na vysoké úrovni, flex zatím nefunguje tím způsobem, že bychom mu řekli: "hele, ptřebuju lexikální skener pro můj jazyk, tak bys na tom měl začít makat!". Říct mu to nelze, je třeba to napsat :). Flex potřebuje vědět jaké symboly se mohou ve zdrojovém souboru který bude zpracovávat vyskytovat. To mu sdělíme pomocí jiného souboru, kterému se dává pípona .l a jehož strukturu si hnedle popíšeme. Lex soubor (vstupní soubor pro flex) se skládá celkem ze tří částí které jsou odděleny symbolem %%. ### Struktura souboru lex: `definice %% pravidla %% funkce` Flex pro nás podle takového souboru vygeneruje .c soubor, tedy zdrojový kód lexikálního skeneru v jazyce C, který je pak nutné zkompilovat nebo zakomponovat do nějakého projektu. První část kterou jsem označil `definice` slouží, jak už název možná napovídá, k definování proměnných které budeme používat v programu či k vložení potřebných hlavičkových souborů. Tato část bude přímo zkopírována do vygenerovaného souboru, čili je nutno dodržet syntaxi C nebo C++, podle toho na jakém kompileru budete soubor kompilovat. Část `pravidla` slouží k definování výrazů pro rozpoznávání řetězců, symbolů které jsou povoleny v souboru který bude lexikální skener zpracovávat. Proč budeme potřebovat nějaké výrazů? Říkal jsem že lexikální skener bude potřebovat znát všechny symboly které náš jazyk podporuje,jako třeba klíčová slova. V případě klíčových slov je to snadné, to stačí napsat třeba jen if, a skener bude vědět že v souboru může být takový symbol a už máme zajištěno že nám toto klíčové slovo pro rozhodovací blok nenahlásí jako neplatné. Co ale takové řetězcové konstanty? Řetězce budeme také potřebovat. Nebo názvy proměnných. Je nemožné je do souboru všechny vypsat, že? Proto budeme muset použít výrazy kterým flex rozumí, abychom mu řekli jak pozná řetězcovou konstantu či proměnné. O těchto výrazech si povíme za chvíli. Poslední část `funkce` je také přímo kopírována do vygenerovaného souboru a slouží k definici funkcí včetně těl funkcí, tj. ne jen prototypů. Prototypy můžete napsat do první části. ### Příklad: `%{ #include <stdio.h> %} %% \n printf("Novy radek\n"); [ \t]+ /*nic nedelej, jen to preskoc*/ \"[^\"\n]*\" printf("Retezec\n"); [0-9]* printf("Cele cislo\n"); [0-9]*"."[0-9]* printf("Desetinne cislo\n"); if printf("IF\n"); exit printf("EXIT\n"); "+" printf("Plus"); . printf("Neplatny znak\n"); %% int yywrap(void) { return 1; }` V ukázkovém lex souboru vidíte všechny tři části. V první části jsem jen vložil hlavičkový soubor stdio.h kvůli funkci printf. V poslední části je definice funkce yywrap. Lexikální skener vygenerovaný programem flex tuhle funkci používá a přesto že by mělo být její tělo vygenerováno také, je vygenerován jen prototyp. Kdybychom ji nepřipsali ručně, kompiler by nahlásil chybu. Ani nevím co ta funkce má dělat, ale to pro nás stejně není důležité. Stačí vědět že do jejího těla stačí napsat return 1 a bude to fungovat správně (našel jsem to v nějakém návodu na používání flex nebo v nějakém tutoriálu). V prostřední části jsem definoval symboly které jsou pro lexikální skener platné (to jsou ty výrazy co nedávají moc smysl, zatím) a akce které se provedou pokud lexikální skener takový symbol najde. Špatně se to popisuje, takže se radši podívejte co lexikální skener definovaný tímto příkladem vypíše pokud mu zadáte zpracovat takovýhle vstup: Vstup: IF "retezec" + 789 exit 000.0456 chyba Výstup: Neplatny znak Neplatny znak Retezec PlusCele cislo EXIT Desetinne cislo Neplatny znak Neplatny znak Neplatny znak Neplatny znak Neplatny znak Novy radek Vidíte, že pokaždé když skener narazí na platný symbol, spustí akci což je v tomto případě jen vypsání textu. Pokud symbol povolen není, vypíše se hláška "Chybný znak". Vidíme že v ukázkovém řetězci je neplatné už slovo IF. V lex souboru je sice definován if, ale ten je s malými písmeny. Jak vidíte dále, řetězcová konstanta, celé číslo, desetinné číslo, plus i exit prošly bez problému. Problémy činí až zase slovo chyba, které by muselo být v uvozovkách aby prošlo. Myslím, že je na čase vysvětlit si jaký význam mají ty plusy, hvězdičky a hranaté závorky a jak to že se podle toho pozná, že jde o řetězec nebo o číslo. Pomocí těchto znaků se tvoří tzv. regurélní výrazy kterými je možné popsat jakýkoliv typ řetězce/symbolu. Opět se to špatně popisuje. Čtěte dál a snad to bude jasnější. Regurélní výrazy mohou být použity k popsání celé řady řetězců. ### Regurélní výrazy
Výraz: | Význam:
--- | ---
. | Kterýkoliv znak kromě nového řádku.
\n | Nový řádek
+ | Jedna nebo více kopií výrazu..
* | Žádná nebo více kopií výrazu.
? | Žádná nebo jedna kopie výrazu.
| | Nebo. Logický součet.
"a+b" | Řetězec a+b.
^ | Negace. Znamená všechno co nenásleduje za tímto znakem.
[] | Jeden ze znaků uvedený v závorce.
Z tabulky to také většinou není jasné. Vždycky je nejlepší příklad. Výraz ahoj+ odpovídá řetězcům: ahoj, ahojj, ahojjj, ahojjjj ... Výraz [abc] je jeden ze znaků: a, b nebo c. Výraz [ \t\n]+ odpovídá "bílému místu". Respektive, jde o jeden nebo více výskytů znaku mezera, tabulátor nebo nový řádek. Pravidla jsou vyhodnocována v tom pořadí jak je zapíšeme. Probereme si teď pravidla z našeho ukázkového souboru. První byl \n, což je jen nový řádek a také jsme o tom vypsali zprávu. [ \t]+ je jeden nebo více výskytů mezery nebo tabulátoru. Toto pravidlo nemá přiřazenou žádnou akci, to znamená že se tyhle znaky budou jednoduše přeskakovat. \"[^\"\n]*\" představuje řetězcovou konstantu. Uvozovky není možné stejně jako v C zapsat normálně, musíme k tomu použít ješte lomítko. Zbytek uvnitř hranatých závorek říká, že se v uvozovkách může vyskytovat všechno kromě dalších uvozovek a nového řádku. Hvězdička za závorkou jak už víme z tabulky říká že se to všechno co vyhovuje vnitřku závorky může vyskytnout vůbec nebo vícekrát :). Výraz [0-9]* pro řetězce jenž reprezentují celá čísla vám je nyní určitě také jasné. Čárka mezi znaky 0 a 9 představuje rozmezí, čili platný řetězec splňující tento výraz obsahuje jeden nebo více symbolů od 0 do 9 a to je celé číslo. Obdobně jako pro celá čísla máme i výraz pro čísla desetinná [0-9]*"."[0-9]*. Je to to samé jako v případě celých čísel, jen je to uvedeno dvakrát a uprostřed je tečka jako desetinná čárka. Před desetinnou tečkou i za desetinnou tečkou může být libovolný počet číslic od 0 do 9. Zvolil jsem ty jednodušší příklady. V našem skriptovacím jazyce budou podmínky pro celá a desetinná čísla trochu jiné, pač tam nebude povoleno zapsat čísla jako 00005 nebo 00005.25 ale musí to být 5 nebo 5.25. Prostě zbytečné nuly na začátku čísla jsou jinak naformulovaným výrazem zakázány, považovány za chybné. V tomto příkladě taková čísla platí. Pak už následuje jen if pro klíčové slovo if, exit pro klíčové slovo exit a + pro operátor sčítání nebo jednoduše symbol plus. Poslední je tečka jenž má přiřazenu akci výpisu chyby. Tečka jak víme z tabulky znamená kterýkoliv znak kromě nového řádku. Protože je tento výraz uveden jako poslední a když se něj lexikální skener dostane, je jasné že vstupní řetězec nebo znak nevyhovuje žádnému z předchozích pavidel a nemá proto v souboru co dělat. Doufám že jste aspoň trochu pochopili jak popsat lexikální skener pomocí regurélních výrazů. Takže přihustíme a podíváme se na lex soubor lexikálního skeneru pro náš kompiler. ### Lex soubor pro Universal Script Language: `/* basic language like c flex file*/ %{ #include "common.h" #include "lang.tab.h" #include #include "error.h" extern int line_number; int rem_depth = 0; %} %x remarks %% /*zvlastni skupina pravidel pro rozpoznavani komentaru*/ { \n line_number++; "*/" {rem_depth--; if (!rem_depth) BEGIN(INITIAL);} "/*" {rem_depth++;} "//"[^\n]* /*ignoruj jednoradkovy komentar*/ <> yyerror("Unclosed Comment!"); [^*/\n]* /*ignoruj vsechno co neni *, / nebo novy radek*/; . /*ignoruj vse ostatni*/ } [ \t]+ /*ignoruj jeden ci vice vyskytu tabulatoru ci mezery*/ "/*" {rem_depth++; BEGIN(remarks);}; \n line_number++; "//"[^\n]* /*ingnoruj jednoradkove komentre, tj vsechno co je po // a neni to novy radek*/ if return tIF; else return tELSE; for return tFOR; while return tWHILE; function return tFUNCTION; return return tRETURN; extern return tEXTERN; int return tINT; string return tSTRING; double return tDOUBLE; void return tVOID; "N/A" return tNA; "&&" return tAND; "==" return tEQUALS; ">=" return tGEQUALS; "<=" return tLEQUALS; "!=" return tNEQUALS; "||" return tOR; "++" return tINC; "--" return tDEC; "+=" return tPLUSASSIGN; "-=" return tMINUSASSIGN; "*=" return tMULASSIGN; "/=" return tDIVASSIGN; "%=" return tMODASSIGN; "<<=" return tSHLASSIGN; ">>=" return tSHRASSIGN; "<<" return tSHL; ">>" return tSHR; "&=" return tANDASSIGN; "|=" return tORASSIGN; "=" return '='; ">" return '>'; "<" return '<'; "!" return '!'; "+" return '+'; "-" return '-'; "*" return '*'; "/" return '/'; "%" return '%'; "{" return '{'; "}" return '}'; ";" return ';'; "(" return '('; ")" return ')'; "," return ','; "&" return '&'; //bitovy and "|" return '|'; //bitovy or /*cisla, povolene je bud nula nebo cisla 1 a neco. Nelze mit cisla 007. Ty jsou nepovolena*/ 0|([1-9][0-9]*) {yylval.intconst = atoi(yytext); return tINTCONST;} /* Tohle je pro double cisla. Rika ze to muze byt cislo jako 0.neco, ale ne 000.neco. Nebo cislo muze byt jako libovolny pocet cislic 1-9 pred . a libovolny pocet 0-9 za .*/ (0"."[0-9]*)|([1-9]*"."[0-9]*) {yylval.doubleconst = atof(yytext); return tDOUBLECONST;} true {yylval.intconst = 1; return tINTCONST;} false {yylval.intconst = 0; return tINTCONST;} \"[^\"\n]*\" {yytext[strlen(yytext)-1] = '\0'; yylval.stringconst = strdup(yytext + 1); return tSTRINGCONST;} [A-Za-z_][A-Za-z0-9_]* {yylval.identifier = strdup(yytext); return tIDENTIFIER; } . yyerror("Invalid character '%s'.",yytext); %% int yywrap() { return 1; }` Netrapte se tím, že nevíte co je to tIF, tWHILE nebo třeba tELSE. Psal jsem že potřebujeme skript převést do podoby čísel aby se nám s ním lépe pracovalo. Třeba u konstrukce if (a < b). Tohle počítači nic neřekne. Ale když budeme mít tIF '(' 'a' '<' 'b' ')' je to pro počítač jednodušší, protože je to nějaká konstanta tIF (tj. číslo) a zbytek jsou znaky z ASCII tabulky, tj. vlastně taky čísla. To že má být první tIF, pak závorka atd. a jestli to tak je bude zjišťovat až další modul který vytvoříme v další kapitole. Úkolem lexikálního skeneru je to co jsem právě popsal. Čili akce které se spustí při splnění regurélního výrazu nebude nějaký výpis pomocí printf jak to bylo v ukázkovém příkladu ale return číslo jak to vidíte i v souboru. Klíčová slova jako je if, else, while a další jsou řetězce a ty nemůžeme vrátit jako nějaké číslo, proto máme pro ně nadefinované konstanty (budeme je definovat až v další kapitole) jako tIF. Zbytek jako znaménka aritmetických a jiných operací jsou znaky ASCII tabulky a to jsou vlastně čísla která můžeme vrátit jako výsledek. Flex disponuje také několika předdefinovanými proměnnými. Jistě si říkáte, že je hezké když lexikální skener najde řetězecovou konstantu a vrátí nám číselnou konstantu tSTRINGCONST abychom vedeli ze našel řetězec. Ale kde zůstane ten řetězec co našel? Myslím tím, že zjistí že v textu je "řetězcová konstanta", která vyhovuje výrazu pro řetězcové konstanty. Lexikální skener vrátí konstantu tSTRINGCONST, čímž indikuje že přečetl řetězcovou konstantu. Kde ale zůstane onen řetězec "řetězcová konstanta", ten stále potřebujeme. Na řetězcové konstanty spjaté s nalezeným symbolem ukazuje předdefinovaná proměnná yytext. Jak můžete vidět v lex souboru, je tam použita pro uložení řetězce. Proměnná yylval je určena pro uchovávání hodnoty spjaté s rozpoznaným symbolem. Vidíte v lex souboru, že je používána jako struktura, tj. má členské proměnné intconst, doubleconst, stringconst do kterých ukládáme příslušné hodnoty při nalezení celého čísla, desetinného čísla i řetězcové konstanty. Typ proměnné yylval se dá také nadefinovat, což uděláme v další kapitole aby odpovídala unii kterou používáme a mohli jsme s ní pracovat tak jak s ní pracujeme. Další věc o které je třeba se zmínit je %x remarks a s tím související blok <remarks>{...}. To je způsob jak nadefinovat nějakou skupinu pravidel. Remarks jsem si zvolil. Můžete místo toho napsat cokoliv jiného. Název Remarks jsem zvolil protože v bloku bude uzavřen seznam pravidel která platí pro komentáře. Když se nad tím trochu zamyslíme, jistě bude každý souhlasit že při zpracovávání komntářů nemusíme testovat všechny výrazy jako v případě kódu skriptu. Můžete i odhadnout jak se přepíná na tuto skupinu pravidel. Ze začátku se budou používat hlavní pravidla ab když dojde na pravidlo "/*", přepne se pomocí makra BEGIN (je také definováno flexem) na pravidla v bloku remarks. Můžete si také všimnout že se počítá hloubka komentářů. Tj. komentáře mohou být vnořené ale musí být všechny uzavřené. Když komentář skončí "*/" přepneme se pomocí stejného makra BEGIN na původní pravidla INITIAL. Jinak v souboru myslím už nic tak složitého není. Pokud nerozumíte úplně něktrým pravidlům pro řetězce nebo čísla, určitě je rozluštíte když si k tomu na chvíli sednete a podíváte se do tabulky co jaký znak znamená v regurélním výrazu nebo to pochopíte jako já, někdy v době až budete kompiler hotový a začnete se v něm hrabat sami :) ### Kompilace příkladu: Mohlo by vás také zajímat jak můžete vytvořit z ukázkového lex souboru fungující program :) Není to zas tak složité, ale nejde jen o prosté načtení souboru a jeho zkompilování. K vygenerování lexikálního skeneru budete potřebovat vytvořit lex soubor. To je jen textový soubor s příponou .l do kterého napíšete to co jsem uvedl jako krátký ukázkový lex soubor. Teď přijde na řadu flex. Spusťte flex z příkazové řádky a jako jediný parametr mu zadejte název vašeho lex souboru. Například flex.exe priklad.l. Pokud je soubor vpořádku, objeví se ve stejném adresáři soubor lex.yy.c, který obsahuje kód vygenerovaného lexikálního skeneru. Vytvořte si ve Visual C++ nový projekt - Win32 Projekt - Konzolová aplikace. Bude vygenerován základní projekt s funkcí main. Otevřete vygenerovaný lex.yy.c a celý jeho obsah zkopírujte do vytvořeného projektu. Kurzor nastavte za řádek `#include "stdafx.h"`. Tím kód lexikálního skeneru vložíte za zmíněný řádek a nepřepíšete si funkci main. Pokud to nyní zkusíte zkompilovat, pravděpodobně to skončí s chybami. Například že kompiler nemůže najít hlavičkový soubor unistd.h. Ten si budete muset do adresáře projektu zkopírovat ručně, buď z mého ukázkového projektu nebo je také obsažen u utilitky bison. Tím se to ale ještě nespraví. Ve vygenerovaném lexikálním souboru je soubor vkládán jako systémový hlavičkový soubor, čili `#include <unistd.h>`. Najděte tento řádek a změňte ho na `#include "unistd.h"` a měli by jste mít od této chyby pokoj. Flex ještě generuje funkci main pro vytvořený lexikální skener, která ale platí pro klasické C. Deklarace této main funkce se nachází na konci vygenerovaného souboru, který jste už ale překopírovali do projektu. Já osobně tuto část házím do komentáře. V Projektu to najdete kousek nad funkcí main kterou vygenerovalo Visual C++ (bude až na konci zdrojového souboru). Definice téhle main funkce je uzavřena do `#if YY_MAIN...#endif`. Soubor by měl vypadat asi takhle nějak: flex_example.cpp `#include "stdafx.h" /* A lexical scanner generated by flex */ . . . #include "unistd.h" . . . /*#if YY_MAIN int main() { yylex(); return 0; } #endif*/ #line 20 "priklad.l" int yywrap(void) { return 1; } int _tmain(int argc, _TCHAR* argv[]) { yylex(); return 0; }` Posledním krokem k tomu aby program fungoval je zavolání funkce yylex, která spouští lexikální skener z naší main funkce, jak je to také zvýrazněno ve výpisu. Kompilace by se měla podařit už bez problémů. Po spuštění se vám objeví jen prázdná konzole do které můžete psát. Zkuste tedy napsat nějaký text který z části vyhovuje pravidlům které jsou v ukázkovém souboru definovány a z části ne a po stisku klávesy Enter uvidíte jak si s tím program poradí. ### Projekt pro kompiler Stejně jako jsme před chvílí udělali projekt pro ukázkový lexikální skener uděláme i základní projekt pro kompiler. Opět si vytvořte konzolovou Win 32 aplikaci. Já jsem si ji pojmenoval kompiler. Vložte do projektu nový prázdný zdrojový soubor cpp a do něj zkopírujte obsah soubor lex.yy.c který dostanete když pusíte flex na lex soubor určený pro náš kompiler. To jest ten delší, druhý z těch dvou co jsem tu ukazoval :). Zkopírujte do projektu hlavičkový soubor unistd.h a opravte příkaz pro jeho vložení stejně jako v předchozím případě. To je pro tuto část vše. Kompiler zatím nekompilujte, stejně se vám to nemůže podařit dokud se neprodereme druhou částí. Nemáte zatím definované konstanty jako tIF, tELSE a proto bude kompilace neúspěšná ať se budete snažit sebevíc. Část 2