Kompiler - Část 2 , Parser, AST |  |
Pokrok :) Hotový projekt Vítejte snad v nějtěžší kapitole celého kurzu :) Tady to bude trochu složitější, ale čsem se přes to určitě dostanete, tak jako já když jsem se to učil z anglického tutoriálu. Pokud kapitolu nebudete 100% chápat, přečtěte si ji znovu a znovu, nebo jděte na další části a pochopíte to, jak už jsem říkal v minulé kapitole, až se začnete vrtat v hotovém kompileru a dělat nový pro váš vlastní jazyk. Než jsem celý kompiler pochopil, stačil jsem upravit původní jazyk který jsem vytvořil pomocí anglického tutoriálu a poté vytvořit svůj Universal Scripting Language. V této kapitole také vytvoříme první kompilovatelnou část kompileru. ### Parser, co to je? Tento pojem už jsem vysvětloval v teorii, ale radši si ho ještě zopakujeme. Parser má za úkol zjistit zda symboly ve zdrojovém souboru jdou za sebou v takovém pořadí jak je to správné :) Například cyklus for by měl vypadat následovně: `for ( inicializace; podmínka; aktualizace) tělo_cyklu`. Taková syntaxe je správná, tedy například v C ale i v Universal Scripting jazyce. Když parser narazí v našem skriptu na cyklus for, jeho práce je zjistit zda za klíčovým slovem for opravdu následuje závorka, inicializace, středník, podmínka, středník, aktualizace, závorka a tělo_cyklu. Prográmek nebo funkce co by tohle dělala by nám asi také zabrala dost času kdybychom ji chtěli psát růčo od začátku. Naštěstí tohle je druhá úloha se kterou nám pomůže k tomu určená utilita, totiž bison. Parser vygenerovaný bisonem spolupracuje s lexikálním skenerem vygenerovaným flexem. Jak spolupracuje a jak vůbec funguje si řekneme později, nejdřív se musíme prokousat skrze další teorii :). ### Context-Free Grammar Abychom mohli zjistit jetsli symboly ve zdrojovém skriptu jdou za sebou ve správném pořadí, bude to chtít definovat nějaká pravidla, nějakou gramatiku jazyka. Context-free grammar (nevím přesně jak to přeložit - gramatika nezávislá na kontextu, bez textových souvislostí) se říká gramatice programovacích jazyků. Definuje se pomocí production rules (produkční, výrobní pravidla). Produkční pravidla - opět nic neříkající překlad, některé termíny je asi lepší nechat bez překladu. Kompiler vám naštěstí bude fungovat i pokud nebudete znát terminologii. Tedy měl by :) Ukážeme si příklad jednoduchých produkčních pravidel, která definují syntaxi třeba pro jednoduchou kalkulačku. 1) výraz -> výraz + výraz 2) výraz -> výraz - výraz 3) výraz -> výraz * výraz 4) výraz -> výraz / výraz 5) výraz -> identifikátor 6) výraz -> číslo Začneme u prvního pravidlo. První pravidlo říká, že nějaký obecný výraz může být součtem dvou výrazů. Druhé pravidlo říká, že výraz může být rozdíl výrazů. Obdobně třetí a čtvrté pravidlo pro násobení a dělení výrazů. Páté pravidlo říká, že výraz může být také identifikátor, tj. název nějaké proměnné. Poslední pravidlo zase říká, že výraz může být i číslo. Pomocí těchto pravidel můžeme sestavit například následující výrazy: x + 5 4 - 8 7 * 8 - x 9 / 4 + 4 * 4 Všechny příklady splňují daná pravidla. Například kdybychom chtěli první výraz `x + 5` odvodit podle definovaných pravidel. x splňuje podmínku že výraz může být identifikátor. Číslo 5 splňuje podmínku že výraz může být číslo. Součet x a 5 splňuje podmínku že výraz může být součtem dvou jiných výrazů. Tedy součet x + 5 bereme jako jeden výraz, který se ale skládá z výrazu: x a z výrazu: 5 a ty se sčítají. K úplnosti přihodím ještě dva termíny a to nonterminal a terminal symbol, neboli neukončující a ukončující symboly. Nonterminal se značí symboly na levé straně produkčních pravidel (před šipkou). V případě našich jednoduchých šesti pravidel je nonterminal výraz. Terminal jsou symboly na straně pravé, ale jen ty co už nejsou na levé. V příkladě to jsou aritmetické operátory + - * / a číslo a identifikátor. Ukážeme si ještě odvodit delší příklad `7 * 8 - x`. Správná terminologie by sice byla, že se pokoušíme dokázat jestli z daných produkčních pravidel můžeme odvodit daný výraz. Zdá se mi ale lepší, aspoň k pochopení to brát od zadu od samostatných symbolů a kontrolovat jestli každý vyhovuje nějakému pravidlu a tak dále dokud nezkontrolujeme celý výraz. Jedna z možností jak odvodit/ rozložit příklad: 1) Výraz 7 * 8 - x rozdělíme jako násobení výrazu 7 * výraz (8 - x). 2) Výraz 7 je číslo, dál už rozložit nejde. 3) Výraz 8 - x můžeme rozložit na rozdíl výrazů 8 a x. 4) Výrazy 8 a x již také nejdou dál dělit. Jistě jste si ale všimli že by to šlo udělat i obráceně, jako rozdíl výrazů 7 * 8 a x. Záleží na člověku jak to udělá. Pro strojové zpracování ale tohle není vůbec dobré, stroj se sám nerozhodne jakou cestu zvolí. Navíc u složitějších pravidel a várazů než jsou tyto ukázkové se může stát že pokud zvolíte jednu cestu, výraz bude všechny pravidla splňovat, ale pokud se vydáte druhou cestou, výraz všechny pravidla nesplní a bude brán jako gramatická chyba i když bude správně. Budeme muset ujít ještě kousek cesty než se pustíme do psaní produkčních pravidel pro Universal Script jazyk. ### Parse Tree a nejednoznačné definice Možná jste si všimli, že předešlé příklady jsme rozebírali do jakéhosi stromu (parse tree),i když jsme postupovali od zadu, od listů po kořen. Také z posledního příkladu `7 * 8 - x` víme, že se dá rozložit dvěma způsoby, což vede k nejednoznačnému stromu. A to jak víme není dobře. Člověk sice pozná, že by měl nejprve provést opraci násobení a pak teprve odčítání. Počítač to ale neví a je mu jedno jakou cestu zvolí. Každá ze dvou možností nám navíc dá jiný výsledek z nichž jeden musí být špatně. Kde se tento problém vlastně bere? Je to způsobeno produkčními pravidly která dovolují takový výraz zapsat. Díky tomu je i gramatika našeho jazyka nejednoznačná. Nyní obrázek jak vypadají oba stromy, pro obě možnosti. Doufám že obrázek objasnil pojem parse tree (je to strom do kterého rozložíme zkoumané řetězce). Co ale teď s tím. V kompileru potřebujeme aby byl vytvořen vždy jen jeden strom a to ten správný. V našem příkladu je to strom číslo 1. Možným řešením by bylo použití závorek, abychom určili co se má vypočítat jako první. Výraz bychom pak mohli napsat jako: `(7 * 8) - x` nebo `7 * (8 - x)` To náš problém ale neřeší. I tak zústává gramatika jazyka nejednoznačná. Nemůžeme člověka nutit aby pomocí závorek udával postup výpočtu. Ne že by to nešlo, ale jendnoduše by to uživatele "štvalo". Správně určitě přemýšlíte o tom, že by bylo dobré nadefinovat prioritu aritmetických operátorů. Tak jak to známe ze základní školy. Každý víme že násobení a dělení má přednost před sčítáním a odčítáním a my potřebujeme, aby to věděl i náš parser. Pokud to bude vědět, může produkovat vždy správný a jediný strom. Nadefinujeme-li který operátor má přednost před kterým, stane se gramatika jednoznačná a nebudou vznikat žádné situace kdy by parser/počítač nevěděl co má dělat. ### Shift-Reduce Parse Technique Název téhle části se také nepřekládá zrovna nejlépe, ale znamená to něco jako technika analýzy pomocí posuvné redukce. No, když si to řeknu samotné, nic moc mi to něříká. Opět ale není důležité vědět jak se tomu říká ale pochopit to a použít to. Není to nic složitého. Jde o techniku jak parser zjišťuje zda jdou symboly za sebou ve správném pořadí. Tuto techniku bude používat i parser který vygenerujeme pomocí utility bison. Již v první lekci jsem psal že parser spolupracuje s lexikálním skenerem. Možná jsem to psal obráceně :) Parser volá funkci yylex, která něco udělá pokaždé když najde ve zdrojovém souboru platný symbol. Lexikální skener, který jsme vytvořili, vrací nějaké číslo, které říká co bylo přečteno. Například číselná konstanta. Parser si uloží na zásobník to co mu funkce yylex vrátí a pokračuje čtením dalšího symbolu. Když hodnota/ty které má parser na zásobníku odpovídají nějakému produkčnímu pravidlu, pokud je parser může zredukovat pomocí nějakého pravidla, tak všechny tyto hodnoty ze zásobníku vyndá a uloží je do jednoho výrazu který uloží zpět do zásobníku. Opět si to ukážeme na příkladu: `x + 5`. 1) Je přečten symbol x a ten je uložen na zásobník parseru. 2) Parser zjistí že x odpovídá pravidlu pro výraz. Vyjme x ze zásobníku a uloží jej tam znova, jen s informací, že je to výraz-identifikátor. 3) Dále je čten symbol +, který je také uložen na zásobník. 4) Dále je přečten symbol 5. Je uložen na zásobník. 5) Parser zjistí že 5 odpovídá pravidlu pro výraz. Vyjme 5 ze zásobníku a uloží jej tam znova, jen s informací, že jde o výraz-číslo. 6) Parser zjišťuje, že má na vrcholu zásobníku 5, pod ním + a na nejnižší pozici je x. To odpovídá pravidlu pro sčítání výrazů. Vyjme ze zásobníku tyto tři hodnoty a na vrchol zásobníku uloží jednu hodnotu, spíše objekt. Bude to výraz-sčítání dvou výrazů, který bude vědět že na levé straně od plus má identifikátor x a na straně pravé číslo 5. Abych tady nemlžil jak je parser chytrý, on vlastně sám o sobě neví o tom že 5 je číslo a x je identifikátor a neumí ukládat informace o tom co je co. On umí jen rozpoznat zda to co má na zásobníku odpovídá nějakému pravidlu a pokud ano tak spustí nějakou akci, kterou nadefinujeme podobně jako v případě když jsme vytvářeli lexikální skener. Pospal jsem to tímto způsobem jen proto, že takhle bude pracovat náš parser. Jiný parser by klidně mohl dělat to, že kdyby zjistil že má v zásobníku součet dvou výrazů, vypsal by na obrazovku pomocí printf: našel jsem sčítání výrazů. Pochopit jak pracuje parser je snad nejdůležitější věc v téhle kapitole. To znamená chápat jak ukládá na zásobník a zjednodušuje. V dalších odstavcích pochopíte i to o těch dodatečných informacích, jako že jde o čísla, identifikátory atd. Následuje grafické vyjádření ukázkového příkladu. Na obrázku vidíte jak je zpracován výraz `x + 5`. Ty obdélníčky představují zásobník parseru :) Situace 1 - 6 odpovídají tomu co jsem se snažil popsat v bodech 1 - 6 o odstavec výše. Obecně tedy parser dělá toto: 1) Načte symbol který uloží na zásobník. 2) Pokud je v zásobníku obecně například C B A a tomu odpovídá pravidlo A B C, parser vyjme hodnoty ze zásobníku a zredukuje je pomocí pravidla A B C. Pokračuje krokem 1. ### Od teorie k praxi Uf, prošli jsme dost teorie a každý z vás se určitě těší, že bychom to konečně mohli začít prakticky používat. Na předchozím obrázku jste viděli jak je zredukován výraz x + 5. Jak parser po poznání že má na zásobníku x vezme x ze zásobníku a uloží ho tam znovu jen s informací, že jde o výraz typu identifikátor. To je hezké, ale musíme to naprogramovat sami. Tj. že parser takové informace sám nedoplní. Jak by se to dalo lehce zvládnout? Odpovědí je, že každý povolený symbol Universal Scriptu bude reprezentován ve stromu který vytvoří parser pomocí datové struktury. Takový strom do kterého parser rozloží skript bude podobný tomu jaký jste viděli na jednoduchém příkladu na prvním obrázku v této kapitole. Každý jeho uzel bude ale struktura která bude reprezentovat nějakou část skriptu. Třeba probírané sčítání výrazů. Budeme mít strukturu reprezentující výraz. Pro výraz sčítání v ní bude uložena informace že jde o sčítání a bude obsahovat ukazatele na levý a pravý operand. V případě x, tj. levý operand v příkladě, bude ukazovat na strukturu která obsahuje informace o identifikátoru. V případě čísla 5 bude ukazatel ukazovat na strukturu výraz která má v sobě uloženu celočíselnou konstantu. Budeme používat `union`, unie, takže pokud jste je zapoměli, tak si je zopakujete, jako já. Až u kompileru jsem si vzpoměl že to existuje a k čemu se to hodí. Všechno tedy bude mít svou strukturu. Může vám to připadat jako že to bude zabírat moc paměti. Ano, nějakou paměť to sežere. Ale uvidíte, že v takové podobě do stromu uspořádaných struktur se bude skript analyzovat mnohem snadněji než v jeho textové podobě. Mimochodem takovému stromu, který vytvoříme pomocí parseru se říká Abstract syntax tree - AST. Soubor skriptu může obsahovat definici několika funkcí, které spolu nemusejí souviset. Nemusejí se navzájem volat. Mohou to být například funkce pro nějaké matematické výpočty. Můžeme tedy pro vyjádření toho, že skript bude obsahovat těla funkcí použít následující produkční pravidlo: skript -> funkce To sice funguje, ale znamená to že skript může obsahovat právě jednu funkci. Ne míň a ne víc. My ale chceme mít v souboru víc funkcí. Potřebujeme proto zapsat že skript se může skládat z nějakého pole funkcí, nebo že jich prostě může být víc než jedna. To by se dalo udělat například takhle: skript -> toplevels toplevels -> toplevel toplevels -> toplevel toplevels toplevel -> funkce Vypadá to možná složitě, ale není. toplevels a toplevel jsme přidali abychom mohli popsat libovolný počet opakování. První pravidlo tedy říká, že skript se může skládat z nějakých toplevels (vyšších úrovně). Toplevels pak může být toplevel nebo to může být toplevel následovaný toplevels podle pravidel 2 a 3. Ale protože toplevels na pravé straně pravidla 3 jde rozložit dále podle pravidla 2, je to vlastně jako kdybychom napsali toplevels -> toplevel toplevel toplevel.... Jenomže takovým pevným zadáním nemůžeme nikdy popsat libovolný počet prvků. Už vidíte ten způsob vytvoření pravidla pro popis více stejných prvků za sebou? Je fakt že bychom místo toplevel mohli psát rovnou funkce: skript -> toplevels toplevels -> funkce toplevels -> funkce toplevels Tohle by taky šlo. Ale co kdyby jste chtěli později přidat nějaké konstrukce, jako podprogramy, třídy a já nevím co ještě. Museli by jste pracně předělaávat pravidlo pro toplevels. Kdežto když ponecháte toplevel, zůstane pravidlo pro toplevels stejné a nové věci přidáte pod toplevel: skript -> toplevels toplevels -> toplevel toplevels -> toplevel toplevels toplevel -> funkce toplevel -> trida toplevel -> podprogram toplevel -> rozhrani Zmíněné konstrukce ale přeci jenom nejsou ještě zcela úplně správné. Taková pravidla by nepovolila soubor skriptu kde by nebylo nic, tj. prázdný soubor. To by bylo bráno jako chyba. Ano, může to být bráno jako chyba, ale my pokus zkompilovat prázdný soubor jako chybu brát nebudeme a upravíme pravidla tak aby soubor mohl obsahovat 0 a více funkcí: skript -> toplevels toplevels -> /* nic */ toplevels -> netoplevels netoplevels -> toplevel netoplevels -> toplevel netoplevels toplevel -> funkce Tato pravidla už povolí 0 a více funkcí. Předpona ne před toplevels znamená non-empty. To že něco nemusí obsahovat žádné složky definujeme tak že na pravou stranu pravidla prostě nic nenapíšeme. Já jsem tam napsal komentář, aby to nevypadalo, že jsem tam snad něco napsat zapoměl. Doufám že se mi tohle podařilo aspoň trochu vysvětlit a půjdeme dál. Z výše uvedených pravidel, která platí už pro Universal Script můžeme možná vyčíst, jaké tři základní struktury budeme potřebovat. Kořen stromu bude reprezentovat struktura SCRIPT. Další bude struktura TOPLEVEL a třetí FUNCTION. Ve stromu bude jedna instance struktury SCRIPT, která bude představovat kořen stromu. Bude také obsahovat ukazatel na první strukturu TOPLEVEL. Tato struktura zase obsahuje ukazatel na další strukturu TOPLEVEL, pokud existuje a ukazatel na strukturu FUNCTION, která bude reprezentovat funkci. Vlivem definovaných pravidel víme, že ukazatel na strukturu TOPLEVEL ve struktuře může být NULL. Tj. případ že ve skriptu nebude definována jediná funkce. Pokud ale bude ve skriptu minimálně jedna funkce, tento ukazatel bude platný a bude též platný ukazatel na strukturu FUNCTION ve struktuře TOPLEVEL. A pokud ne, může to být jen vlivem nějaké vyšíí moci nebo příčinou jiné chyby která se objeví jednou za tisíc let a kterou jsem tím pádem ještě neodchytil :) Pojďme se podívat jak jsou tyto struktury definovány: `struct SCRIPT { int line_number; //cislo radku struct TOPLEVEL* toplevels; //ukazatel na toplevel class CHashedSymbolTable* symbolTable; //tabulka symbolu }; //**************************************************************************************************************** /*struktura predstavujici vetve stromu pokud uz existuje, ukazatel na funkci musi byt vzdy platny */ //**************************************************************************************************************** struct TOPLEVEL { int line_number; FUNCTION* function; //ukazatel na funkci TOPLEVEL* next; //dalsi toplevel }; //**************************************************************************************************************** /*struktura predstavujici funkci*/ //**************************************************************************************************************** struct FUNCTION { FunctionKind kind; int line_number; /*co se tyka primo funkce*/ struct TYPE* type; char* name; //jmeno funkce char* signature; //sem se ulozi jmeno a podpis fce bool returns_value; //zjisti jestli fce vraci hodnotu struct DECLARATION* declaration; //argumenty funkce struct STATEMENT* statements; //telo funkce class CHashedSymbolTable* symbolTable; //tabulka symbolu funkce int localsLimit; // int labelCount; //pocet navesti ve funkci struct LABEL* labels; //vsechna navesti vyskytujici se ve funkci class CInstruction* opcodes; /*spojovy seznam struktur typu CODE predstavujicich kod funkce v assembleru jazyka */ char* library; //z jake knihovny fce je };` V každé struktuře můžete vidět člen line_number, což je jen číslo řádku na kterém se funkce vyskytuje a je to využito pří hlášení chyb. Ukazatel na strukturu TOPLEVEL ve struktuře SCRIPT a stejně tak uazatel na strukturu FUNCTION a další TOPLEVEL ve struktuře TOPLEVEL. Se zbytkem členů se seznámíme během dalších částí. Struktur je v kompileru mnohem více, ale nebudu je sem všechny kopírovat. Je to jednak zbytečné a jednak je toho mooooc. Budete muset také chvíli studovat zdrojáky, které jsou doufám dostatečně okomentované. Myslím že už se můžeme pomalu vrhnout na utilitku bison a na popis jejího vstupního souboru. ### Soubor pro bison(a) Je jako v případě utility flex rozdělen do tří částí... `definice %% pravidla %% funkce` První část slouží k definici symbolů - znaků, které se mohou v souboru vyskytnout. Lépe řečeno, stejně jako potřebuje lexikální skener vygenerovaný flexem vědět jaké znaky či symboly má považovat za platné aby mohl vracet jim příslušné číselné konstanty, když je najde, potřebuje parser vygenerovaný bisonem vědět s jakými konstantami může počítat. V minulé lekci jsem psal ať se netrápíte s konstantami jako tINT, tIF, tWHILE, že je nadefinujeme zde. Definice těchto konstant se provede tady. Ne ale tak jak to děláme v C, ale pomocí slova %token konstanta. Tj. například %token tIF. Když jich chceme napsat víc, můžeme před každou konstantu napsat %token, nebo je můžeme psát za sebou oddělené mezerou. V první části můžeme uvést také klasický céčkový kód, který musí být opět uzavřen mezi %{...%}. Do prostřední části se píší samotná produkční pravidla. Píše to stejně jako jsem to psal v příkladech výše, jen s tím rozdílem že místo šipky je dvojtečka a spojka nebo není chápana tak že bychom napsali nový řádek s pravidlem jak se může něco dělit dál, ale používá se znak |. Příklad bude asi jednodušší :). Tahle pravidla: skript -> toplevels toplevels -> /* nic */ toplevels -> netoplevels netoplevels -> toplevel netoplevels -> toplevel netoplevels toplevel -> funkce zapíšete do části pro pravidla takto: skript : toplevels toplevels : /* nic */ | netoplevels netoplevels : toplevel | toplevel netoplevels toplevel : funkce Nyní už si ukážeme soubor pro bison(a) z kterého bude vygenerován parser pro kompiler Universal skriptu: `/*bison file for Universal Scripting Language v 1.0 */ %{ #include <stdio.h> #include <string.h> #include <malloc.h> #include "error.h" #include "tree.h" /*prototyp funkce yylex*/ int yylex(); extern SCRIPT* theScript; %} /*Token definitions radek %start script urcuje startovni symbol od ktereho se pokusime skript odvodit. je dulezite vedet kde yacit, nemuzeme zacit skript odvozovat od jakehokoliv prikladu. zacneme od zacatku*/ %start script /*tato unie v sobe schovava vsechny datovy typy ktere mohou mit uzly v AST stromu.*/ %union { struct SCRIPT* script; /*kolekce funkci*/ struct TOPLEVEL* toplevel; struct FUNCTION* function; struct IDENTIFIER *identifiers; struct EXPRESSION* expression; struct DECLARATION* declaration; struct FORINIT* forinit; struct STATEMENT* statement; struct LVALUE* lvalue; struct TYPE* type; char* identifier; //identifikator int intconst; //integer konstanta double doubleconst; //double konstanta char* stringconst; //retezcova konstanta }; /* definice symbolu ktere mimojine vraci funkce yylex. Bison pro ně vygenruje konstanty. Prvni bude mit cislo 258. ASCII tabulka ma 256 znaku, 1 se vynecha a mame 258*/ %token tIF tELSE tFOR tWHILE tFUNCTION tRETURN tAND tEQUALS tGEQUALS tLEQUALS tNEQUALS tOR tINTCONST tSTRINGCONST tIDENTIFIER tDOUBLECONST tINC tDEC tPLUSASSIGN tMINUSASSIGN tMULASSIGN tDIVASSIGN tMODASSIGN tSHLASSIGN tSHRASSIGN tSHL tSHR tANDASSIGN tORASSIGN tEXTERN tINT tSTRING tDOUBLE tVOID tNA /*u nekterych symbolu budeme potrebovat znak jejich puvodni hodnotu a ne jejich repreyentcai v podobe ciselne konstanty. Napriklad tINTCONST repreyentuje ze ve skriptu bylo rozpoznano cislo, tak by se nam hodilo vedet co to bylo ya cislo a ne jen ze to bylo cislo. U takovych symbolu kde se chceme vratit k puvodni hodnote potrebujeme vedet jakeho jsou typu. To je definovane v unii vyse. Tady v nasledujicich ctyrech radkach zacinajicich %token jen dame vedet o ktere jde. Potom tedy tIDENTIFIER bude ukazatel na retezec, tINTCONST integer cislo atd.*/ %token <identifier> tIDENTIFIER %token <intconst> tINTCONST %token <stringconst> tSTRINGCONST %token <doubleconst> tDOUBLECONST /*nasledujici radky vlastne definuji datovy typ uylu v AST stromu. Datove typy jsou definovany v unii vyse a my tady rekneme jakym uzlum ve stromu prislusi. */ %type <script> script %type <toplevel> toplevels netoplevels toplevel %type <function> function %type <identifiers> identifiers %type <expression> initialization expression unaryexpression unarypostfixexpression exps neexps %type <declaration> declaration formals simpledeclaration neformals formal %type <forinit> forinits neforinits forinit %type <statement> nestatement statement compoundstatement %type <lvalue> lvalue %type <type> type /*vyporadani se s konflikty ) a else*/ %left ')' %left tELSE /*priorita operatoru i kdyz je to matouci, tak nejnizsi prioritu maji operatory z prvniho radku. Pise se to tedy o nejniysi priority k nejvyssi, i kdyz logictejsi by to mozna bylo obracene. Nejvyssi prioritu ma tedy %. To ze maji operace prirazeni nejnizsi prioritu dava smysl. pac nejdriv vzdycky chceme vyhodnoti celou pravou stranu vyrazu a pak teprve to nekam ulozit. %left znamena ze to plati pro zpracovani zleva doprava> Muzete pouzit i %right pro zpracovai zprava do leva, ale s tim by byly nejake problemy */ %left '=' tPLUSASSIGN tMINUSASSIGN tMULASSIGN tDIVASSIGN tMODASSIGN tSHLASSIGN tSHRASSIGN tANDASSIGN tORASSIGN %left tOR tAND tSHL tSHR '|' '&' %left tEQUALS tNEQUALS tLEQUALS tGEQUALS '<' '>' %left '+' '-' %left '*' '/' %left '%' %% /*produkcni pravidla*/ script : toplevels {theScript = makeSCRIPT($1);} ; toplevels : /*prazdne*/ {$$ = NULL;} | netoplevels {$$ = $1;} ; netoplevels : toplevel {$$ = $1;} | toplevel netoplevels {$$ = $1; $$->next = $2;} ; toplevel : function {$$ = makeTOPLEVELfunction($1);} ; //deklarace promenne nebo vice promennych //jako a = 0; nebo a,b,c = 0; declaration : identifiers initialization ';' {$$ = makeDECLARATIONvariable($1,$2);} ; simpledeclaration : tIDENTIFIER initialization {$$ = makeDECLARATIONsimplevar($1,$2);} ; identifiers : tIDENTIFIER {$$ = makeIDENTIFIER($1);} | tIDENTIFIER ',' identifiers {$$ = makeIDENTIFIER($1); $$->next = $3;} ; initialization : /*empty*/ {$$ = NULL;} | '=' expression {$$ = $2;} ; type : tINT {$$ = makeTYPEint();} | tDOUBLE {$$ = makeTYPEdouble();} | tSTRING {$$ = makeTYPEstring();} | tVOID {$$ = makeTYPEvoid();} ; function : tIDENTIFIER '(' formals ')' compoundstatement {$$ = makeFUNCTION($1,$3,$5);} | tEXTERN '<' tSTRINGCONST '>' type tIDENTIFIER '(' tINTCONST ')' {$$ = makeFUNCTIONextern($3,$5,$6,$8);} | tEXTERN '<' tSTRINGCONST '>' type tIDENTIFIER '(' tNA ')' {$$ = makeFUNCTIONextern($3,$5,$6,-1);} ; formals : /*empty*/ {$$ = NULL;} | neformals {$$ = $1;} ; neformals : formal {$$ = $1;} | formal ',' neformals {$$ = $1; $$->next = $3;} ; formal : tIDENTIFIER {$$ = makeDECLARATIONformal($1);} ; compoundstatement : '{' '}' {$$ = NULL;} | '{' nestatement '}' {$$ = $2;} ; nestatement : statement {$$ = $1;} | nestatement statement {$$ = makeSTATEMENTsequence($1,$2);} ; statement : ';' {$$ = makeSTATEMENTskip();} | tRETURN ';' {$$ = makeSTATEMENTreturn(NULL);} | tRETURN expression ';' {$$ = makeSTATEMENTreturn($2);} | tIF '(' expression ')' statement {$$ = makeSTATEMENTif($3,makeSTATEMENTscope($5));} | tIF '(' expression ')' statement tELSE statement {$$ = makeSTATEMENTifelse($3,makeSTATEMENTscope($5),makeSTATEMENTscope($7));} | tWHILE '(' expression ')' statement {$$ = makeSTATEMENTwhile($3,$5);} | tFOR '(' forinits ';' expression ';' exps ')' statement {$$ = makeSTATEMENTfor($3,$5,$7,makeSTATEMENTscope($9));} | compoundstatement {$$ = makeSTATEMENTscope($1);} | declaration {$$ = makeSTATEMENTdeclaration($1);} | expression ';' {$$ = makeSTATEMENTexpression($1);} ; forinits : /*empty*/ {$$ = NULL;} | neforinits {$$ = $1;} ; neforinits : forinit {$$ = $1;} | forinit ',' neforinits {$$ = $1; $$->next = $3;} ; forinit : simpledeclaration {$$ = makeFORINITdeclaration($1);} | expression {$$ = makeFORINITexpression($1);} ; expression : lvalue '=' expression {$$ = makeEXPRESSIONassignment($1,$3);} | expression tEQUALS expression {$$ = makeEXPRESSIONequals($1,$3);} | expression tNEQUALS expression {$$ = makeEXPRESSIONnequals($1,$3);} | expression '<' expression {$$ = makeEXPRESSIONless($1,$3);} | expression '>' expression {$$ = makeEXPRESSIONgreater($1,$3);} | expression tLEQUALS expression {$$ = makeEXPRESSIONlequals($1,$3);} | expression tGEQUALS expression {$$ = makeEXPRESSIONgequals($1,$3);} | expression '+' expression {$$ = makeEXPRESSIONplus($1,$3);} | expression '-' expression {$$ = makeEXPRESSIONminus($1,$3);} | expression '*' expression {$$ = makeEXPRESSIONmul($1,$3);} | expression '/' expression {$$ = makeEXPRESSIONdiv($1,$3);} | expression '%' expression {$$ = makeEXPRESSIONmod($1,$3);} | expression tAND expression {$$ = makeEXPRESSIONand($1,$3);} | expression tOR expression {$$ = makeEXPRESSIONor($1,$3);} | lvalue tINC {$$ = makeEXPRESSIONpostinc($1);} | tINC lvalue {$$ = makeEXPRESSIONprefinc($2);} | lvalue tDEC {$$ = makeEXPRESSIONpostdec($1);} | tDEC lvalue {$$ = makeEXPRESSIONprefdec($2);} | lvalue tPLUSASSIGN expression {$$ = makeEXPRESSIONplusassign($1,$3);} | lvalue tMINUSASSIGN expression {$$ = makeEXPRESSIONminusassign($1,$3);} | lvalue tMULASSIGN expression {$$ = makeEXPRESSIONmulassign($1,$3);} | lvalue tDIVASSIGN expression {$$ = makeEXPRESSIONdivassign($1,$3);} | lvalue tMODASSIGN expression {$$ = makeEXPRESSIONmodassign($1,$3);} | expression tSHL expression {$$ = makeEXPRESSIONshl($1,$3);} | expression tSHR expression {$$ = makeEXPRESSIONshr($1,$3);} | lvalue tSHLASSIGN expression {$$ = makeEXPRESSIONshlassign($1,$3);} | lvalue tSHRASSIGN expression {$$ = makeEXPRESSIONshrassign($1,$3);} | lvalue tANDASSIGN expression {$$ = makeEXPRESSIONandassign($1,$3);} | lvalue tORASSIGN expression {$$ = makeEXPRESSIONorassign($1,$3);} | expression '&' expression {$$ = makeEXPRESSIONbitand($1,$3);} | expression '|' expression {$$ = makeEXPRESSIONbitor($1,$3);} | unaryexpression {$$ = $1;} ; unaryexpression : '-' unaryexpression {$$ = makeEXPRESSIONuminus($2);} | '!' unaryexpression {$$ = makeEXPRESSIONnot($2);} | unarypostfixexpression {$$ = $1;} ; unarypostfixexpression : tINTCONST {$$ = makeEXPRESSIONintconst($1);} | tSTRINGCONST {$$ = makeEXPRESSIONstringconst($1);} | tDOUBLECONST {$$ = makeEXPRESSIONdoubleconst($1);} | lvalue {$$ = makeEXPRESSIONlvalue($1);} | '(' expression ')' {$$ = $2;} | tIDENTIFIER '(' exps ')' /*volani funkce*/ {$$ = makeEXPRESSIONcall($1,$3);} ; exps : /*empty*/ {$$ = NULL;} | neexps {$$ = $1;} ; neexps : expression {$$ = $1;} | expression ',' neexps {$$ = $1; $$->next = $3;} ; /*LVALUE zachyti prirazeni vyrazu promenne, coz je ted to same jako deklarace samotne promenne a jeji inicilizace kdyz se nemusi zadavat datovy typ promennych */ lvalue : tIDENTIFIER {$$ = makeLVALUEidentifier($1);} ;` Stále jste se mnou? Dobře, ještě si musíme vysvětlit pár věcí. Zaprvé, bude to chtít aby jste si ten soubor prolezli sami a pár minut/hodin nad ním strávili :) Přehoupneme se hned na ona pravidla, protože v první části jsou komentáře. Možná vás straší ta spousta funkcí začínající na make...a něco dál. Ty budete muset všechny napsat. Nejde o nijak složité funkce, jen vytvářejí nové instance příslušných struktur. Větší problémy by mohly dělat ty $$, $1, $2 atd. $$ reprezentuje výraz na levé straně pravidla, čili nonterminal. $1 až $n zase reprezentuje terminal symboly na pravé straně pravidla. Třeba tato část souboru: `declaration : identifiers initialization ';' {$$ = makeDECLARATIONvariable($1,$2);} ; identifiers : tIDENTIFIER {$$ = makeIDENTIFIER($1);} | tIDENTIFIER ',' identifiers {$$ = makeIDENTIFIER($1); $$->next = $3;} ; initialization : /*empty*/ {$$ = NULL;} | '=' expression {$$ = $2;} ;` To jsou pravidla pro deklaraci proměnné/ných. Kód uzavřený v závorkách {...} se spustí pokaždé když parser použije dané pravidlo k redukci. $$ tady reprezentuje symbol declaration, který je na levé straně pravidla. Na začátku souboru jste si mohli povšimnout, že declaration je definován jako ukazatel na strukturu DECLARATION*. Tento symbol také reprezentuje hodnotu která bude uložena na zásobník když bude k redukci použito toto pravidlo. To bude tedy ukazatel na strukturu DECLARATION. $1 je identifiers, to je první terminal symbol na pravé straně pravidla ( za dvojtečkou). Před použitím pravidla je tato hodnota uložena na vrcholu zásobníku v parseru a je to ukazatel na strukturu IDENTIFIER. Stejně tak $2 je druhý terminal symbol, je v zásobníku uložen pod prvním a je to ukazatel na strukturu INITIALIZATION. Chce to se souborem prodrat a pochopíte jak to funguje, buď rychle nebo časem. Chce to jen dostatečně chtít. Pokud systém jakým se utváří AST chápete, jistě nebudete nic namítat proti tvrzení, že struktura SCRIPT která je vlastně kořenem stromu, bude vytvořena až jako poslední a že strom je vlastně vytvářen od listů ke kořenu. `unarypostfixexpression : tINTCONST {$$ = makeEXPRESSIONintconst($1);} | tSTRINGCONST {$$ = makeEXPRESSIONstringconst($1);} | tDOUBLECONST {$$ = makeEXPRESSIONdoubleconst($1);} | lvalue {$$ = makeEXPRESSIONlvalue($1);} | '(' expression ')' {$$ = $2;} | tIDENTIFIER '(' exps ')' /*volani funkce*/ {$$ = makeEXPRESSIONcall($1,$3);} ;` V této části si zase můžete všimnout vytváření struktur které v sobě uchovávají číselné nebo řetězcové konstanty a informace o tom o co jde. Na začátku souboru pro bison je definováno, že tINTCONST nebude představovat konstantu která by reprezentovala nalezení celočíselné konstanty v souboru, ale že to bude přímo nalezené číslo. Stejně tak tDOUBLECONST, tSTRINGCONST a tIDENTIFIER. Pokud jste to přehlédli, je to popsané někde na začátku souboru v komentáři. `%left ')' %left tELSE` Tyto dva řádky říkají parseru, že závorka ) má přednost před klíčovým slovem else. Zabraňuje se tak konfliktům s nejednoznačností konstrukce if. Takováto podmínka: `if (a) if (b) c; else d;` Může znamenat toto: `if (a) { if (b) c; else d; }` nebo: `if (a) { if (b) c; } else d;` Ve většině jazycích je správně první volba a stejně tak i v Universal Scriptu. Nastavit vyšší prioritu závorce ) než klíčovému slovu else je jednodušší řešení než vymýšlet jiná produkční pravidla. Když nad příkladem a nad tím jak ho parser zpracuje s použitím nadefinované priority popřemýšlíte, zjistíte že nemůže dojít k jinému výsledku než je první verze :) ### Vygenerování parseru Když máme napsaný soubor pro utilitu bison, zbývá nám už jen podle něj nechat vygenerovat parser. Přesuňte si napsaný .y soubor do adresáře bin ve složce bison, kde je i bison.exe. Parser vygenerujeme následujícím příkazem bison.exe -d soubor.y. Například bison.exe -d lang.y. Pokud je .y soubor vpořádku, výstupem vám budou soubory lang.tab.h a lang.tab.c. Vygenerování hlavičkového souboru má na svědomí parametr -d. Když ho nepoužijete, vygeneruje se jen zdrojový soubor c. V hlavičkovém souboru jsou ale nadefinovány konstanty které prozatím chyběly lexikálnímu skeneru, čili doporučuji vygenerovat i tento hlavičkový soubor :) Hlavičkový soubor jen přesuňte do adresáře projektu a informujte Visual Studio o tom že zmíněný soubor do projektu také patří (Project->Add Existing File...}. Pak do projektu vložte prázdný zdrojový soubor a vložte do něj hlavičkový soubor stdafx.h (`#include "stdafx.h"`) a common.h (`#include "common.h"`). Pak do něj můžete zkopírovat celý soubor lang.tab.c. Pokud zkusíte projekt zkompilovat, ještě stále to nepůjde a obdržíte slušnou dávku chybových hlášení. To je dáno tím, že ješte nemáte napsané zmiňované funkce make... a pár menších dodatečných funkcí, jako yyerror pro hlášení chyb. Než se vám projekt podaří zkompilovat, budete muset ještě dopsat soubory error.h, tree.h, error.cpp a tree.cpp. První modul kompileru, který je implementován jako třída najdete v ukázkovém projektu. Jde o část kterou jsem nazval PrintTree a jediné co dělá je rekurzivní prúchod AST stromem a výpis stromu do souboru. Tento modul není nezbytný a jeho existence má jediný smysl, totiž abychom si mohli v souboru prohlédnout strom do jakého byl skript rozložen. A věřím že vám stejně jako mě chvíle studia takto vypsaného stromu pomůže pochopit jak je skript v paměti uložen a jak ten strom vypadá. Aby vám to chodilo jako mě, budete potřebovat ještě common.h, asmutils.h a asmutil.cpp. To jsou pomocné soubory s definicemi a funkcemi které používám ve většině částí kompileru. Buď si je ode mě zkopírujte nebo opište. Funkce které obsahují popíši až se dostaneme k jejich použití. Ve všech souborech jsou komentáře, takže je nebudu zbytečně zobrazovat i tady ale nechám na vás ať si je projdete. Poslední věc kterou vám chci v této kapitole ukázat je jak bude vypadat AST strom pro příklad z teorie - Hello World skript. `/*****************************Ahoj svete****************************************/ //Definice externi funkce. MessageBox slouzi pro zobrazeni dialogoveho okna s textem a nachazi se v knihovne user32.dll. int rika ze funkce vrati hodnotu typu int. Vice o tomto problemu v dalsich castich kurzu. Cislo 4 v zavorce udava ze funkce ma 4 parametry. extern <"user32.dll"> int MessageBoxA(4) main() { /*To ze pro kazdy parametr definuji promennou neznamena, ze by nebylo podporovano prime zadani parametru do funkce. Chci jen ukazat definici promennych u nichz se nezadava datovy typ*/ Nula = 0; //Promenna je typ jakykoliv a je v ni ulozen integer. V tomto miste se symbol Nula objevuje poprve. Jedna se tedy o deklaraci promenne a jeji inicializaci na 0. Zprava = "Ahoj světe";//Promenna je typ jakykoliv a je v ni ulozen retezec. Titulek = "Universal Script Language"; Nula = 0; //Symbol Nula se uz vyskytuje nahore, kde je deklarovan. Zde tedy nejde o deklaraci promenne ale o prirazeni hodnoty. MessageBoxA(Nula,Zprava,Titulek,Nula); }` Abstract Syntax Tree: Text který je napsán u čar (větví) spojujících různé obdélníčky (uzly, ty co nemají další uzly jsou listy) je název ukazatele ve struktuře, který ukazuje na další prvek. Uvnitř uzlú/listů jsou vypsány nejdůležitější členy daných struktur. Název struktur je vypsán tučně v horní části každého uzlu/listu. Jestli jsem tam někde neudělal chybu, stejný strom bude vypsán do souboru pokud pustíte kompiler na skript helloworld, jen to nebude tak hezké jako na obrázku. Můžete si ve stromu všimnout, že obsahuje dvakrát uzel s deklarací proměnné Nula. To je chyba kterou později opravíme. Doufám že se mi podařilo vysvětlit aspoň něco z této druhé a nejtěžší kapitoly. V této kapitole už je to vše. Až se prokousáte zdrojáky k této lekci, uvidíme se v třetí části. Část 1 Část 3