Kompiler - Část 3 , Weeding |  |
Pokrok :) Hotový projekt Jsem rád že jste to po druhé lekci nevzdali :) Plení, tak by dal přeložit výraz weeding. Tímto modulem začneme analýzu skriptu. Pokud skript projde parserem bez záseků, tzn. že v něm nejsou syntaktické chyby ani žádné nepovolené symboly, můžeme ho začít pomalu analyzovat. Uvidíte že když máme skript v reprezentaci stromu, že se nám s ním bude pracovat lépe než s jeho textovou formou. Také se seznámíme s rekurzivním procházením stromu, jež budeme v bledě modrém používat i v dalších částech. Velká část programového kódu je pak jen nějaké větvení a rekurzivní volání funkcí. Těch řádků které pro nás mají význam je málo a nejsou nijak složité. Ale to posoudíte sami, mě se to nyní zdá celé jednoduché :) Takže co budeme v tomto modulu dělat? Odchytíme zde ty nejjednodušší chyby které se ve skriptu mohu vyskytnout. Například pokus o dělení nulou. Dále budeme u funkcí zjišťovat jestli vracejí nějakou hodnotu a upozorníme uživatele pokud narazíme na kód který se nikdy nespustí - unreachable code. Modul budeme realizovat jako třídu CWeeding jenž potom použijeme jako jeden z modulů třídy CCompiler, kterou už jste určitě viděli ve zdrojových kódech minulé lekce, jež měly sloužit pro samostudium, pač to nebylo popsáno v kapitole. Nebudu to tady už déle okecávat, tady je definice třídy CWeeding: `/*Weeding (pleni, odstraneni plevele a nahlaseni zavaznych chyb) modul Stargate Scriptu Prvni modul ve front-end casti kompileru, ktere fce vraceji hodnotu, hledame zda kod neobsahuje kod ktery nebude nikdy vykonan a najdeme take deleni nulou */ //**************************************************************************************************************** //Trida pro pleni //**************************************************************************************************************** class CWeeding { private: void processTOPLEVEL(TOPLEVEL* toplevel); void processFUNCTION(FUNCTION* function); void processSTATEMENT(STATEMENT* statement); void processDECLARATION(DECLARATION* declaration); void processEXPRESSION(EXPRESSION* expression); void processFORINIT(FORINIT* forinit); bool processSTATEMENTCheckUnreachableCodeAndIfReturnsValue(STATEMENT* statement); bool processSTATEMENTForUnreachableCode(STATEMENT* statement); public: void Process(SCRIPT* theScript); };` Vidíte že to není žádná strašná třída. Má jen jednu metodu která je viditelná zvenčí a to je metoda Process. Jak si můžete všimnout, jediným jejím parametrem je ukazatel na strukturu SCRIPT, čili na uzel stromu. Popravdě každá funkce zpracovává nějaký uzel stromu. Uzel stromu jak víme je reprezentován různými strukturami. Pro zpracování každé takové struktury tu tedy máme funkci. Snad jen kromě struktury IDENTIFIER, kterou nemá cenu v tomhle modulu zpracovávat protože snad neexistuje chyba která by v ní mohla být a kterou by jsme tady mohli odchytit. Podíváme se na první dvě funkce: Process a processTOPLEVEL. `//**************************************************************************************************************** /*zaciname s plenim u korenu stromu*/ //**************************************************************************************************************** void CWeeding::Process(SCRIPT* theScript) { if (theScript->toplevels != NULL) //pokud mame nejake toplevely processTOPLEVEL(theScript->toplevels); //preplejem vsechny toplevely } //**************************************************************************************************************** //prochazeni toplevelu //**************************************************************************************************************** void CWeeding::processTOPLEVEL(TOPLEVEL* toplevel) { processFUNCTION(toplevel->function); //pleni funkce if (toplevel->next != NULL) //pleni dalsiho toplevelu processTOPLEVEL(toplevel->next); }` Jak vidíte jde u úplně jednoduché funkce. Jen kontrola ukaztelů a volání funkcí pro zpracování dalších uzlů. Skript nemusí obsahovat žádnou funkci, proto se musí zkontrolovat ukazatel toplevels který ukazuje na první toplevel. Pokud není žádná funkce, je tento ukazatel neplatný. Ve funkci pro zpracování struktury TOPLEVEL se může rovnou volat funkce pro zpracování struktury FUNCTION. Pokud totiž ve skriptu je aspoň jedna funkce, existuje struktura TOPLEVEL a tím pádem i FUNCTION. To je dáno produkčními pravidly a tím jak se konstruuje strom. Ukazatel na další toplevel ale už kontrolovat musíme. Další funkcí kterou si ukážeme je processFUNCTION: `//**************************************************************************************************************** //pruchod fci //**************************************************************************************************************** void CWeeding::processFUNCTION(FUNCTION* function) { switch (function->kind) { case localT: //lokalni fce, je definovana ve skriptu if (function->declaration != NULL) //pokud ma funkce nejake parametry processDECLARATION(function->declaration); //musime je taky zkontrolovat function->returns_value = false; if (function->statements != NULL) //pokud ma funkce nejake telo, { processSTATEMENT(function->statements); //zkontrolujeme kazdy prikaz v jejim tele a pak zkontrolujeme zda obsahuje return function->returns_value = processSTATEMENTCheckUnreachableCodeAndIfReturnsValue(function,function->statements); processSTATEMENTForUnreachableCode(function->statements); } //zmen jmeno funkce tak aby bylo slozeno ze jmena funkce a podpisu, to nam dovoli //pouzivat pretizene funkce function->signature = stringConcat(function->name,makeSignature(function),NULL); break; case externT: //u externi fce zkusime jestli jsou nazvy platne a jestli muzem ziskat jeji adresu FARPROC funcadress = NULL; HMODULE hDll = NULL; //nejdriv ziskat handle knihovny, tato fce pocita s tim ze je knihovna nactena v pameti hDll = GetModuleHandle(function->library); if (!hDll) { //knihovna neni v pameti nactena, takze ji nacteme a ziskame na ni drzadlo pomoci fce LoadLibrary hDll = LoadLibrary(function->library); if (!hDll) //pokud se to nepovede, nahlasime warning. Knihovna jen nemusi byt v systemovem adresari nebo v adresari s //kompilerem, ale az bude program spusten pravdepodobne uz bude pritomna theLog.ReportWarning(function->line_number,"Warning: Cannot load library %s to check if it contains function %s.\n",function->library,function->name); } //pokud mame handle knihovny if (hDll) { //pokusime se ziskat adresu externi funkce funcadress = GetProcAddress(hDll,function->name); if (!funcadress) //opet vypis pokud se to nepovede theLog.ReportWarning(function->line_number,"Warning: Failed to retrieve adress of function %s. The name of function is invalid or it is located at other library!\n",function->name); FreeLibrary(hDll); } //nastav u funkce jestli vraci hodnotu function->returns_value = (function->type->kind == voidT) ? false : true; } }` Ve funkci si musíme rozdělit akce pro případ že kontrolujeme lokální nebo externí funkci. Lokální funkce je napsaná ve skriptu, má nějaké parametry a tělo. Externí funkce tělo definované nemá. Při dúkladnějším studiu funkce si všimnete volání funkcí pro zpracování dalších členských struktur lokální funkce. Třeba zpracování deklarací, tj. parametrů funkce a těla funkce. Tělo funkce kontrolujeme třikrát. Při druhé kontrole hledáme v těle funkce příkaz `return`, abychom zjistili zda funkce vrací hodnotu a při třetí kontrole hledáme kód který se nikdy neprovede. Co se týče externí funkce, u té se pokusíme ji načíst z knihovny v jaké se má nacházet. Pokud se nám nepodaří funkci načíst, bereme to zatím jen jako varování. Knihovna ve které se funkce nachází totiž nemusí být v systémové složce nebo ve složce ve které skript kompilujeme. To může být důvod proč funkce nešla načíst, protože se nám nepovedlo načíst ani knihovnu v které by být měla. Proto uživatele jen varujeme aby o tom věděl a dal si pozor aby při spouštění programu knihovna byla v systémové složce nebo ve složce ze které budeme skript spouštět. Můžete si všimnout že pro lokální funkci skládáme jakýsi řetězec který ukládáme do členské proměnné signature. To je tzv. podpis funkce, který je vytvořen spojením jména funkce a posčtu jejích parametrů v závorkách. Tento podpis budeme využívat v další lekci při kontrole symbolů. Například funkce: fce(a,b,c,d,e) by měla podpis: fce(5). Její jméno je fce a má pt parametrů. Pro externí funkci je podpis generován už při vytváření AST stromu ve funkci makeFUNCTIONextern. Nyní si ukážeme funkci která zjistí zda je v tělě funkce příkaz return. `//**************************************************************************************************************** /*Fce pro kontrolu zda funkce obsahuje prikaz return a zda ho obsahuje vsude kde ma byt, aby nevznikaly chyby kdy nejsou kdy nekontrolujeme vsechny moyne cesty kudy vratit hodnotu */ //**************************************************************************************************************** bool CWeeding::processSTATEMENTCheckIfReturnsValue(STATEMENT* statement) { switch (statement->kind) { case returnT: //pokud narazime na return, vratime true ze jsme nasli return if (statement->val.returnS.expression) return true; else return false; return true; case forT: return processSTATEMENTCheckIfReturnsValue(statement->val.forS.body); case whileT: return processSTATEMENTCheckIfReturnsValue(statement->val.whileS.body); case ifT: return processSTATEMENTCheckIfReturnsValue(statement->val.ifS.body); case ifelseT: //hledej return v if casti tela prikazu if-else i v casti else if (processSTATEMENTCheckIfReturnsValue(statement->val.ifelseS.ifbody) || processSTATEMENTCheckIfReturnsValue(statement->val.ifelseS.elsebody)) return true; return false; case sequenceT: if (processSTATEMENTCheckIfReturnsValue(statement->val.sequenceS.firts) || processSTATEMENTCheckIfReturnsValue(statement->val.sequenceS.second)) return true; else return false; case scopeT: /*scope taky musime zkontrolovat*/ return processSTATEMENTCheckIfReturnsValue(statement->val.scopeS.statement); default: return false; } }` Pokud tělo funkce obsahuje příkaz return, může být tento příkaz jen v uzlu který je reprezentován strukturou STATEMENT která obsahuje příkaz return (kind=returnT) a tento příkaz musí vracet hodnotu. Příkaz return se může vyskytovat i samostatně bez jakékoliv hodnoty. Pak nejde o vrácení hodnoty ale jen o návrat z procedury. Proto se v případě že kontrolujeme příkaz return se musíme rozhodnout ještě podle toho zda vrací hodnotu (ukazatel `statement->val.returnS.expression` není NULL). U ostatních programových konstrukcí (if,if-else...) kontrolujeme těla daných konstrukcí. Jediný příkaz který nemusíme kontrolovat je deklarace proměnné (kind=declstmT). Tam se return ani vyskytnout nemůže. Tento případ je odchycen větví default: a je vráceno rovnou false. K pochhopení proč tato a další funkce vypadá tak jak vypadá je nutné aby jste chápali jak může a nemůže vypadat AST strom skriptu. Nyní funkce pro nalezení neproveditelného kódu. `bool CWeeding::processSTATEMENTForUnreachableCode(STATEMENT* statement) { switch (statement->kind) { case returnT: //pokud narazime na return, vratime true ze jsme nasli return return true; case ifelseT: //hledej return v if casti tela prikazu if-else i v casti else if (processSTATEMENTForUnreachableCode(statement->val.ifelseS.ifbody) || processSTATEMENTForUnreachableCode(statement->val.ifelseS.elsebody)) return true; return false; case sequenceT: if (processSTATEMENTForUnreachableCode(statement->val.sequenceS.firts)) { theLog.ReportWarning(statement->line_number,"Unreachable Code"); return true; } else return processSTATEMENTForUnreachableCode(statement->val.sequenceS.second); case scopeT: /*scope taky musime zkontrolovat*/ return processSTATEMENTForUnreachableCode(statement->val.scopeS.statement); default: return false; } }` Neproveditelný kód najdeme snadno. Takový kód se může vyksytnout jen v případě že return je obsaženo v prvním příkazu ze sekvence dvou příkazů. Například `return; a=b;`. Takový příkaz bude ve stromu reprezentován strukturou STATEMENT typu sekvence příkazů. První příkaz bude return a druhý příkaz bude deklarace nebo přiřazení a = b. Druhý příkaz se tedy nikdy neprovede a je to neproveditelný kód. Dále si můžete všimnout že kromě sekvence příkazů kontrolujeme už jen příkazy if-else a scope. Scope znamená nové vnoření příkazů, tj. příkazy uzavřené mezi {}. Konstrukce if-else musí obsahovat return v obou větvích, aby následující kód byl nevykonatelný. Konstrukci if není třeba kontrolovat, protože tam nevíme jestli podmínka bude nebo nebude splněna. Zbylé konstrukce také není třeba kontrolovat, protože jejich vykonání je také závislé na podmínce kterou nemůžeme při kompilaci vyhodnotit, proto všechny ostatní příkazy zachytí volba default která hned vrátí false. To znamená že příkaz return se v takových případech nevyskytuje a následující kód nemůže být neproveditelný. Následuje část funkce processEXPRESSION, kde se odchytávají pokusy o dělení nulou. `. . case divT: processEXPRESSION(expression->val.divE.left); /*zachyceni pokusu o deleni nulou staci jen zjistit zda vyraz na prave strane je ciselna konstanta a pokud ano jestli je to nula. Pokud je to nula, jde jasne o deleni nulou. Pokud vyraz na prave strane neni cislo ale dalsi vyraz, pokracujeme v rekurzi dale */ switch (expression->val.divE.right->kind) { case intconstT: if (expression->val.divE.right->val.intconstE == 0) theLog.ReportError(expression->val.divE.right->line_number,"Division by zero!"); break; case doubleconstT: if (expression->val.divE.right->val.doubleconstE == 0.0f) theLog.ReportError(expression->val.divE.right->line_number,"Division by zero!"); break; case stringconstT: if (atof(expression->val.divE.right->val.stringconstE) == 0.0) theLog.ReportError(expression->val.divE.right->line_number,"Division by zero!"); break; default: processEXPRESSION(expression->val.divE.right); } break; . . case divassignT: //zase hlidani pokusu o deleni nulou switch (expression->val.divassignE.right->kind) { case intconstT: if (expression->val.divassignE.right->val.intconstE == 0) theLog.ReportError(expression->val.divassignE.right->line_number,"Division by zero!"); break; case doubleconstT: if (expression->val.divassignE.right->val.doubleconstE == 0.0f) theLog.ReportError(expression->val.divassignE.right->line_number,"Division by zero!"); break; case stringconstT: if (atof(expression->val.divassignE.right->val.stringconstE) == 0.0) theLog.ReportError(expression->val.divassignE.right->line_number,"Division by zero!"); break; default: processEXPRESSION(expression->val.divassignE.right); } break; . .` Protože jste se dúkladně seznámili se souborem tree.h, víte, že divT značí výraz děleno (/) a divassingT značí výraz děleno rovná se (/=). To jsou jediné dva výrazy kde má cenu kontrolovat zda nejde o dělení nulou. V prvním případě (/) kontrolujeme zda pravý operand (dělitel) není celočíselná konstanta, konstantní desetinné číslo nebo řetězcová konstanta a pokud ano, tak zda tato konstanta je nula nebo ne. Pokud ano, vypíše se chyba a pokračuje se dál. V případě druhém (/=) se kontrola provádí úplně stejně. Předposlední bude část funkce pro kontrolu příkazů - processSTATEMENT: `. . case ifT: processEXPRESSION(statement->val.ifS.condition); /*zachyt podminky kde je jen cislo 0 nebo 0.0 nebo "0", tj. podminky typu if (0). Tyto podminky nebudou nikdy provedeny. Pokud je najdem, nahlasime varovani*/ if (statement->val.ifS.condition->kind == intconstT) { if (statement->val.ifS.condition->val.intconstE == 0) theLog.ReportWarning(statement->line_number,"If body never executed! Condition is always false!"); } if (statement->val.ifS.condition->kind == doubleconstT) { if (statement->val.ifS.condition->val.doubleconstE == 0.0f) theLog.ReportWarning(statement->line_number,"If body never executed! Condition is always false!"); } if (statement->val.ifS.condition->kind == stringconstT) { if (atof(statement->val.ifS.condition->val.stringconstE) == 0.0f) theLog.ReportWarning(statement->line_number,"If body never executed! Condition is always false!"); } processSTATEMENT(statement->val.ifS.body); break; . .` Tato část funkce si bere na mušku příkazy if které nebudou nikdy vykonány. To jest příkazy typu `if (0)`. Kontrola je úplně stejná jako kontrola dělení nulou v předchozí funkci. Podíváme se jestli podmínka konstrukce if není celočíselná konstanta, konstantní desetinné číslo nebo konstantní řetězec a pokud ano, tak jestli to je nula či ne. V případě že je podmínkou nulová konstanta, vypíšeme varování. Tohle není problém kvůli kterému by se nemohlo pokračovat v kompilaci. Poslední věc co si vysvětlíme se týká funkce processDECLARATION. Opět je to jen část funkce. `. . case variableT: /*prevedeni seznamu identifikatoru na seznam deklaraci prevedeni deklarace jako int a, b = 0; na int a=0; int b=0; */ if (declaration->val.variableD.identifiers->next != NULL) //pokud deklarace promenne obsahuje vice identifikatoru { tmp = declaration->next; //ulozime si docasne ukazatel na nasledujici deklaraci //jako dalsi deklaraci vytvorime deklaraci promenne se stejnym identifikatorem, stejneho typu, //identifikator bude dalsi v seznamu a inicilizace taky stejna //clenska promenna identifiers muze trochu mast. predstavuje ukazatel na prvni identifikator //a ten pak pomoci promenne next ukazuje na dalsi identifikatory. Takze my v jednom kroku vlastne //zmensime seznam identifikatoru o jedna, z jednoho identifikatoru udelame deklaraci samostatne promenne //a tuto deklaraci vloyime mezi declaration a declaration->next, respektive tu na kterou ukazuje tmp //dalsi rekurye bude pokracovat na declaration->next, kde bude ale vlozena tato nova deklarace a ta bude //obsahovat v promenne identifiers zbyle identifikatory, ktere postupne po jednom prevedeme vsechny na //deklaraci promenne declaration->next = makeDECLARATIONvariable(declaration->val.variableD.identifiers->next, declaration->val.variableD.initialization); //vynulujeme ukazatel na dalsi identifikatory v seznamu declaration->val.variableD.identifiers->next = NULL; //ukazatel na dalsi deklaraci v nove vytvorene deklaraci promenne nastavime na puvodni //deklaraci kterou mame ulozenou v docasne promenne declaration->next->next = tmp; } //este zkontrolujeme zda je promenna inicializovana, pokud ne, incializujeme ji na nula if (!declaration->val.variableD.initialization) { //informuj o tom ze inicializujes na nulu theLog.TraceF("Variable '%s' is not initialized. Initializing it to zero. ",declaration->val.variableD.identifiers->name); declaration->val.variableD.initialization = makeEXPRESSIONintconst(0); } processEXPRESSION(declaration->val.variableD.initialization); break; . .` Zde nejde o žádnou kontrolu, jen o krok který nám zjednodušší život v dalších lekcích. Pokud ve skriptu deklarujete více proměnných najednou: `a,b,c = 0;`, vytvoří se v paměti jedna struktura DECLARATION typu variableT, která bude ukazovat na jednu strukturu EXPRESSION, což je inicializace všech proměnných. Druhý ukazatel bude ukazovat na první strukturu IDENTIFIER, která v sobě bude schovávat "a". Tato struktura bude svým ukazatelem -7>next ukazovat na další IDENTIFIER s proměnnou "b" a ta na poslední strukturu která schovává "c". Co se nám na tom nelíbí. Nic, je to fajn. Ale v modulu Resource Calculations kde budeme počítat indexy proměnných by se nám více hodilo aby každá deklarace ukazovala jen na jednu strukturu IDENTIFIER. Nechceme tedy žádný spojový seznam identifikátorů. Pozměníme proto strom tak aby to vapadlo že každá proměnná byla definována samostatně a ne že byly definovány všechny najednou. Bude to odpovídat tomu kdyby jste do skriptu napsali: `a=0;b=0;c=0;`. Ze začátku je trošku složitější kód této funkce pochopit. My totiž v každém volání funkce převedeme jednu strukturu IDENTIFIER na samostatnou deklaraci. Také si všimněte automatické inicializace proměnných která nebyly inicializovány na nulu. Chce to u toho kódu přemýšlet o tom co to dělá a odkrokovat si to. Ještě obrázek toho jak to vypadá před a po: A máme za sebou modul Weeding. Že to nebylo nic těžkého? Zbytek kódu prostudujte v ukázkovém projektu. Je to ale už jen rekurzivní průchod stromem. To důležité jsme probrali zde. Část 2 Část 4