Univerzita Karlova v Praze Matematicko-fyzikální fakulta BAKALÁSKÁ PRÁCE. Pavel Janík Interpret Pascalu. Katedra softwarového inženýrství

Univerzita Karlova v Praze Matematicko-fyzikální fakulta

BAKALÁ SKÁ PRÁCE

Pavel Jan ík Interpret Pascalu Katedra softwarového inženýrství

RNDr. Jakub Yaghob, Ph.D. Informatika, Informatika programování

2008

Rád bych pod koval vedoucímu mé práce RNDr. Jakubu Yaghobovi za trp livost, as a podporu p i tvorb interpretu a psaní samotné práce.

Prohlašuji, že jsem svou bakalá skou práci napsal samostatn citovaných pramen . Souhlasím se zap j ováním práce. V Praze dne 5. srpna 2008

a výhradn

…………………… Pavel Jan ík 2

s použitím

1 2

3

4

5 6 7 P P

Úvod .....................................................................................................................................5 Interpretované jazyky ........................................................................................................6 2.1 Typické interpretované jazyky ..............................................................................6 2.2 Virtuální stroje.......................................................................................................8 2.3 Pokro ilé metody používané ve VM ...................................................................10 Vnit ní návrh ....................................................................................................................12 3.1 P ehled .................................................................................................................12 3.2 Lexikální analýza.................................................................................................13 3.3 Syntaktická analýza[18][22] ....................................................................................14 3.4 CodeGenerator t ídy ............................................................................................16 3.5 Typový systém.....................................................................................................20 3.6 Prom nné .............................................................................................................21 3.7 Vrstvy ..................................................................................................................23 3.8 Virtuální stroj.......................................................................................................24 3.9 Hlášení chyb ........................................................................................................28 3.10 P eložení projektu, spušt ní, licence ...................................................................29 Vstupní jazyk ....................................................................................................................30 4.1 Klí ová slova .......................................................................................................30 4.2 Vstup interpretu ...................................................................................................30 4.3 Program ...............................................................................................................30 4.4 Jednotky...............................................................................................................31 4.5 Náv ští .................................................................................................................32 4.6 Typy.....................................................................................................................32 4.7 Procedury a funkce ..............................................................................................35 4.8 Prom nné a konstanty..........................................................................................38 4.9 Výrazy .................................................................................................................39 4.10 P íkazy .................................................................................................................39 4.11 Vestav né funkce.................................................................................................44 Srovnání s dalšími implementacemi Pascalu .................................................................47 Záv r ..................................................................................................................................51 Zdroje ................................................................................................................................52 íloha - Zkratky a pojmy .....................................................................................................53 íloha - CD ............................................................................................................................54

3

Název práce: Autor: Katedra (ústav): Vedoucí bakalá ské práce: email vedoucího:

Interpret Pascalu Pavel Jan ík Katedra softwarového inženýrství RNDr. Jakub Yaghob, Ph.D. [email protected]

Abstrakt:

Práce má prohloubit znalosti studenta v oblasti návrhu a tvorby frontendu p eklada , pokro ilých programovacích technik a nástroj používaných p i jejich tvorb . Má vzniknout interpret podmnožiny jazyka Pascal, který se bude vyzna ovat objektovým, rozumn rozši itelným návrhem, který by p edstavoval použitelnou platformu pro další vývoj a rozši ování. Student se seznámí s již existujícími a používanými virtuálními stroji a v rámci práce na interpretu navrhne vlastní jednoduchý virtuální stroj a jeho instruk ní sadu

Klí ová slova:

Pascal, interpret, programovací jazyky

Title: Author: Department: Supervisor: Supervisor’s email address:

Pascal interpreter Pavel Jan ík Department of Software Engineering RNDr. Jakub Yaghob, Ph.D. [email protected]

Abstract:

Work has to enlarge student’s knowledge about design and programming of interpreters. Student will use advanced programming techniques and tools commonly used in compilers. Target of work is creating interpreter that process subset of Pascal programming language. Its design is object oriented and easily extensible. Goal of this work is create platform for future development. Student will study existing virtual machines used in other interpreters and create own simple virtual machine and instruction set.

Keywords:

Pascal, interpreter, programming languages

4

1 Úvod Zadáním mé práce bylo vytvo it interpret, jehož vstupem by byla podmnožina programovacího jazyka Pascal. Pro Pascal jsem se rozhodl, protože jej velmi dob e znám. Jedná se o jazyk, který Niklaus Wirth vytvo il pro výuku programování a zvládá jej velké množství programátor . Interpret jsem zvolil s ohledem na to, že jeho vytvo ení je jednodušší, než naprogramování celého p eklada e. Druhý d vod hovo ící pro interpret p edstavuje virtuální stroj. V rámci p ípravy na jeho implementaci se seznámím s r znými dalšími virtuálními stroji, jejich vlastnostmi a technikami, které se v nich používají. K volb Pascalu p isp lo, že neobsahuje vlastnosti typické pro interpretované jazyky, a tak se návrh virtuálního stroje, který je sou ástí mé práce, více blíží v sou asnosti nejpoužívan jším VM. Tvorba p eklada se v dnešní dob dynamicky rozvíjí, stále se objevují nové programovací jazyky, vymýšlí se nové optimalizace pro urychlení kódu. Tento rozvoj se samoz ejm týká i optimalizací pro virtuální stroje, kde se více projevuje požadavek na rychlost jejich provedení. Velkou výzvu p edstavuje nap íklad paralelizace, zvlášt pak automatická, vznikající až v kompilátoru. Celá paleta program t ží z toho, že v sob obsahují programovací ( i skriptovací) jazyk. Z t ch komplexn jších zmi me nap íklad tabulkové procesory. Jednodušší jazyky mohou být použity pro popis r zných pravidel p i zpracování paket , a už p i jejich sm rování nebo filtrování. Pro ovládaní robot se též hodí mít k dispozici prost edky pro popis inností, které mají provád t. Databáze asto v rámci rozší ení SQL umož ují ukládání procedur. Ty se vytvá í, na rozdíl od SQL p íkaz , v procedurálním jazyce, asto siln inspirovaném Pascalem. Za rozvojem interpretovaných jazyk stojí mimo jiné to, že dnes již s minimálním dopadem na výkon dokáží poskytnout funkcionalitu, které by bylo u klasických programovacích jazyk velmi t žké dosáhnout. Jedná se p edevším o p enositelnost mezi platformami, což velmi láká softwarové firmy, protože díky tomu mohou oslovit v tší množství z potenciálních zákazník . I jim poskytuje volnost ve výb ru opera ního systému, který nasadí ve svém prost edí. Dále umož uje lépe sledovat innost program tím, že má pod kontrolou volané procedury z virtuálního stroje. Takto je možné lépe zajistit bezpe nost. V ur itých specifických p ípadech mohou dokonce interpretované jazyky kompilované v rychlosti p ekonávat. A to díky tomu, že se mohou p ímo p izp sobit konkrétnímu procesoru. Více spušt ných interpretovaných program asto obsluhuje jeden proces interpretu, tím lze omezit režii za p epínání context . Tyto ale i další vlastnosti stojí za masivním rozší ením interpretování. Zmi me alespo dva nejznám jší interpretované jazyky. V sou asné dob velmi používanou Javu s její Java virtual machine a platformu .NET spolu s C#. Cílem této práce není vytvo it n co nového, co ješt nebylo implementováno. Pro Pascal samoz ejm existuje množství p eklada , z nejznám jších p ipome me Turbo Pascal a Free Pascal. Zám rem bylo detailní pochopení požadavk kladených na front-end, vyzkoušet si návrh a implementaci této rozsáhlé, zajímavé ásti. M l jsem identifikovat typické, ale i mén známé a na první pohled ne tak z ejmé problémy, které se zde vyskytují, seznámit se s nimi a navrhovat r zná jejich ešení, prohloubit celkové znalosti o dané problematice. Vzniklý interpret pak m že p edstavovat zajímavý základ pro další rozši ování r znými sm ry, v emž by m l spo ívat jeho nejv tší význam. V druhé kapitole se zmi uji o interpretaci obecn i o dalších interpretovaných jazycích, všímám si jejich specifických vlastností, o používaných virtuálních strojích i technikách v nich používaných. Kapitola t i je v nována vlastní implementaci interpretu. Nejprve ve zkratce zmíním kompletní strukturu a poté již rozebírám jednotlivé ásti a jejich návaznost mezi sebou. Na záv r této kapitoly se zmi uji o p ekladu projektu. tvrtá kapitola obsahuje popis vstupního jazyka, význam jednotlivých konstrukcí pro interpret spolu se syntaktickými diagramy. Poté již následuje záv r. 5

2 Interpretované jazyky Interpretované jazyky mají velmi dlouhou tradici. Jeden z prvních interpretovaných jazyk byl Lisp, který pat í k prvním vyšším programovacím jazyk m. Dodnes je používán hlavn v oblasti um lé inteligence. Dalším starším a dob e známým interpretovaným programovacím jazykem je Basic, který byl implementován i v mnohých 8bitových po íta ích. I p es dlouhou historii t chto jazyk jejich význam nejvíce vzrostl v posledním desetiletí, kdy již interpretované jazyky, díky mnoha pokro ilým technikám nejsou o mnoho, (pokud v bec) pomalejší než kompilované. Programovací jazyky jde rozd lit na interpretované a kompilované, ale toto len ní není striktní. Pro interpretované jazyky mohou existovat kompilátory a naopak. Jako p íklad zmi me Javu a GCJ p ípadn Basic a kompilátor QuickBasic. Opa ným sm rem by se p íklad dalo najít velké množství, protože interpret je p edstupe p ed vytvo ením celého kompilátoru. Rozd lení na interpretované a kompilované jazyky se provádí spíše podle ur itých znak . Jisté vlastnosti jazyka jsou typické pro interpretované jazyky a u kompilovaných by bylo velmi složité takové vlastnosti podporovat. Mezi typické znaky pro interpretované jazyky pat í dynamické typování a s tím související pole s r znými typy položek i podpora eval – vygenerování p íkaz za b hu. asto se též vyskytuje automatická správa pam ti, ale tu lze používat i u neinterpretovaných jazyk . Kompilované jazyky mají obvykle statické typy, manuální správu pam ti a dalších zdroj . V poslední dob se používá „interpretování“ i pro jazyky, které již charakteristické znaky interpretovaných jazyk nemají. Jde konkrétn o Javu a C#, C++ na .NET platform . V t chto p ípadech je totiž možné vhodným návrhem získat za cenu jen malé ztráty výkonu nové vlastnosti, jako nap íklad nezávislost na platform a malou velikost výsledného programu. Díky vhodnému návrhu jazyka, pokro ilým technikám jako nap íklad just in time (JIT) kompilací i optimalizací p ímo pro sou asnou konfiguraci po íta e dochází ke zvýšení rychlosti až na úrove kompilovaných jazyk . V rámci mé práce jsem se zevrubn seznámil s r znými programovacími jazyky, jejich historií a vlastnostmi. Jednak tato znalost pat í ke všeobecnému informatickému základu, jednak abych se dov d l o problémech, které auto i interpret musí typicky ešit.

2.1 Typické interpretované jazyky Java [1] První verze byla uvoln na v roce 1995 firmou Sun Microsystems. Vyvíjena byla již od roku 1991 pro použití v set top boxech a další spot ební elektronice. P estože byla p vodn vyvíjena pro použití v embedded za ízeních, dnes je její využití mnohem širší, od serverových aplikací, p es webové alpety i „standalone aplikace“, až po mobilní telefony. Syntaxe Javy je ovlivn na C++. Jde o staticky typovaný, objektov orientovaný jazyk s podporou výjimek, vláken, synchronizací a garbage collectingem. Cílem návrhá bylo vytvo it efektivní, bezpe ný, platform nezávislý jazyk a minimalizovat velikost mezikódu. Standard jazyka Javy spravuje Java Community Process. Kv li vysoké rozdílnosti a protich dnosti požadavk kladených na Javu jednotlivými prost edími, kde se tento jazyk používá, vzniklo n kolik r zných Java platforem, které se liší v dostupných knihovních funkcích. Java Platform, Micro Edition

(Java ME)

ur ena pro prost edí s omezenými zdroji (mobilní telefony, embedded za ízení, ...) ur eno na workstations zam eno na podnikové a internetové prost edí (Servlets, JavaServer Pages)

Java Platform, Standard Edition (Java SE) Java Platform, Enterprise Edition (Java EE)

6

Java se distribuuje bu jako Java Runtime Environment (JRE), kde se nachází vše pot ebné pro spušt ní javovského mezikódu (JVM, p eložené knihovny, ...). A dále v podob Java Development Kit (JDK), která navíc obsahuje nástroje pot ebné pro vývoj aplikací (kompilátor do mezikódu, Javadoc, debuger, hlavi kové soubory knihoven ...) Mezikód Javy je vykonáván pomocí Java Virtual Machine, o které se zmi uji dále. PHP [3] Jméno PHP byla p vodn zkratka od Personal Home Page. V roce 1997 spolu s uvedením PHP3 došlo ke zm n a PHP je rekurzivní zkratka pro PHP Hypertext Preprocesor. Je primárn ur en pro tvorbu dynamických webových stránek, kde p edstavuje jednu z nejpoužívan jších technologií. PHP ale není omezené pouze na webové stránky, lze v n m tvo it konzolové i desktopové aplikace. Syntaxe jazyka je inspirována jazyky C, Pascal, Perl. PHP je dynamicky typovaný jazyk s heterogenními poli (každá položka pole m že být r zného typu), s vestav nou podporou Unicode, výjimkami a podporou objekt . Jazyk není oficiáln standardizován, standardem je de facto implementace vytvo ená The PHP Group. Python[7] Byl uveden v roce 1991 Guido van Rossumem. O vývoj jazyka se od roku 2001 stará Python Software Foundation. Jazyk není standardizovaný a de facto standardem je open source CPython implementace. Jazyk podporuje objekty, ale i procedurální a áste n i funkcionální programování. Python byl ovlivn n jazyky ABC, Lisp, Haskel, Perl i Java. Jedná se dynamicky typovaný jazyk se silnou typovou kontrolou a automatickou správou pam ti. Odsazení má význam, slouží k ur ování blok kódu. Má jednoduchou syntaxi a podporuje výjimky. Má velmi dobrou podporu pro spolupráci s jinými programovacími jazyky a je používán jako skriptovací jazyk v ad projekt , nap íklad v OpenOffice i vim. Mezi nejznám jší implementaci Pythonu pat í CPython, dále v Jav napsaný Jython, ve kterém lze používat javovské t ídy a který produkuje javovský bytecode. Dále zmi me IronPython generující mezikód pro platformu .NET i Nokií vydaný PyS60, což je implementace Pythonu pro Symbian. V sou asné dob se vyvíjí nová verze Python 3.0, která má být zp tn nekompatibilní, plánuje se vytvo it konverzní nástroj. Perl [5] Vznikl v roce 1987. Autorem je Larry Wallem. Stal se oblíbeným jazykem lingvist pro své dobré schopnosti práce s textem. Je též populárním nástrojem pro vytvá ení CGI skript . Charakteristické vlastnosti : • podpora objekt • garbage collecting (automatické správa pam ti) • dynamické typy • snadná práce s textem (XML, HTML), Unicode • podpora pro regulární výrazy • eval – generování vlastního kódu za b hu Bash Jde o z ejm nejpoužívan jší p íkazový interpret v Linuxu, ale díky jeho silným skriptovacím schopnostem je zajímavý i jako ukázka netypického programovacího jazyka. Protože se jedná hlavn o p íkazový interpret, negeneruje žádný mezikód. Podporuje funkce a 7

pole. Prom nné jsou textové, ale lze deklarovat i celo íselné. Podporuje eval a práci s regulárními výrazy.

2.2 Virtuální stroje Backend tvo í u interpret v tšinou virtuální stroj, který vykonává vygenerovaný mezikód. Tento mezikód, po vzoru Javy typicky zvaný bytecode, má p esn definovanou strukturu a je nezávislý na konkrétní hardwarové architektu e. Jeho specifikace jsou asto zve ejn né a zdarma k dispozici dalším vývojá m. Díky zve ej ování vznikají nejen alternativní virtuální stroje pro stejný mezikód, ale i nové p eklada e z již existujících jazyk do daného bytecodu. Mezi nejznám jší VM pat í Java virtual machine (JVM), Common Language Infrastructure (CLI) pro .NET a Parrot. Existující virtuální stroje : Parrot [6] Virtuální stroj pocházející od vývojá Perlu, jako interpret pro Perl 6. P i vývoji se kladl d raz na podporu dynamicky typovaných jazyk (Perl, Python), schopnost spolupráce mezi r znými jazyky. Parrot VM p ímo vykonává bytecode. Jeho vstupem m že být i Parrot abstract syntaxt tree (PAST) i Parrot assembly (PASM). Tyto vstupní formáty se p evádí na bytecode, který se poté vykonává. Pod PASM se rozumí symbolický zápis bytecodu, PAST p edstavuje typický výstup z p eklada e po provedení sémantické analýzy. Virtuální stroj je registrový. P i volání procedury se aktuální registry (register frame) uloží na zásobník a po ukon ení volané rutiny jsou odtud op t na teny. Po et registr není pevn dán, pro každou proceduru m že být rozdílný, jejich po et se ur uje b hem p ekladu do bytecodu. Registry jsou íslovány a mají 4 r zné typy : Integers (I) Numbers (N) odpovídají reálným ísl m Strings (S) PMCs (P) „Parrot Magic Cookie“, slouží k uložení struktur, polí, … Virtuální stroj obsahuje garbage collector, podporu pro vlákna. Pro n které procesory podporuje JIT kompilaci. PHP - Zend Engine [3][4] Implementace PHP vytvo ená The PHP Group. V podstat p edstavuje standard a nejpoužívan jší platformu pro tento jazyk. Obsahuje velké množství r zných rozší ení a knihoven. Nap íklad knihovny pro spolupráci s databázemi (MySQL, Oracle, ODBC,...), úpravy obrázk , pro práci s internetovými protokoly (HTTP, FTP, SMTP, POP3, LDAP, …). Jeho jádrem je Zend Engine, který je uvoln n jako open source. PHP skripty jsou p eloženy do mezikódu a ten posléze pomocí ZE interpretován. P i návrhu se kladl d raz na výkon a rozši itelnost. Pro zvýšení výkonu PHP je možné použít optimizery i cache. Od dalších autor zmi me kompilátor Roadsend (http://www.roadsent.com/) nebo softwarový projekt na MFF PHP.NET (http://www.php-compiler.net/) pod vedením RNDr. Vojt cha Jákla. Java Virtual Machine [2] JVM je virtuální stroj, jehož vstup p edstavuje bytecode v podob class soubor . Primárn vnikl pro interpretaci Javy, ale díky zve ejn ní toho formátu byly vytvo eny p eklada e z široké palety jazyk (C, C++, Ada …). Existuje velké množství open source i proprietárních implementací JVM. Mezi nejpoužívan jší pat í HotSpot od firmy Sun. Z dalších zmi me Oracle JVM (používá ji ve svých databázích), od IBM V9 VM, Kaffe, Juice, 8

NanoVM. Pro Javu existují i p eklada e, generující p ímo spustitelný kód, což umož uje zvýšit výkon, ale p ijde se o možnost spušt ní programu na více platformách, nap íklad GCJ . JVM je zásobníkov orientovaný stroj. Každá instrukce má délku jeden byte, což dává potenciál pro 256 r zných instrukcí. Ve skute nosti je po et instrukcí menší a obsahuje aritmetické, Load Store instrukce, instrukce pro práci se zásobníkem, volání metod, ale i instrukce pro vyvolávání výjimek, synchronizaci i pro zacházení s objekty. P ed spušt ním bytecodu se typicky provádí kontroly - verifikace. HotSpot [1] je virtuální stroj od Sun Microsystem. Své jméno získal od zp sobu jakým funguje. Pr b žn analyzuje program a vyhledává „hot spots“ - místa která jsou asto vykonávána a na tyto posléze aplikuje r zné optimalizace. Díky tomu se snižuje as pot ebný na optimalizace, snižuje rozsah optimalizovaných míst. HotSpot využívá JIT i adaptivní optimalizace. Obsahuje n kolik r zných garbage collector . Zmi me „fully accurate“ genera ní GC, který používá pro krátce žijící objekty, a Mark-Compact Old object collector pro správu dlouho žijících objekt . HotSpot v sob obsahuje dv verze VM – Client a Server. Client verze je optimalizovaná pro rychlý start aplikací a spot ebu pam ti, neprovádí komplexní optimalizace, zatímco serverová verze je optimalizovaná pro maximální rychlost, provádí d kladnou analýzu i optimalizace, je vhodná pro dlouho b žící aplikace. Common Language Infrastructure (CLI) [8] Common language infrastructure je otev ený standard, který vyvinula firma Microsoft. Popisuje prost edí .NET Frameworku. Cílem návrhá bylo vytvo it prost edí, které je nezávislé na platform a umož uje spolupráci mezi r znými vyššími jazyky. Jeho hlavní ásti popisují typy a operace s nimi (Common type system – CTS), metadata, výkonnou ást (Virtual execution system – VES) a pravidla umož ující spolupráci mezi jazyky (Common language specification – CLS). Sou ástí specifikace je i popis instrukcí virtuálního stroje. Tento „assembler“ je nazýván Common intermediate language – CIL, asto též zvaný MSIL (Microsoft intermediate language). Zkratka MSIL pochází z dob p ed standardizací jazyka. Jedná se o zásobníkový stroj, s podporou výjimek, objekt a vláken. Podporuje též garbage collecting, který se ovšem nemusí používat – CIL obsahuje dva druhy ukazatel „Managed“ a „Unmanaged“, s rozdílným p ístupem garbage collector . Na rozdíl od javovského bytecodu, kde byl typ položek na zásobníku ur ován instrukcí (iadd, fadd instrukce), obsahuje CIL pouze jednu instrukci a podle aktuálního obsahu zásobníku bu s ítá celo íseln nebo v plovoucí ádové árce. Existují r zné implementace tohoto standardu zmi me CLR, Mono, DotGNU, Portable .NET Framework. Common Runtime Language (CLR) [9] CLR je implementací CLI standardu firmou Microsoft. Je sou ástí balíku .NET Framework. Podporuje opera ní systémy rodiny Windows. Mono [10] Mono je open source projekt podporovaný firmou Novell. Cílem je vytvo it nejen implementaci CLI ale i další nástroje, zmi me p eklada C#. Podporované systémy jsou Linux, MacOS, Solaris, Unix, FreeBSD i Windows. V sou asné dob obsahuje JIT kompilátor pro procesory rodiny x86, PowerPC a Sparc. Interpretovan je schopen spoušt t aplikace na procesorech ARM a Itanium. Sou ástí projektu je i implementace knihoven dodávaných s .NET Frameworkem, jako nap íklad Windows Forms i ASP.NET. Tyto knihovny nejsou sou ástí standardu CLI a n které jsou p edm tem patentové ochrany.

9

2.3 Pokro ilé metody používané ve VM V nejvýkonn jších VM jsou implementované r zné optimalizace a u nejexponovan jších ástí kódu dochází ke generování nativního kódu pro procesor, na kterém je program spušt n. T mito postupy se VM op t p ibližují ke klasickým p eklada m. V sou asné dob stále probíhá vývoj, vylepšování algoritm , které se ve VM používají. Na rozdíl od p eklada , kde se dají použít i asov náro n jší algoritmy, zde musí být použity extrémn rychlé algoritmy. VM optimalizují až v okamžiku vykonávání programu a as strávený optimalizací se p i ítá do doby b hu programu. Just in Time compilation (JIT) [11] P i tomto postupu dochází k transformaci bytecodu a vytvo ení nativního kódu, který je možný spustit na aktuálním procesoru. K transformaci nemusí docházet u celého programu, ale pouze u jeho ástí. Pak je pot eba doplnit kód, který se postará o korektní p echod z nativní do interpretované ásti. P estože transformace do nativního kódu trvá ur itý as, tak výhody z b hu maximální rychlostí p evažují. Protože je už znám konkrétní procesor, b hové statistiky a aktuální dynamické knihovny, je možné nap íklad optimalizací na konkrétní procesor, správným výb rem instrukcí, inlinováním funkcí i z knihoven získat další zvýšení výkonu. Adaptivní optimalizace Je technika, p i níž se dynamicky provádí rekompilace ásti programu v závislosti na získaných profilujících informacích. Umož uje využít rychlosti JIT kódu, aniž by se musel celý projekt p ekládat, p ípadn na nejexponovan jší ásti kódu využít déletrvající optimalizace. Oproti profilování u neinterpretovaných jazyk m že využívat informace z aktuálního b hu a dynamicky se p izp sobovat jejich zm nám. Garbage collectors [12] Garbage collecting je zp sob automatické správy zdroj , nej ast ji pam ti, kdy dochází k automatickému uvol ování již nepot ebných zdroj . GC mají dlouhou historii, používají se již od roku 1959. Garbage collecting se asto používá u interpretovaných jazyk (nap . v Jav , C#, Perle, Ruby), ale i v funkcionálních jazycích jako Haskell i Lisp, p ípadn skriptovacích jazycích. I do jazyk , které garbage collecting standardn neobsahují, se dá asto pomocí knihoven p idat, což je p ípad C++. Existují dva hlavní p ístupy p i implementaci GC – Reference counting a Reference tracing. Dalším hlediskem, dle kterého m žeme d lit algoritmy, je p esnost detekce nedosažitelných blok , p ípadn jestli provád jí p esuny blok pam ti. Exaktní (též „accurate“ i „precise“ ) algoritmy naleznou všechny nedosažitelné bloky, kdežto konzervativní algoritmy mohou n které z nedosažitelných blok ozna it za dosažitelné. Kompaktující algoritmy po uvoln ní nedosažitelných blok pam ti provádí p esuny zbylých blok , cílem je vytvo it co nejv tší blok(y) pam ti obsahující pouze naalokované objekty. Dochází tím ke snížení fragmentace pam ti, vylepšuje se lokalita referencí a využití vyrovnávacích pam tí, umož uje provád t rychlejší alokaci. Reference counting Zp sob založený na po ítání po tu ukazatel sm ujících na objekt. S každým objektem je asociováno po ítadlo, které obsahuje aktuální po et referencí na tento objekt. P i zm n ukazatele musíme po ítadla aktualizovat. Pokud se p i aktualizaci po ítadlo sníží na nulu, je objekt zrušen. Problém p edstavují cykly, kdy je nedosažitelný celý cyklus. V rámci cyklu mají objektu nenulový po et referencí a tudíž se nezruší. A dále více vláknové aplikace, kdy se musí aktualizace provád t atomicky. 10

Reference tracing Metody založené na procházení po et zcích ukazatel . Takto se naleznou všechny dosažitelné objekty a zbytek se odalokuje. Na po átku se jako dosažitelné ozna í všechny globální objekty a objekty uložené na zásobníku. Postupn mezi dosažitelné p idáváme všechny objekty, na které existuje v dosažitelných objektech ukazatel, jinými slovy tvo íme tranzitivní uzáv r. Nejjednodušší implementace pot ebovaly zastavit b h programu („stop the world“ algoritmy), aby se nem nily ukazatelé a tím i dosažitelné objekty. Složit jší implementace dovolují st ídání b hu („incremental“ algoritmy) GC a programu, p ípadn i jejich sou asný b h („concurrent“ GC).

Diagram 1: Reference counting – cycle

11

3 Vnit ní návrh 3.1 P ehled Vnit ní struktura mého interpretu odpovídá zažité struktu e frontendu u p eklada . Rozdíl spo ívá v backendu, kde interpret ve své nejjednodušší podob obvykle mívá virtuální stroj, který zpracovává vygenerovaný mezikód. Na po átku je vstupní soubor lexikálním analyzátorem p eveden na tokeny, ze kterých pak syntaktický analyzátor vytvo í stromovou strukturu (abstract syntax tree) zachycující deriva ní strom gramatiky. Nad vzniklým stromem se provede sémantická analýza a poté se z n j vygeneruje mezikód. Sémantické testy jsou pro svoji velmi rozdílnou povahu roztroušeny na mnoha místech kódu. V tšina z nich se nachází v t ídách, které mají na starosti generování mezikódu, i reprezentují pascalské typy. Srdcem interpretu je syntaktický analyzátor, který žádá o další tokeny a vyvolává sémantické akce. Interpret je dvou pr chodový. B hem parsování procedury se p i vyvá ení AST provádí první pr chod a ihned po dosažení konce procedury se spustí druhá fáze, která pro proceduru vygeneruje mezikód. Poté již AST není pot eba a m že být uvoln n, ím lze šet it pam . B hem parsování se vytvá í i jiné objekty, které slouží k reprezentaci uživatelem definovaných typ , prom nných, konstant a label . Takto vytvo ené objekty se registrují v k nim p íslušných správcích. Poté se místo ukazatel na tyto objekty p edávají jejich indexy. Správcovské t ídy p edstavují rozhraní pro p evod identifikátor na dané objekty. P evodní informace se ukládají do vrstev, struktura vrstev kopíruje strukturu zano ování procedur. Ke každé procedu e p ísluší vrstva. V té jsou uloženy objekty ze vstupního jazyka, které jsou v této procedu e vytvo ené. Koncept vrstev se používá za ú elem simulace viditelnosti prom nných. B hem zpracovávání dané procedury je vrstva k ní pat ící na zásobníku vrstev a tedy objekty v ní jsou viditelné. Po dokon ení zpracovávání procedury je vrstva ze zásobníku odstran na, ím se objekty zneviditelní. Generování mezikódu se z v tší ásti odehrává na dvou místech. Instrukce zodpov dné za aritmetické a logické operace se generují ve t íd reprezentující daný typ. Potomci t ídy CodeGenerator vytvá í mezikód odpovídající základním konstrukcím interpretovaného jazyka Pascal (repeat until, if then else). Vygenerovaný mezikód je registrového typu, kde po et registr není omezen. To

Diagram 2 : Vnit ní struktura 12

p edstavuje nejv tší odlišnost od b žného asembleru. Registry jsou uloženy ve vrstvách a p i volání procedury se vytvo í nová vrstva, která drží hodnotu registr . Tento návrh byl inspirován virtuálním strojem Parror. Instrukce jsou ukládány do basic blok , proto tedy neexistují instrukce pro skoky i podmín né skoky. Úpln mimo stojí funkce pro hlášení chyb.

3.2 Lexikální analýza Lexikální analýzu v mém p ípad provádí lexer vygenerovaný pomocí programu flex[15], což je voln ši itelná alternativa programu lex. Flex slouží ke generování textových analyzátor , které se používají pro hledání vzor . Tyto analyzátory se používají nejen v p eklada ích. Další z mnoha využití je nap íklad p i zpracování textov orientovaných sí ových protokol , p ípadn konfigura ních soubor . Dalšími známými generátory scanner jsou flex++, Ragel a Quex. Flex++ je flex rozší ený o schopnost generovat C++ analyzátor. Ragel[13] je multiplatformní, voln ši itelný generátor. Jeho p edností je schopnost vygenerovat výsledný analyzátor v mnoha r zných jazycích. Umí vytvo ený stavový automat zobrazit v grafické podob pro snadn jší lad ní a provádí jeho minimalizaci. Quex[14] je schopen generovat analyzátory s podporou vstupu Unicode znak , výsledný analyzátor je v C++. Vygenerovaný analyzátor p ímo odpovídá vstupní gramatice. Naproti tomu analyzátor z flexu obsahuje vygenerované tabulky p echod a pevný kód pro procházení tabulek. Výhodou tohoto netabulkového p ístupu je vysoká rychlost vygenerovaného analyzátoru. Výstupem z lexikálního analyzátoru je token, jeho p ípadné up esn ní p edstavované unií lexval a objekt location, ur ující pozici tokenu ve vstupním souboru. Z unie lexval se pro pot eby lexikální analýzy používají pouze položky dtge a idx. Dtge slouží k uložení p esn jší informace o operaci. Aritmetické a logické operace jsou rozd leny podle priority a jsou reprezentovány pouze n kolika málo tokeny. A tato položka ur uje, o kterou konkrétní operaci se jedná. Položka idx se používá v p ípad identifikátor , kdy obsahuje index, pod kterým je text identifikátoru uložen v tabulkách symbol . Po zavolání funkce yylex vrátí parser další token jako návratovou hodnotu. Tato funkce p edstavuje rozhraní mezi syntaktickým a lexikálním analyzátorem. Vstup pro analyzátor p edstavuje soubor se zdrojovými soubory v Pascalu. Nastavování toho, který soubor se má zpracovávat, se ovšem provádí nep ímo p es metody t ídy FileManager. Hlavním d vodem pro vytvo ení tohoto rozhraní byla schopnost cachovat již zpracované soubory a kv li ur ení správného po adí soubor pro zpracování. Implementace metod, které se starají p ímo o p epínání vstupu pro analyzátor se nachází na konci souboru InterpFlex.lex, protože jinde nejsou definované (a viditelné) pot ebné typy a makra, což považuji za velmi neš astné ešení od autor Flexu. Tokeny, které parser vrací jsou definovány v souboru InterpBison.y respektive v souboru InterpBison.hpp, který je z n j vygenerován. Nejv tší ást token odpovídá klí ovým slov m ze vstupního jazyka a matematickým operacím. Vstupem pro flex je soubor InterpFlex.lex. Zde se v úvodní ásti nalézají definice pomocných prom nných používaných v parseru a nastavení pro generátor. V další ásti jsou pomocí regulárních výraz popsány lexémy a akce, které se mají vykonat p i jeho nalezení na vstupu. V záv re né fázi je kód, který se stará o p epínání vstupu pro parser. B hem p ekladu se na tento soubor spouští flex, který z n j vygeneruje soubory InterpFlex.h, InterpFlex.cpp, které obsahují vygenerovaný parser a lex.backup, který obsahuje informace o problémech, které se vyskytly b hem generování parseru. V souboru InterpFlexFunctions.h se nacházejí deklarace pomocných funkcí používaných v parseru. V tšina z nich se týká zpracování textu a ísel v r zných zápisech. Tyto metody testují rozsahy, p evádí text na ísla a ukládají je do tabulek symbol .

13

V této ásti programu by si asi nejvíce zasloužilo zm nit generátor, na takový který generuje C++ analyzátor a umož uje jednodušeji p epínat vstupní soubory. Dále by bylo vhodné zlepšit po ítání pozice jednotlivých token . V sou asné dob se po ítají pouze ádky, bylo by rozumn jší po ítat i pozici znaku na ádce. Toto chování je poz statek z d ív jších verzí, kdy se bisonem ješt negeneroval C++ syntaktický parser a pro ur ování pozice se místo t ídy location používal integer s íslem ádku.

3.3 Syntaktická analýza[18][22] Dalším krokem po provedení lexikální analýzy je analýza syntaktická. Vstupní jazyk je typicky popsán pomocí bezkontextové gramatiky. Úkolem syntaktické analýzy je rozhodnout, jestli proud token z lexikálního analyzátoru m že být touto gramatikou generován, kdy a jaké p episovací pravidlo se použilo. V praxi se používají dva zp soby, jak tyto úkoly provést. Prvním p ístupem je rekurzivní sestup. Tato metoda se hodí pro ru ní generování parser . Lze jí rozeznávat LL gramatiky. Po odstran ní levých rekurzí a faktorizací, jde gramatiku jednoduše p epsat do zdrojového kódu, kde každý neterminál p edstavuje funkci, ve které se podle výhledu rozhodujeme, jaký by m l být další token i neterminál a provádíme sémantické akce. Druhou možností jak postupovat, je takzvané Bottom-up parsování (analýza zdola nahoru), kdy se deriva ní strom staví zdola a hledá se nejprav jší derivace pro vstupní et zec. Protože vytvo it parser, není úpln jednoduchá záležitost, vznikly r zné generátory parser . Mezi nejznám jší pat í Bison, Coco/R a ANTLR. Coco/R[16] je generátor jak pro lexikální analyzátor tak syntaktický parser. Generuje LL(1) parser, kdy kolize lze ešit bu to prodloužením výhledu LL(k) nebo sémantickými akcemi. Výsledný parser m že vygenerovat v C++, C# nebo Jav . Coco/R je vydáván pod GNU licencí, ale vygenerovaný kód již pod GNU licenci nespadá. ANTRL[17] je zkratka pro ANother Tool for Lanuguage Recognition. Vytvá í LL parsery ve velkém množství jazyk – C, C++, C#, Java i Pythonu. Pat í k nejpoužívan jším a je aktivn vyvíjen. V mém p ípad se parser generuje pomocí programu bison ze souboru InterBison.y. Výstupem je InterpBison.hpp obsahující t ídu parser a seznam token , které mohou být výstupem lexikální analýzy. Dále vytvo í soubory location.hh se stejnojmennou t ídou, jejíž instance reprezentuje spojitý blok ve vstupním souboru, position.hh, který obsahuje t ídu reprezentující bod ve vstupním souboru a InterpBison.output, který popisuje parser, p echody jednotlivých stav a problémy, které se v gramatice nachází. Veškeré t ídy, které bison vytvo í jsou v jmenném prostoru yy. Vstupem parseru jsou tokeny z enumu yy::yytokentype, dopl ující lexikální informace o tokenu a pozice tokenu p edstavovaná instancí objektu yy::location. V p ípad , že parser pot ebuje další token ze vstupu, zavolá globální funkci yylex. Nejd ležit jší inností parseru, krom detekce syntaktických chyb, je vytvo ení AST, který reprezentují objekty potomk t ídy CodeGenerator, a napln ní tabulek s vytvo enými typy, prom nnými a labely. V souboru InterpBisonFunctions.h se deklarují pomocné funkce, které jsou volané ze sémantických akcí parseru. V tšina t chto akcí, pokud není p edstavovaná jedním p íkazem, je z d vodu itelnosti vstupního souboru p evedena na volání funkce z toho souboru. Tento p ístup zamezuje duplikaci kódu, protože tyto funkce jsou asto volány z více r zných míst. V tšina funkcí se týká vytvá ení typ a prom nných, zpracování jednotek a p íkazu case. Gramatika odpovídající vstupnímu jazyku se nachází v souboru InterpBison.y. Po áte ní neterminál je pocatek. Tento se oproti o ekávání d lí na t i pravidla – parsování programu, první ást jednotky a poslední je implementation ást pro jednotku po restartování parseru. Pravidla popisující výraz mají shodn jako návratovou hodnotu položku Exp typu

14

Expression z unie lexval, která již v sob nese informaci o umíst ní ve vstupním souboru. Oproti pov stné gramatice1 pro parsování výraz máme neterminály vyraz a vyrazFnc. Rozdíl mezi nimi spo ívá ve funkcích a procedurách bez parametr , kdy vyraz již reprezentuje jejich zavolání, kdežto vyrazFnc je chápe jako adresu. Dalším rozdílem proti pov stné gramatice je podpora unárních operací „+“, „-“ p idáním jednoduchyVyraz, dále neterminál fncCall, který reprezentuje „operaci“ zavolání funkce a rozší ení o porovnávací operace. Pravidla týkající se zpracování p íkaz mají jako návratovou hodnotu položku CodeGen z unie lexval. Op t máme dva neterminály: prikazBezLabelu a prikaz. Existenci prvního si vynutila podpora pro case. Problém zp sobovaly labely p ed prvním p íkazem, nejednozna nost se vyskytovala pokud byly labely íselné, stejn tak jako hodnota ur ující rozsah v case v tvi. P ímo v gramatice bylo pot eba ur it, že hodnotu p ed první dvojte kou musíme chápat jako konstantu definující rozsah a hodnoty p ed dalšími dvojte kami jako labely. Dále bylo pot eba vy ešit tzv. Dangling-else problém, kdy je pot eba správnou úpravou gramatiky odstranit nejednozna nost v p íslušnosti else k if. Sémantické akce u p íkaz obsahují pouze budování AST vytvá ením objekt odpovídajících CodeGenerator t íd. Seznamy identifikátor , použitých nap íklad p i definici prom nných, seznamy parametr procedur a další jsou specializací šablony list ze souboru InterpList.h. List vytvá í spojový seznam, kde lze nové prvky p ipojovat na po átek, který umí spo ítat svou délku a ud lat kopii. Pro snadn jší uvol ování a klonování seznamu seznam jsou v souboru vytvo ena speciální makra. V p ípad vytvá ení konstant, typ , prom nných, label a procedur je situace odlišná od p íkaz a výraz . Již nedochází k budování AST, ale vytvo í se objekty zastupující daný element ze vstupního jazyka a ty p idáváme do p íslušných tabulek, aby je pozd ji, až se na n bude odkazovat, bylo možné dohledat. Sekce const a var používají kv li velké podobnosti stejné pomocné funkce. Rozdílný je ale zp sob zpracování, kdy konstanty a inicializované prom nné jsou zpracovávané jednotliv po definici a prom nné po celé sekci. Zpracování po celé sekci se p idávalo dodate n a s výhodou se používá p i definování strukturovaného typu (record). Labely, typy, deklarace a definice procedur i jednotky zpracováváme jednotliv po definicích a jejich pravidla nevrací žádnou návratovou hodnotu. U procedur situaci mírn komplikuje pouze v tší množství pomocných neterminál – pro zpracování formálních parametr , neterminály odpovídající úvodnímu záhlaví procedury i funkce (zahlaviProc, zahlaviFce). Dále se k procedurám vztahují pravidla pro definici a deklaraci v programu (blokProcFuncPart) a v interface ásti u jednotky(unitIfaceProcFuncPart). Další typ pravidel gramatiky se týká celých blok s r znými sekcemi. V podstat je t eba rozlišit 3 typy blok . Jeden, který se používá v interface ásti jednotek, kde lze používat uses a deklarace procedur má sv j zvláštní tvar (interfaceBlock), pak úvodní blok programu, kde jde používat uses a deklarace procedur má obvyklý tvar (blokStartPartUses). Tento typ bloku se používá též v implementation ásti jednotek. Poslední typ bloku se používá v procedurách a na rozdíl od p edchozího již nesmí obsahovat uses (blokStartPart). Nejslabším místem v syntaktické analýze je podle m špatn navržené p edávání informací o poloze token . V n kterých p ípadech nedochází k ukládání polohy, nap íklad v seznamech identifikátor p i definování prom nných a vý tových typ . Bylo by vhodné zavést pravidlo, že pro každý token se pamatuje i jeho pozice ve vstupním souboru. Dalším problemati t jším místem je zastavování a obnovování parsování souboru, kde jsou použité ne moc isté programovací praktiky. To je z d vodu podpory jednotek. Problém spo ívá v tom, že vygenerovaný parser neumož uje p erušit parsování a pozd ji od stejného místa pokra ovat dále. ešením by bylo použít parser, který p erušování podporuje.

1

Literatura [22] – ást Lexikální a syntaktická analýza, strana 11; Jednoduchá gramatika pro aritmetické výrazy s binárními operacemi „+”a “*”, závorkami a identifikátory prom nných

15

D kladn jší pohled by si zasloužilo i zotavování ze syntaktických chyb. V sou asnosti je již základní zotavení podporováno, ale ur it by si zasloužilo d kladn jší analýzu. Zotavení z chyb a další pokra ování v parsování sebou p ináší zvýšené požadavky na návrh dalších ástí front-endu, kde se musí po ítat s nekorektností vstupu a p ípadným chybovým stavem vnit ních struktur. Rozumné by bylo zlepšit hlášení syntaktických chyb.

3.4 CodeGenerator t ídy AST je v mém p eklada i reprezentován stromem vytvo eným z instancí potomk t ídy CodeGenerator, která definuje obecné rozhraní. Až na drobné výjimky, o kterých se pozd ji zmíním, AST odpovídá deriva nímu stromu gramatiky ze syntaktického parseru. Výhodou tohoto p ístupu, oproti generování mezikódu p ímo bez vytvá ení AST, je možnost pozd ji jednoduše p idat vysokoúrov ové optimalizace. Hlavním úkolem t chto t íd je generovat výsledný mezikód a provád t sémantické kontroly. Bu k nim dochází p ímo v konstruktorech t chto t íd, anebo nep ímo, nap íklad u operací, kdy se kontroly provádí ve volaných metodách na objektech reprezentující typy operand . Speciálním potomkem je t ída Expression, která rozši uje rozhraní tak, aby obsáhlo požadavky kladené na výrazy. Potomci CodeGenerator t ídy v tšinou odpovídají klí ovým slov m ve vstupním jazyce a velmi asto provádí zm ny v control-flow, tedy správným zp soben na sebe napojují basic bloky. Definice rozhraní se nachází v souboru InterpExpression.h a definice konkrétních potomk se nalézají v souboru InterpExpressions.h. Nyní si popíšeme a vysv tlíme význam jednotlivých metod t ídy CodeGenerator. Nejd ležit jší metodou je genCode. Ta zajiš uje vygenerování mezikódu pro daný podstrom AST. V ní se neprovádí testování a hlášení chyb. I z tohoto d vodu se všechny testy, pomocné prom nné a basic bloky vytvá í již v konstruktorech. Proto není možné volat tuto metodu na konkrétní instanci podstromu vícekrát. Zp sobilo by to vícenásobné vygenerování stejného mezikódu do p edp ipravených basic blok . V p ípad nutnosti je možné daný podstrom naklonovat a posléze z této nové instance vygenerovat mezikód podruhé. Metody setParrent a getParrent slouží k nastavení a získání rodi e v AST stromu. Povinností každého potomka této t ídy je, nastavit se v konstruktoru nastavit za otce u všech p ímých potomk . Tento zp tný ukazatel se využívá u klí ových slov break a continue, kdy se prochází strom ke ko eni a hledá se objekt reprezentující cyklus. Pro detekci cykl slouží metody getStartBB a getNextBB. První jmenovaná metoda vrací místo kam sko it v p ípad klí ového slova continue (podmínka u vstupu do cyklu) a druhá vrací místo, kde pokra uje vykonávání kódu po opušt ní cyklu, což odpovídá sémantice p íkazu break. V p ípad , že daný objekt nereprezentuje cyklus, vrací se neplatná hodnota. Pro ú ely korektního hlášení chyb vznikla metoda getLocation, která vrací pozici ve vstupním souboru s p íkazy, ze kterých se vzniklý AST strom vygeneroval. CloneCodeGenerator vytvá í novou kopii AST podstromu, která používá nové pomocné prom nné, basic bloky a lze ji použít pro nové generování mezikódu. V sou asné dob se tato metoda nepoužívá, vznikla jako p íprava pro vysokoúrov ové optimalizace. T ída Expression je rozší ením rozhraní z CodeGenerator. Nejd ležit jší novou metodou je storedResult, která vrací prom nnou, kam vygenerovaný mezikód uloží výslednou hodnotu. V p ípad volání procedury i chyby ve výrazu je návratová hodnota index pro neplatnou prom nou. CloneExpression se chová stejn jako u t ídy CodeGenerator, pouze vrací více specializovanou t ídu. IsVariable je p íznak, který signalizuje, zda daná t ída odpovídá prom nné. P íznak isFunctionCall signalizuje, zda daná instance p edstavuje zavolání procedury nebo funkce. Jeho významem je odlišení chybného výrazu od volání procedury, které jsou reprezentované stejným výsledkem (stored result je index neplatné prom nné).

16

Ke t ídám definující rozhraní jsem vytvo il pomocné t ídy sufixované Prefab. V nich jsou generická t la pro metody, u kterých se dá o ekávat, že budou u v tšiny potomk stejná. Konkrétn jsou u CodeGeneratorPrefab definované metody pro práci se zp tnou hranou na otce (getParrent a setParrent) a pozicí (getLocation). T la metod getStartBB a getNextBB, jsou vhodná pro t ídy, které nereprezentují cyklus. U t ídy ExpressionPrefab jsou to metody isVariable a isFunctionCall vracející false. A jejich implementace se používá u všech potomk až na ExpressionVariable a ExpressionFunctionCall. Speciální t ídou je CodeGeneratorSupportRutines, která obsahuje pouze statické podp rné a testovací metody, které se používají z ostatních t íd v této sekci. Jde o metody testující, zda je daný výraz ordinální (isOrdinalExpression), i lze-li ho použít v podmínce (isBooleanExpression). Pak jde o correctFunctionResultName, jejím ú elem je umožn ní nastavování návratové hodnoty. Pokud je výraz na vstupu prom nná procedury, kterou práv zpracovávám, zm ní výraz tak, aby odpovídal návratové hodnot této procedury. V ostatních p ípadech vstupní výraz nem ní. Aplikuje se na levou stranu p i azovacího p íkazu. Poslední metodou je getInterpreterProcedure. Tato metoda vrací reprezentaci aktuáln zpracovávané procedury v interpretu. Každý basic blok, který se vytvo í, musí mít vlastníka (InterpreterProcedure). Tato metoda slouží pro jeho zjišt ní. Z tohoto návrhu plyne omezení na klonovací metody, kdy nem žu klonovat v p ípad , že se zm nila aktuáln zpracovávaná procedura na jinou. P i programování potomk výše zmín ných t íd jsem se snažil dodržovat ur itá pravidla. Jejich hlavním cílem bylo konzistentní chování p i výskytu chyb a odolnost v i nim, snadná pochopitelnost, pr hlednost kódu. Jejich pochopení by m lo usnadnit porozum ní zdrojovému kódu t chto potomk a pomoci p i p ípadném rozši ování. Veškeré testování se provádí v konstruktorech a pokud se vyskytne chyba, tak se objekt p evede do chybového stavu, kde se negeneruje žádný mezikód a prom nná s výsledkem odsahuje index neplatné prom nné. Dále je pot eba pokra ovat v kontrolách i po nalezení chyby tak, aby prob hly veškeré testy a byly nahlášeny všechny chyby a ne pouze první. Privátní prom nná checkPassed slouží jako p íznak chybového stavu. Metoda generateBasicBlock se volá z konstruktor po úsp šném provedení sémantických a jiných test a slouží k inicializaci pomocných prom nných, typicky k vytvo ení basic blok , ale též i k tvorb pomocných výraz . GenerateCode metody nehlásí chyby. Chyba by m la být otestována a nahlášena již v konstruktoru. Toto pravidlo se snaží zamezit stav m, kdy se chyby hlásí na p eská ku a p ípadn vícenásobn , pokud by byl kód generován i z naklonované procedury. Pro nelze vygenerovat kód vícekrát a musí docházet k jeho klonování? Problém je v tom, že se nové basic bloky vytvá í již v konstruktorech objekt a ne až když jsou pot eba pro generování mezikódu. Jejich umíst ní v konstruktoru je vynuceno existencí metod getStartBB a getNextBB, které musí n jakou hodnotu vracet. A dále pokud by byl mezikód vygenerován i s novými basic bloky vícekrát, který z t chto basic blok by metody m ly vracet. Pokud by docházelo ke specializaci kódu v jednotlivých v tvích, nebylo by možné je mezi sebou zam ovat. Mimo to by vícenásobné generování kódu vedlo na násobné použití pomocných prom nných. Tím budou mít n kolik typicky disjunktních dob života. Detekce t chto situací klade v tší nároky na analýzu rozsah platnosti p i pozd jších optimalizacích. ExpressionVariable je velmi jednoduchou t ídou. Reprezentuje použití uživatelem definované prom nné ze vstupního souboru ve výrazu, p ípadn pomocné prom nné vytvo ené interpretem pro proceduru i jiný objekt. Jediným testem je, zda prom nná pod daným indexem v bec existuje. Mezikód se generovat nemusí. T ída ExpressionConvert provádí konverze mezi r znými pascalskými typy. Tato t ída nemá reprezentaci v gramatice vstupního jazyka. A díky ní si deriva ní stromy gramatiky a ATS neodpovídají. Používá se tak, že dostane výstupní typ a libovolný výraz. Pokud je to 17

nutné a pokud to dokáže, snaží se provést konverzi. Pokud nelze konverzi provést, nahlásí sémantickou chybu o neschopnosti zkonvertovat typ. Sou asná implementace dokáže p evád t celá ísla na reálná, zv tšovat p esnost u reálných typ a p evád t na sebe r zné intervalové typy. Z d vodu výpo tu konstantních výraz b hem p ekladu umí p evád t i konstantní prom nné. Tyto se na rozdíl od oby ejných prom nných musí konvertovat už v konstruktoru, aby se jejich hodnota dala používat dále p i výpo tech t chto výraz . Proto jsou rutiny provád jící konverze na dvou místech v této t íd a musí se udržovat v i sob konzistentní. ExpressionOperation je t ída zodpov dná za generování kódu pro aritmetické a logické operace. Jejím úkolem je podle operand rozhodnout, na jakém typu se má daná operace provád t a vykonat nezbytné typové konverze pomocí d íve zmín né t ídy ExpressionConvert. Na t íd reprezentující daný typ nejprve volá metodu genOperationStorage, aby získal prom nnou pro uložení výsledku, a pak se z genCode volá genOperationCode pro vygenerování instrukcí provád jící danou operaci. Oproti p ístupu, kdy by se kód pro generování mezikódu nacházel p ímo v této t íd , vychází mnou zvolený p ístup jako snadn ji rozši itelný, s p ehledn jším a lépe len ným zdrojovým kódem a odpovídá p ístupu, že typ by m l v d t, jak se na n m provád jí jednotlivé operace. Zvláštní operací, která si vysloužila vlastního reprezentanta, je volání funkce. Tuto zastupuje t ída ExpressionFunctionCall. Oproti regulérním aritmetickým operacím má funkce prom nný po et parametr a vyžaduje mírn odlišné zacházení p i generování mezikódu. Pro uložení parametr slouží callParam, což je vektor výraz . Protože ale b hem parsování parametr vytvá ím list výraz , obsahuje tato t ída statickou metodu ExpressionList2callParams pro p evod mezi t mito dv ma reprezentacemi. Volací konvence p edpokládá, že místo pro volanou funkci vytvá í i uvol uje volaná funkce. P estože tento typ volací konvence umož uje používání prom nného po tu parametr , mnou zvolená reprezentace toto nepodporuje. Ovšem ani v mnohých jiných implementacích Pascalu se podpora pro funkce s prom nným po tem parametr nevyskytuje. Tímto jsme dokázali popsat výrazy, zbývající ást se týká popisu potomk CodeGenerator, kte í zastupují r zné jazykové konstrukce. Pro reprezentaci bloku p íkaz slouží CodeGeneratorStatement. Jeho innost je velmi jednoduchá, pouze se postará o vygenerování mezikódu pro všechny p íkazy, které jsou v daném bloku obsaženy. CodeGeneratorIf reprezentuje podmín ný výraz. Je to první ze t íd, kde dochází ke zm n control-flow. Musí se um t vypo ádat s neexistencí else v tve a testovat, zda je daný výraz podmínkou. CodeGeneratorRepeat a CodeGeneratorWhile zastupují stejnojmenné cykly. Rozdílem je pouze cíl skoku z p edchozího basic bloku a opa ný význam podmínky. V p ípad repeat cyklu se ská e na t lo cyklu, u while cyklu nejprve do ásti pro vyhodnocení podmínky. U while cyklu existují dv možnosti jak vygenerovat výsledný kód. Vygenerovaný mezikód umož uje, aby p i linearizování mezikódu vznikla verze, kde je pouze jeden skok v t le cyklu. V mém mezikódu ovšem po et skok neušet ím, protože z d vodu existence klí ového slova continue musí být podmínka v samostatném basic bloku, aby na ni bylo možno sko it. T ída CodeGeneratorBreakContinue je o poznání zajímav jší a reprezentuje ze vstupního jazyka klí ová slova break, continue a exit. O jaký typ klí ového slova se jedná pozná podle parametru v konstruktoru. P i generování mezikódu pro continue a break procházím, pomocí zp tných hran, v AST stromu sm rem ke ko eni a podle návratové hodnoty metody getStartBB poznávám, jestli daný uzel reprezentuje cyklus. Takto najdu reprezentanta nejvnit n jšího cyklu a podle typu reprezentovaného klí ového slova získám bu basic blok s podmínkou (continue), anebo s pokra ováním za cyklem (break). V p ípad exitu je situace mírn odlišná. Bohužel jednoduché ešení s myšlenkou vygenerovat instrukci 18

ret, která by ukon ila aktuální proceduru, není použitelné. D vodem jsou prom nné, kdy každá prom nná má možnost mít sv j inicializa ní (genInitCode) a destruk ní (genExitCode) kód. Proto je nutné nalézt zástupce pro aktuální proceduru a zjistit basic blok, kde je vygenerovaný mezikód, který se stará o korektní ukon ení procedury. I p es mírn odlišné chování od zbylých dvou klí ových slov, jsem se rozhodl, že k nim pat í a že není pot eba pro exit vytvá et zvláštní t ídu. Každé z nich totiž provádí zm nu control-flow a opouští aktuáln zpracovávaný blok. P íkazy break a continue nejsou ovšem dostate n obecné a proto se v p ípad v tšího množství zano ených cykl neobejdeme bez p íkazu goto a s ním spojenými labely. Toto je jeden z mála d vod , kdy je pot eba goto opravdu použít a v podstat nejd ležit jší d vod pro tato konstrukce v mnohých jazycích stále p ežívá. Pro podporu goto vznikly t ídy CodeGeneratorGoto a CodeGeneratorLabel. Labely je pot eba v Pascalu deklarovat a posléze definovat. Na rozdíl od prom nných není label viditelný v jiné procedu e než v té, ve které byl definován, tedy ani ve vno ených ne. Proto nelze pomocí goto skákat mezi procedurami. Po deklaraci labelu se ve vrstv pro danou proceduru ud lá zástupce signalizující jeho existenci. Po té co jej ve zdrojovém souboru definuji, se vytvo í instance CodeGeneratorLabel, která zastupuje umíst ní daného labelu v mezikódu. Stará se o to, aby byl mezikód po daném labelu vygenerován do nového základního bloku a tak šlo na dané místo sko it. Tato t ída musí ov it, že label s daným jménem existuje, že nejde o druhou definici téhož labelu, a poté zástupci nastaví pozici, kde bude pro daný label mezikód vygenerován. P edávání informace o pozici labelu je pot eba d lat takto nep ímo, protože na rozdíl od cykl , není možné jednoduše v AST strom najít místo, kde je label definován. T ída CodeGeneratorGoto zastupuje p íkaz goto a jejím úkolem je ov it, zda je v procedu e volaný label definován. Pak ze zástupce pro daný label zjistí basic blok, kde bude vygenerován mezikód, a opraví control-flow programu. Pro p i azovací p íkaz máme t ídu CodeGeneratorAssign. Tato t ída musí nejprve ov it, zda cílový výraz nemá být návratová hodnota funkce a p ípadn výraz opravit. Poté ov uje zda daný výraz není volání funkce bez parametr a p ípadn dojde k jeho konverzi. U ostatních výraz a podmínek se tato konverze d je automaticky, ale pro cíl p i p i azování se používá kv li návratovým hodnotám nezkonvertovaná verze a proto je pot eba zde tyto testy provád t. Provádí se test, zda je možné do prom nné p i azovat, jestli je tzv. l-hodnotou. Výsledný mezikód ovšem negeneruje tato t ída, ale podobn jako u aritmetických operací typ odpovídající cílové prom nné, protože typy ví, jak se na nich dané operace mají správn provád t. O generování mezikódu pro for cyklus se stará CodeGeneratorFor. Implementace této t ídy je mírn komplikovan jší. Na rozdíl od všech p edešlých p ípad zde t ída sama vytvá í mezikód pro zv tšování prom nné po iteraci, test zda pokra ovat v opakování a pro nastavení po áte ní hodnoty ídící prom nné cyklu. Pro tyto t i p ípady si vytvá ím speciální pomocné code generator strome ky (ty jsou uloženy v cgaIteration, rangeTest a cgaInitial). Sice by šlo mezikód generovat p ímo, pak bych ale duplikoval kód zodpov dný za generování instrukcí. První verze by se nacházela v t íd reprezentující ordinální typ a druhá zde, což by znesnad ovalo p ípadné zm ny generovaného mezikódu. Další jazykovou konstrukcí je case p íkaz. Nejv tší problém v jeho p ípad p edstavuje prom nný po et v tví. Ty se p edávají konstruktoru CodeGeneratorCase jako spojový seznam struktury structCaseEntry. Ta reprezentuje jednu v tev a ve svých položkách má poznamenán typ (else v tev nebo oby ejná), p íkazy, pozici dané v tve a rozsah ídící prom nné, p i které se mají p íkazy vykonat. Rozsah je uložen op t spojovým seznamem, ve kterém se pamatuje, zda jde o konstantu i interval, po áte ní a koncové hodnoty. V konstruktoru se musí ov it korektnost vstupu nap íklad jestli v seznamu není více else v tví, i korektnost rozsah . Tedy zda jde o konstanty ordinálního typu, který je 19

kompatibilní s ídící prom nnou. Tento test pro jednu hodnotu d lá metoda checkRangeVal. V metod genRangeCheckCode se vytvá í mezikód s podmínkou na test rozsahu pro jednu v tev, podobn jako u for cyklu se i zde vytvá í pomocný strome ek s podmínkou. Aby nevznikalo zbyte n mnoho basic blok a tím se snížila režie za skoky, tak vygenerovaný mezikód pro podmínku nastavuje pomocí porovnání instrukcí and a or jednu pomocnou prom nnou, podle které se nakonec rozhodne, zda p íslušnou v tev vykonat nebo zkoušet další. Protože jsou hranice jednotlivých interval konstanty, není t eba je vyhodnocovat, což by v p ípadech s již p edem jasným výsledkem mohlo zdržovat. Proto by m lo být toto ešení oproti ešení s postupným vyhodnocováním se skoky výhodn jší. Sou asná implementace neumí testovat, zda jsou intervaly v rámci podmínek disjunktní. Vygenerovaný mezikód sekven n testuje podmínky jednotlivých v tví a první, u které test usp je, se provede. K testování podmínek dalších v tví už nedochází a pokra uje se až za case p íkazem. Poslední t ídou je CodeGeneratorCallC, která nemá p ímý ekvivalent ve zdrojovém kódu. Jeho úkolem je generovat mezikód zodpov dný za volání externích procedur implementovaných p ímo v interpretu. Takto se vyvolává v tšina knihovních funkcí. V sou asné implementaci by bylo rozumné vylepšit systém p etypování. Aktuální verze podporuje pouze n kolik nejnutn jších možností a není rozumn rozši itelná. Optimální by bylo ur it pravidla pro výb r typu, který bude konverzi provád t, a rozší it t ídy reprezentující typy o metody pro konverze. Bylo by vhodné p idat i testy disjunktnosti rozsah u case p íkazu a generovat Diagram 3: CodeGenerator t ídy p íslušné varování.

3.5 Typový systém T ídy TypeClass reprezentují vestav né i uživatelem definované typy. V p ípad vytvo ení nového typu dojde k vytvo ení instance odpovídající specializované t ídy, která ho zastupuje. Pouze v p ípad p ejmenování již existujícího typu nedojde k vytvo ení nového objektu, ale pouze k novému zapsání již existujícího reprezentanta do TypeManageru pod jiným jménem. Z jejich rozhraní jsou nejd ležit jší metody, které ov ují typovou identitu 20

(isIdentical) a typovou kompatibilitu (isCompatible). Podstatné jsou i metody pro generování mezikódu pro operace nad operandy daného typu. Zde se jedná o metodu genOperationCode, která vytvá í mezikód pro danou operaci, typicky jednu instrukci. A metodu genOperationStorage, ta vytvá í prom nnou, do které lze výsledek operace uložit. V p ípad , že jde o konstantní výraz, tak rovnou po ítá výsledek a vrací konstantní prom nnou. Ob tyto metody jsou používané v ExpressionOperation. Poslední d ležitou metodou je metoda getVariableGeneric pro vytvo ení prom nné daného typu. Takto vznikají prom nné deklarované ve var sekcích. Kv li tomu, aby tuto innost bylo možné provád t takto unifikovan , mají konstruktory t íd zastupující prom nné velmi podobné konstruktory a nastavování vlastností prom nných se provádí p es flagy. U potomk potomk má tato metoda i negenerickou verzi, která se od této liší pouze specializovaným typem vrácené t ídy. Jako i u jiných typ rozhraní TypeClassPrefab t ída implementuje spole né ásti. Její nejd ležit jší inností je zpracování adresního operátoru („@“). P vodní genOperation metody, pak p evádí na genNonGeneric metody. Pouze u procedur je jejich chování nevhodné, kv li odd lení datových a procedurálních adres. TypeClassNoDefined slouží pro reprezentaci deklarovaných objekt neznámeho typu. Po doko ení deklarací bloku, by všechny již m ly být nahrazeny za správnou typovou t ídu. Blíže se o významu existence této t ídy zmi uji v úvodu sekce 3.7 v pojednání o registraci objekt a identifikátorech. Ordinální typy mají spole ného p edka TypeClassOrdinals. Aby se nemusely ve všech potomcích ešit porovnávací operace, které všechny ordinální typy umí, jsou zde p edp ipravené genCompareCode metody. Též obsahuje pomocnou metodu pro ur ení typu registru, který se má pro prom nnou daného rozsahu vyhradit. T ída dále rozhraní rozši uje o další metody pro ur ení rozsahu, které jsou pot eba pro konstantní výrazy. Potomkem této t ídy je TypeClassInterval, který reprezentuje jak uživatelem reprezentované intervaly tak vestav né celo íselné typy, TypeClassEnum, který reprezentuje vý tový typ, TypeClassChar a TypeClassBoolean. Reálné typy reprezentuje TypeClassFloats. Pro reprezentaci ukazatel slouží t ída TypeClassPointer. Pro konstantu nil se musel vytvo it zvláštní potomek TypeClassNil. Nil je totiž speciální tím, že jde o obecný ukazatel dosaditelný do libovolného jiného ukazatele. Oby ejní ukazatelé musí mít identický bázový typ, aby mezi nimi bylo možné p í azovat. Pro procedury vznikl typ TypeClassProcedure. Ke klasickému rozhraní p idává ješt metody pro práci s parametry. Ty používají t ídy reprezentující procedurální prom nné.

3.6 Prom nné Potomci VarClass t ídy reprezentují prom nné ze vstupního jazyka, ale i pomocné prom nné použité pro mezivýpo ty. VarClass p edstavuje rozhraní. To si v rychlosti popíšeme. Prom nné mohou být t í druh : inicializované, neinicializované a konstanty. Pro nastavení hodnoty slouží metody setValue. V obecném rozhraní je jedna nespecializovaná, jednotliví potomci poté mají i svou specializovanou metodu na konkrétní typ hodnoty. Druh se obvykle ur uje p i vytvá ení pomocí flag p edaných konstruktoru. Nejd ležit jší metodou je getOperand. P i použití prom nné ve výrazu, se tímto získává reprezentace prom nné. Vrácený operand s hodnotou prom nné, se pak dává jako vstup instrukcím. Vytvo ení operandu m že být v ur itých p ípadech komplikované a m že si vyžádat ur itou práci, proto vznikly metody TopLevelizePTR a removeIndirection. U každé prom nné se pamatuje, do které vrstvy pat í. To je nezbytné pro správné generování p ístupu k prom nné. Slouží k ur ení, jestli se nachází v registrech, anebo se musí ud lat nep ímý p ístup do pam ti. Dále zde máme n kolik p íznak , které blíže popisují prom nnou (isLValue, isIndirect). 21

Indirect prom nné jsou nap íklad parametry s p íznakem var, p ípadn dereferencované pointery. Znamená to, že nemám p ímo hodnotu prom nné, ale adresu na ni. Na rozdíl od ukazatel zde ovšem odpovídá typ (TypeClass i VarClass) této prom nné odkazované hodnot . U pointer je Type i VarClass typu ukazatel. Metody genInitCode a genExitCode vytvá í kód, který zatím slouží pro nastavení hodnoty u inicializovaných prom nných. VarClass též dokáže vrátit typ prom nné (index TypeClass). Pro usnadn ní implementace rozhraní vznikla t ída VariableClassPrefab, která obsahuje rutiny spole né pro všechny potomky a dále rozhraní mírn rozši uje. A to hlavn ve sm ru zpracování konstant. Zbylou v tšinu rozhraní z VariableClass implementuje, a proto pro klasické prom nné mohou být zástupné t ídy docela jednoduché. Tím se myslí t ídy VariableClassFloats, VariableClassOrdinals a VariableClassPointer. Speciální kategorií jsou procedurální prom nné. Primárn jméno procedury reprezentuje svou adresu, stejn jako u procedurální prom nné. Proto bylo logické reprezentovat proceduru pomocí specializované t ídy VariableClassProcedure. Protože se ale od procedury o ekává více schopností, muselo se pro ni rozhraní rozší it. Toto rozší ení p edstavuje t ída VariableClassProcedures. Ta p idává hlavn metody ohledn parametr funkce a jejího vyvolání. Nejprve se metodou genCodeInitCall oznámí, že chci volat proceduru. Tato funkce inicializuje strukturu procedureCallContext, která je pro uživatele black boxem a obsahuje nezbytné informace pro generování volání procedury. Toto vy len ní mimo objekt reprezentující proceduru, je nutné kv li násobnému vyvolávání procedury. B hem generování kódu pro výpo et parametru m že dojít k op tovnému vyvolání stejné funkce a p i uložení informací pro volání funkce v objektu, by docházelo ke konflikt m. Po inicializaci se pomocí genCallSetParam nastavují hodnoty jednotlivých parametr , poté následuje vygenerování vlastního zavolání funkce metodou genCallCode. Po zkopírování návratové hodnoty se volání dokon í vykonáním genCodeExitCall. Jako zástupce procedurální prom nné slouží t ída VariableClassProcVar. P i návrhu interpretu jsem se díky velké vzájemné podobnosti procedur bez parametr s jednotkami a hlavním programem rozhodl i tyto reprezentovat specializovanými t ídami procedurálních prom nných. Tyto se zaregistrují pod specializovanými identifikátory a proto nejsou ze vstupního jazyka dosažitelné. Celkov jsou vytvo ené 3 specializace: VariableClassProcedure, VarableClassUnit, VariableClassPreMain. Ty jsou potomci t ídy VariableClassProceduresPrefab (VCPP), která dále rozši uje rozhraní o jejich spole né vlastnosti. VariableClassProcedure reprezentuje procedury a funkce, VarableClassUnit zastupuje jak jednotky tak spoušt ný program, který v podstat odpovídá jednotce bez interface ásti. VariableClassPreMain zajiš uje inicializace b hového prost edí a spušt ní hlavního bloku programu. VCPP dále rozši uje rozhraní procedury o spole né prvky, které pot ebují všichni potomci. P idává hlavn metody, které jsou pot eba p i zpracovávání (parsování) procedury. Reprezentant procedury se vytvá í p i prvním setkání s danou procedurou, pokud jde o definici, tak se po zpracování hlavi ky zavolá metoda define, která ov í, že parametry odpovídají parametr m v deklaraci p i vytvo ení objektu a p ipraví jak objekt tak parser pro zpracování této procedury. Pro ov ení parametr v p ípad deklarace se dá použít metoda isParameterListCompatible. Po áte ní informace o parametrech si t ída bere z TypeClass dané procedury. Po define dochází ke zpracování deklarací prom nných, typ , label a vno ených procedur. Toto se d je typicky bez p i in ní tohoto objektu. K další innosti v objektu dojde až po zpracování t la procedury, kdy se pomocí volání setBody nastaví p íkazy, které má procedura vykonávat. Poté je nutné provést r zné kontroly zavoláním metody postParsingChecks. Jedná se hlavn o test, zda všechny deklarované objekty v dané procedu e byly i definované. Poté již lze pomocí genCode vygenerovat mezikód dané procedury. Krom toho dojde k vytvo ení InterpreterProcedury, které daný vygenerovaný mezikód pat í a p enastavení stavu 22

parseru, tak aby odpovídal situaci p ed za átkem zpracování této procedury. Ke generování kódu se ješt váží metody genInitCode a genExitCode, které generují kód, který se má provést okamžit po zavolání procedury a t sn p ed ukon ením procedury. Provádí nastavování ukazatel ve vrstv p edstavující Display. Dál se ješt používají metody genVariablesInitCode a genVariableExitCode. Ty pro inicializované prom nné z dané vrstvy vytvá í kód pro nastavení jejich po áte ní hodnoty. Po inicializaci prom nných se generuje kód t la procedury. Jednotlivé specializované procedury se liší již jen v detailech. Konvence p i vytvá ení VariableClass je taková, že každá t ída se musí zaregistrovat ve VariableManageru. Díky tomu se již není nutné starat o její odblokování, protože bude zrušena spolu s vrstvou, do které byla p idaná.

3.7 Vrstvy Jednotlivé TypeClass, VarClass a další objekty se musí registrovat a pak se místo konkrétních objekt p edávají jejich identifikátory, pod kterými je lze op t dohledat. Tento nep ímý p ístup k objekt m byl zvolen proto, aby šlo objekty p edefinovávat. Mimoto ovšem p ináší další výhody. Seznam všech objekt daného typu je p ístupný na jednom míst a máme o nich díky tomu lepší p ehled, lze je centráln odalokovávat. Nevýhody daného p ístupu jsou v pomalejším b hu interpretu a složit jším lad ní. Schopnost p edefinovávat je pot eba u typ . Protože je možné deklarovat ukazatel na ješt neexistující typ, není možné v tento okamžik pro onen neznámý typ vytvo it pot ebnou TypeClass. Práv toto umož ují identifikátory ešit pomocí p edefinování objektu pod identifikátorem. Jiný p ístup, jako nap íklad obecný typový objekt, který se pozd ji zm ní, p ípadn se zm ní jen jeho chování, sebou p ináší technické i jiné problémy. Nap . p i rozši ování rozhraní u specializovaných typových objekt . Vrstvy byly vytvo eny, aby mohly simulovat viditelnost objekt . P idáním vrstvy se p ipojí další identifikátory prom nných, typ , label , procedur a funkcí. Po dokon ení zpracování bloku procedury se op t odebere a její identifikátory se stanou neviditelné. P evodní metoda by mohla být nap íklad sou ástí reprezentanta procedury. Pak by sta ilo udržovat pouze zásobník zano ených procedur, ale to by zp sobovalo problémy p i použití s jednotkami, nehled na to, že toto odd lení od sebe zp ehled uje strukturu interpretu. Základ tvo í t ída Layer, ta je sjednocením r zných specializovaných vrstev. Existuje jeden specializovaný potomek BottomLayer. Ten drží specializované spodní vrstvy, které obsahují r zné vestav né konstanty a typy. Instance této vrstvy je p ístupná pod globální prom nnou BL. T ída LayerStack reprezentuje seznam vrstev. Tento seznam pak slouží jako zdroj vrstev p i vyhledávání jednotlivých identifikátor . LayerStack by m l reprezentovat seznam viditelných vrstev. LayerStack byl vy len n z LayerManageru, kv li podpo e jednotek. Každá jednotka pot ebuje mít sv j LayerStack, který by se dal p idat na zásobník vrstev, p i p ipojení jednotky. Též p i zpracování jednotek se velmi hodí rychlé p epínání mezi r znými LayerStacky. T ída LayerManager p edstavuje rozhraní, které ostatní manager t ídy používají pro procházení vrstvami p i vyhledávání identifikátor a index . Dále má metodu pro nastavení LayerStacku, s jehož vrstvami se pracuje a metody pro práci s vrstvami. LayerStack se nikdy neupravuje p ímo, ale vždy p es metody LayerManagera. Layer hlavn sjednocuje ostatní typy specializovaných vrstev: TypeLayer, VarLayer, LabelLayer a RegistryLayer. V podstat vrstva p edstavuje místo, kam se p i deklaracích a definicích objekt ukládají vytvo ení reprezentanti. Mimoto ješt zná vlastníka (proceduru), kterému tato vrstva pat í. Ten je pot eba nap . p i vytvá ení basic blok , aby bylo možné ur it, které procedu e výsledný basic block pat í. Mimo to ješt obsahuje nastavení, které objekty ze specializovaných vrstev jsou vid t. Jednotka je p edstavována 1 vrstvou. Ta 23

pak v sob obsahuje identifikátory z interface ásti, které jsou viditelné jak p i zpracování jednotky, tak p i jejím p ipojení (LVS_PUBLIC) i z implementation ásti, které lze používat pouze b hem zpracování jednotky (LVS_PRIVATE). Každý p idaný objekt si p i p idání uloží i sv j stav viditelnosti a p i jeho zp tném získání z identifikátoru se testuje, jestli je vid t a tedy jestli jej m že vrátit. Specialiované Layer t ídy TypeLayer, VarLayer, LabelLayer jsou specializací obecné šablony GenericLayer. Navíc p idávají pouze schopnost p idání objektu do vrstvy. Tento kousek kódu v šablon není zám rn . P idání objektu totiž p edpokládá otestování, zda n kde v jiné specializaci se toto jméno již nepoužívá. O t chto svých specializacích šablona neví. Zvláštním typem vrstvy je RegisterLayer. Ta se nestará o p evody jmen na identifikátory, ale o p id lování registr pro procedury. Po naalokování všech registr dokáže vytvo it MemLayer, která je dostate n velká, aby je dokázala pojmout. Mimo to si ješt pamatuje, pozici v Display. Ta se používá pro nep ímé adresování t chto prom nných. T ída Display, slouží pro uložení ukazatel na vrstvy jednotek a práv zpracovávaných procedur. Slouží jako náhrada aktiva ního záznamu na zásobníku, speciáln jako náhrada za odkaz na aktiva ní záznam nad azené funkce. T ída Display tvo í reprezentaci tohoto zásobníku v interpretu, umí vyhradit místo pro uložení ukazatel , vygenerovat pot ebný kód pro jejich nastavení, vytvo it požadovanou pam ovou vrstvu pro uložení ukazatel a podobn . K v tšin typ vrstev existují manager t ídy, které se starají o práci s obsahem vrstev. Slouží pro p evod jména na identifikátor, p evod identifikátoru na objekt, p idání nového mapování a podobn . Vzhledem k v tší rozdílnosti mezi managery již nedošlo k vytvo ení spole ného p edch dce. U label se nap íklad hledá pouze v horní vrstv , protože jména label se ned dí, u typ je zase v p ípad dop edné definice u pointer pot eba mít možnost p edefinování a podobn . Aby byla zaru ena jedine nost identifikátor , mají t ídy privátní kontruktory a instance se získává statickou metodou. Pro snazší p ístup k nim, jsou vytvo ené globální prom nné TM pro TypeManager, VM pro VariableManager a LblM pro LabelManager. Tyto t ídy též umí generovat jména pro pomocné objekty. Vyhledání jména probíhá tak, že postupn procházím vrstvy od vrcholu zásobníku až na dno a zkouším, jestli se v dané vrstv nenachází objekt s daným jménem. P idává se vždy do horní vrstvy.

3.8 Virtuální stroj Výsledná VM byla tvo ena s ohledem na interpretování mezikódu a jeho vlastnosti. Pro p ípadné další zpracování backendem je výhodn jší neužívat linearizovanou formu, ale používat d lení na basic bloky. V tšina backend by si stejn tuto strukturu jako jeden z prvních krok vytvo ila. A dále díky tomu není pot eba po ítat délku skok , rozhodovat, který blok kam umístit. Druhým faktorem, který ovlivnil výslednou VM je množství prom nných. P vodním zám rem bylo vytvo it registrový stroj, ale v backendu se typicky zjiš uje podrobn doba platnosti prom nné (live-range analysis), pro kterou je výhodn jší, pokud i každá pomocná prom nná má své vlastní místo v pam ti. Proto generovaný kód obsahuje velké množství pouze jednou použitých registr . V p ípad použití registrového stroje s optimistickým kódem a zásobníkem by se muselo p i volání procedury množství údaj p esouvat z registr na zásobník a zp t, p ípadn provád t n jakou zjednodušenou analýzu rozsahu a mít instrukce pro práci se zásobníkem. Proto jsem zvolil ešení, kdy se ukládá na zásobník aktuální vrstva registr a pro novou funkci se použije vrstva nová, která se p i návratu odstraní. Jak jsem pozd ji zjistil, stejná myšlenka je použitá u VM Parrot. V podstat to odpovídá p edstav zásobníku, ve kterém instrukce mohou pracovat nejen s vrcholkem zásobníku ale i s ur itou omezenou vrchní ástí. 24

Dalším cílem bylo co nejp esn ji p edávat velikost prom nné z frontendu do backendu, aby se p ípadn daly alokovat subregistry. Z toho d vodu vznikly r zné integerové znaménkové i neznaménkové registry. Protože musí virtuální stroj um t pracovat s alokovanou pam tí, kde se nepo ítá s ukládáním typ uložených dat, jsou pot eba instrukce, které implicitn p edpokládají ur itý typ registr jako parametry. (oproti CLI, kde jsou instrukce netypované) Proto máme addi, fadd a adda. Aby se pro každý integerový typ nemusela vytvá et zvláštní instrukce, což by bylo velmi zdlouhavé a pro generování kódu ne moc p íjemné, vytvo ila se pouze jedna integerová verze a o zarovnání typ se starají operandy t chto instrukcí. Ve výsledku tedy máme registrový kód se zásobníkem pam ových vrstev, které mohou p edstavovat registry i na heapu na alokovaná data, a typované instrukce. Zdrojové a hlavi kové soubory, týkající se VM mají prefix Interpreter. Struktura by se dala rozd lit do dvou vrstev. Na spodní, kterou p edstavuje správce basic blok (BasicBlockMan), na basic bloky obsahující instrukce a na samotné instrukce s jejich operandy. Horní vrstva obsahuje Interpreter, který vše zast ešuje, správce pam ti (MemManager), reprezentanty procedur, a správce knihovních funkcí. D vodem pro toto rozd lení byla i snaha vytvo it prost edí, které by umož ovalo sdílet kód ( ásti spodní vrstvy) mezi r znými interprety, p ípadn vícenásobné spušt ní téhož programu. Žádná z t chto vlastností v sou asné dob není implementovaná a p edstavovala by v tší množství práce. Horní vrstva Základ horní vrstvy tvo í t ída Interpreter. Ta je reprezentací p eloženého programu se všemi jednotkami. Obsahuje seznam procedur, drží správce pam ti (MemManager), obsahuje správce s knihovními funkcemi (CallCMan), dále se stará o práci se zásobníkem volaných funkcí (konstanty IP_*, typ call_stack_entry). Obsahuje metodu pro nastavení návratové hodnoty interpreteru (halt). Tato metoda ihned neukon í vykonávání programu, k tomu dojde p i první zm n basic bloku, proto by instrukce halt, která tuto metodu volá, m la být vždy poslední instrukcí v bloku. Pro p idání nové procedury slouží metoda addProcedure, kterou používá frontend p i vytvo ení nové procedury. Každá procedura obdrží jedine ný identifikátor. Jejím opakem je getInterpreterProcedure, která se používá p i vyvolávání procedur. Metoda execute slouží ke spušt ní celého programu. Ješt p edtím, než m že být program spušt n, se musí pomocí setMainProcedure nastavit, která z registrovaných procedur se má spoušt t. O toto nastavení se stará frontend. Nejpodstatn jší práci v této t íd provádí metoda execute. Na po átku provede inicializaci a spustí nastavenou hlavní proceduru (vyvolá její execute metodu). Podle návratové hodnoty práv spušt né procedury pozná, jestli jde o vyvolání nové procedury, pak uloží stav sou asné na zásobník a spustí volanou funkci, a nebo, jestli jde o její ukon ení (IP_RETURN), pak obnoví vykonávání p erušené funkce od uloženého stavu. Dále se ješt testuje, jestli nebyla zavolána metoda halt a pokud ano, vykonávání ukon í. T ída InterpreterProcedure reprezentuje proceduru nebo funkci - cíl call instrukce. Její identifikátor, získaný p i p idání do interpretu, slouží jako parametr v call instrukci. Každý reprezentant obsahuje obraz pam ti pro proceduru, správce basic blok , který se stará o bloky pat ící dané procedu e, metody execute a metody pro získání p id leného identifikátoru. P edtím než m že být daná procedura vykonána musí mít nastavený obraz pam ti a po áte ní basic blok. Metody sloužící k tomuto nastavení volá frontend p i vytvá ení procedury. P ed spušt ním celého programu se pomocí preExecuteCheck ov uje, zda k tomuto nastavení došlo. K vytvo ení pam ové vrstvy p i volání procedury musí dojít p ed samotnou instrukcí call, aby bylo možné nastavovat parametry. K tomu slouží instrukce mem_create, která používá metodu getProcedureRegisters této t ídy, aby vytvo ila kopii 25

uloženého obrazu pam ti. S metodou execute je spojena metoda initializeExecutionState, která se stará o nastavení stavu, který vrací execute metody tak, aby neodpovídal p erušenému vykonání procedury, ale novému volání této procedury. Metoda execute pouze p edává vykonávání do spodní vrstvy správci basic blok . Správce pam ti tvo í t ída MemManager. Než za nu vysv tlovat její funkci, je rozumné si ícti pár slov o adresách. Adresování se inspirovalo segmentací, takže se každá adresa skládá ze 2 ástí, ísla segmentu a offsetu v n m. Každý segment je reprezentován potomkem t ídy MemPlace, n kdy se o segmentech zmi uji jako o vrstvách. MemManager má za úkol p id lovat a p evád t ísla segment na konkrétní instance MemPlace. Tedy MemManager zajímá pouze segmentová ást adresy, a vrstvu pak pouze offset. Registry VM, jsou vždy namapovány z pam ti, a jsou p ístupné i pod speciálním íslem segmentu (MemoryPlaceStackID). Tímto si zjednodušuji situaci p i generování mezikódu a u ukazatel . MemManager se používá za b hu interpretu a plní 2 hlavní úkoly, dynamické p id lování ísel segment vrstvám (RegisterMemPlace), p evod zp t (getMemPlace) a jejich „uvol ování“ (zrušení mapováni) metodou RemoveMemPlace je prvním úkolem. Druhým je pak spravování zásobníku vrstev. Protože jsou registry uložené v pam ové vrstv , musí se p i zavolání procedury vytvo it nová vrstva pro tuto volanou proceduru a tu v instrukci call dát na vrcholek zásobníku vrstev. P i instrukci ret ji pak zase odstranit a zp ístupnit vrstvu p vodní. Bohužel te máme dva synchronizované zásobníky, jeden s uloženým p erušeným stavem v interpretu a druhý zde s vrstvami. Situace vznikla proto, že p vodn se v interpretu stav neukládal a používala se rekurze (což teoreticky mohlo zp sobit vy erpání zásobníku interpretu a jeho pád). Protože bylo pot eba mít zásobník s vrstvami pro jejich p epínání p i call a ret, musel vzniknout zde. Pozd ji p i vylepšování interpretu se rekurze odstranila a vytvo il se zmi ovaný druhý zásobník. Pro práci se zásobníkem slouží metody setStackTop a removeStackTop. Implementace pam ového subsystému se nachází v souborech InterpreterMemory. Pro implementaci knihovních funkcí, hlavn v oblasti vstupu a výstupu, byl vytvo en systém pro vyvolání funkcí v interpretu p ímo z Pascalu. Pro vyvolání slouží instrukce call_c, jejímž jediným operandem je íslo – identifikátor volané funkce. Tato instrukce zavolá CallCMan, který požadavek dále zpracuje. Implementace knihovních funkcí za íná v souboru InterpreterCallC.xml, kde po úvodním popisu typ parametr za íná popis jednotlivých knihovních funkcí. Pro vytvo ení knihovní funkce je pot eba pro ni do tohoto souboru p idat záznam. Ten obsahuje jméno funkce v Pascalu, popis parametr , nastavení, co se bude generovat automaticky, a jméno funkce, která se má v interpretu vyvolat. Po vytvo ení této „cé kové” funkce, která provádí požadovanou akci, je vytvo ení knihovní funkce hotové. Pomocí xslt transformací se z daného popisu vytvo í CallC t ída, odpovídající dané knihovní funkci. Tyto t ídy jsou v souboru InterpreterCallCGen.cpp. T ída CallC p edstavuje obecné rozhraní, které musí každá knihovní funkce spl ovat. Obsahuje metodu execute, která se stará o vykonání dané knihovní funkce, a registerFunction, která má na starosti vytvo ení své reprezentace ve vstupním jazyce, nebo-li zp ístupn ní dané funkce pro programátora v Pascalu. Vygenerované funkce používají t ídu CallCPrefab, která rozhraní rozši uje o funkce více popisující konkrétní funkci, jméno, parametry a pomocí t chto údaj vytvá í registra ní funkci. Ta v podstat zaregistruje jméno funkce, jména parametr do tabulek symbol , vytvo í seznam parametr a vytvo í reprezentanta procedury (její TypeClass, VariableClass), u prom nné nastaví t lo na instrukci call_c a pro tuto funkci vygeneruje mezikód. Dále ješt ov í, jestli si odpovídají alespo typy parametr na úrovni intermediate typ (typ v mezikódu). Celou tuto mašinérii zast ešuje t ída CallCMan. Ta ve svém automaticky generovaném konstruktoru vytvá í CallC t ídy vygenerovaných knihovních funkcí, které se 26

samy v manageru zaregistrují. Pro tyto ú ely slouží metody add a remove. Dále CallCMan obsahuje metodu pro registrování p idaných funkcí a execute metodu, která spustí execute metodu volané funkce. Dolní vrstva Adresu v pam ti reprezentuje t ída MemAddr. Tato t ída definuje typy a n které konstanty ohledn adres. Obsahuje metody pro na tení z reprezentace adresy za b hu a nazpátek pro její uložení (RT_load_from, RT_save_to). Druhou ástí pam ového subsystému jsou implementace rozhraní MemPlace. Toto rozhraní slouží operand m pro p ístup do pam ti. Hlavní metodou je getData, která vrátí adresu, na které jsou daná data uložená. Metoda clone slouží k vytvo ení kopie, v etn uložených dat, používá se p i volání procedur v instrukci mem_create. Rozhraní MemPlace implementují 2 t ídy - MemHeap a MemStack. MemHeap v pam ti naalokuje souvislý jednolitý blok dané velikosti. V sou asné dob se používá jak pro dynamicky alokovanou pam , tak pro registry funkcí a procedur. P i p ístupu se pouze testuje rozsah, jestli se nep istupuje mimo platnou oblast. MemStack byl p vodn navržen pro uložení registr procedur a funkcí. Myšlenka byla taková, že jednotlivé druhy typ v interpretu budou uloženy odd len . To m lo zajistit lepší typovou bezpe nost u pointer a snazší ladící výstupy obsahu vrstvy, protože typ položky by byl známý. Nakonec se tento p ístup p estal používat, protože tato struktura je velmi nevhodná pro reprezentaci polí a strukturovaného typu. V sou asné dob se používá pouze na Display. Jeho specialitou bylo, že indexy mohly nabývat i záporných hodnot, takže parametry funkcí by m ly mít záporné indexy a lokální prom nné by za ínaly od nuly. T ída BasicBlock p edstavuje posloupnost instrukcí, která se vždy provede celá. Po vytvo ení se do ní pomocí metody appendInstruction p idávají na konec další instrukce. Pro ur ení, kterým blokem se bude po provedení tohoto pokra ovat slouží metody setSucessor. První verze odpovídá instrukci jump, druhá podmín nému skoku, kdy se podle prom nné ur í, jestli se ská e na blok z druhého i t etího parametru. Proto nemáme instrukce skoku. Závislost jednotlivých blok na sob je tedy statická a nelze provád t nap . instrukce skoku, kde by cíl byl nekonstantním výrazem. Execute metody zp sobí vykonání všech instrukcí v basic bloku. T ída BasicBlockMan spravuje jednotlivé basic bloky. Pomocí metody RegisterBB jim p id luje jedine né identifikátory, které slouží pro jejich nalezení, nebo pro nastavování bloku s pokra ováním. Dále v sob obsahuje typ pro uložení stavu a jeho inicializaci, který je pot eba pro obnovení innosti po call. Ze všeho nejpodstatn jší jsou execute metody, které naleznou požadovaný basic blok, ten vykonají, a pokra ují dalším (jeho následníkem). Každá instrukce je reprezentovaná vlastní t ídou. Ta je potomkem t ídy Instruction a nalézá se v namespace Instructions. Protože výkon nebyl hlavním cílem, nedochází ke generování bytecodu nebo dokonce ke generování nativního kódu (JIT). Každá instrukce má metodu execute, která provádí danou innost. Kód v tšiny instrukcí je automaticky generovaný pomocí xstl transformací. Pro n které složit jší instrukce jsou t la psána ru n . Pro pojmenování instrukcí existují tato pravidla : p edpona f – instrukce v plovoucí ádové árce koncovka i – celo íselná instrukce koncovka a – instrukce pro práci s adresami koncovka s – znaménková verze instrukce Instruk ní sada obsahuje aritmetické a porovnávací instrukce, p esuny, p evody. Pro podmín ný a nepodmín ný skok instrukce neexistují, realizují je basic bloky. Z mén obvyklých instrukcí zmi me instrukci call_c pro vyvolání externích knihovních funkcí, 27

mem_create a mem_remove pro práci s vrstvami pam ti, memcpy pro kopírování blok pam ti, mem_top_layer pro získání ísla segmentu vrstvy, která je práv na vrcholu zásobníku, getAddr pro získání adresy dané prom nné v pam ti a rangeChecki pro ov ení, zda je hodnota prom nné v ur itém rozsahu, pokud ne vyvolá b hovou chybu. Instrukce provádí operace s daty a operandy p edstavují rozhraní, jak data instrukcím dodávat. Ke každému typu v mezi jazyku existují odpovídající typy operand . VM obsahuje 3 druhy operand . Operandy pro p ímý p ístup, který v klasickém assembleru odpovídá tení hodnoty registru (dec eax). Operandy s konstantní hodnotou, ekvivalent p ímé hodnoty v zápisu instrukce. A operandy pro nep ímý p ístup, kdy parametrem je místo s adresou (dec [eax]). Implementace se nachází v souborech InterpreterOperands. Pro generování jednotlivých t íd operand je využit preprocesor (direktiva define). D vodem bylo porovnání využití xslt transformací a preprocesoru pro generování zdrojového kódu. Implementace VM není dokonalá a je zde spousta místa pro zlepšování. V rámci vyhodnocování výraz se provádí i výpo et konstantních podvýraz . P i této operaci je pot eba p esn emulovat chování instrukcí. Bylo by rozumn jší, aby se kód provád jící ur itou operaci nacházel p ímo v t íd dané instrukce a p i vyhodnocování výraz se odkazovalo na instrukce, p idat informace o pozici ve zdrojovém kódu odkud daná instrukce pochází pro lepší hlášení b hových chyb. V sou asné dob se typy operand instrukce testují až p i jejím vytvá ení p i spušt ní interpretu (jestli fadd nemá za operand adresu). P i zavedení vhodné hierarchie t íd u operand , by šlo tuto kontrolu d lat automaticky kompilátorem již p i p ekladu. Dále by se mohly generovat deklarace cé kových funkcí volaných knihovními procedurami a rozší it knihovní framework i na prom nné. Celkov interpret zrychlit.

3.9 Hlášení chyb Pro hlášení chyb a varování, které je nedílnou sou ástí každého p eklada e, se stará funkce report_error. Jejím hlavním parametrem je íslo chyby (enum err_numbers), podle kterého se ur uje, jaká chybová hláška se má vypsat. Poté následuje parametr s umíst ním chyby a p ípadné další dopl ující parametry závislé na ísle chyby. Jednotlivé chyby jsou popsané v poli errs umíst ném v souboru InterpError.cpp. Jednotlivé položky pole obsahují íslo chyby, popis dopl ujících parametr a textu, který se má v p ípad chyby vypsat. Díky tomu, že jsou texty chyb umíst né takto na jednom míst , je možné jednodušeji upravovat chybové hlášky, lépe udržovat konzistenci mezi jednotlivými chybami, p ípadn i lokalizovat interpret do jiného jazyka.. Položka popisující dopl ující informace ( enum err_type) má zavedenu tuto jmennou konvenci. Jméno za íná vždy na ERRT_ a až na výjimku ERRT_VOID, která znamená, že chyba nemá žádné další dopl ující parametry, platí, že první písmeno popisuje typ prvního parametru, druhé druhého a tak dále. Celkový po et parametr je ur en po tem písmen. V tabulce uvádím seznam použitých písmen a jejich význam. S String Textový et zec const char* C Character Znak Char I Integer Celé íslo Int T idenTifier Identifikátor z tabulek symbol SYMTAB_INDEX O Operator Operátor TOKGE_* Ne všechny kombinace ovšem existují, byly vytvo eny pouze ty, které jsou pot eba a další nové se musí jednoduchým zp sobem doplnit.

28

3.10 P eložení projektu, spušt ní, licence Pro p eklad na platform windows byl vytvo en projekt ve Visual Studio 2005. Pro jeho úsp šnou kompilaci je pot eba mít nezbytné nástroje. Jde o generátor lexikálních analyzátor flex, generátor syntaktických parser bison a nástroj pro provád ní xslt transformací xsltproc. Jejich umíst ní je bráno relativn k pozici projektu a pro jednoduchý p eklad projektu jsou na CD umíst né v požadovaných místech. Pro umožn ní kompilace se musí celé CD p ekopírovat na zapisovatelé médium, nejlépe na pevný disk. To je vynuceno pot ebou ukládat vygenerované soubory. Ty se vytvá í do adresá e se zdrojovými texty. Pro návrat projektu do p vodního stavu a smazání všech do asn vytvo ených a vygenerovaných soubor je možné použít soubor Clear.NET2005.bat. Ten uvede projekt do stavu v jakém se nachází na CD. Pro kompilaci na platform linux je v adresá i src\unix umíst n makefile. Tento makefile p edpokládá vykonání pomocí gmake. Pro p eklad projektu musí být v systému nainstalovaný flex, bison a xsltproc. Tyto utility musí být dostupné bez zadávání cest. Jako p eklada se používá gcc. I v p ípad p ekladu na linuxu je pot eba mít obsah celého CD. P i tvorb syntaktického parseru se odtud používají n které soubory jako vstup. Parametry pro makefile jsou standardní. Make all slouží k p eložení celého projektu, make clean pro vymazání všech objektových a vygenerovaných soubor . P eklad byl zkoušen pod cygwinem. Projekt nepot ebuje k b hu žádné speciální knihovny, krom pot ebují b žn p eložené programy (libc).

standardních jaké

Interpret p i svém spušt ní o ekává jako parametr jméno souboru k vykonání. Tento soubor hledá v aktuálním adresá i. Koncovku pas se pokouší automaticky doplnit. P ed jméno souboru je možné dát speciální nastavení pro interpret. Jedná se o parametr –d, kdy se zobrazují r zné pomocné výstupy, které pomáhají p i lad ní programu. Program je ší en pod GNU GLP2 licencí. P vodn byla tato nebo jiná svobodná licence zamýšlená. Te je ovšem nutná, protože bisonem vytvo ený c++ parser již tuto licenci má.

29

4 Vstupní jazyk Vstupem interpretu je jazyk pascalského typu, který je siln ovlivn n Turbo Pascalem (dále jen TP) od firmy Borland. Nejedná se o klon TP, neimplementuje veškeré jeho schopnosti, ale na druhé stran TP v ur itých v cech rozši uje. Tento interpret podporuje jednotky, procedury a procedurální prom nné, ukazatele a dynamické prom nné, labely, konstanty a inicializované prom nné, reálné a ordinální typy, uživatelsky definované intervalové a vý tové typy, základní knihovní funkce a strukturovaný typ. Z nepodporovaných v cí zmi me objekty, unie, pole, et zce, v tšinu direktiv a klasickou write/writeln proceduru, která je ovšem speciálním hackem do jazyka. Oproti TP m že funkce vracet libovolný typ, je odstran no omezení na délku identifikátoru a vylepšeno volání funkcí bez parametr .

4.1 Klí ová slova Mezi základní elementy jazyka pat í identifikátory, klí ová slova a íselné konstanty. Jako univerzální odd lova e t chto element slouží mezery, tabelátory, konce ádku a komentá e. Komentá za íná znakem „{“ a kon í znakem „}“. Komentá e se na rozdíl od TP mohou do sebe vno ovat, to znamená, že po et { a } si musí odpovídat. Komentá neukon í první zavírací složená závorka, ale až závorka párová k otvírací, která komentá za ala. Tento p ístup usnad uje komentování blok se zdrojovými texty.V ur itých kontextech mohou jako odd lova sloužit i další znaky. Nap íklad aritmetické operace, te ka, árka atd. Identifikátor za íná písmenem, na pozici dalších znak pak m žou být jak písmena tak i íslice. íselných konstant máme n kolik druh : celá ísla, celá ísla zapsaná hexadecimálním zápisem a reálná ísla. Celé íslo je p edstavováno posloupností íslic, hexadecimální íslo je uvozeno znakem „$“ následovaným íslicemi a písmeny „a“ až „f“. Reálné íslo m že být zapsáno jak v desetinném tak ve v deckém tvaru. Chybné identifikátory za ínající na íslici, jsou interpretovány jako špatn vytvo ená ísla.. Klí ová slova jsou and, array, begin, break, case, const, continue, div, do, downto, else, end, exit, for, forward, function, goto, halt, if, implementation, interface, label, mod, nil, not, of, or, packed, procedure, program, record, repeat, shl, shr, then, to, type, unit, until, uses, var, while a with. Klí ová slova p edstavují speciální identifikátory, které mají sv j vlastní význam a už je nelze použít pro jména prom nných, funkcí , typ a dalších objekt .

4.2 Vstup interpretu Vstupem programu je textový soubor. Vstupní soubory jsou dvou typ : programy a jednotky. Jméno souboru s programem je jedním z parametr spoušt ného interpret. Pokud jméno daného souboru neobsahuje koncovku, p ipojí se standardní p ípona „.pas“. Soubory se hledají v aktuálním adresá i. Vstupní soubor se zadává jako parametr interpretu.

4.3 Program Soubor s programem za íná klí ovým slovem (dále jen kl. sl.) program následované identifikátorem a st edníkem. Poté následuje defini ní úsek programu, kde mohou být v libovolném po adí bloky vytvá ející typy, labely, konstanty, inicializované i

Diagram 4: Program 30

neinicializované prom nné, p ipojující jednotky, a kde se definují a deklarují funkce a procedury. Po této ásti musí být základní blok programu p edstavovaný složeným p íkazem (begin-end blok), který je ukon ený znakem te ka. P íkazy ze základního bloku programu se provedou p i spušt ní programu ihned po inicializaci p ipojených jednotek.

4.4 Jednotky P ipojování jednotek lze provád t v defini ním úseku programu a jednotky. P ipojovací blok (Unit blok) za íná kl. sl. uses, po kterém následuje árkami odd lený seznam identifikátor jednotek ukon ený st edníkem. Jednotky se p ipojují v po adí, v jakém jsou uvedeny v seznamu, tedy prom nné z první jednotky mohou být p epsány prom nnými z dalších jednotek uvedených pozd ji v seznamu. Identifikátor jednotky p edstavuje jméno souboru, který obsahuje zdrojový kód této jednotky. Protože identifikátor nesmí jako svou sou ást obsahovat te ku, použije se pravidlo pro dopln ní standardní koncovky „.pas“. Z výše uvedeného vyplývá omezení pro jména soubor obsahující jednotky. Ty musí odpovídat požadavk m na jména identifikátor , aby je bylo možné p ipojit do programu. Soubor s jednotkou za íná kl. sl. unit identifikátorem a st edníkem. Poté následuje kl. sl. interface a defini ní úsek jednotky. V tomto úseku mohou být v libovolném po adí bloky, ve kterých se Diagram 5: Jednotka vytvá ejí typy, definují labely, p ipojují další jednotky, vytvá í prom nné a konstanty, deklarují procedury. Všechny zde uvedené objekty jsou ve ejné a viditelné v souborech, které tuto jednotku p ímo i nep ímo p ipojují. Jedinou vyjímkou jsou labely, které se ned dí a jsou vždy viditelné v ásti, kde jsou definovány. Interface ást je ukon ena kl. sl. implementation. Po n m následuje defini ní úsek programu (viz. sekce program) a pak inicializa ní blok, p edstavovaný bu složeným p íkazem (begin-end blok) zakon eným znakem te ka a nebo pouze kl. sl. end následované te kou. Typy, prom nné a další objekty definované v implementa ní ásti jsou privátní a tedy neviditelné mimo jednotku. V této ásti musí být definovány všechny procedury a funkce, které byly v interface ásti jednotky deklarované. Inicializa ní blok slouží k uvedení jednotky do funk ního stavu, nastavení prom nných a podobn . P ed vykonáním inicializa ního bloku je zaru eno, že prob hla inicializace u všech jednotek z p ipojených v interface ásti (i proto podmínka na neexistenci orientovaného cyklu). Toto ovšem neplatí pro jednotky p ipojené z privátní implementa ní ásti, kde toto z d vodu existence cykl zaru it nelze. P esto, pokud to je možné, se interpret snaží inicializovat i tyto jednotky. Po adí inicializace jednotek není, podobn jako v TP, definované a podobnost posloupnosti s TP nebyla v bec testována.

31

4.5 Náv ští Náv ští slouží k ozna ení míst ve zdrojovém kódu tak, aby se mohlo stát cílem skoku. Každé náv ští je pot eba deklarovat a definovat. Náv ští jsou vid t pouze v tom bloku (procedu e, hlavním bloku programu i jednotky), ve kterém jsou definované. Oproti typ m a prom nným nejsou vid t ani ve vno ených procedurách, takže skákat lze vždy pouze v rámci bloku. Náv ští v jednom bloku musí být jedine né. Náv ští se deklarují v Label bloku, který za íná kl. sl. label a po n m pokra uje árkou odd leným seznamem label , který je ukon ený st edníkem. Labelem m že být identifikátor a nebo celé kladné íslo integerového rozsahu. Definice náv ští se provádí p ed p íkazem, který má sloužit jako cíl skoku. A to uvedením labelu a dvojte ky p ed samotným p íkazem. Takto je možné dát i více náv ští p ed p íkaz.

4.6 Typy Pascal obsahuje velké množství vestav ných typ , které m že programátor dále rozši ovat vlastními. Typy lze rozd lit do n kolika kategorií: na ordinální, reálné, strukturované, ukazatele a procedurální typy. Definice typ (type block) za íná kl. sl. type po kterém následuje seznam definic jednotlivých typ . Každá definice je ukon ena st edníkem. Definice jednotlivého typu vždy za íná identifikátorem p edstavující jméno nového typu. Pak následuje rovnítko a po n m definice typu nebo identifikátor se jménem již existujícího typu. Pokud použijeme jméno již existujícího typu, jedná se o p ejmenování. V druhém p ípad se vytvá í nový typ a p esný tvar definice záleží na tom, o jaký konkrétní typy se jedná. Tvar definice bude probrán spolu s jeho vlastnostmi níže. Dva typy jsou identické pokud pochází ze stejné definice typu. Jména se mohou díky p ejmenovávání lišit. Typová identita je nutná u formálních parametr funkcí. Na rozdíl od identity jsou podmínky u typové kompatibility voln jší. Typová kompatibilita se vyžaduje ve výrazech a v p i azovacím p íkazu. U p i azování do íselných ordinálních typ se ješt provádí testovaní rozsahu. Dva typy jsou kompatibilní pokud jsou oba : • celo íselného ordinálního typy • reálného typu • ukazatelé s identickými bázovými typy • procedurálního typu se identickou návratovou hodnotou a stejným po tem parametr , které mají identické typy Ve výrazech a parametrech funkce, které nemají direktivu var se provádí implicitní konverze z reálného typu na p esn jší reálný typ, mezi r znými celo íselnými ordinálními typy a z celo íselných typ na reálné. Ordinální typy Pascal v sob obsahuje n kolik vestav ných ordinálních íselných typ . Jedná se konkrétn o tyto: 255 Byte 0 Word 0 65535 Integer -32768 32767 Longint -2147483648 2147483647 Na t chto íselných typech lze provád t v tšinu aritmetických operací. Z unárních jde o bitový not a operaci mínus, z binárních o rela ní operace = <>, <, >, <=, >=, bitový and, or

32

a xor, rotace vlevo (shl) a vpravo (shr), operaci celo íselného d lení (div) i zbytku po n m (mod) a standardní aritmetické operace +, -, * a /. Dále lze v programu definovat vlastní intervalové typy. Každý intervalový typ má bázový typ, podle kterého se ur uje, jaké operace na n m lze provád t. Definice typu interval se skládá ze dvou celo íselných konstant, které tvo í meze intervalu a tedy ur ují obor hodnot, které lze do prom nné uložit. Mezi t mito konstantami musí být znaky „..“. Podle typu a velikosti konstant se ur uje bázový typ. Vý tový typ, je dalším z programov definovatelných ordinálních typ . Hodí se pro reprezentaci dat, které mohou nabývat pevný, p edem známý, relativn malý po et r zných hodnot. Definice vý tového typu za íná znakem „(“, po kterém následuje árkou odd lený seznam identifikátor , který je ukon en znakem „)“. Na vý tovém typu lze provád t pouze rela ní operace =, <>, <, >, <= a >=. Platí, že hodnota identifikátoru A je menší než hodnota B, pokud je A v seznamu z definice typu d íve než B. Typ boolean slouží k reprezentaci logických hodnot. M že nabývat hodnot true (pravda) a false (nepravda). Vestav ná konstanta true je intern reprezentovaná hodnotou 1, false hodnotou 0. Na tomto typu jsou definovány operace logický nor, and, or, xor a dále rela ní operátory = <>, <, >, <= a>=. Dá se íci, že boolean je speciálním druhem vý tového typu, který je rozší ený o logické operace. Char je vestav ný typ sloužící pro reprezentaci znak . M že nabývat hodnot od 0 do 255. Pro vytvo ení znakové konstanty lze použít dva zápisy. Pro znaky z klávesnice lze použít tvaru znak konstanty mezi dv ma apostrofy (nap . ' A' ). Druhou možností je použít znak # a za ním íslo reprezentující hodnotu znaku. (nap . #32 pro mezeru). Na typu char lze provád t pouze rela ní operace =, <>, <, >, <=, >=. Reálné typy Pro reprezentaci a výpo ty s reálnými ísly existují vestav né typy real, single, double a extended. Protože z principu nelze reprezentovat všechna reálná ísla, reprezentuje se pouze více i mén hustý výb r diskrétních hodnot z intervalu, který daný typ pokrývá. Jednotlivé reálné typy jsou v úvodním seznamu se azeny podle p esnosti od nejmén p esného. Z mén p esného na p esn jší typ existuje automatická konverze. Na reálných typech lze provád t rela ní operace =, <>, <, >, <= , >= a aritmetické operace +, -, *, /. Rozsahy ísel, které dokáží jednotlivé typy pojmout, vyplývají z tabulky. Samoz ejm platí symetricky i pro zápornou ást íselné osy. typ nejmenší kl. . nejv tší kl. platných cif. Real 2.9e-39 1.7e38 11 Single 1.5e-45 3.4e38 7 Double 5.0e-324 1.7e308 11 Extended 5.0e-324 1.7e308 15 Standardní typ extended má kladný rozsah od 3.4e-4932 do 1.1e4932 a 19 platných cifer v desítkovém zápisu. Protože pro zjednodušení interpretr obsahuje pouze jeden interní reálný typ a tento nepokrývá celý rozsah skute ného typu extended, je kv li zp tné kompatibilit vytvo en extended se zmenšeným rozsahem. Typ ukazatel Na rozdíl od prom nných ostatních typ , které obsahují konkrétní hodnoty, ukazatel data neuchovává, ale obsahuje odkaz na místo, kde se data nacházejí. Obsahem ukazatele je tedy adresa. Na ukazatelích lze provád t rela ní operace = <>, a operaci ^ (dereference) neboli p ístup k odkazovanému objektu. Porovnávat lze spolu pouze ukazatele kompatibilních typ . 33

Deklarace pointeru se za íná znakem „^“, po kterém následuje identifikátor se jménem odkazovaného typu. P estože toto na první vypadá jako omezení, protože zde m že být pouze jméno typu, není tomu tak. Z d sledku pravidel typové kompatibility na pointerech by použití deklarace nového „anonymního“ typu uvnit definice ukazatele znemožnilo vytvo it libovolnou adresu, která by byla do tohoto ukazatele p i aditelná. Vytvo ená adresa operátorem @ by totiž nebyla kompatibilní a tedy by se nedalo dosazovat. Speciální vlastností je, že p i definici ukazatele ješt nemusí být bázový typ znám, tedy identifikátoru ješt nemusí být p i azen žádný typ. Každopádn p ed ukon ením defini ního úseku a za átkem begin-end bloku jeho typ již musí být definován. V rámci ukazatel je pot eba se zmínit o speciální hodnot nil, která znamená, že daný ukazatel neobsahuje adresu na žádný objekt. Tuto speciální hodnotu je možné dosadit do každého ukazatele nezávisle na typu. K ukazatel m též pat í adresní operátor @. Tento unární prefixový operátor vrací adresu objektu, který se vyskytuje za ním. Nelze vracet adresu do asných objekt , které si kompilátor vytvá í nap . pro mezivýpo ty, a adresu konstant, protože ty typicky adresu nemají. Procedurální typ Procedurální typ v sob uchovává adresu funkce, kterou umož uje pozd ji vyvolat. Dá se použít pro dynamickou volbu funkce, která se má provád t. Na procedurálním typu lze mezi identickými typy provád t rela ní operace = a <>, vyvolávat je jako normální funkce. Jediný rozdíl je u neparametrických procedur a funkcí, kde u procedurálních prom nných nedochází k automatickému vyvolání t chto funkcí p i použití jména této prom nné. U t chto procedurálních prom nných je pot eba vždy použít závorkovou konvenci, kde je seznam parametr prázdný. Více o vyvoláními funkcí a procedur je v další sekci. Procedurální typ se rozd luje na procedury a funkce. Procedury nevrací návratovou hodnotu a proto nemohou být sou ástí výraz a volání procedury p edstavuje jeden z p íkaz . Naproti tomu funkce návratovou hodnotu vrací a proto mohou být pouze sou ástí výraz . Definice procedurálního typu za íná kl. sl. procedure po kterém následuje deklarace formálních parametr . U funkce jde o kl. sl. function a deklaraci formálních parametr , po kterém následuje znak „:“ a definice typu, který p edstavuje návratovou hodnotu funkce. Jména parametr použitých v deklaraci parametr nemají žádný vztah ke jmén m parametr dosazované procedury, d ležité je po adí a jejich typy. Jak se definují formální parametry je uvedeno v následující sekci o procedurách a funkcích. Strukturovaný typ Strukturovaný typ neboli záznam se používá pro uložení dat, které k sob logicky pat í a obvykle se používají zárove . Na rozdíl od TP zatím nepodporuji variabilní ást tohoto typu. Na strukturovaný typ se nedá používat v tšina operátor až na p i azení a adresní operátor. Pro p ístup k položkám se používá znak „.“ kdy na levé stran od te ky je prom nná se strukturou a na pravé jméno položky struktury. Definice tohoto typu za íná kl. sl. record po kterém následuje seznam definic prom nných podobn jako p i deklaraci oby ejných prom nných (Var blok), který je na záv r ukon en kl. sl. end. Definice konstantních nebo inicializovaných struktur zatím není podporovaná a p i dalším vývoji by m la být p idaná.

34

Diagram 6: Type blok, Definice typu

4.7 Procedury a funkce Procedury slouží k vykonání podprogram . Rozd lení úlohy na menší, logicky rozd lené ásti, zlepšuje p ehlednost, itelnost a pochopitelnost kódu. Vykonání procedury znamená vyhodnocení parametr a vykonání t la procedury, tj. p íkaz , které p ísluší vyvolané procedu e. Funkce na rozdíl od procedur vrací návratovou hodnotu. Neplatí omezení jako v TP na typ návratové hodnoty, ta m že být libovolná. Proceduru je možné vyvolat poté, co byla deklarovaná i definovaná. Každá deklarovaná procedura musí být pozd ji i definovaná. Viditelné procedury jsou ty, které jsou definované v defini ním úseku (interface ást) p ipojených jednotek. Procedury deklarované i definované p ed práv zpracovávaným místem a jsou p edch dci práv zpracovávané procedury (je do nich vno ena). Syntaxe pro definování a deklarování procedur se mírn liší podle místa, na kterém se nachází. Hlavi ka procedury za íná kl. sl. procedure a po n m se o ekává identifikátor ur ující jméno dané procedury. Pak následuje definice formálních parametr . Hlavi ka funkce za íná na kl. sl. function, následuje identifikátor se jménem funkce a definice formálních parametr . Poté následuje znak „:“ a definice typu. Ta je obvykle reprezentována identifikátorem se jménem již d íve definovaného typu. Definice formálních parametr je pro neparametrické procedury prázdná, pro funkce s parametry za íná znakem „(“ a pak následují st edníkem odd lené definice parametr . Na záv r je nutné závorku uzav ít znakem „)“. Definice parametru za íná kl. sl. var, které m že být p esko eno. Poté následuje árkou odd lený seznam se jmény prom nných a po n m znak „:“ a definice typu. Tento typ, stejn jako direktiva var, jsou spole né pro všechny parametry 35

vytvo ené v této ásti. Pokud je použita direktiva var, znamená to že jde o parametr volaný odkazem, v opa ném p ípad je p edávaný hodnotou. Pro parametry p edávané hodnotou se p i volání funkce vytvo í kopie hodnoty speciáln pro vyvolanou proceduru, ta jej pak m že libovoln m nit, aniž by zm nila p vodní prom nnou. Proto mohou být použity pouze jako vstupní parametry. Vytvá ení kopií m že být zejména u struktur a polí asov náro né. Hodnotou je možné p edávat konstanty. Skute ným parametrem též m že být výraz, na rozdíl od druhého typu parametru. Parametry p edávané odkazem nevytvá í kopii dat, ale p edává se ukazatel na skute ný parametr. Proto tyto parametry mohou být i výstupní, jakákoliv zm na se provede na prom nné skute ného parametru. Protože je pot eba získat ukazatel, nemohou být skute ným parametrem konstanty a výrazy.

Diagram 7: Hlavi ky procedur a funkcí Deklarace procedur a funkcí ve ve ejné ásti jednotky (Procedure unit block) je ve tvaru hlavi ka procedury nebo funkce, za kterou následuje st edník. Protože po et a po adí blok ve ve ejné ásti jednotky není omezen, je takto možné deklarovat libovolné množství procedur. V rámci Procedure bloku již mohou být jak deklarace tak definice. Deklarace vypadá tak, že po hlavi ce procedury i funkce následuje „;“, po n m kl. sl. forward a op t „;”. V p ípad definice po hlavi ce a st edníku následuje defini ní úsek procedury, kde lze definovat typy, konstanty, prom nné, které jsou privátní pouze pro tuto proceduru a pro procedury a funkce do ní vno ené. Ty lze v rámci defini ního úseku též vytvá et. Po defini ním úseku p ijde na adu st edníkem ukon ený složený p íkaz (Begin-end blok), který p edstavuje t lo procedury. T lo procedury jsou tedy p íkazy, které se vykonají p i zavolání procedury. Mezi deklarací a definicí funkce se musí zachovat po et a typy parametr , jejich jména se mohou m nit a v t le funkce platí jména z definice. Jména parametr musí být v rámci funkce jedine né.

36

Diagram 8: Definice a deklarace procedur Vyvolání procedury nebo funkce vypadá v programu podobn . Nejprve je výraz, který ur uje volanou proceduru. Typicky jde o jméno funkce, ale m že to být nap . i jméno procedurální prom nné ve struktu e, i návratová hodnota funkce. Po ur ení, co vlastn budeme volat, se musí specifikovat skute né parametry. U funkcí bez parametr m žeme tuto ást vynechat. Skute né parametry za ínají znakem „(“, po kterém m že následovat seznam výraz odd lený árkami, a na záv r znak „)”. Po et skute ných parametr a jejich typy musí odpovídat formálním parametr m volané procedury. Tímto je popsaná syntaxe volání, ale vzhledem k tomu, že jméno funkce m že mít podle kontextu až 3 r zné významy, je vhodné se o této ásti zmínit podrobn ji. Pokud stojí za jménem procedury závorka s parametry, jde v každém p ípad o vyvolání procedury. Na toto chování se dá nahlížet jako na operátor volání funkce, který má nejvyšší prioritu. O úrove níž s prioritou stojí prefixový operátor @ (adresa objektu). Pokud se tedy objeví p ed vyvoláním procedury, znamená to, že má vracet adresu návratové hodnoty. Toto je tedy první význam pro jméno procedury. Druhý význam je u funkcí. Pokud jméno funkce stojí, jako samostatný výraz, vlevo u p i azení, nastavuje se takto návratová hodnota funkce. Takto jde nastavit jak návratovou hodnotu aktuáln zpracovávané funkce, tak návratovou hodnotu funkcí, do kterých je práv zpracovávaná procedura i funkce vno ená. Jako poslední má jméno procedury a funkce význam adresy daného objektu. Jméno musí být použito bez závorek, které by znamenaly její vyvolání. V podstat to odpovídá operátoru @. Situace je mírn odlišná u neparametrických funkcí a procedur (ale ne u neparametrických procedurálních prom n ných), kde jejich jméno znamená jejich vyvolání a ne adresu. Aby bylo možné vyvolat procedurální prom nné funkcí

37

bez parametr , je možné, na rozdíl od TP, tyto funkce vyvolávat pomocí závorky s prázdným seznamem parametr .

4.8 Prom nné a konstanty Prom nná p edstavuje pojmenované místo v pam ti pro uložení dat. Hodnoty, které jdou do prom nné uložit, závisí na jejím typu a lze je b hem výpo tu programu m nit. Po áte ní hodnota prom nné není do prvního zápisu definovaná. Deklarace prom nných (Var blok) za íná kl. sl. var, po kterém následuje seznam deklarací jednotlivých prom nných (Deklarace prom nné). Každá taková deklarace je ukon ena st edníkem. Deklarace prom nné za íná árkou odd leným seznamem identifikátor budoucích prom nných, po kterém následuje znak „:“ a definice typu, která je obvykle p edstavována jménem typu. Tento typ je spole ný pro všechny prom nné, které tato deklarace vytvá í. Prom nné vytvo ené v defini ním úseku programu i jednotky jsou vždy v jednom exemplá i (i kdyby byla jednotka p ipojena vícekrát) a žijí po celou dobu b hu programu. Naproti tomu prom nné deklarované v defini ním úseku procedury, mohou existovat vícekrát. Vždy p i zavolání dané procedury jsou tyto její prom nné vytvo eny speciáln pro tuto instanci. Žijí a jsou p ístupné až do ukon ení dané instance. Krom b žných prom nných, které na po átku nemají definovanou hodnotu, existují i inicializované prom nné, které mají p ednastavenou hodnotu. N kdy jsou ozna ovány jako typové konstanty. Toto jméno vychází z toho, že jsou deklarovány v const bloku a na rozdíl od pravých, „netypových“ konstant je v jejich deklaraci ur en i jejich typ. Deklarace obou typ konstant (Const blok) za íná kl.sl. const a po n m následuje seznam deklarací jednotlivých konstant, kdy každá tato deklarace je ukon ena st edníkem. Deklarace konstanty za íná identifikátorem, za kterým m že být znak „:“ a definice typu. Poté již vždy následuje znak „=“ a konstantní výraz ur ující hodnotu konstanty. U netypových konstant se jejich typ ur í podle konstantního výrazu. Zatím jsem se nezmínil o viditelnosti identifikátor . Ve zkratce by se dalo íci, že lze vid t pouze identifikátory z defini ních úsek do kterých jsem zano en a které byly definovány p ed aktuální pozicí. Dá se p edstavit, že mám seznam t chto úsek , který postupn prohledávám, než daný identifikátor naleznu. Ve st edu tohoto seznamu mám úsek aktuáln zpracovávaného souboru. V p ípad , že jde o jednotku, pak jde o oba dva její defini ní úseky. Za každou p ipojenou jednotku postupn p ipojím p ímo za tento st ed seznam p idávané jednotky. Pokud jsem v hlavním bloku programu, anebo v inicializa ním bloku jednotky, potom je tento seznam již kompletní a identifikátory vyhledávám v n m. Pokud je aktuální pozice v procedu e, tak na za átek postupn p ipojuji úseky procedur do kterých jsem vno en. Beru z nich v potaz ovšem pouze ty identifikátory, které byly alespo deklarovány p ed aktuální pozicí v práv zpracovávaném souboru. Tento postup se používá pro všechny identifikátory až na labely, kde se hledá pouze v aktuálním úseku. V rámci jednoho defini ního úseku smí být identifikátor použitý pouze jednou. Nelze tedy definovat prom nnou i typ pod stejným jménem. Toto ovšem neplatí pro r zné úseky navzájem. Proto lze mít v r zných vrstvách prom nné se stejným jménem. Pak se použije ta prom nná, jejíž vrstva byla v seznamu uvedená d íve. íkáme, že tato zakryla prom nnou ze spodn jší vrstvy.

38

Diagram 9: Var blok, Const blok

4.9 Výrazy Výraz se dá p edstavit jako vzorec nebo p edpis, podle kterého se po ítá výsledek. Práv vracení výsledku je pro výraz charakteristické, na rozdíl od p íkaz , pro které je typická jejich innost. Výraz se dá použít obecn tam, kde se o ekává n jaká hodnota, nap íklad v parametrech funkcí, u for cyklu jako mez, v podmínce u podmín ného p íkazu a podobn . Výraz se skládá ze zdroj dat, které p edstavují prom nné, výsledky po volání funkcí a konstanty. Krom zdroj dat obsahuje výraz ješt operace. Ty z nich po ítají výsledek. U operací platí b žné priority jako v matematice, pro jejich úpravu je možné použít závorek. Výraz je u operátor stejné priority vyhodnocován obvyklým zp sobem, tedy zleva doprava. Priority jednotlivých operátor uvádím v seznamu, operace s nejvyšší prioritou jsou azeny naho e a postupn jejich priorita klesá. Jako první se vyhodnocují závorky, po jejích vyhodnocení se závorka nahradí jejím výsledkem, jako by to byla oby ejná prom nná. • @ not, unární + a – • * / div mod and shr shl • + - or xor • < > <= >= <> = U jednotlivých operátor je pot eba dát pozor na to, aby m ly jejich operandy správný typ. Tedy abychom nes ítali znak a íslo. Též je pot eba dát pozor na to, aby nám výsledek operace nep etek (aby se vešel do rozsahu povolených hodnot výsledné prom nné). V rámci deklarace konstant byly zmín ny konstantní výrazy. Výraz je konstantní, pokud je možné jeho hodnotu spo ítat již b hem p ekladu, což znamená, že se v n m nepoužívá operátor adresa, nekonstantní prom nné a dále, že se v n m nevolají žádné funkce.

4.10 P íkazy Základním stavebním kamenem popisujícím innost programu je p íkaz. Pascal jako standardní programovací jazyk obsahuje stejnou sadu základních typ p íkaz jak ji známe z dalších klasických procedurálních jazyk . Pascal je rekurzivn spo etným jazykem. Existují 39

r zné p íkazy a ty si dále ve zbytku této sekce popíšeme. Pokud se zmíním, že n kde o ekávám p íkaz, m že na tomto míst stát libovolný z nich. Složený p íkaz pat í k nejpoužívan jším p íkaz m. Za íná kl. sl. begin, poté následuje st edníkem odd lený seznam p íkaz a je ukon en kl. sl. end. St edník za posledním p íkazem je volitelný. Gramatika ho standardn neo ekává, ale díky existenci prázdného p íkazu lze mimo jiné i zde psát st edník. Vykonání složeného p íkazu, znamená postupné lineární vykonávání p íkaz ze seznamu. Tato lineární posloupnost m že být narušena pouze skokem (goto, break, continue, exit. a halt).

Diagram 10: Složený p íkaz Dalším typem ídících struktur jsou cykly. While cyklus se vyzna uje podmínkou na za átku a p edem neznámým po tem opakování. Díky podmínce na po átku se nemusí t lo cyklu v bec vykonat. P íkaz za íná kl. sl. while následovaným podmínkou a kl. sl. do po kterém následuje p íkaz. (St edník, který se v tšinou po p íkazu vyskytuje, pochází obvykle z Begin-end bloku). Vykonání jedné iterace cyklu znamená vyhodnotit podmínku, v p ípad jejího spln ní vykonat p íkaz a zahájit další iteraci cyklu. V p ípad , že podmínka není spln na, je vykonávání while cyklu ukon eno.

Diagram 11: While cyklus Další typ cyklu je repeat-until, který se vyzna uje podmínkou na konci cyklu a p edem neznámým po tem iterací. Syntaxe této ídící struktury je mírn atypická, protože v sob obsahuje posloupnost p íkaz . Díky podmínce na konci cyklu je zaru eno, že t lo cyklu bude provedeno alespo jedenkrát. Tento p íkaz za íná kl. sl. repeat. Po n m se o ekává posloupnost st edníkem odd lených p íkaz . Cyklus je zakon en kl. sl. until a podmínkou. Vykonání cyklu znamená opakované vykonávání p íkaz a vyhodnocování podmínky. V p ípad , že je podmínka spln na, ukon í se vykonávání tohoto cyklu, v opa ném p ípad se zahájí nová iteraci a vykonávání cyklu pokra uje dál.

40

Diagram 12: Repeat cyklus V Pascalu má for cyklus podmínku na po átku a po et opakování je p edem známý. Oproti jiným programovacím jazyk m (C, Java) nenabízí stejnou vyjad ovací sílu. Cyklus za íná kl. sl. for. Poté následuje ídící prom nná, p i azovací symbol a výraz ur ující po áte ní hodnotou ídící prom nné. Za ním se o ekává kl. sl. to nebo downto a výraz s koncovou hodnotou. Po n m p ijde na adu kl. sl. do a p íkaz. ídící prom nná musí být l-hodnota ordinálního typu. Hodnota ídící prom nné se nesmí v t le cyklu m nit. Výrazy s po áte ní a koncovou hodnotou se vyhodnocují práv jednou p ed za átkem vykonávání cyklu a jejich výsledek musí mít typ kompatibilní s ídící prom nnou. Vyhodnocení tohoto cyklu znamená vyhodnotit oba výrazy a nastavit ídící prom nnou na po áte ní hodnotu. Poté se opakovan provádí test ov ující, jestli je ídící prom nná v intervalu mezi po áte ní a koncovou hodnotou (v etn mezí). Pokud ne, provád ní for cyklu je ukon eno. V opa ném p ípad se vykoná p íkaz. Pokud bylo v definici for cyklu použito kl. sl. to je ídící prom nná o jedni ku zv tšená, pokud downto pak o jedni ku zmenšená a za ne se provád t další iterace za ínající testem na rozsahy.

Diagram 13: For cyklus K cykl m se váží ješt p íkazy, které slouží pro ízení pr chod cykly. P íkaz break ukon í provád ní nejvnit n jšího cyklu a vyhodnocování pokra uje na prvním p íkazu za t lem cyklu. P íkaz continue ukon í vykonávání t la cyklu v této iteraci (tj. p esko í p íkazy za continue až do konce t la cyklu). Dochází k nové iteraci se vším co k ní pat í (úprava ídící prom nné, vyhodnocování podmínek). Tato klí ová slova mohou být použita pouze p ímo uvnit t la cyklu, nelze nap íklad použít continue v procedu e, která je z t la cyklu volána a sama žádný cyklus neobsahuje.

41

Diagram 14: ízení pr chodu cyklem Podobn jako pro cykly, existují i p íkazy pro kontrolu pr chod procedurami. Jedná se o p íkaz exit. Ten okamžit ukon í vykonávání procedury i funkce. V p ípad p ed asného opušt ní funkce se jako její výsledek použije naposledy jí nastavená návratová hodnota p ed vykonáním exitu. Pokud je exit v základním bloku programu, potom ukon uje celý interpret. P íkaz halt slouží k okamžitému ukon ení interpretu. Existují dv varianty. První, kdy se volá jako funkce bez parametr (samotné kl. sl. halt) a druhá, kdy se volá jako funkce s 1 parametrem. Ten musí být typu word. Tento parametr pak p edstavuje návratovou hodnotu spušt ného interpretu.

Diagram 15: ízení pr chodu blokem Podmín ný p íkaz spolu s case umož uje v tvení programu, neboli na základ podmínky rozhodnout, který p íkaz se má vykonat. Tato klauzule za íná kl. sl. if, poté pokra uje podmínkou, kl. sl. then a p íkazem, po n m m že následovat kl. sl. else spolu s p íkazem. V p ípad , že se v p íkazu vyskytuje i else ást, hovo íme o úplném podmín ném p íkazu, v opa ném p ípad o neúplném. Typickou chybou v tomto p íkazu bývá st edník za p íkazem p ed else. Vykonání if p íkazu znamená vyhodnocení podmínky. Pokud je spln na, dojde k vykonání p íkazu z then v tve. Když podmínka není spln na, dojde k vykonání p íkazu z else v tve, je-li tato v tev p ítomná.

Diagram 16: Podmín ný p íkaz Druhý z p íkaz , který slouží k v tvení programu je case. Na rozdíl od if, který se v tví na dv v tve, zde po et v tví není explicitn omezený a z toho plyne mírn složit jší syntaxe p íkazu. Ten za íná kl. sl. case a výrazem ur ující ídící hodnotu, podle které se rozhoduje, jakou v tev vykonat. Po n m se o ekává kl. sl. of a seznam st edníkem odd lených definic jednotlivých v tví a na záv r kl. sl. end. Výsledek výrazu musí být ordinálního typu. V tve jsou dvojího typu. Prvním typem je intervalová v tev. Ta za íná seznamem árkou 42

odd lených konstantních výraz a uzav ených konstantních interval , který je ukon en dvojte kou a po n m následuje p íkaz. Typ výsledných výraz musí být kompatibilní s ídícím výrazem. V tev usp je a p íkaz se vykoná v p ípad , že hodnota ídícího výrazu bu to náleží do n kterého z interval , nebo p ímo odpovídá n které z konstantních hodnot. Hodnoty a intervaly musí být v rámci všech v tví disjunktní. Druhým typem je else v tev, která se m že vyskytovat pouze na konci seznamu. Ta za íná kl. sl. else a následuje p íkaz, který se provede, pokud žádná z p edešlých v tví neusp la. Vykonání p íkazu case znamená vyhodnotit ídící výraz a rozhodnutí, do které v tve daná hodnota pat í. Pak dojde k vykonání p íkazu z dané v tve. V sou asné dob se testují jednotlivé v tve lineárn po sob a provede se první v tev, do které hodnota ídící prom nné pat í. V p ípad , že p íkaz obsahuje labely, které mají íselné identifikátory, m že být zápis mén intuitivní. Veškeré hodnoty p ed první dvojte kou jsou chápány jako seznam definující, kdy se daná v tev má použít. Vše za první dvojte kou už považuje za sou ást p íkazu, tedy za labely.

Diagram 17: Case p íkaz P íkaz skoku slouží ke zm n místa vykonávaných p íkaz . Za íná kl. sl. goto, po kterém následuje náv ští. Vykonání tohoto p íkazu zp sobí, že dalším vykonaným p íkazem bude ten, který následuje za definicí náv ští uvedeného za goto.

Diagram 18: P íkaz skoku P i azovací p íkaz slouží k nastavování hodnot prom nných. Po cílovém výrazu, který p edstavuje nastavovanou prom nou, následuje „:=“ a po n m výraz s dosazovanou hodnotou. Vykonání p íkazu p edstavuje vyhodnotit cílový výraz. Tím získáme prom nnou, do které se 43

uloží výsledek. Poté dojde na vyhodnocení druhého výrazu s dosazovanou hodnotou. Oba výrazy musí být kompatibilního typu, a cílový výraz musí být l-hodnotou, aby do n j bylo možno dosazovat. Typicky je cílový výraz jméno prom nné, kam se má hodnota dosadit.

Diagram 19: P i azovací p íkaz V rámci výraz už umíme vyvolávat funkce. P íkaz pro vyvolání procedury má stejnou syntaxi a sémantiku. Pouze nesmí být v rámci výrazu, protože nevrací žádnou hodnotu. Proto musí stát samostatn jako p íkaz. Typicky jde o jméno procedury následované seznamem parametr . Pouze v p ípad jména procedury, která nemá žádné parametry, lze závorky úpln vynechat a volat pouze jejím jménem. Posledním p íkazem je p íkaz with. Tento p íkaz je atypický tím, že p ímo neovliv uje vykonávání programu, ale zp sob, jakým se p eklada dívá na p íkaz, který je jeho sou ástí. Po kl. sl. with. následuje seznam árkou odd lených výraz , kl. sl. do a p íkaz. Tento p íkaz je typicky begin-end blok. Vykonání tohoto p íkazu znamená vyhodnotit výrazy ze seznamu a poté vykonat p íkaz. Výsledný typ výraz ze seznamu musí být struktura. V p íkazu, který následuje po do, se potom na prvky dané struktury nemusíme odkazovat p es te kovou notaci, ale lze je používat p ímo jako oby ejné prom nné. Pokud by se položka stejného jména vyskytovala ve více strukturách ze seznamu, potom by se použila ta struktura, která z nich byla v seznamu na posledním míst .

Diagram 20: P íkaz with

4.11 Vestav né funkce Programovací jazyk netvo í pouze p íkazy, ale i vestav né knihovní funkce díky kterým m že program komunikovat s okolím, pracovat s adresami a pod. Sou asná implementace obsahuje alespo ty nejpoužívan jší základn jší funkce. Díky p ipravenému frameworku pro tvo ení knihovních funkcí není až tak t žké tento seznam dále rozší it. Funkce pro práci s celými ísly function abs( val : longint) : longint; Funkce vrací absolutní hodnotu parametru. function sqr( val : longint) : longint; Vypo ítá druhou mocninu parametru val. function round( val : double) : longint; Zaokrouhlí hodnotu parametru na celé íslo. Pokud je výsledek mimo rozsah longintu zp sobí b hovou chybu. 44

function trunc( val : double) : longint; Odsekne z hodnoty parametru desetinnou ást ísla. Pokud je výsledek mimo rozsah longintu vyvolá b hovou chybu. function hi( val : longint) : longint; Vrátí horní ást slova. (Nechá nastavený pouze 8 -15bit) function lo( val : longint) : longint; Vrátí dolní ást slova. (Nechá nastavený pouze 0-7bit) function swap( val : longint) : longint; Prohodí dolní a horní ást slova. ( 8-15 s 0-7 bitem) procedure inc( var val : generic ordinal variable); P i te k hodnot parametru jedni ku. V p ípad , že se bere adresa této funkce potom tato je typu inc( var val:longint). procedure dec( var val : generic ordinal variable); Ode te od hodnoty parametru jedni ku. V p ípad , že se bere adresa této funkce potom tato je typu dec( var val:longint). Funkce pro práci s reálnými ísly function sin( rad : double) : double; Funkce vypo ítá sinus úhlu z parametru zadaného v radiánech. function cos( rad : double) : double; Vrací cosinus úhlu z parametru. Úhel je zadán v radiánech. function tan( rad : double) : double; Vypo ítá tangens z úhlu. Úhel je zadán v radiánech. function arctan( val : double) : double; Vrací arcustangens argumentu funkce. Výsledný úhel je v radiánech. Arctan je inverzní funkcí k funkci tan na intervalu (- /2; /2). function fabs( val : double) : double; Vrátí absolutní hodnotu reálného ísla. function exp( val : double) : double; Vypo ítá hodnotu exponenciální funkce v bod val. (Vrací eval). Pro výpo et 10x lze použít vztahu 10x = ex*ln(10) function ln( val : double) : double; Vrací p irozený logaritmus z argumentu. (Vrací logaritmus o základu e). Pro výpo et log10 lze použít vztahu log10x = ln(x) / ln(10) function sqrt( val : double) : double; Vrátí odmocninu z daného reálného ísla. function fsqr( val : double) : double; Vypo ítá druhou mocninu z hodnoty reálného argumentu. function intPart( val : double) : double; Vrací celou ást z reálného ísla argumentu. function fround( val : double) : double; Zaokrouhlí reálné íslo z argumentu. function ftrunc( val : double) : double; Vrací celou ást z reálného ísla argumentu. function pi() : double; Vrátí hodnotu = 3.1415926535897933 Generování náhodných ísel function random( max : longint) : longint; Vrátí náhodné íslo z intervalu <0;max) 45

procedure randomize(); Inicializuje vestav ný generátor náhodných ísel. Využívá systémových hodin. Funkce pro práci s ukazateli Adresy vypadají na první pohled podobn jako v TP (adresování x86 reálného módu). Skládají se ze segmentu a offsetu. Tím ovšem v tšina podobnosti kon í. Segment i offset je rozší en z 16 na 32 bit . A dále již neplatí, že adresa v pam ti je segment * 16 + offset. Adresování v interpretu by se dalo p irovnat k segmentaci. Segment ( íslo segmentu) p edstavuje souvislý blok místa n kde v pam ti a offset pozici v rámci tohoto segmentu. Jednotlivé segmenty jsou na sob nezávislé a disjunktní. function addr( object ) : pointer; Podobn jako operátor @ vrací adresu objektu. Pozor na neparametrické funkce a procedury, kde v p ípad uvedení jejich jména jako parametru, dochází k jejich automatickému vyvolání a vrácení adresy výsledku. function assigned( ptr : pointer ) : boolean; Testuje zdali byla do ukazatele p i azena hodnota, anebo jestli obsahuje konstantu nil. Vrací true v p ípad , že parametr prt nemá hodnotu nil. function ptr( seg : longint; off : longint) : pointer; Vytvo í ukazatel ze segmentu a offsetu. Tato funkce umož uje provád t pointerovou aritmetiku. Její použití není doporu eno, protože m že být v budoucích verzích odstran na. function ofs( ptr : pointer) : longint; Vrátí offsetovou ást ukazatele. function seg( ptr : pointer) : longint; Vrátí segmentovou ást ukazatele. Funkce pro práci s dynamickou pam tí procedure new( var prt : pointer); Naalokuje na heapu pam pro typ, na který se pointer prt odkazuje. Nastaví pointer na nealokovanou adresu. procedure dispose( var prt : pointer); Uvolní naalokovanou pam a nastaví pointer na nil. Funkce pro práci se vstupem a výstupem procedure write( val : longint); Vypíše hodnotu celo íselného argumentu na obrazovku. procedure writeln( val : longint); Vypíše hodnotu celo íselného argumentu na obrazovku a od ádkuje. procedure fwrite( val : double); Vypíše hodnotu reálného parametru na výstup. procedure fwriteln( val : double); Vypíše hodnotu reálného parametru na výstup a od ádkuje. procedure writeEmptyln(); Od ádkuje. procedure putc( c : char); Vytiskne znak na výstup. function readln() : longint; Na te celé íslo ze vstupu. V p ípad ne íselného vstupu vrací 0. function freadln() : double; Na te reálné íslo ze vstupu. V p ípad ne íselného vstupu vrací 0. 46

5 Srovnání s dalšími implementacemi Pascalu V této kapitole srovnám r zné kompilátory Pascalu s mojí implementací. Za dlouhou dobu od vzniku tohoto programovacího jazyka bylo vytvo eno mnoho kompilátor . Zmi me alespo Turbo Pascal od firmy Borland, Free Pascal (www.freepascal.org), GNU Pascal (http://www.gnu-pascal.de), placený Irie Pascal (www.irietools.com), Vektor Pascal (http://www.dcs.gla.ac.uk/). Každý sebou p ináší vlastní rozší ení jazyka. Takto vzniklo mnoho r zných dialekt . Jazyk byl standardizován, existují 2 normy - Pascal ISO 7185:1990 (www.iso.org) a Extended Pascal ISO/IEC 10206:1991. Turbo Pascal je de-facto standardem a v tšina kompilátor implementuje v tšinu z jeho rozší ení. Pro srovnání jsem zvolil Turbo Pascal, Free Pascal a GNU Pascal. Protože se jedná o široce používané produkty s mnohem delší historií je z ejmé, že množství podporovaných vlastností bude o poznání širší než v mém interpretu. TP jsem zvolil proto, že se jedná asi o nejznám jší implementaci. FreePascal slouží jako ukázka možného rozší ení TP a p echod k více platformám. GNU Pascal zastupuje jiný dialekt Pascalu. Historie TP sahá až do roku 1983, kdy byla p edstavena první verze p eklada e. TP je od po átku je svázán s opera ním systémem MS-DOS. Již první verze v sob zahrnovala i jednoduché vývojové prost edí. Na rychlost p eklada e i vygenerovaného kódu upozor ovalo slovo turbo ve jménu p eklada e. Velkou zm nu p edstavovala tvrtá verze, kdy bylo zm n no IDE a p idáno generování soubor v exe formátu. D íve se vytvá ely com soubory. Verze 5.5 p išla se základní podporou objekt . Všechny tyto starší verze uvolnila p ed n kolika lety firma Borland pro bezplatné používání a lze si je stáhnout z jejich stránek. Ve verzi 7 krom p ejmenování na Borland Pascal a drobných úprav v jazyce p ibyla schopnost generovat i nativní Windows aplikace. Poté již vývoj sm oval k Delphi a grafickému návrhu. Na konci 80tých a v první polovin 90tých let minulého století byl TP na vrcholu své slávy. Free Pascal vznikl jako náhrada Turbo Pascalu. Proto implementuje tém veškeré schopnosti TP. Oproti TP, ale b ží na více opera ních systémech a hardwarových architekturách. Jedná se o 32/64 bitový p eklada . Jeho vývoj zapo al v dob , kdy Borland oznámil, že nevyjde BP 8. Obsahuje spoustu rozší ení a nových schopností, na rozdíl od TP se stále vyvíjí. GNU Pascal se snaží držet standard pro Pascal. Základním cílem autor byl ud lat kompilátor spl ující ISO normy Pascalu, až v druhé ad byla kompatibilita s dalšími standardy. P esto rozdíl není mnoho. Stejn jako Free Pascal podporuje mód se zvýšenou kompatibilitou. GNU Pascal je spojen s celou rodinou GNU jazyk . Kompilátor obsahuje frontend pro Pascal, ale backend je již spole ný s dalšími jazyky z této rodiny (nap gcc). Z toho plyne i velké množství podporovaných platforem. Aktivní vývoj projektu ustrnul p ed n kolika lety. Podporované platformy TP a jím p eložený program je schopen b hu pod MS-DOSem a v kompatibilních opera ních systémech. Z toho plyne, že je podporovaná pouze IA32 platforma. Výsledný vygenerovaný kód je 16 bitový. U BP7 to platí v p ípad p ekladu pro reálný mód. Tato úzká symbióza je daná mimo jiné i datem vzniku prvních verzí TP a umož uje mít v jazyku n které zvláštní konstrukce, které nejdou rozumn p enášet na jiné platformy. Jde o pole mem a ports, near a far volání funkcí, i direktivu interrupt apod. FreePascal je multiplatformní dokáže b žet pod Windows, Linuxem, FreeBSD, OpenBSD i OS/2. Umí vygenerovat výsledný soubor pro procesory z rodiny IA32 (x86) i pro její 64bitové rozší ení, PowerPC, Sparc od Sunu a ARM. Kompilátor je schopen provád t 47

cross kompilaci, tedy vytvo it spustitelný soubor pro jinou platformu, než na které je práv spušt n. Vygenerovaný kód je 32 nebo 64 bitový, podle platformy, na kterou se p ekládá. Práv díky ší i podporovaných systém již nem že být jazyk tak úzce svázán s opera ním systémem, a proto práv konstrukce výše zmín né u TP spolu s vestav ným assemblerem p edstavují asi nejv tší problémy p i p echodu z TP na Free Pascal. GNU Pascal podporuje též velké množství opera ních systém . Je schopen b žet pod Linuxem, Os X, OS/2, na rodin BSD systém , na opera ním systému Hurd a zprost edkovan s pomocí cygwinu i mingw i pod Windows. Podporované procesory jsou z rodiny IA32 i s jeho 64bitovým rozší ením, z rodiny procesor Sparc, Mips a dalších. Vygenerovaný kód je 32 nebo 64 bitový, podle platformy, na kterou se p ekládá. M j interpret je schopen b hu pod Windows i Linuxem. Na dalších opera ních systémech jsem jej nezkoušel p ekládat, ale protože v n m nejsou použité žádné speciální nep enositelné techniky ani p ímé volání funkcí kernelu, tak se dá o ekávat, že portování na další opera ní systémy nebude náro né. Jiné je to ohledn podporovaných procesor , zatím vždy se interpret spoušt l na IA32 platform . P i p ípadném p enosu na jinou platformu, by mohly vzniknout problémy nap íklad v požadavku na zarovnání prom nných v pam ti. IDE TP v sob již od prvních verzí obsahoval integrované vývojové prost edí. To bylo na svou dobu velice dob e provedené a dá se p edpokládat, že práv to spolu s jeho použitelností pro praktické programování stálo za jeho velkou oblibou. Vývojové prost edí bylo textové a obsahovalo vše, co bylo pot eba pro tvorbu programu a jeho následné lad ní, takže nebyl d vod ho b hem práce opoušt t a používat jiné specializované nástroje. Toto vývojové prost edí není nutné používat, kompilátor existuje i ve verzi pro p íkazovou ádku. Free Pascal si sebou p ináší též textové vývojové prost edí, které je na první pohled velmi podobné IDE z TP. To ale v sob obsahuje další moderní prvky, jako je nap íklad svn klient a jiná drobná rozší ení. GNU Pascal stejn jako m j interpret neobsahuje žádné integrované vývojové prost edí. S Free Pascalem i GNU Pascalem je možné použít i IDE Dev-Pascal od firmy Bloodsheed. To je již typická aplikace pro Windows. Ovšem komer ním vývojovým prost edím nem že konkurovat. Chybová hlášení TP skon í p eklad p i první nahlášené chyb . Pozice chyby je ur ena ádkem. Chyby jsou ve v tšin p ípad srozumitelné a dob e popisují v em je problém. V p ípad konstantních podvýraz dochází k jejich vyhodnocení již b hem p ekladu a p ípadné chyby jako je d lení nulou hlásí již p i kompilaci. V p ípad b hové chyby dokáže z adresy chyby nalézt místo v programu, kde k ní došlo. Free Pascal pokra uje v p ekladu i po první nalezené chyb , pozici chyby hlásí s p esností na znak. Stejn jako v p ípad TP vyhodnocuje konstantní podvýrazy ihned. Z d lení nulou se již nevzpamatuje a v p ekladu dál nepokra uje. GNU Pascal v p ekladu po chyb pokra uje. Pozici hlásí s p esností na ádky. D lení nulou hlásí jako chybu již p i p ekladu, z této chyby se ovšem vzpamatuje a na rozdíl od Free Pascalu pokra uje v kompilaci dál. M j interpret hlásí chyby s p esností na jednotlivé ádky a po nalezení chyby se snaží v kompilaci pokra ovat, ale za cenu docela velkého množství zavle ených chyb. V p ípad d lení nulou v konstantním podvýrazu, toto hlásí jako varování a až za b hu jako b hovou chybu. Tento p ístup je zvolen s ohledem na to, že k danému d lení nakonec nemusí dojít a v tom p ípad se podle mého názoru jedná o platný program. 48

Základní jazykové konstrukce TP podporuje všechny základní jazykové konstrukce. Oproti standardnímu Pascalu jsou sice mírn rozší ené, ale tato rozší ení byla v tšinou ostatních p eklada p ejata. B hem zkoumání vlastností jsem se dozv d l i o n kterých chybách a problémech, které bu implementace nebo návrh gramatiky obsahuje. Zmi me nap íklad možnost vícenásobného použití téže hodnoty v case v tvích. Další problém se skrývá v inicializovaných prom nných, kdy se pro dosazení hodnoty používá operátor „=“. Ten ovšem m že být i sou ástí výrazu a proto u intervalových typ nemusí být vždy jasné, kde kon í konstantní výraz s hranicí intervalu a kde již za íná výraz ur ující nastavovanou hodnotu. Free Pascal též podporuje všechny základní konstrukce. Obsahuje ovšem adu drobných rozší ení, odstra uje n která omezení z TP. Oproti BP neomezuje návratový typ funkcí. U jednotek je možné p idat nejen inicializa ní kód, ale i kód, který se provede p i ukon ení programu. GNU Pascal umož uje používat všechny základní jazykové konstrukce. Z mnoha rozší ení zmi me nap . pointerovou aritmetiku. Podobn jako Free Pascal umož uje u jednotek ur it kód pro ukon ení programu. Syntaxe tohoto rozší ení je ovšem rozdílná. U funkcí není omezení na návratovou hodnotu a u jejich parametr lze používat v tší množství modifikátor než v TP. Funkce lze používat i jako procedury, potom se vrácená hodnota ignoruje. M j interpret umí používat v tšinu jazykových konstrukcí. Nepodporuji variabilní ást u strukturovaných prom nných, množinu, pole, et zce a soubory. Na rozdíl od TP nemám omezení návratové hodnoty u funkcí. Stejn jako TP netestuji disjunktnost rozsah jednotlivých v tví v case p íkazu. Podpora objekt V TP jsou objekty podporované již od verze 5.5. Oproti jiným jazyk m s podporou objekt ovšem nenabízí podobné možnosti. To se zlepšilo až s p íchodem Delphi, kde byla podpora objekt zna n vylepšena. V TP lze používat virtuální metody, konstruktory a destruktory. Neobsahuje ovšem statické metody, tak jak je známe z C++. ízení p ístupu u objekt umož uje použití pouze ve ejných a privátních metod. Privátní ovšem znamená, že tyto metody a prom nné jsou vid t pouze v jednotce, kde byla t ída vytvo ena. Free Pascal dále rozši uje podporu objekt . Toto rozší ení je inspirováno Delphi. Podporuje lepší ízení p ístupu k metodám objekt . Ve specifikaci viditelnosti lze používat public, protected a private. Jejich sémantika odpovídá C++. Na rozdíl od TP podporuje i abstraktní metody. Vícenásobná d di nost je nahrazena konceptem rozhraní (Interface). Pro snazší implementaci callback funkcí, byl vytvo en speciální typ metody. Message metody umož ují definovat jaký typ zpráv zpracovávají a p eklada sám vytvo í speciální dispatcher, který za ídí p i p íchodu daného typu zprávy vyvolání této metody. Na rozdíl od Delphi mohou být identifikátory zpráv i textové. GNU Pascal též obsahuje podporu objekt . Ta odpovídá verzi z Borland Pascalu 7. Další rozší ení, která by odpovídala Delphi nebo standard m Pascalu již nebyla implementovaná. M j interpret zatím neobsahuje podporu objekt . V p ípad dalšího rozši ování by bylo p idání objekt jedna z prvních v cí, na které by se pracovalo. Pokro ilé schopnosti Protože TP považujeme za obvyklou implementaci, jsou jím podporované konstrukce považovány za standardní schopnosti, které se od ostatních implementací automaticky o ekávají. Tento p ístup je ovlivn n tím, že vývoj TP byl ukon en p ed dlouhou dobou a nové vlastnosti mu tedy již nep ibývají. 49

Free Pascal je v tomto sm ru asi nejpokro ilejší implementací Pascalu. Oproti TP povoluje navíc p edefinování operátor . Mimo to umož uje p et žování funkcí. Podobn jako v C++ jsou podporovány výjimky a šablony. Dokáže pracovat s dynamickými knihovnami, obsahuje v sob podporu pro vlákna. Podporuje MMX instrukce, obsahuje speciální typ a omezené množství operátor , nad kterými dokáže toto rozší ení použít. Obsahuje obrovské množství dodávaných knihoven. Podporuje základní optimalizace. V GNU Pascalu není tak mnoho pokro ilých vlastností. Umož uje p edefinovávat operátory. Na rozdíl od Free Pascalu obsahuje v tší množství optimalizací a vzhledem k tomu, že používá stejný backend jako gcc se dá o ekávat, že bude generovat rychlejší kód. Pokud bych si z porovnávaných implementací m l vybrat nejlepší, zvolil bych Free Pascal. Jde o velmi kvalitní, stále se rozvíjející projekt. TP diskvalifikuje jeho stá í. Z toho plyne podpora pouze pro 16bitové procesory. U GNU Pascalu je problémem zase v podstat ukon ený vývoj, který nebyl dotažen do konce. P i intenzivní práci s databázemi, by se vyplatilo zvážit použití i jiných distribucí, nap íklad komer ního Irie Pascalu.

50

6 Záv r V rámci práce jsem se seznámil s nástroji pro generování kódu a s jejich za le ováním do projektu. Velmi d kladn jsem porozum l syntaxi (Turbo) Pascalu i se záludnostmi, které v sob obsahuje, a které nejsou na první pohled vid t – cykly v p ipojování jednotek, vyvolávání funkcí bez parametr , definování intervalových typ . Zvažoval jsem r zné alternativy, jak mnohé v ci ud lat. Stalo se mn , že jsem vid l, jak zvolené ešení p es své výhody p i implementaci p ináší další problémy. A to v p ípad odd leného ukládání prom nných r zných typ , p i rozd lení ukazatel na datové a procedurální, ale i v dalších situacích. D kladn jsem poznal typový systémem. Sou ástí projektu byl i jeho rozši itelný objektový návrh a implementace. Musel jsem ešit ur ování pozic prom nných v pam ti tak, aby odpovídalo požadavk m, které na n j budou klást pole a struktury. Porovnal jsem r zné druhy generování kódu (xslt transformacemi a direktivou define). Vyzkoušel jsem si práci na rozsáhlém projektu i p izp sobováním aplikace pro b h na více platformách. Zevrubn jsem se seznámil s teorií a myšlenkami, které stojí za lexikálními analyzátory i syntaktickými parsery, poznal jejich význam pro frontend. Výsledkem mé práce je interpret podmnožiny Pascalu. Jeho výhodou jsou rozumn len né, dostate n dokumentované a p enositelné zdrojové kódy. V ím, že po krátkém seznámení se strukturou projektu, pochopení významu jednotlivých t íd a zp sobu p ekladu, by na tuto práci dokázal jiný programátor bez problém navázat. Asi nemá význam zde v záv ru znovu popisovat strukturu projektu, rad ji vás odkáži na za átek t etí kapitoly, kde se tento nástin nachází. Vzhledem k provázanosti ástí interpretu by vysv tlení jedné z nich bylo siln vytržené z kontextu a p i jeho dopln ní bych již opisoval programátorskou dokumentaci, což není vhodné. Když se s odstupem asu dívám na tento sv j projekt, vidím spoustu v cí, které bych ud lal jinak, které by si zasloužily p epsat a tím zlepšit p ehlednost kódu, jeho rozši itelnost apod. Na to se dá dívat z více pohled . Jedním z nich m že být, že jsem se b hem dlouhé doby implementace posunul zase n kam dál se svými schopnostmi, že danému problému více rozumím. Druhým z nich m že být, že v ci nedokáži dokonale analyzovat a rozvrhnout. Je pravdou, že komplexnost a rozsáhlost tohoto problému mn d lala ur ité problémy. Byl to asi první projekt, kdy již nesta ilo vše b hem chvíle jednoduše promyslet a za ít implementovat. Proto jsem se d kladné analýze musel u it a ne vše se napoprvé ud lalo dokonale. Pochopil jsem, že tvorba kompletního p eklada e, je náro ná týmová práce. Toto téma v sob skrývá velký potenciál pro rozši ování mnoha r znými sm ry. Doufám, že v projektu budu moci pokra ovat dál a dotáhnu jej do použitelného stavu, kdy by se hodil i dalším uživatel m. Po dokon ení implementace chyb jících vlastností z Pascalu, objekt a zlepšení stability, bych z n j rád vytvo il nástroj, který se dá jednoduše integrovat do jiných projekt . Tím jim poskytnout dynami nost, schopnost používat makra, vnit ní jazyk, kterým budou uživatelé ovliv ovat jeho chování. Je zde i mnoho dalších možností a sm r , kterými by šlo v práci pokra ovat. Zm nit virtuální stroj za jiný rychlý a již vytvo ený, nebo sou asný vylepšit, aby používal pokro ilejší techniky. Díky této svojí bakalá ské práci jsem se detailn ji seznámil s problematikou p eklada a interpret . V noval jsem tematice virtuálních stroj a zkusil si ho vytvo it. Prošel jsem si návrhem interpretu a jeden též implementoval. B hem práce jsem se musel potýkat s mnoha problémy. Jejich p vod byl r zný, n které zp soboval rozsah práce, jiné m j špatný návrh, jindy nekompatibilita p eklada . Jejich ešení mn ovšem p inášelo nové neocenitelné zkušenosti. Práv poznání toho širokého a zajímavého tématu spolu s nabytými zkušenostmi si nejvíce cením.

51

7 Zdroje [1] http;//java.sun.com/ http://java.sun.com/docs/overviews/java/java-overview-1.html http://java.sun.com/products/hotspot/whitepaper.html [2] http://en.wikipedia.org/wiki/Java_bytecode [3] http://www.php.net/ [4] http://www.zend.com/ http://www.zend.com/en/products/guard/in-depth [5] http://en.wikipedia.org/wiki/Perl [6] http://www.parrotcode.org/docs/ [7] http://www.python.org/about/ [8] Common language infrastructure - stadard http://www.ecma-international.org/publications/files/ECMA-ST/Ecma-335.pdf [9] http://msdn.microsoft.com/ Inside the .NET Framework http://msdn.microsoft.com/en-us/library/a4t23ktk(VS.71).aspx [10] http://www.mono-project.com/What_is_Mono [11] http://en.wikipedia.org/wiki/Just-in-time_compilation [12] http://dsrg.mff.cuni.cz/~ceres/sch/osy/slides/main.pdf [13] Ragel - http://www.cs.queensu.ca/~thurston/ragel/ [14] Quex - http://quex.sourceforge.net/ [15] Flex - http://www.gnu.org/software/flex/manual/html_mono/flex.html [16] Coco/R - http://www.ssw.uni-linz.ac.at/coco/ [17] ANTRL - http://www.antlr.org/ [18] Bison - http://www.gnu.org/software/bison/manual/index.html [19] Mikula P., Juhová K., Soukenka J.: Turbo Pascal 7.0 Kompletní pr vodce, Grada, 1993 [20] Polách E. : http://home.pf.jcu.cz/~edpo/program/prginfo.html [21] Aho V. A., Sethi R., Ullman D.J.: Compilers: Principles, Techniques and Tools Pearson Education, 2001 [22] Principy p eklada http://ulita.ms.mff.cuni.cz/pub/predn/PP/

52

P íloha - Zkratky a pojmy AST CLI CLR deklarace definice GC GCJ IDE iterace JVM JIT kl. sl. l-hodnota PHP te ková notace TP VM ZE

Abstract syntax tree Common language infrastructure Common runtime language íká, že pozd ji bude daný symbol definován. Od deklarace se daný objekt smí používat. vytvá í daný objekt Garbage collecting – Automatická správa zdroj The GNU Compiler for the Java Integrated Development Environment – Vývojové prost edí jeden pr chod cyklem Java virtual machina Just in time klí ové slovo výraz i prom nná do které se m že p i azovat hodnota PHP Hypertext Preprocesor p ístup k položkám struktury pomocí znaku „.“, kdy vlevo od te ky je prom nná strukturovaného typu a vpravo jméno položky struktury Turbo Pascal, „referen ní“ implementace Pascalu Virtuální stroj Zend engine – virtuální stroj pro PHP

53

P íloha - CD Obsah CD V adresá ích flex, bizon a xslt jsou umíst ny nezbytné nástroje. Projekt pro Visual studio je využívá p i p ekladu interpretu. V projektu jsou na n cesty nastavené relativn . V adresá i bin se nachází p eložený interpreter. Adresá src obsahuje daný projekt. V jeho podadresá i Source se nachází zdrojové soubory. V adresá i TestFiles se nachází vzorové soubory pro testování interpretu. Adresá Unix obsahuje makefile pro p eklad souboru pomocí GNU make. A kone n adresá VS.NET 2005 obsahuje soubory projektu ve Visual studiu 2005. Soubor clear.NET2005 slouží pro odstran ní vygenerovaných a jiných pomocných soubor vzniklých p i p ekladu.

54