PŘEKLADAČ PRODEDURÁLNÍHO JAZYKA PROCEDURAL LANGUAGE COMPILER

VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ BRNO UNIVERSITY OF TECHNOLOGY

FAKULTA STROJNÍHO INŽENÝRSTVÍ ÚSTAV AUTOMATIZACE A INFORMATIKY FACULTY OF MECHANICAL ENGINEERING INSTITUTE OF AUTOMATION AND COMPUTER SCIENCE

PŘEKLADAČ PRODEDURÁLNÍHO JAZYKA PROCEDURAL LANGUAGE COMPILER

DIPLOMOVÁ PRÁCE DIPLOMA THESIS

AUTOR PRÁCE

BC. JOSEF VÁGNER

AUTHOR

VEDOUCÍ PRÁCE SUPERVISOR

BRNO 2007

ING. JAN ROUPEC, PH.D.

Strana 2

Strana 3

ZADÁNÍ ZÁVĚREČNÉ PRÁCE (na místo tohoto listu vložte originál a nebo kopii zadání Vaš práce)

Strana 4

Strana 5

LICENČNÍ SMLOUVA (na místo tohoto listu vložte vyplněný a podepsaný list formuláře licenčního ujednání)

Strana 6

Strana 7

ABSTRAKT Tento dokument popisuje proces vývoje a implementace překladače jednoduchého programovacího jazyka s použitím nástrojů pro generování lexikálního a syntaktického analyzátoru. Vývoj takového překladače je dobrým příkladem systematické aplikace technik OOP/strukturovaného programování při návrhu a implementaci netriviálního programu. Dalším cílem je všeobecný úvod do problematiky struktury, činnosti a tvorby překladačů. Její zvládnutí umožní hlubší pochopení problematiky umění programování ve vyšších programovacích jazycích. Zároveň se programátorovi zjednoduší pohled na celkový proces návrhu složitých systému pro specifické aplikace.

ABSTRACT This document describes development and implementation process of compiler of simplified procedural language. Construction of such a compiler gives a good example of OOP/structured programming aproach during design and implementation of non-trivial program. The next goal is the general introduction of structure, operation and construction of compilers. Mastering of this is essential to programming in high-level programming languages. This work should give programmer a better view in process of development of more complex systems for specific applications area.

KLÍČOVÁ SLOVA Překladač, kompilátor, interpretr, byte kód.

KEYWORDS Translator, compiler, interpreter, byte code.

Strana 8

Strana 9

PODĚKOVÁNÍ

Děkuji touto cestou Ing. Janu Roupcovi, Ph.D. za odbornou pomoc při řešení diplomové práce a všem kteří mi pomohli odbornými radami.

Strana 10

Strana 11

Obsah: Zadání závěrečné práce...................................................................................................3 Licenční smlouva..............................................................................................................5 Abstrakt.............................................................................................................................7 Poděkování........................................................................................................................9 1 2

Úvod.................................................................................................................................13 Základy teorie kompilátorů..........................................................................................15 2.1 Úvod..............................................................................................................................15 2.2 Druhy překladačů..........................................................................................................15 2.3 Struktura překladače......................................................................................................17 2.4 Tvorba překladačů jako vědecká disciplína..................................................................19 2.5 Syntaxe..........................................................................................................................19 2.5.1 Definice gramatiky.....................................................................................................20 2.5.2 Syntaxí řízený překlad ..............................................................................................23 2.5.3 Syntaktická analýza....................................................................................................25 2.5.3.1 Prediktivní syntaktická analýza............................................................................26 2.5.3.2 Levá a pravá rekurze............................................................................................29 2.5.3.3 Překladač jednoduchých aritmetických výrazů.....................................................29 2.5.3.4 Úprava překladového schématu............................................................................30 2.6 Lexikální analýza..........................................................................................................35 2.6.1 Odstranění bílých znaků a komentářů........................................................................35 2.6.2 Konstanty...................................................................................................................35 2.6.3 Rozpoznávání klíčových slov a identifikátorů...........................................................36 2.6.4 Lexikální analyzátor...................................................................................................37 3 Překladač programovacího jazyka CSC......................................................................41 3.1 Definice programovacího jazyka CSC.........................................................................41 3.2 Struktura překladače......................................................................................................46 3.3 Kód generovaný v instrukcích intermediárního kódu...................................................48 4 Lexikální analýza............................................................................................................55 4.1 Generátor lexikální analýzy Lex...................................................................................55 4.2 Zdrojový soubor pro lexikální analyzátor jazyka CSC.................................................58 5 Syntaxí řízený překlad...................................................................................................61 5.1 Generátor syntaktické analýzy Yacc..............................................................................61 5.2 Intermediární kód..........................................................................................................65 5.2.1 Specifikace mezikódu................................................................................. ...............65 5.2.2 Generování mezikódu..................................................... ...........................................65 6 Interpretace intermediárního kódu..............................................................................67 7 Závěr...............................................................................................................................69 Seznam použité literatury.............................................................................................71 Seznam příloh.................................................................................................................71

Strana 12

Strana 13

1

ÚVOD

První elektronické počítače se objevily ve čtyřicátých letech devatenáctého století a byly programovány ve strojovém kódu sekvencí nul a jedniček, které přímo instruovaly počítač, jakou operaci má provést a v jakém pořadí. Operace samy o sobě byly nízkoúrovňové např. přesun dat z jedné lokace na jinou, sečtení obsahu dvou registrů, porovnání dvou hodnot a podobně. Tento způsob programování byl pomalý, obtížný a náchylný na chyby. Programy napsané ve strojovém kódu byly málo srozumitelné a jen těžko modifikovatelné. Krokem vpřed k více uživatelsky přívětivým programovacím jazykům byl vývoj jazyků symbolických adres v padesátých letech, které programování zpříjemňovaly tím, že jednotlivé instrukce ve strojovém kódu byly slovně pojmenovány a kde dále pomocí maker bylo možné vytvořit zkratky pro často opakované části kódu. Hlavním krokem k vyšším programovacím jazykům byl v polovině padesátých let vývoj jazyku Fortran pro věděcké výpočty, Cobolu pro nasazení pro obchodní aplikace a Lispu pro symbolické výpočty. Filozofií těchto jazyků byl zápis programu na vyšší úrovni, zjednodušující programátorům psaní programů pro pro aplikace z oblasti vědy a obchodu. V následujícíh desetiletích byly vyvinuty další jazyky jejichž společným rysem bylo usnadnění programování. V dnešní době existují stovky programovacích jazyků. Vývoj kompilátorů je s výše pospaným vývojem programovacím jazyků a stejně tak i s vývojem architektury počítačů úzce spjat. Posun v těchto oblastech kladl a dále klade na tyto nástroje nové požadavnky. Kompilátor mimo jiné určuje, jak dobře bude program zapsaný v kompilovaném jazyce využívat výpočetního výkonu počítače. Cílem tohoto dokumentu je ilustrovat celý vývojový cyklus překladače, a to na projektu CSC (Compiler of Simplified C), tedy překladače jazyka SC (Simplified C). Tento jazyk byl navržen právě pro účely této práce a je odvozen od jazyka C. Funkční překledač je včetně kompletních zdrojových kódů součásti přílohy této práce. V příloze jsou rovněž demostrační příklady, specifikace navrženého jazyka a mezikódu a dokumentace k programu. Překladač očekává na vstupu program v jazyce SC, přeloží ho do navrženého mezikódu, a ten následně interpretuje. Výstupy programu jsou zobrazeny na standardním výstupu. Teoretická část práce je členěna do sedmi kapitol. První část je úvodem do teorie komplilátorů, v další části je uvedeno řešení překladače CSC. Následující kapitoly popisují nástroje lex a yacc použité při tvorbě překladače. Praktickou část tvoří vlastní překladač programovaný v jazyce ANSI C++.

Strana 14

Strana 15

2 2.1

ZÁKLADY TEORIE KOMPILÁTORŮ Úvod

Programovací jazyk je nástroj pro formulaci výpočetních procesů pro počítače a jejich uživatele. Každý program běžící na počítači musí být napsán v nějakém programovacím jazyce. Před spuštěním musí být každý program převeden do tvaru, ve kterém může být prováděn na počítači. Nástroj pro takový převod se nazývá překladač. [1]

2.2

Druhy překladačů

Kompilátor je program, který převádí program napsaný v jednom jazyce (zdrojový jazyk) na ekvivalentní program v druhém jazyce (cílový jazyk). Program přeložený do spustitelného strojového kódu může být vykonán pro zpracování vstupů a generování výstupů. [1]

Obr.1 Kompilátor.

Obr. 2 Běh cílového programu. Interpretr nepřevádí zdrojový program do spustitelné formy, ale přímo vykonává operace specifikované zdrojovým programem nad vstupy programu.[1]

Obr. 3 Interpretr.

Strana 16

2 Základy teorie kompilátorů

Hybridní překladač kombinuje kompilaci a interpretaci. Zdrojový kód je nejprve kompilátorem přeložen do tzv. byte kódu (mezikódu). Byte kód je pak interpretován virtuálním strojem. Toto je i přístup zvolený pro náš překladač. [1]

Obr. 4 Hybridní přek ladač. Kromě vlastního kompilátoru se procesu vytvoření spustitelného cílového programu mohou účastnit také další programy, respektive jejich použití je v jistých případech přímo nutné. Takovými programy jsou například preprocesor, assembler, linker a zavaděč (loader). Obr. 5 ilustruje činnost systému složeného z těchto programů. Tyto programy nejsou v případě našeho řešení použity, a proto se jejich detailnějším popisem v rámci této práce nebudeme dále zabývat. Připomeňme, že cílem práce je naprogramování překladače, a ne tvorba celého vývojového prostředí.

Obr. 5 Průběh zpracování zdrojového programu.


2.3

Strana 17

Struktura překladače

Proces převodu zdrojového programu na ekvivalentní cílový program lze při bližším pohledu rozdělit na část analytickou a na část syntetickou.[1] Analytická část (front end) rozkládá zdrojový program na elementy jazyka (tokeny) a ukládá je do gramatické struktury (syntaktický strom). Tato stromová struktura je použita ke generování mezikódu, který je vnitřní reprezentací zdrojového programu. Informace o zdrojovém programu (identifikátorech) jsou v této části vkládány do datové struktury nazývané tabulka symbolů. Ta je spolu s mezikódem dále předána syntetické části kompilátoru.[1] Syntetická část (back end) za použití tabulky symbolů generuje z mezikódu cílový program. Proces kompilace sestává s posloupnosti fází, kde každá fáze transformuje zdrojový program z jedné reprezentace do druhé. Obr. 6 ilustruje tuto skutečnost. Několik fází může být seskupeno, případně některé (jako třeba optimalizace) mohou být vynechány.

Obr. 6 Fáze překladu.

Strana 18


Ve fázi lexikální analýzy se čte vstup a znaky se seskupují do lexémů. Syntaktická analýza vytvoří syntaktický strom – reprezentaci, která odráží gramatickou strukturu proudu tokenů. Př: Převod výrazu na tokeny obvod = 2 * PI * polomer <=><2><*><*>

Obr. 7 Přek lad přiřazovacího přík azu.


2.4

Strana 19

Tvorba překladačů jako vědecká disciplína

Nejzákladnějším problémem při konstrukci překladače je složitost. Tento problém může být vyřešen jen použitím abstrakce a uplatněním matematických metod. Pro řešenou úlohu se formuluje vhodný matematický model, který postihuje klíčové charakteristiky dané úlohy. Takto popsaná úloha se pak vyřeší použitím matematických technik. [1][2] Problematika tvorby kompilátorů je spojena zejména s hledáním vhodného matematického modelu a volbou odpovídajícího algoritmu. Mezi základní modely patří konečné automaty, regulární výrazy a bezkontextové gramatiky. [2][7] Konečné automaty a regulární výrazy slouží k popisu lexikálních jednotek programu a k popisu algoritmů používaných k rozpoznávání těchto jednotek v průběhu překladu. Bezkontextové gramatiky slouží k popisu syntaktických konstrukcí programu jako jsou konstrukce pro řízení programu apod. Hlubší studium těchto modelů je nad rámec této práce a dále se zaměříme jen na úvod do technik používaných při tvorbě překladačů v rozsahu dostatečném pro vytvoření funkčního překladače s využitím nástrojů pro generování konstruktorů syntaktické a lexikální analýzy.[1][2]

2.5

Syntaxe

V následující části popíšeme model analytické části kompilátoru a zavedeme základní pojmy. Součástí klasického překladače je část analytická, která ma za úkol rozdělit zdrojový program na základní prvky a vytvořit pro ně vniřní reprezentaci – mezikód [1][7]. Část syntetická přeloží mezikód do cílového programu. Při výstavbě našeho překladače je cílovým jazykem speciální forma mezikódu, která může být použita virtuálním strojem. Syntetická část pak v tomto pohledu nahrazuje fázi generování mezikódu.[1]

Obr. 8 Front end model k ompilátoru. Analytická fáze je řízena syntaxí překládaného jazyka. Syntaxe programovacího jazyka popisuje správnou formu programů v něm napsaných. Sémantika jazyka definuje význam – co se děje při vykonávání programu. Pro popis syntaxe uvedeme notaci, která se jmenuje bezkontextová gramatika (dále jen gramatika), nebo také BNF notace (Backus-Naur Form). V současné době však neexistuje vhodná notace pro jednoduchý popis sémantiky jazyka, místo toho se používá neformální popis doplněný o názorné příklady. [1][7]

Strana 20 2.5.1


Definice gramatiky Bezkontextová gramatika je čtveřice tvořena:

1. Množinou terminálních symbolů (tokenů). Terminály jsou elementární symboly jazyka. 2. Množinou nonterminálních symbolů (taky nazývané jako syntaktické proměnné). Každý nonterminál je tvořen řetězcem terminálů. 3. Množinou přepisovacích pravidel. Každé pravidlo se skládá z hlavy (levé strany), přepisovacího operátoru a z těla (pravé strany). Hlava je nonterminál, tělo je posloupnost terminálů a nonterminálů. 4. Startovním symbolem, což je speciálně označený nonterminál. Gramatika je specifikována výčtem pravidel, přičemž pravidlo pro startovní symbol se uvede jako první. Nonterminály budeme zapisovat kurzívou, ostatní symboly považujeme za terminály. Pravidla se stejnou levou stranou budeme slučovat s použitím symbolu | pro oddělení jednotlivých pravých stran.[7] Označení pravidla

Přepisovací pravidlo výraz 

člen

p1

výraz 

výraz + člen

p2

člen 

faktor

p3

člen 

člen * faktor

p4

faktor 

proměnná

p5

faktor 

(výraz)

p6

proměnná 

a

p7

proměnná 

b

p8

proměnná 

c

p9

Významy symbolů ve výrazech Terminální symboly Nonterminální symboly

+*()abc výraz, člen, faktor, proměnná

Tab. 1 Příklad gramatiky pro výraz, který umožňuje sčitat a násobit. Při tvorbě řetězců podle dané gramatiky postupujeme tak, že vezmeme startovní symbol a opakovaně nahrazujeme nonterminál pravou stranou pravidla tohoto nonterminálu. Tento proces se nazývá derivace. Množina všech terminálních řetězců (vět), která může být derivována ze startovního nonterminálu podle gramatiky, určuje jazyk touto gramatikou definovaný.[1][2]


Strana 21

Jazyk definovaný v tabulce Tab. 1 se skládá z posloupností proměnných oddělených aritmetickými operátory + a *, přičemž každá podposloupnost může být uzavřena do závorek. Například výraz (a + b) * c je součástí tohoto jazyka, protože může být generován ze startovního symbolu derivací uvedenou v tabulce Tab. 2.

Posloupnost derivací

Použité přepisovací pravidlo

výraz

p1

člen

p4

člen * faktor

p3

faktor * faktor

p6

(výraz) * faktor

p2

(výraz + člen) * faktor

p1

(člen + člen) * faktor

p3

(faktor + člen) * faktor

p5

(proměnná + člen) * faktor

p7

(a + člen) * faktor

p3

(a + faktor) * faktor

p5

(a + proměnná) * faktor

p8

(a + b) * proměnná

p9

(a + b) * c

Tab. 2 Příklad derivace výrazu (a+b)*c na základě gramatiky z Tab. 1. Proces nalezení derivace pro daný řetězec nonterminálů (dále jen řetězec) a zjištění, zda taková derivace existuje, se nazývá syntaktická analýza. [1] Pro grafické vyjádření struktury řetězce v dané gramatice používáme derivační strom. Derivační strom podle dané gramatiky je strom s vlastnostmi:[7] 1. 2. 3. 4.

Uzly derivačního stromu jsou ohodnoceny terminálními a neterminálními symboly. Kořen stromu je ohodnocen startovním symbolem. Jestliže má uzel alespoň jednoho následníka, je ohodnocen neterminálním symbolem. Jestliže n1, n2, ...., nk jsou bezprostřední následovníci uzlu n, který je ohodnocen symbolem A, a tyto uzly jsou zleva doprava ohodnoceny symboly A1, A2, ..., Ak, pak A  A1A2...Ak je pravidlo v dané gramatice.

Strana 22


Obr. 9 Derivační strom pro výraz (a+b)*c. Každý uzel stromu je ohodnocen gramatickým symbolem. Vnitřní uzel a spolu se svými potomky odpovídá pravidlu v gramatice a to tak, že vnitřní uzel tvoří jeho levou stranu, potomek pravou. Tak odpovídajícím pravidlem pro kořen tohoto stromu, který je ohodnocen startovním nonterminálem výraz spolu s jeho potomkem, který je ohodnocen symbolem člen je pravidlo výraz  člen (p1)

Koncové uzly derivačního stromu tvoří zleva doprava výsledek derivačního stromu. Na Obr 9. je to řetězec: (a + b) * c.

Příklad : Gramatiku z Tab. 1 upravíme tak, že syntaktické kategorie člen, faktor a proměnná nahradíme jedinou kategorií výraz. Dostáváme následující gramatiku: výraz  výraz + výraz | výraz * výraz | (výraz) |a |b |c


Strana 23

Výrazu a + b * c v této gramatice odpovídají dva různé derivační stromy, které odpovídají dvěma možnostem uzávorkování výrazu (a + b) * c, a + (b * c). Následující derivační stormy zobrazují tuto situaci.

Obr. 10 Derivační strom pro výraz (a+b)*c.

Obr. 11 Derivační strom pro výraz a+(b*c).

Gramatika, ve které pro daný řetězec neterminálních symbolů může existovat více derivačních stromů, se nazývá nejednoznačná. Takový řetězec mívá většinou více významů a je nutné při tvorbě překladače navrhnout gramatiku jednoznačnou nebo nejednodnazčnou gramatiku doplnit dodatečnými pravidly pro řešení víceznačnosti, to jsou zejména informace o asociativitě a prioritě operátorů.[1] Příklad : Příkazy jazyka csc jsou podmnožinou jazyka C příkaz

 if ( výraz ) příkaz | if ( výraz ) příkaz else příkaz | while ( výraz ) příkaz | do příkaz while ( výraz ) | return výrazopt | { příkazy } příkazy  příkazy příkaz | e

2.5.2 Syntaxí řízený překlad Bezkontextová gramatika specifikuje syntaxi jazyka. Kromě toho může být použita k řízení překladu programu. Tato metoda se jemnuje syntaxí řízený překlad (SDT) a uskutečňuje se přiřazením programových fragmentů (akcí) pravidlům gramatiky.[1] Pro SDT zavedeme následující pojmy: Atributy. Atribut je libovolná hodnota asociovaná s terminálními a neterminálními symboly, které používá gramatika pro reprezentaci částí kódu překladáného programu. Například můžeme přiřadit výrazům hodnoty a typy. Překladová schemata. Překladové schema je notace pro přiřazení akcí přepisovacím pravidlům gramatiky. Akce se vykoná při použití pravidla v průběhu syntaktické analýzy. Výsledkem aplikace všech akcí v pořadí určeném syntaktickou analýzou je překlad programu. Definice SDT přiřazuje: 1. Každému gramatickému symbolu množinu atributů. 2. Každému pravidlu množinu sémantických akcí pro výpočet hodnot atributů asociovaných se symboly daného pravidla.

Strana 24


Upravme gramatiku z Tab. 1 pro popis jednoduchých aritmetických výrazů: výraz  člen | výraz + člen | výraz - člen člen  faktor | člen * faktor | člen / faktor faktor  číslo | (výraz)

Pro výraz (1 + 2) * 7 sestrojíme atributovaný derivační (překladový) strom, který bude zobrazovat hodnoty atributů jednotlivých uzlů.

Obr. 12 Atributovaný derivační strom pro výraz (1+2)*7. Hodnotu atributu přiřazeného startovnímu symbolu výraz získáme aplikací sémantických akcí při postorder průchodu derivačním stromem. Atribut se nazývá syntetizovaný, jestliže je jeho hodnota určena pouze jeho vlastní hodnotou a hodnotami atributů potomků uzlu, kterému je přiřazen. Jiným typem je atribut, jehož hodnota závisí na kontextu, ve kterém se příslušný podstrom nachází. Atribut s tímto typem závislosti nazýváme dědičný. Uvedenou gramatiku doplníme o sémantické akce pro získání hodnoty výrazu. Atributy přiřazené neterminálním symbolům představují číselnou hodnotu příslušného symbolu v průběhu syntaktické analýzy.[1]


Strana 25

Přepisovací pravidlo

Sémantické pravidlo

výraz  výraz + člen

výraz.atr = výraz.atr + člen.atr

výraz  výraz – člen

výraz.atr = výraz.atr – člen.atr

výraz  člen

výraz.atr = člen.atr

člen

 člen * faktor

člen.atr = člen.atr * faktor.atr

člen

 člen1 / faktor

člen.atr = člen.atr / faktor.atr

člen

 faktor

člen.atr = faktor.atr

faktor  (výraz)

faktor.atr = výraz.atr

faktor  číslo

faktor.atr = číslo

Tab. 3 Syntaxí řízené překladové schema. Index používáme k odlišení neterminálního symbolu pravé strany pravidla od neterminálního symbolu levé strany, číslo zastupuje terminální symbol. 2.5.3

Syntaktická analýza

Připomeňme, že syntaktická analýza je proces určující, jak může být řetězec terminálních symbolů generován gramatikou. Podle pořadí, v kterém jsou vytvářeny uzly syntaktického stromu v průběhu syntaktické analýzy, rozlišujeme syntaktickou analýzu shora dolů a zdola nahoru. Dále uvedeme metodu syntaktické analýzy shora dolů rekurzivním sestupem.[1][2] Uvažujme gramatiku generující podmnožinu příkazů jazyka C: příkaz  výraz ; | if ( výraz ) příkaz | for (výrazopt ; výrazopt ; výrazopt) příkaz | jiný výrazopt  e | výraz

Zvýrazněny jsou terminální symboly. Pro zjednodušení považujeme symboly výraz a jiný za terminální symboly. Symbol e značí prázdný řetězec. Metodou syntaktické analýzy shora dolů sestrojíme syntaktický strom programového fragmentu: for (e ; výraz ; výraz ) jiný

Syntaktický strom začneme vytvářet od kořene, který označíme startovním neterminálním symbolem příkaz. Opakovaně provádíme následující kroky: 1. Pro uzel N, označený neterminálním symbolem A, vybereme jedno z přepisovacích pravidel pro tento symbol a sestrojíme potomky uzlu N pro symboly levé strany přepisovacího pravidla. 2. Najdeme další uzel, pro který je třeba sestrojit takový podstrom, typicky to bude levý krajní ještě nezpracovaný neterminální symbol. Pro uvedenou gramatiku lze uvedené kroky implementovat během jednoprůchodového prohledávání vstupního řetězce zleva doprava.[1]

Strana 26


Obr. 13 Syntaktický strom programového fragmentu for ( e; výraz; výraz; ) příkaz. 2.5.3.1

Prediktivní syntaktická analýza

Syntaktická analýza rekurzivním sestupem je metoda, která používá množinu rekurzivních funkcí pro zpracování vstupu. Pro každý neterminální symbol gramatiky existuje jedna funkce. Popíšeme jednoduchou formu analýzy rekurzivním sestupem, nazvanou prediktivní syntaktická analýza.[1][7] Ta je založena na předpokladu, že vstupní terminální symbol jednoznačně určuje správný výběr funkce pro zpracování daného neterminálního symbolu. Posloupnost volání funkcí v průběhu analýzy vstupního řetězce implicitně určuje derivační strom zpracovávaného řetězce a může být použita pro konstrukci explicitního derivačního stromu.[1] Prediktivní syntaktický analyzátor pro gramatiku z následujícího příkladu se skládá z funkcí pro neterminály příkaz a výrazopt, a pomocné funkce zpracuj. Globální proměnná aktualni obsahuje aktuálně zpracovávaný vstupní terminální symbol. Funkce zpracuj porovnává svůj argument s obsahem proměnné aktualni a mění její hodnotu na další terminální symbol pokud hodnoty souhlasí. Analýza se spustí voláním funkce pro startovní neterminální symbol příkaz. Pro vstupní řetězec z příkladu bude proměnná aktualni na počátku obsahovat terminální symbol for. Funkce prikaz provádí kód odpovídající pravidlu: příkaz  for ( výrazopt ; výrazopt ; výrazopt ) příkaz

Kód pro zpracování tohoto pravidla porovnává každý terminální symbol s aktuálně zpracovávaným symbolem prostřednictvím volání funkce zpracuj. Pro každý neterminální symbol se volá odpovídající funkce v následujícím pořadí zpracuj(for); zpracuj('('); vyraz_opt(); zpracuj(';'); vyraz_opt(); zpracuj(';'); vyraz_opt(); zpracuj(')'); prikaz();

Analyzátor je uveden ve výpisu 1. Jednotlivé kroky v průběhu prediktivní analýzy lze pro uvedenou gramatiku provádět jen na základě informace o dalším terminálním symbolu vstupního řetězce. Toto není vždy možné. Příklad: Uvažujme gramatiku S  xA | xB A y|z B u|w

Tato gramatika generuje množinu obahující slova xy, xz, xu, xw. Pro první vstupní symbol nedokážeme rozhodnout, jestli se má vykonat posloupnost volání funkcí odpovídající levé straně pravidla obsahující neterminální symbol A nebo symbol B.


Strana 27

Formálně, jestliže je dáno přepisovací pravidlo A  ζ1 | ζ2 | … | ζn

kde a je posloupnost gramatických symbolů (terminálních i netreminálních), tak množiny počátečních symbolů všech vět, které je možné generovat ze symbolu ai musí být disjunktní, tj. FIRST(ζi) c FIRST(ζj) = 0

pro všechny i = j

Množina FIRST(ζ) je množina všech terminálních symbolů, které se můžou objevit jako první symbol vět odvozených ze symbolu ζ. Množinu FIRST(ζ) spočteme podle těchto pravidel:

1. Jestliže je prvním symbolem argumentu terminální symbol, pak FIRST(aζ) = {a}

2. První symbol je neterminální symbol s přepisovacím pravidlem A  α1 | α2 | … | αn

Pak FIRST(Aζ) = FIRST(α1) u FIRST(α2) u … u FIRST(αn)

Pro pravidlo S  xA | xB

je FIRST(xA) = {x}, FIRST(xB) = {x}, tím je porušeno tvrzení a pro uvedenou gramatiku nelze sestrojit prediktivní syntaktický analyzátor.[2] Pro gramatiku z příkladu jsou množiny FIRST(příkaz) = {výraz, if, for, jiný} FIRST(výrazopt) = {výraz}

v tomto případě není nutno množiny FIRST uvažovat, protože nemáme žádné dvě pravidla ve tvaru A  α a A  β. void prikaz() { switch (aktualni) { case výraz: zpracuj(výraz) ; zpracuj(';'); break; case if: zpracuj(if); zpracuj('('); zpracuj(výraz); zpracuj(')'); prikaz(); break; case for: zpracuj(for); zpracuj('('); vyraz_opt(); zpracuj(';'); vyraz_opt(); zpracuj(';'); vyraz_opt(); zpracuj(';'); zpracuj(')'); prikaz(); break; case jiný: zpracuj(jiný); break; default: error(“syntax error“);

Strana 28

2 Základy teorie kompilátorů } } void vyraz_opt() { if (aktualni == výraz) zpracuj(výraz); } void zpracuj(terminal t) { if (aktualni == t) aktualni = getNextTerminal(); else error(“syntax error“);

} Výpis 1 Pseudokód pro prediktivní analyzátor. Analyzátor používá implicitně e-pravidlo v případě, že nelze použít žádné jiné pravidlo. Pro vstupní řetězec for (e ; výraz ; výraz ) jiný

bude po zpracování terminálních symbolů for a ( proměnná aktualni obsahovat symbol ;. Následně se zavolá funkce vyraz_opt() a bude vykonán kód

if (aktualni == výraz) zpracuj(výraz); Neterminální symbol výrazopt má pravidla výrazopt  e | výraz Proměnná aktualni obsahuje symbol ';', podmínka if (aktualni == výraz) není splněna, proměnná aktualni zůstane nezměněna a funkce vyraz_opt() v tomto případě nedělá nic, což odpovídá použití e-pravidla. Nyní můžeme zobecnit návrh prediktivního syntaktického analyzátoru pro každou gramatiku, která má disjunktní množiny FIRST pro levou stranu pravidel příslušející kterémukoliv neterminálnímu symbolu. Jestliže dále máme příslušnou gramatiku doplněnou o akce (překladové schema), pak tyto akce mohou být vykonány v rámci funkcí navrhovaného analyzátoru. Prediktivní syntaktický analyzátor je program, který se skládá z funkcí odpovídajících každému neterminálnímu symbolu. Funkce odpovídající neterminálnímu symbolu A vykonává: 1. Na základě aktuálně zpracovávaného terminálního symbolu rozhoduje o tom, které pravidlo se použije. Pravidlo A  α, kde α není prázdný řetězec, se použije, jestliže aktuální symbol náleží do množiny FIRST(α). Jestliže existuje e-pravidlo, tak bude použito v případě, kdy aktuální symbol nebude náležet do žádné množiny FIRST levých stran neterninálního symbolu A. 2. Funkce odráží strukturu levé strany vybraného pravidla. Postupně jsou volány funkce odpovídající jednotlivým symbolům těla pravidla v pořadí jak jsou uvedeny. Pro neterminální symbol se zavolá odpovídající funkce. Terminální symbol se porovná s aktuálně zpracovávaným symbolem, který je obsažen v globální proměnné. V případě shody bude načten další vstupní terminální symbol, jinak funkce ohlásí syntaktickou chybu.

2 Základy teorie kompilátorů 2.5.3.2

Strana 29

Levá a pravá rekurze Uvažujme pravidlo s levou rekurzí výraz  výraz + člen

kde levý krajní symbol těla pravidla je shodný s neterminálním symbolem pravé strany. Dále mějme funkci vyraz() odpovídající neterminálnímu symbolu výraz prediktivního analyzátoru. Pak v průběhu syntaktické analýzy dojde k jejímu rekurzivnímu volání při zpracování symbolu výraz. Protože v průběhu jejího volání nedojde ke změně aktuálně zpracovávaného symbolu, nebude tato rekurze nikdy ukončena. Levou rekurzi lze odstranit přepisem daného pravidla s použitím pravé rekurze. [2] Uvažujme neterminální symbol A s pravidly A  Aα | β

kde α a β jsou posloupnosti terminálních a neterminálních symbolů, které nezačínají neterminálním symbolem A. Pravidlo A  Aα je pravidlo s levou rekurzí, protože má symbol A také jako první symbol na levé straně pravidla. Toto pravidlo generuje posloupnost α řetězců umístěných vpravo od symbolu A. Proces odvozování je ukončen při použití pravidla A  β. Stejného efektu dosáhneme zavedením dalšího neterminálního symbolu R a přepisem pravidel pro A A  βR R  αR | e

Pravidlo R  αR | e používá pravou rekurzi, protože má neterminální symbol R na své levé straně a zároveň jako poslední symbol pravé strany.[2] Derivační stromy pro pravidla s levou a pravou rekurzí jsou uvedena na obr.

Obr. 14 Generování řetězce použitím levé a pravé rekurze. 2.5.3.3

Překladač jednoduchých aritmetických výrazů

Popsané techniky nyní použijeme pro konstrukci jednoduchého syntaxí řízeného překladače aritmetických výrazů do kódu pro hypotetický zásobníkový počítač ve formě funkčního programu v C++. Pro jednoduchost budeme uvažovat výrazy skládající se z číslic a operátorů pro sčítání, odčítání, násobení a dělení. Pro výraz 7 – 5 + 2 * 3 překladač vygeneruje kód push 7 push 5 sub push 2 push 3 mul add

Strana 30


Toto je gramatika jazyka přijímaného překladačem doplněná o sémantické akce: vyraz  vyraz + clen | vyraz – clen | clen

{ print(“add“) } { print(“sub“) }

clen  clen / primarni_vyraz | clen * primarni_vyraz | primarni_vyraz primarni_vyraz

0 | 1

{ print(“div“) } { print(“mul“) }

{ print(“push 0“) } { print(“push 1“) } …

| 9

{ print(“push 9“) }

Jinými slovy, výraz obsahuje jeden nebo více členů oddělených znaménky + a -. Každý člen může obsahovat jednu nebo více číslic oddělených znaménky * a /. Výchozí gramatika obsahuje pravidla s levou rekurzí a musí být upravena, protože prediktivní syntaktický analyzátor nedokáže taková pravidla zpracovat. Dříve než ukážeme úpravu překladového schématu pro odstranění levé rekurze, zavedeme strukturu, která se nazývá syntaktický strom. [1][7] Syntaktický strom je abstrakcí derivačního stromu. Jeho koncovými uzly jsou operandy, vnitřními uzly pak operátory. Vnitřní uzly derivačního stromu tvoří neterminální symboly, které můžou představovat operátory nebo programové konstrukce, často jde však o pomocné syntaktické kategorie jako jsou např. clen nebo primarni_vyraz. Při konstrukci syntaktického stromu nejsou tyto pomocné symboly potřebné, a jsou proto vypuštěny. Na Obr. 15. je znázorněn syntaktický strom výrazu 7 – 5 * 3. 2.5.3.4

Úprava překladového schématu

Uvedenou techniku pro odstranění pravidel s levou rekurzí z gramatiky můžeme rozšířit na úpravu pravidel doplněných o překladové akce. Nejprve upravíme přepisovací pravidla pro symboly vyraz a clen. V uvedené gramatice pro ně existují pravidla s levou rekurzí ve formě A  B 

Aα | Aβ | B Bδ | Bζ | η

zavedeme další neterminální symboly R, S a pravidla přepíšeme s použitím pravé rekurze A R B S

 BR  αR | βR | e  ηS  δS | ζS | e

Sémantické akce transformujeme stejně jako by šlo o terminální symboly. Nechť A α β B δ ζ η

= = = = = = =

vyraz + člen – člen clen * primarni_vyraz / primarni_vyraz primarni_vyraz

{ print(“add“) } { print(“sub“) } { print(“mul“) } { print(“div“) }


Strana 31

pak je výsledkem transformace překladové schéma vyraz

 clen R

R

 + člen | - clen | e

clen

{ print(“add“) } R { print(“sub“) } R

 primarni_vyraz S

S  * primarni_vyraz | / primarni_vyraz | e primarni_vyraz  0 | 1 ... | 9

{ print(“mul“) } S { print(“div“) } S { print(“push 0“) } { print(“push 1“) } { print(“push 9“) }

Na Obr. 15 je znázorněn překlad výrazu 7 – 5 * 3 s použitím uvedeného schématu.

Obr. 15 Překlad výrazu 7-5*3. Výpis 2 uvádí funkce pro jednotlivé neterminální symboly. Funkce vyraz() implementuje pravidlo vyraz  clen R voláním clen() následovaným R(). Funkce R() implementuje tři pravidla neterminálního symbolu R. Používá první pravidlo, jestliže aktualni symbol je znaménko plus, druhé pravidlo pro znaménko mínus a pravidlo R  e ve všech ostatních případech. Aktualni symbol + je zpracován v první if větvi voláním zpracuj('+'). Po zavolání clen() následuje implementace sémantické akce generováním instrukce add. Pravidla pro zpracování ostatních operátorů jsou implementována analogicky. Pravidlo R  e, respektive S  e, je zpracováno v prázdné else větvi. Pravidla pro primarni_vyraz generují uložení deseti číslic na zásobník. Všimněme si, že funkce zpracuj(aktualni) mění obsah proměnné aktualni, a je proto nutné použít dočasnou proměnnou t pro její uložení k pozdějšímu tisku.

Strana 32


void vyraz() { clen(); R(); } void R() { if (aktualni == '+') { zpracuj('+'); clen(); print(“add“); R(); } else if (aktualni == '-') { zpracuj('-'); clen(); print(“sub“); R(); } else { } /* ponechej vstup beze změn */ } void clen() { primarni_vyraz(); S(); } void S() { if (aktualni == '*') { zpracuj('*'); primarni_vyraz(); print(“mul“); S(); } else if (aktualni == '/') { zpracuj('/'); primarni_vyraz(); print(“div“); S(); } else { } /* ponechej vstup beze změn */ } void primarni_vyraz() { if (aktualni je cislice) { pom = aktualni; zpracuj(aktualni); print(“push t“); } else report(“syntax error“); }

Výpis 2 Pseudokód pro neterminální symboly. Uvedený kód dále zjednodušíme. Poslední příkaz v prvních dvou větvích funkce R() je rekurzivní volání této funkce. Analogicky to platí pro volání S(). Takové volání se nazývá koncově rekurzivní. Pro funkci bez parametrů může být jednoduše nahrazeno skokem na začátek těla funkce. Výpis 3 uvádí přepis pro R(). Dokud je aktualní symbol znaménko plus nebo mínus, funkce zpracovává znaménko, volá clen() pro zpracování svého operandu, generuje instrukci add a pokračuje v tomto procesu. V opačném případě se řízení vrací volající funkci. Po odstranění koncové rekurze ve funkcích R() a S() zůstane volání těchto funkcí jedině jednou v tělech vyraz() a clen(). Toto volání můžeme proto nahradit přímo těly R() a S().

2 Základy teorie kompilátorů void R() { while (true) { if (aktualni == '+') { zpracuj('+'); clen(); print(“add“); continue; } else if (aktualni == '-') { zpracuj('-'); clen(); print(“sub“); continue; } break; } }

Výpis 3 Odstranění koncové rekurze ve funkci R().

Kompletní program #include class Error { public: Error(const char* report) { cerr << report << endl; } }; class Parser { char aktualni; void zpracuj(char c) { if (aktualni == c) do cin.get(aktualni); while (isspace(aktualni)); else throw new Error("syntax error"); } void primarni_vyraz() { if (isdigit(aktualni)) { cout << "\tpush " << aktualni << endl; zpracuj(aktualni); } else throw new Error("syntax error"); } void clen() { primarni_vyraz(); while (true) if (aktualni == '*') { zpracuj('*'); primarni_vyraz(); cout << "\tmul" << endl; } else if (aktualni == '/') { zpracuj('/'); primarni_vyraz(); cout << "\tdiv" << endl;

Strana 33

Strana 34

2 Základy teorie kompilátorů } else return; }

public: Parser() { do cin.get(aktualni); while (isspace(aktualni)); } void vyraz() { clen(); while (true) if (aktualni == '+') { zpracuj('+'); clen(); cout << "\tadd" << endl; } else if (aktualni == '-') { zpracuj('-'); clen(); cout << "\tsub" << endl; } else return; } }; int main(void) { Parser *p = new Parser(); p->vyraz(); cout << endl; return 0; }

Výpis 4 Odstranění koncové rekurze ve funkci R() - kompletní program.


2.6

Strana 35

Lexikální analyza

Lexikální analyzátor načítá znaky ze vstupu a seskupuje je do tokenů. Token je objekt, který reprezentuje terminální symbol doplněný o hodnotu. Posloupnost vstupních znaků tvořících jeden token označujeme jako lexém. [1] V této části sestavíme lexikální analyzátor, který nám umožní doplnit čísla, identifikátory a bílé znaky (mezery, tabelátory a znaky pro nové řádky) do gramatiky uvedené v předchozí části. Rozšířené překladové schéma bude pak vypadat takto: vyraz

clen

primarni_vyraz

 vyraz + clen | vyraz – clen | clen

{ print(“add“) } { print(“sub“) }

 clen / primarni_vyraz | clen * primarni_vyraz | primarni_vyraz

{ print(“div“) } { print(“mul“) }

 cislo | jmeno | jmeno = vyraz | - primarni_vyraz | (vyraz)

{ print(“push cislo.hodnota“) } { print(“push jmeno.lexem“) } { print(“pop jmeno.lexem“) } { print(“uminus“) }

Předpokládáme, že terminální symbol cislo má atribut cislo.hodnota, kterému odpovídá celočíselná hodnota symbolu. Terminální symbol jmeno má atribut jmeno.lexem, což je řetězec znaků tvořících jméno.[1] Postup uvedený v této části je vhodný pro návrh ručně psaných lexikálních analyzátorů. V části 4 je popis nástroje Lex, který generuje lexikální analyzátor ze zadané specifikace. 2.6.1

Odstranění bílých znaků a komentářů

Většina jazyků umožňuje ve zdrojovém souboru mezi jednotlivými tokeny použití libovolného množství bílých znaků. Stejně tak jsou v průběhu syntaktické analýzy ignorovány komentáře. Výpis 5 uvádí pseudokód, který přeskakuje prázdné znaky, tabulátory a nové řádky. Proměnná aktualni obsahuje další vstupní znak, proměnná radek počítá znaky pro nové řádky. for ( ; ; aktualni = dalsi vstupni znak) { if (aktualni je mezera nebo tabelator) ; else if (aktualni je novy radek) radek = radek + 1; else break; }

Výpis 5 Odstranění bílých znaků. 2.6.2

Konstanty

Použití celočíselných konstant umožníme zavedením terminálního symbolu, například cislo, pro takovou konstantu nebo začleněním syntaxe pro celočíselné konstanty do gramatiky. Úkolem lexikálního analyzátoru je shromáždění znaků pro celá čísla a výpočet celkové číselné hodnoty. Syntaktický analyzátor pak pracuje s čísly jako s jednotlivými objekty. [1] Když se na vstupu objeví posloupnost číslic, lexikální analyzátor předá syntaktickému analyzátoru token, který se skládá z terminálního symbolu cislo a celočíselné hodnoty vypočtené z těchto číslic. Vstup 45 + 20 + 57 poskytne následující posloupnost tokenů: <+> <+>

Strana 36


Pseudokód z výpisu 6 načítá číslice ze vstupu do celého čísla a počítá jeho celočíselnou hodnotu do proměnné hod. if (aktualni obsahuje cislici) { hod = 0; do { hod = hod * 10 + celociselna hodnota cislice aktualni; aktualni = dalsi vstupni znak; } while ( aktualni obsahuje cislici); return token; }

Výpis 6 Algoritmus převodu číslic ze vstupu na celé číslo. 2.6.3

Rozpoznávání klíčových slov a identifikátorů

Jazyk používá řetězce znaků pro označování programových konstrukcí. Takové řetězce nazýváme jako klíčová slova. [1] Dalším použitím znakových řetězců je pojmenování proměnných, funkcí, objektů, apod. Takové řetězce označujeme jako identifikátory. Pro zjednodušení syntaktické analýzy jsou identifikátory specifikovány v gramatice jako terminální symboly. Syntaktický analyzátor pak očekává stejný terminál, např. id, při výskytu libovolného identifikátoru na vstupu. Token pro identifikátor má atribut, který obsahuje jméno identifikátoru. [1] Například vstup pocet = pocet + prirustek;

bude analyzátorem zpracován jako id = id + id. Odpovídajíci posloupnost token objektů je <=> <+> <;>

Klíčová slova všeobecně splňují pravidla pro vytváření identifikátorů, proto je nutné mít mechanismus pro rozhodnutí, zda lexém tvoří klíčové slovo nebo identifikátor. Jedna možnost je vyhradit klíčová slova jako rezervovaná, pak je nelze použít jako identifikátory. Znakový řetězec tvoří identifikátor jedině, když se nejedná o klíčové slovo. Navrhovaný lexikální analyzátor používá pro ukládání znakových řetězců tabulku. Před prvním použitím se tabulka inicializuje vložením klíčových slov. Jestliže lexikální analyzátor načte řetězec, který může tvořit identifikátor, nejprve hledá tento řetězec v tabulce. Pokud je nalezen, analyzátor vrací příslušný token z tabulky, jinak vrací token s terminálním symbolem id. Standartní knihovna jazyka C++ obsahuje asociativní kontejner mapa, který můžeme použít pro ukládání prvků s páry klíč/hodnota. Ve třídě Lex analyzátoru je deklarace položky tab, map<string, class Slovo*> tab; která asociuje lexém s příslušným token objektem. Pseudokód pro vyhledávání klíčových slov a vkládání identifikátorů uvádí výpis 7.


Strana 37

if (aktualni obsahuje pismeno) { shromazdi pismena nebo cislice do bufferu b; s = retezec tvoreny znaky z b; w = token vraceny funkci tab.get(s); if (w není null) return w; else { vloz par klic/hodnota (s, ) do tab; return token ; } }

Výpis 7 Rozlišování klíčových slov a identifikátorů. Řetězec s je tvořen písmeny a číslicemi, první znak musí být písmeno. Jestliže tabulka obsahuje položku pro s, pak se vrací token objekt získaný funkcí tab.get(s). Zde s může být klíčové slovo, které bylo do tabulky vloženo při inicializaci, nebo identifikátor získaný v průběhu lexikální analýzy. V opačném případě se do tabulky vloží token id s atributem s. 2.6.4

Lexikální analyzátor

Doposud uvedené fragmenty pseudokódu použijeme pro návrh funkce ctiToken, která vrací token objekt: Token ctiToken() { přeskoč bílé znaky; zpracuj čísla; zpracuj klíčová slova a identifikátory; Token t = new Token(aktualni); aktualni = prázdný znak; return t; }

Následující výpis uvádí kompletní implementaci lexikálního analyzátoru. #include <string.h> #include <map.h> #include #include <stdlib.h> #include #define MAXLENGTH 10 string s; enum Tag { NUM = 256, ID, TRUE, FALSE }; class Token { int tag; public : Token(int _tag) : tag(_tag) { }

Strana 38


}; class Cislo : public Token { int hod; public: Cislo(int _hod) : Token(NUM), hod( _hod) { } }; class Slovo : public Token { string lexem; public: Slovo(int i, string s) : Token(i), lexem(s) { } bool operator==(const Slovo &s) { return (lexem == s.lexem); } bool operator==(string s) { return (lexem == s); } }; class Lex { int radek; char akt; map<string, class Slovo*> tab; public: Lex() { radek = 1; tab["true"] = new Slovo(TRUE, "true"); tab["false"] = new Slovo(FALSE, "false"); } Token* ctiToken() { cin.get(akt); for ( ; ; cin.get(akt)) if (akt == ' ' || akt == '\t') continue; else if (akt == '\n') radek++; else break; if (isdigit(akt)) { int c = 0; do { c = 10 * c + akt - '0'; cin.get(akt); } while (isdigit(akt)); return new Cislo(c); } if (isalpha(akt)) { char buffer[MAXLENGTH]; int i = 0; do { buffer[i] = akt; cin.get(akt); i++;


Strana 39

} while (isalnum(akt)); buffer[i] = '\0'; map<string, class Slovo*>::iterator poz; for (poz = tab.begin(); poz != tab.end(); poz++) if (poz->first == buffer) return poz->second; Slovo *s = new Slovo(ID, buffer); tab[buffer] = s; return s; } Token t = new Token(akt); akt = ' '; return t; } };

Výpis 8 Kód pro lexikální analyzátor. Třída Token představuje základovou třídu pro třídy Cislo a Slovo. Obsahuje položku tag, která slouží k identifikaci terminálních symbolů. Pro jednoznakové symboly bude tato položka obsahovat přímo jejich celočíselnou reprezentaci, pro terminální symboly jmeno a cislo, bude naplněna hodnotou výčtového typu Tag. Hodnoty TRUE a FALSE jsou definovány pro ilustraci zpracování klíčových slov. Třída Cislo rozšiřuje Token o položku hod, která reprezentuje celočíselnou hodnotu terminálního symbolu cislo. Třída Slovo je určena pro klíčová slova a identifikátory. Rozšiřuje Token o položku lexem, která se inicializuje v konstruktoru řetězcovou reprezentací příslušného terminálního symbolu. Konstruktor třídy Slovo očekává dále celočíselný argument pro rozlišení klíčových slov a identifikátorů. Vlastní lexikální analyzátor definuje třída Lex. Členská položka radek počítá vstupní řádky, položka aktualni obsahuje další zpracovávaný znak. Konstruktor Lex inicializuje tabulku vložením klíčových slov “true“ a “false“. Členská funkce ctiToken() získá ze vstupu další token. Příkaz cin.get(akt) načítá do proměnné akt jeden znak ze standartního vstupního proudu. Cyklus for ( ; ; cin.get(akt)) přeskočí bílé znaky. Blok pro zpracování čísel je uveden testem if (isdigit(akt)). Funkce isdigit() z hlavičkového souboru zjišťuje číslice, vrací nenulovou hodnotu právě, když akt je číslice. Vypočtená celočíselná hodnota je předána do konstruktoru třídy Cislo a analyzátor vrací nový Token objekt. Řádek if (isalpha(akt)) uvozuje blok pro zpracování identifikátorů a klíčových slov. Funkce isalpha() a isalnum() jsou další funkce pro testování znaků z . Funkce isalpha() zjišťuje písmena, isalnum() písmena a číslice desítkové soustavy. Proměnná buffer bude obsahovat výslednou řetězcovou reprezentaci. Test na přítomno získaného jména v tabulce realizuje následující cyklus. Řádek for (poz = tab.begin(); poz != tab.end(); poz++) je standartním zápisem pro procházení kontejneru. Pokud je jméno nalezeno, vrací se příslušný token objekt. Jinak je vrácen, a do tabulky vložen nový token reprezentující identifikátor. Nakonec, příkaz Token t = new Token(akt) vytvaří nový token objekt, který reprezentuje jednoznakový terminální symbol.

Strana 40

Strana 41

3 3.1

PŘEKLADAČ PROGRAMOVACÍHO JAZYKA SC Definice programovacího jazyka SC

Po seznámení se základními teoretickými poznatky bude popsán překladač jednoduchého programovacího jazyka. Překladače jsou programy velmi složité a také značně rozsáhlé. Z hlediska rozsahu této práce je nutné, aby jeho rozsáhlost nepřestoupila rozumnou mez a zároveň, aby byly v překladači postiženy všechny významné rysy vyskytující se v moderních programovacích jazycích. Rozsah i komplexnost překladače je určována hlavně typem programovacího jazyka, který je překládán a dále typem počítače, pro který je vytvářen cílový program. Pokud jde o cílový počítač, bývá obvyklou cestou volba neexistujícího abstraktního počítače. Námi konstruovaný překladač je kombinací klasického kompilátoru a interpretru – hybridní překladač. Skládá se z překladače, který generuje mezikód pro virtuální zásobníkový počítač a interpretru, který umí instrukce vygenerovaného mezikódu vykonávat. Překládaným jazykem je programovací jazyk SC (Simplified C), který byl vytvořen pro potřeby této práce. Jazyk SC je odvozen z jazyka C. Jeho řídící struktury jsou vzhledem k jazyku C poměrně kompletní. Jazyk obsahuje příkaz pro vyhodnocení výrazu, složený příkaz, příkazy cyklu while, for a do – while, úplný podmíněný příkaz a prázdný příkaz. Vzhledem k požadavku jednoduchosti je podporován jediný datový typ integer. Pro možné budoucí rozšíření obsahuje jazyk ještě typy bool a string. Nad typem integer lza provádět obvyklé operace a relace. Gramatiku jazyka ve formátu přijímaném generátorem syntaktického analyzátoru yacc uvádí Výpis 9. Terminální symboly jsou uvedeny velkými písmeny, neterminální malými. program : fun_def_or_var_decl program | /* e */ fun_def_or_var_decl : fun_def | var_decl var_decl : type_spec id_list T_SEMIC id_list : T_IDENTIFIER T_COMMA id_list | T_IDENTIFIER fun_def : type_spec T_IDENTIFIER T_BOPEN param_list_or_void T_BCLOSE T_BEGIN stats_or_var_decls T_END param_list_or_void : T_VOID | param_list param_list : param T_COMMA param_list | param

Strana 42

3 Překladač programovacího jazyka SC

param : type_spec T_IDENTIFIER type_spec : T_INT | T_STRING | T_BOOL | T_VOID stats_or_var_decls : stat_or_var_decl stats_or_var_decls | /* e */ stat_or_var_decl : stat | var_decl stat : T_SEMIC | expr T_SEMIC | T_IF T_BOPEN expr T_BCLOSE stat_or_var_decl else_branch | T_FOR T_BOPEN expr_or_not T_SEMIC expr_or_not T_SEMIC expr_or_not T_BCLOSE stat_or_var_decl | T_WHILE T_BOPEN expr T_BCLOSE stat_or_var_decl | T_DO stat_or_var_decl T_WHILE T_BOPEN expr T_BCLOSE T_SEMIC | T_RETURN expr_or_not T_SEMIC | T_BEGIN stats_or_var_decls T_END | T_PUT expr T_SEMIC expr_or_not: expr | /* e */ else_branch : T_ELSE stat_or_var_decl | /* e */ expr: expr_comma expr_comma : expr_assign | expr_comma T_COMMA expr_assign expr_assign : expr_cond | expr_cond T_ASSIGN expr_assign


expr_cond : expr_lor | expr_lor T_QUEST expr T_COLON expr_cond expr_lor : expr_land | expr_lor T_LOR expr_land expr_land : expr_bor | expr_land T_LAND expr_bor expr_bor : expr_band | expr_bor T_BOR expr_band expr_band : expr_eq | expr_band T_BAND expr_eq expr_eq : expr_rel | expr_eq T_EQ expr_rel | expr_eq T_NEQ expr_rel expr_rel : expr_shift | expr_rel T_GT expr_shift | expr_rel T_LT expr_shift | expr_rel T_GEQ expr_shift | expr_rel T_LEQ expr_shift expr_shift : expr_add | expr_shift T_SHL expr_add | expr_shift T_SHR expr_add expr_add : expr_mul | expr_add T_ADD expr_mul | expr_add T_SUB expr_mul expr_mul : expr_un | expr_mul T_MUL expr_un | expr_mul T_DIV expr_un | expr_mul T_MOD expr_un

Strana 43

Strana 44


expr_un : expr_term | T_SUB expr_un | T_ADD expr_un | T_LNOT expr_un | T_BNEG expr_un /* | T_INC expr_un | T_DEC expr_un */ | T_SIZEOF expr_un | T_SIZEOF T_BOPEN type_spec T_BCLOSE expr_term : T_IVAL | T_SVAL | T_IDENTIFIER | T_BOPEN expr T_BCLOSE /* | expr_term T_INC | expr_term T_DEC */ | T_IDENTIFIER T_BOPEN arg_list_or_no T_BCLOSE | expr_term T_IOPEN expr T_ICLOSE | T_GET arg_list_or_no : arg_list | /* e */ arg_list : expr_assign T_COMMA arg_list | expr_assign

Výpis 9 Gramatika jazyka SC. Program se skládá z jednoho souboru, který obsahuje posloupnost deklarací globálních proměnných a definic funkcí. Právě jedna z funkcí musí být pojmenována main. Voláním kódu pro tuto funkci je zahájeno vykonávání programu. Funkční prototypy nejsou podporovány. Funkce může vracet hodnotu. Pokud funkce nemá žádné parametry, musí být explicitně použito klíčové slovo void. Funkce se může volat rekurzivně.


Strana 45

Proměnná musí být před svým použitím deklarována. Deklarace spojená s inicializací není povolena. Pravidla pro viditelnost proměnných jsou stejná jako v jazyce C. Jazyk obsahuje následující operátory: Operátor

Význam

Použití

()

volání funkce

jméno_funkce ( seznam_výrazů)

()

vytvoření hodnoty

( seznam_výrazů )

get

získání znaku

get

sizeof

velikost objektu

sizeof výraz

sizeof

velikost typu

sizeof ( typ )

~

komplement

~ výraz

!

negace

! výraz

-

unární minus

- výraz

+

unární plus

+ výraz

*

násobení

výraz * výraz

/

dělení

výraz / výraz

%

modulo

výraz % výraz

+

sčítání

výraz + výraz

-

odčítání

výraz - výraz

<<

posun vlevo

výraz << výraz

>>

posun vpravo

výraz >> výraz

<

menší než

výraz < výraz

<=

menší nebo rovno

výraz <= výraz

>

větší než

výraz > výraz

>=

větší nebo rovno

výraz >= výraz

==

rovno

výraz == výraz

!=

nerovno

výraz != výraz

&

bitové AND

výraz & výraz

|

bitové OR

výraz | výraz

&&

logické AND

výraz && výraz

||

logické OR

výraz || výraz

?:

podmíněný výraz

výraz ? výraz : výraz

=

přiřazení

adresový_výraz = výraz

,

řazení

čárka(řazení)

Tab. 4 Operátory jazyka SC.

Strana 46


Použití jednotlivých operátorů je stejné jako v jazyce C. Výraz je posloupnost operátorů a operandů, které specifikují hodnotu. Výraz může poskytnout výslednou hodnotu a může vyvolat vedlejší účinky. Operátor get slouží k získání dalšího znaku ze standartního vstupu. Výpis 10 uvádí přehled a syntaxi příkazů. příkaz: { seznam_příkazůopt } výrazopt ; if ( výraz ) příkaz if ( výraz ) příkaz else příkaz while ( výraz ) příkaz do příkaz while ( výraz ) for ( výrazopt ; výrazopt ; výrazopt ) příkaz return výrazopt ; put výraz ; seznam_příkazů: příkaz seznam_příkazůopt

Výpis 10 Syntaxe příkazů jazyka SC. Neexistuje žádný zvláštní přiřazovací příkaz nebo příkaz pro volání procedury; s přiřazením i voláním funkce se zachází stejně jako s výrazem. Příkaz put společně s operátorem get realizují jednoznakové vstupně/výstupní operace.

3.2

Struktura překladače

Struktura vyvíjeného překladače je uvedena na Obr. 16. Zdrojový kód v jazyce CSC bude překládat do mezikódu, vlastní překladač bude napsán v jazyce C++.

Obr. 16 Struktura překladače CSC. Jeho vnitřní struktura, uvedená na Obr. 17, je typickou strukturou hybridního kompilátoru.


Obr. 17 Struk tura hybridního k ompilátoru. Program realizující kompilátor v jazyce C++ má tento tvar: # include "csc.h" Program* program = 0; int csc_main (void) { extern int yyparse (void); int i; i = yyparse(); if (i) return 1; program->dump(); IntermediateCodeModule *module = program->compile(); module->dump(); ICOStream out("out.intc"); out << *module; delete module; delete program; ICIStream istr("out.intc"); IntermediateCodeModule module (istr); module.dump(); RuntimeEnvironment rte; module.searchMain()->execute(rte, 0, module);

Strana 47

Strana 48


return 0; }

Výpis 11 Program realizující kompilátor CSC. Directiva # include "csc.h" vkládá deklarace pro všechny třídy používáné překladačem. Tak třída Program je definovaná v stree.h a slouží k uložení syntaktického stromu po skončení syntaktické analýzy. Funkce yyparse() z y_tab.cpp vygeneruje syntaktický strom a uloží ho do proměnné program. Příkaz program->dump() vypisuje program v postfixové notaci. Vlastní proces překladu realizuje metoda compile() třídy Program. Výsledkem překladu je nový modul mezikódu, obsažený v objektu třídy IntermediateCodeModule, který obsahuje kód generovaný v instrukcích virtuálního zásobníkového počítače. Řádek module->dump() vypisuje obsah modulu pro diagnostické účely. Konstruktor ICOStream out("out.intc") vytváří nový objekt pro uložení modulu mezikódu na disk do souboru s názvem out.intc. Sekvence příkazů uvozená deklarací ICIStream istr("out.intc") vytváří nový objekt typu ICIStream, který slouží k načtení mezikódu z externího souboru a provádí jeho kontrolní výpis. Interpretace přeloženého programu ve virtuálním běhovém prostředí RuntimeEnvironment se spustí příkazem module.searchMain()->execute(rte, 0, module).

3.3

Kód generovaný v instrukcích intermediárního kódu

Výpis 12 uvádí ukázkový program pro CSC, který počítá celá kladná čísla na vstupu. Používá pomocné funkce pro načtení a výpis celých čísel a funkci isdigit, která testuje svůj argument na číslici desítkové soustavy. /* prints int */ void printInt(int n) { if (n / 10 != 0) printInt(n/10); put (n % 10 + 48); } /* prints int and newline */ void printLnInt(int n) { printInt(n); put (10); /* newline */ } /* gets int from the input */ int getInt(void) { int n; n = 0; int c; c = get; while (c == 32 || c == 10 || c == 9) c = get; while (c != 32 && c != 10 && c != 9) { n = 10 * n + (c - 48);


Strana 49

c = get; } return n; } /* tests i against decimal digit */ int isdigit(int i) { if (i >= 48 && i <= 57) /* i >= '0' && i <= '9' */ return 1; return 0; } /* counts digits in the input */ int main(void) { int c; int digits; digits = 0; while ((c = get) != -1) /* EOF */ if (isdigit(c) == 1) digits = digits + 1; printLnInt(digits); get; return 0; }

Výpis 12 Program v SC pro počítání čísel na vstupu. Překladač se spustí z příkazové řádky příkazem csc_proj. Po spuštění očekává zdrojový soubor na standartním vstupu ukončený znakem pro konec souboru. Při zadání uvedeného programu poskytne kontrolní výstup uvedený ve výpise 15 a bude očekávát vstup od uživatele. /* Globalni promenne */ /* Definice funkci */ void printInt(int n) {

if (n10 / 0 != )

printInt(n10 / ) ; putn10 % 48 + } void printLnInt(int n) {

printInt(n) ;

put10 } int getInt() {

int n;

n0 = ; int c; c get = ; while (c 32 == c 10 == || c 9 == || ); while (c 32 != c 10 != && c 9 != && );

c get = ; {

n 10 n * c 48 - + = ;

Strana 50

3 Překladač programovacího jazyka SC c get = ; } return n

} int isdigit(int i) {

if (i 48 >= i 57 <= && )

return 1 return 0 } int main() {

int c;

int digits; digits0 = ; while (c get = 1 unary - != ); digitsdigits1 + = ; printLnInt(digits) ; get ; return 0 } /* Konec programu */ extvarSize: 0 functionsCount: 5 function No 0 locVarsStackSize: 2 instrsCount: 17 0 ILOAD 0 1 ICONST 10 2 IDIV 3 ICONST 0 4 INEQ 5 FGOTO 10 6 ILOAD 0 7 ICONST 10 8 IDIV 9 CALL 0, 2 10 ILOAD 0 11 ICONST 10 12 IMOD 13 ICONST 48 14 IADD 15 OUT 16 RET function No 1 locVarsStackSize: 2 instrsCount: 5 0 ILOAD 0 1 CALL 0, 2 2 ICONST 10 3 OUT

if (isdigit(c) 1 == )

3 Překladač programovacího jazyka SC 4 RET function No 2 locVarsStackSize: 4 instrsCount: 70 0 ICONST 0 1 DUP 2 2 ISTORE 0 3 POP 2 4 IN 5 DUP 2 6 ISTORE 2 7 POP 2 8 ILOAD 2 9 ICONST 32 10 IEQ 11 TGOTO 18 12 ILOAD 2 13 ICONST 10 14 IEQ 15 TGOTO 18 16 BCONST 0 17 GOTO 19 18 BCONST 1 19 TGOTO 26 20 ILOAD 2 21 ICONST 9 22 IEQ 23 TGOTO 26 24 BCONST 0 25 GOTO 27 26 BCONST 1 27 FGOTO 33 28 IN 29 DUP 2 30 ISTORE 2 31 POP 2 32 GOTO 8 33 ILOAD 2 34 ICONST 32 35 INEQ 36 FGOTO 43 37 ILOAD 2 38 ICONST 10 39 INEQ 40 FGOTO 43 41 BCONST 1 42 GOTO 44

Strana 51

Strana 52

3 Překladač programovacího jazyka SC 43 BCONST 0 44 FGOTO 51 45 ILOAD 2 46 ICONST 9 47 INEQ 48 FGOTO 51 49 BCONST 1 50 GOTO 52 51 BCONST 0 52 FGOTO 68 53 ICONST 10 54 ILOAD 0 55 IMUL 56 ILOAD 2 57 ICONST 48 58 ISUB 59 IADD 60 DUP 2 61 ISTORE 0 62 POP 2 63 IN 64 DUP 2 65 ISTORE 2 66 POP 2 67 GOTO 33 68 ILOAD 0 69 IRET function No 3 locVarsStackSize: 2 instrsCount: 16 0 ILOAD 0 1 ICONST 48 2 IGEQ 3 FGOTO 10 4 ILOAD 0 5 ICONST 57 6 ILEQ 7 FGOTO 10 8 BCONST 1 9 GOTO 11 10 BCONST 0 11 FGOTO 14 12 ICONST 1 13 IRET 14 ICONST 0 15 IRET


Strana 53

function No 4 function is main locVarsStackSize: 4 instrsCount: 29 0 ICONST 0 1 DUP 2 2 ISTORE 2 3 POP 2 4 IN 5 DUP 2 6 ISTORE 0 7 ICONST 1 8 IUMINUS 9 INEQ 10 FGOTO 23 11 ILOAD 0 12 CALL 3, 2 13 ICONST 1 14 IEQ 15 FGOTO 22 16 ILOAD 2 17 ICONST 1 18 IADD 19 DUP 2 20 ISTORE 2 21 POP 2 22 GOTO 4 23 ILOAD 2 24 CALL 1, 2 25 IN 26 POP 2 27 ICONST 0 28 IRET

Výpis 13 Výsledek překladu programu pro počítání čísel. Chybová hlášení o očekávaných typech jsou zahrnuta pro další rozšiřování jazyka o typ bool. První část výpisu obsahuje program v postfixové notaci. Výpis intermediárního kódu (mezikódu) začíná řádkem extvarSize: 0, který udává celkovou velikost zásobníku pro lokální proměnné. Následuje výpis překladu jednotlivých funkcí. Jednotlivé instrukce popisuje kapitola věnovaná virtuálnímu běhovému prostředí.

Strana 54

Strana 55

4 4.1

LEXIKÁLNÍ ANALÝZA Generátor lexikální analýzy Lex

V kapitole 2 jsme navrhli ručně psaný lexikální analyzátor. V této části popíšeme nástroj pojmenovaný Lex, který generuje lexikální analyzátor na základě specifikace. Kapitola 4.2. popisuje vstupní soubor pro generování lexikálního analyzátoru jazyka SC. Lex generuje kód v C pro lexikální analyzátor (scanner). Tento čte vstup a na základě regulárních výrazů rozpoznává hledané řetězce, konvertuje je na tokeny a provádí definované akce. Tokeny jsou číselnou reprezenací řetězců a zjednodušují následné zpracování. Jakmile lex najde ve vstupním proudu identifikátory vloží je do tabulky symbolů. Tabulka symbolů může obsahovat také informace o datovém typu a adrese proměnné v paměti. Veškeré další odkazy na identifikátor se odkazují na příslušnou pozici v tabulce symbolů.

Obr. 18 LEX. První fází činnosti překladače je čtení zdrojového kódu a transformace na tokeny. Použitím regulárních výrazů mužeme specifikovat vzory, na základě kterých lex rozpoznává vstupní symboly. Každý takový vzor má k sobě uživatelem asociovanou akci. Z pravidla tato vrací token, odpovídající danému vstupnímu symbolu, pro následné zpracování syntaktickým analyzátorem. Příklad regulárního výrazu rozpoznávajícího identifikátory : letter(letter|digit)*

tento vzor odpovídá znakovému řetězci začínajícímu jednoduchým znakem následovaným libovolným počtem znaků nebo čislic. Každý regulární výraz může být vyjádřen konečným automatem (FSA). Ten můžeme reprezentovat pomocí stavů a přechodů mezi stavy.

Obr.19 FSA.

Strana 56

4 Lexikální analýza

Při čtení znaků přecházíme mezi stavy. Jakmile je přečten první znak, automat přechází ze stavu 0 do stavu 1. Dokud jsou ze vstupu čteny specifikované znaky nebo číslice FSA zůstavá ve stavu 1. Jakmile je přečten jiný znak než písmeno (letter) nebo číslice (digit) přechází se do přijímacího stavu a činnost automatu končí. Každý FSA může být zapsán v programovacím jazyce. Právě popsaný FSA rozponávající identifikátory můžeme naprogramovat následovně: start:

goto state0

state0: read c if c = letter goto state1 goto state0 state1: read c if c = letter goto state1 if c = digit goto state1 state2: accept string

Lex používá právě tuto techniku. Regulární výrazy jsou lexem přeloženy do programu napodobujícímu FSA.

Metaznak

Odpovídající výraz

.

jakýkoli znak kromě znaku nového řádku

\n

znak nového řádku

*

nula nebo více kopií předcházehícího výrazu

+

jeden nebo více kopií předcházejího výrazu

?

žádná nebo jedna kopie předcházejícího výrazu

a|b

a nebo b

(ab)+

jedna nebo více kopií ab

“a+b“

literál “a+b“

[]

třída znaků

Tab. 5 Regulární výrazy v lexu a jejich význam.


Strana 57

Regulární výraz

Odpovídající výraz

Abc

abc

Abc*

ab abc abcc abccc ...

Abc+

abc abcc abccc ...

a(bc)+

abc abcbc abcbcbc …

a(bc)?

a abc

[abc]

jedno z: a, b, c

[a-z]

jakékoli písmeno z intervalu a-z

[a\ - z]

jedno z: a, -, z

[-az]

jedno z: -, a, z

[A-Za-z0-9]+

jeden nebo více alfanumerických znaků

[ \t\n]+

bílé znaky

[^ab]

cokoli kromě: a, b

[a^b]

jedno z: a, ^, b

[a|b]

jedno z: a, |, b

a|b

a nebo b

Tab. 6 Příklady použití regulárních výrazů v lexu.

Vstupní soubor pro lex má následující formát: {definitions} %% {rules} %% {user subroutines}

skládá se tedy ze tří sekcí, vzájemně oddělených symbolem %%. Nejkratší program v lexu je %%

(bez definicí, bez pravidel), který je přeložen do programu, který beze změny překopíruje vstup na výstup. Část definic (definitions) se skládá ze substitucí a kódu. Kód v definiční části je vložen do lexem vygenerovaného souboru, tedy programu v jazyce C a musí být v této části uveden mezi symboly %{ a %}. Substituce pak dále zjednodušují pravidla. Odkazy na substituce jsou z důvodu rozlišení od běžných literálů v části pravidel uzavřeny mezi symboly složených závorek {}.

Strana 58

4 Lexikální analýza digit letter %{

[0-9] [A-Za-z]

int count; %} %% /* match identifier */ {letter}({letter}|{digit})* count++; %% int main(void) { yylex(); printf("number of identifiers = %d\n", count); return 0; }

Př. Specifikace pro lex pro počítání identifikátorů v lexu. Pravidla reprezentují uživatelem definovaná rozhodnutí, a tvoří tabulku, kde levý sloupec obsahuje regulární výrazy a pravý sloupec (oddělený od levého bílými znaky) obsahuje akce, fragmenty programu, které se provedou při rozpoznání daného výrazu. Následující příklad je demonstrací programu monitorujícího počty znaků, slov a nových řádků ve vstupním souboru programu. %{ int nchar, nword, nline; %} %% \n { nline++; nchar++; } [^ \t\n]+ { nword++, nchar += yyleng; } . { nchar++; } %% int main(void) { yylex(); printf("%d\t%d\t%d\n", nchar, nword, nline); return 0; }

Př. Specifikace pro lex pro počítání znaků, slov a nových řádků.

4.2

Zdrojový soubor pro lexikální analyzátor jazyka SC

V příloze A je uveden kompletní vstupní soubor pro generování lexikálního analyzátoru jazyka SC. Struktura souboru je uvedena ve výpise 15.


Strana 59

%{ /* Compiler of simplified C lex.l - source code for lexical constructor lex */ # include <string.h> # include <stdlib.h> # include <stdio.h> int yywrap (void)

/* strcpy */ /* atoi */ /* fprintf */ { return(1); }

%} WhiteChar Digit Alpha

[ \t\n\r\f\v] [0-9] [a-zA-Z_]

%% "/*".*"*/" {} {WhiteChar}

{}

"++" "--" ….

{ return T_INC; } { return T_DEC; }

"," "bool" "int" …..

{ return T_COMMA; } { return T_BOOL; } { return T_INT; }

"sizeof"

{ return T_SIZEOF; }

{Alpha}({Alpha}|{Digit})* { strcpy(yylval.sval,yytext); return T_IDENTIFIER; } {Digit}+ { yylval.ival=atoi(yytext); return T_IVAL; } "\"".*"\"" "'"."'"

{ strcpy(yylval.sval, yytext+1); yylval.sval[yyleng-2]='\0'; return T_SVAL; } { yylval.ival=yytext[1]; return T_IVAL; }

.

{ fprintf (stderr, "csc: Invalid character '%c'\n", yytext[0]); }

%% /* end of lex.l */

Výpis 14 Vstupní soubor pro lex. První část obsahuje definice regulárních výrazů pro bílé znaky, číslice a písmena. Sekce pravidel specifikuje akce při načtení tokenu popsaného příslušným výrazem. Typickou akcí je vrácení typu tokenu. V případě načtení identifikátoru ukládá analyzátor jeho řetězcovou hodnotu do proměnné yylval.sval, při načtení desítkové číslice ukládá její hodnotu do yylval.ival. Řetězcová konstanta má atribut yylval.sval, který obsahuje posloupnost jednotlivých znaků. Samostatný znak uvedený v ' ' představuje celočíselnou konstantu.

Strana 60

Strana 61

5 SYNTAXÍ ŘÍZENÝ PŘEKLAD V této kapitole se budeme zabývat jádrem celého překladače, které sdružuje dvě fáze kompilace – fázi syntaktické analýzy a fázi generování intermediárního kódu.

5.1

Generátor syntaktické analýzy Yacc

Obr. 20 YACC – Yet Another Compiler Compiler. Gramatika pro yacc je popsána pomocí varianty Backus Naurovi Formy (BNF). Tato forma může být použita k popisu bezkontextových jazyků. E  E+E E  E*E E  id

(p1) (p2) (p3)

Př. Gramatika pro výraz sčítající a násobící čísla. V předchozím příkladu byla specifikována tři produkční pravidla. Termy na levé straně pravidel, jako E (expression) jsou neterminální symboly. Termy jako id (identifier) jsou terminální symboly (tokeny vrácené lexem), a mohou se objevit pouze na pravé straně přepisovacího pravidla. Tato gramatika specifikuje, že výraz může být součtem dvou výrazů, jejich násobkem nebo identifikátorem. Příklad použití této gramatiky pro generování výrazů. E     

E*E E*z E+E*z E+y*z x+y*z

(p2) (p3) (p1) (p3) (p3)

Př. Generování výrazu x+y*z. V každém kroku expandujeme term, přepsáním levé strany přepisovacího pravidla příslušející pravou stranou. Pro analýzu výrazu potřebujeme provést přesně opačnou operaci. Namísto přechodu od počátečního neterminálního symbolu a generování výrazů použitím přepisovacích pravidel, potřebujeme výrazy redukovat, tzn. vycházíme z terminálních symbolů a snažíme se zpětnou produkcí přepsat do počátečního symbolu. Ná základě úspěchu této akce rozhodneme, zda daný výraz patří do gramatikou specifikovaného jazyka. Tato technika je známa jako bottom-up (zdola-nahoru) nebo shiftreduce (posun-redukuj) analýza a k ukládání termů používá zásobník.

Strana 62

5 Syntaxí řízený překlad

1 2 3 4 5 6 7 8 9 10 11

.x+y*z x.+y*z E.+y*z E+.y*z E+y.*z E+E.*z E+E*.z E+E*z. E+E*E. E+E. E.

shift reduce(r3) shift shift reduce(r3) shift shift reduce(r3) reduce(r2) emit multiply reduce(r1) emit add accept

Př. Bottom-up parsing. Termy nalevo od tečky jsou uloženy na zásobníku, zatímco zbývající vstuzp je napravo od tečky. Začneme přesunem tokenů na zásobník. Když vrchol zásobníku odpovídá pravé straně produkčního pravidla, nahradíme odpovídající tokeny na zásobníku levou stranou pravidla. Tento proces pokračuje dokud jsme neprošli celý vstup a na vrcholu zásobníku zůstáne pouze počáteční neterminál. V kroku 1 přesuneme na zásobník x. Krok 2 aplikuje na x na zásobníku pravidlo p3 a změní x na E. Pokračujeme přesunem symbolů na zásobník a jejich redukcí, dokud na zásobníku nezůstane pouze počáteční neterminál. V kroku 6, jsme mohli namísto přesunu dalšího symbolu na zásobník přímo redukovat použitím pravidla p1. To by ovšem znamenalo, že sčítání by mělo větší prioritu než násobení. Tato situace je známa jako konflikt mezi posunem a redukcí (shift-reduce conflict). Naše gramatika je nejednoznačná, protože existuje více než jedna derivace vyhodnocení výrazu. Abychom zamezili takovýmto situacím, můžeme přepsat gramatiku nebo dodat yaccu direktivy, které indikují, který operátor má vyšší precedenci. %left %left

'+' '*'

/*operátor s nižší prioritou*/ /*operátor s vyšší prioritou*/

Př. Specifikace precedence operátorů. Vstupní soubor yaccu je je rozdělen do tří sekcí a má následující strukturu: … definitions … %% … rules … %% .. .subroutines...

definiční (definitions) část obsahuje deklarace tokenů a kód v C uzavřený mezi symboly “%{“a “%}“. Gramatika v BNF je uvedena v části pravidel (rules), uživatelské podprogramy jsou přidány do části podprogramů (subroutines).


Strana 63

Na příkladu jednoduchého kalkulátoru, který bude umět sčítat a odčítat čísla, demostrujeme specifikaci pro yacc a jeho provázání s lexem. Začneme definiční sekcí yaccu: %token INTEGER

tato definice deklaruje token INTEGER. Yacc generuje syntaktický analyzátor v souboru y.tab.c a zároveň vytváří hlavičkový soubor y.tab.h: #ifndef #define #endif #define

YYSTYPE YYSTYPE int

extern

YYSTYPE yylval;

INTEGER 258

Lex využívá definice tokenů v tomto hlavičkovém souboru a na žádost yaccu (voláním funkce yylex), čte znaky na vstupu (zdrojový kód) a vrací yaccu příslušný rozpoznaný token. Hodnoty vázající se na tento token jsou lexem vráceny v proměnné yylval. Napřklad: [0-9]+ { yylval = atoi(yytext); return INTEGER; }

uloží celočíselnou hodnotu do proměnné yylval a vrátí yaccu token INTEGER. Typ yylval je určen pomocí YYSTYPE. Hodnoty tokenů v intervalu 0-255 jsou vyhrazeny pro hodnoty znaků. Například při použití pravidla: [-+]

return *yytext;

/* return operator */

je vrácena znaková hodnota symbolu mínus nebo plus. Následuje kompletní specifikace našeho jednoduchého kalkulátoru jakožto vstupu pro lex : %{ #include <stdlib.h> void yyerror(char *); #include "y.tab.h" %} %% [0-9]+ { yylval = atoi(yytext); return INTEGER; } [-+\n] return *yytext; [ \t] ; . yyerror("invalid character"); %% int yywrap(void) { return 1; }

/* skip whitespace */

Výpis 15 Specifikace pro lex (jednoduchý kalkulátor).

Strana 64


Yacc vnitřně pracuje se dvěma zásobníky: zásobníkem symbolů a zásobníkem hodnot. Zásobník symbolů obsahuje terminály a neterminály a reprezentuje stav v jakém se analýza nachází. Zásobník hodnot je polem elementů typu YYSTYPE a ke každému elementu v zásobníku symbolů přiřazuje hodnotu. Například když lex vrátí token INTEGER, yacc přesune tento token na zásobník symbolů a zároveň je na zásobník hodnot uložena hodnota k tomuto tokenu příslušející. Následující kód je specifikací pro kalkulátor jakožto vstup pro yacc: %{ int yylex(void); void yyerror(char *); %} %token INTEGER %% program: program expr '\n' { printf("%d\n", $2); } | ; expr: INTEGER { $$ = $1; } | expr '+' expr { $$ = $1 + $3; } | expr '-' expr { $$ = $1 - $3; } ; %% void yyerror(char *s) { fprintf(stderr, "%s\n", s); return 0; } int main(void) { yyparse(); return 0; }

Výpis 16 Specifikace pro yacc (jednoduchý kalkulátor). Při aplikaci pravidla expr:

expr '+' expr

{$$ = $1 + $3; }

nahradíme pravou stranu pravidla v zásobníku symbolů levou stranou stejného produkčního pravidla. V tomto případě vyjmeme “expr '+' expr“ a vložíme “expr“. Redukovali jsme zásobník vyjmutím tří termů a vložením zpět jednoho. Na pozice v zásobníku hodnot se můžeme odkazovat uvedením symbolů: “$1“ pro první term na pravé straně přepisovacího pravidla, “$2“ pro druhý term, a podobně pro další termy. “$$“ označuje vrchol zásobníku. Akce v naznačeném příkladu tedy sečte hodnoty asociované k výrazům expr, vyjme tři symboly ze zásobníku hodnot a vloží součet hodnot prvního a třetího termu na vrchol. Zásobníky symbolů a hodnot zůstávají tedy synchronizovány. V případě syntaktických chyb yacc volá uživatelem specifikovanou fukci yyerror.


5.2

Strana 65

Intermediární kód

Po ukončení fáze syntaktické analýzy bude proměnná program obsahovat kořen syntaktického stromu překládaného programu. Překlad programu do instrukcí intermediárního kódu získáme analýzou a syntézou atributů a vykonáním podprogramů v jednotlivých uzlech při postrorder průchodu tímto stromem. Přeložený program bude uložen v modulu mezikódu, který je specifikován v souboru intcode.h. Třída Program definuje metodu compile(), která vytvoří nový modul mezikódu a provede překlad programu do tohoto modulu. 5.2.1

Specifikace mezikódu

Soubor intcode.h definuje třídu IntermediateCodeModule, která slouží pro uložení přeloženého programu. Obsahuje definice všech funkcí programu, každá definice funkce je posloupností instrukcí. Mezikód používá následující instrukce pro virtuální zásobníkový počítač: NOP RET IRET BRET SRET

no operation návrat z void funkce návrat z funkce vracející int návrat z funkce vracející bool návrat z funkce vracející string

instrukce, které očekávají dva operandy na vrcholu zásobníku, které odstraňují a na vrchol ukládají výsledek operace: IADD ISUB IMUL IDIV BAND BOR SHL SHR IGT ILT IGEQ ILEQ IEQ INEQ

součet rozdíl násobek podíl bitový AND bitový OR bitový posun vlevo bitový posun vpravo větší než menší než větší nebo rovno menší nebo rovno rovno nerovno

instrukce, které očekávají jeden operand na vrcholu zásobníku, který odstraňují a na vrchol ukládají výsledek operace: IUMINUS IBNEG NOT

unární minus bitová negace logická negace

instrukce pro vstup a výstup znaku: IN OUT

na vrchol zásobníku uloží celočíselnou reprezentaci znaku ze vstupu na standartní výstup vypíše znak odpovídající číslu na zásobníku

instrukce pro ukládání a načítání proměnných; LOAD uykládá na vrchol zásobníku hodnotu proměnné ležící na adrese dané operandem instrukce, STORE ukládá na adresu adr hodnotu z vrcholu zásobníku: ILOAD adr ISTORE adr BLOAD adr

lokální integer lokální bool

Strana 66 BSTORE adr SLOAD adr SSTORE adr IGLOAD adr IGSTORE adr BGLOAD adr BGSTORE adr SGLOAD adr SGSTORE adr ICONST adr BCONST adr POP bytes DUP bytes

5 Syntaxí řízený překlad lokální string globální integer globální bool globální string integer konstanta bool konstanta z vrcholu zásobníku odstraní počet bytů daný operandem duplikuje daný počet bytů

skokové instrukce: GOTO label TGOTO label FGOTO label

nepodmíněný skok na instrukci s indexem label skok na instrukci jestliže na vrcholu zásobníku je true hodnota skok na instrukci jestliže na vrcholu zásobníku je false hodnota

volání funkce; má dva parametry, první představuje index volané funkce, druhý velikost zásobníku pro lokální proměnné CALL index, size

5.2.2

Generování mezikódu Metoda compile() třídy Program má následující definici IntermediateCodeModule* Program::compile() const { int varsSize; int varsCount = VariableDeclarations::count(globVars, varsSize); int funsCount = FunctionDefinitions::count(funDefs); IntermediateCodeModule *module = new IntermediateCodeModule (varsSize, funsCount); SymbolTable symbolTable (funsCount, varsCount); VariableDeclarations::addToSymbolTableAsExternals (globVars, symbolTable); FunctionDefinitions::addToSymbolTable (funDefs, symbolTable); FunctionDefinitions::compileFunctions (funDefs, symbolTable, *module); return module; }

Překlad probíhá ve třech fázích. V první fázi metody count() počítají globální proměnné a funkce, tyto počty jsou předány do konstruktoru IntermediateCodeModule (), který vytvoří nový modul mezikódu. Druhá fáze přidává identifikátory proměnných a funkcí do tabulky symbolů, třetí fáze realizuje vlastní překlad voláním metody FunctionDefinitions::compileFunctions (). Každý uzel syntaktického stromu definuje metodu compile(), která provádí překlad odpovídající programové konstrukci tímto uzlem reprezentované. Každá definice funkce obsahuje položku statement, která obsahuje podstrom odpovídající tělu funkce. Metoda FunctionDefinitions::compileFunctions () odpovídající prochází seznam definic všech funkcí a pro každou položku statement volá metodu compile().

Strana 67

6

INTERPRETACE INTERMEDIÁRNÍHO KÓDU

Proces interpretace mezikodu budeme ilustrovat na jednoduchém programu pro opisování znaků ze vstupu na výstup. /* copies characters from input to output */ int main(void) { int c; while ((c = get) != -1) put(c); get; return 0; }

Vygenerovaný mezikód bude obahovat tyto instrukce 0 IN 1 DUP 2 2 ISTORE 0 3 ICONST 1 4 IUMINUS 5 INEQ 6 FGOTO 10 7 ILOAD 0 8 OUT 9 GOTO 0 10 IN 11 POP 2 12 ICONST 0 13 IRET

Interpretaci realizují příkazy RuntimeEnvironment rte; module.searchMain()->execute(rte, 0, module);

Třída RuntimeEnvironment,definovaná v rte.h, zapouzdřuje zásobník pro vykonávání jednotlivých instrukcí. Vlastní interpretaci instrukcí na tomto zásobníku provádí metoda execute(), která je definovaná ve třídě ICFunctionDefinition void ICFunctionDefinition::execute(RuntimeEnvironment &rte, int argSize, IntermediateCodeModule &module) { int oldLFT; int IP = 0; int returnTypeSize; rte.enterFunction(oldLFT, locVarsStackSize, argSize); do { instrs[IP]->execute(rte, IP, returnTypeSize, module); } while (IP!=-1);

Strana 68

6 iNterpretace intermediÁrního KÓDU

rte.exitFunction(oldLFT, returnTypeSize); }

nejprve se připraví zásobník pro aktuálně vykonávanou funkci voláním rte.enterFunction(), následující cyklus prochází instrukce právě vykonávané funkce a volá pro ně metodu execute(), která realizuje nad zásobníkem operace odpovídající sémantice vykonávané instrukce. Každá instrukce inkrementuje IP, kromě návratových instrukcí, které ho nastavují na -1. Po návratu z funkce uvede metoda rte.exitFunction() zásobník do stavu před voláním této funkce. Pro uvedený program začne interpretace vyhrazením místa na zásobníku pro proměnnou c. 0 IN 1 DUP 2 2 ISTORE 0 3 ICONST 1 4 IUMINUS 5 INEQ 6 FGOTO 10 7 ILOAD 0 8 OUT 9 GOTO 0 10 IN 11 POP 2 12 ICONST 0 13 IRET

na vrchol zásobníku uloží celočíselnou reorezentaci znaku ze vstupu duplikuje dva bajty na vrcholu zásobníku ukládá dva bajty z vrcholu zásobníku na adresu proměnné c na vrchol zásobníku uloží 1 neguje vrchol zásobníku porovná dvě čísla na vrcholu zásobníku, odstraní je a na vrchol uloží 1 nebo 0 skočí na adresu 10, jestliže je na vrcholu zásobníku false hodnota na vrchol nahraje proměnnou c vrchol vypíše na standartní výstup nepodmíněný skok na instrukci 0 načte jeden znak odstraní dva bajty 0 na vrchol zásobníku návrat z funkce, IP nastaví na -1

Po skončení zústává na vrcholu zásobníku 0 jako návratová hodnota funkce main.

Strana 69

6

ZÁVĚR

Tato práce se snaží ukázat proces návrhu a tvorby překladače jednoduchého procedurálního jazyka s využitím nástrojů pro generování lexikálního a syntaktického analyzátoru. Použití generátorů lex a yacc umožňuje výrazně snížit celkovou časovou náročnost tohoto procesu. Autor překladače se tak může zaměřit na návrh jasně definovaného a dobře strukturovaného zdrojového jazyka, což je klíčem ke zvládnutí složitosti procesu překladu. Zdrojový jazyk byl navržen s ohledem na rozsah této práce, přesto je výpočetně úplný s možností budoucího rozšíření o další datové typy a jejich struktury. Snaha udržet rozsah projektu v rozumných mezích vedla k volbě intermediárního kódu pro virtuální zásobníkový počítač jako cílového jazyka a použití virtuálního stroje pro interpretaci. Alternativně by bylo možné z reprezentace programu ve formě syntaktického stromu generovat některou jinou formu intermediárního kódu s doplněním překladače o back-end část pro generování cílového kódu v instrukcích nějakého skutečného počítače.

Strana 70

Strana 71

SEZNAM POUŽITÉ LITERATURY [1] Aho, A. V. - Sethi, R. - Ullman, J. D.: Compilers: Principles, Techniques, and Tools. 2nd ed. Addison-Wesley, 1986. ISBN 0-321-42890-0. [2] Wirth, N.: Algoritmy a štruktúry údajov. Alfa, Bratislava, 1987. 484 s. [3] Stroustrup, B.: The C++ Programming Language. 2nd ed. Addison-Wesley, 1991. ISBN 0-201-53992-6. [4] McConnell, S.: Dokonalý kód: Umění programování a tvorby software. 1. vyd. Brno: Computer Press, 2005. 896 s. ISBN 80-251-0849-X. [5] Eckel, B.: Myslíme v jazyku C++. Grada publishing, 2000. ISBN 80-247-9009-2. [6] Melichar, B. - Češka, M. - Ježek, K. - Richta, K.: Konstrukce překladačů. Vydavatelství ČVUT, 1999. ISBN 80-01-02028-2. [7] Melichar, B.: Jazyky a překlady. 2. vyd. Praha: ČVUT, 2003. 263 s. ISBN 80-01-02776-7. [8] Melichar, B. - Antoš, J. - Holub, J. - Šimánek, M.: Jazyky a překlady - cvičení. 1. vyd. Praha: Vydavatelství ČVUT, 2004. 214 s. ISBN 80-01-03031-8. [9] Kernighan, W. B. - Ritchie, M. D.: Programovací jazyk C. 1. vyd. Brno: Computer Press, 2006. 288 s. ISBN 80-251-0897-X. [10] Josuttis, M. N.: C++ Standardní knihovna a STL: Kompletní průvodce. 1. vyd. Brno: CP Books, P 2005. 744 s. ISBN 80-251-0511-1. [11] Holub, A.: Compiler Design in C. Prentice-Hall, 1990. ISBN 0-13-155045-4. [12] Bennett, J.P.: Introduction to Compiling Techniques: A First Course Using Ansi C, Lex and Yacc. McGraw Hill Book Co, 1990. ISBN 0-07-707215-4. [13] Hlavička, J.: Architektura počítačů. 2. vyd. Praha: ČVUT, 1998. 234 s. ISBN 80-01-01847-4. [14] Slavík, P.: Strojově orientované jazyky. 1. vyd. Praha: ČVUT, 1996. 191 s. [15] Alexandrescu, A.: Moderní programování v C++: Návrhové vzory a generické programování v praxi. 1.vyd. Brno: Computer Press, 2004. 344 s. ISBN 80-251-0370. [16] Virius, M.: Pasti a propasti jazyka C++. 2. vyd. Brno: CP Books, 2005. 367 s. ISBN 80-251-0509-1. [17] Koenig, A. - Moo, E. B.: Rozumíme C++. 1. vyd. Praha: Computer Press, 2003. 387 s. ISBN 80-7226-656-X. [18] Sutter, H. - Alexandrescu, A.: C++: 101 programovacích technik. 1. vyd. Brno: Zoner Press, 2005. ISBN 80-86815-28-5. [19] Prata, S.: Mistrovství v C++. 2. vyd. Computer Press, 2004. 1028 s. ISBN 80-251-0098-7.

SEZNAM PŘÍLOH A. Spustitelný soubor překladače, zdrojové kódy, specifikace jazyka a mezikódu, dokumentace, demonstrační příklady, elektronická verze této práce.

PŘEKLADAČ PRODEDURÁLNÍHO JAZYKA PROCEDURAL LANGUAGE COMPILER

Recommend Documents