Vysoké učení technické v Brně Fakulta elektrotechniky a informatiky Ústav informatiky a výpočetní techniky. Ročníkový projekt

Vysoké učení technické v Brně Fakulta elektrotechniky a informatiky Ústav informatiky a výpočetní techniky

Ročníkový projekt Assembler řízený tabulkami

Jan Nikitěnko 1999/2000

Abstrakt Tato dokumentace popisuje projekt, jehož cílem je vytvoření překladače jazyků symbolických instrukcí, který bude schopen pouze na základě tabulkového popisu překládat libovolný z těchto jazyků pro libovolný mikroprocesor. V úvodu jsou popsány už existující překladače, jejich možnosti a omezení a také používané metody překladu jazyků symbolických instrukcí. Hlavní část této dokumentace je zaměřena na popis návrhu assembleru řízeného tabulkami.

Klíčová slova Assembler, překladač, jazyk symbolických instrukcí, tabulka instrukcí, interpret, generátor kódu, objektový návrh překladače, mikroprocesor, operandy, tabulka symbolů.

Prohlášení Prohlašuji, že jsem tento ročníkový projekt vypracoval samostatně pod vedením Dr. Ing. Petra Peringera. Uvedl jsem všechny literární prameny a publikace, ze kterých jsem čerpal.

V Brně 11. května 2000

..................... Jan Nikitěnko

Obsah 1 Úvod 1.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Struktura tohoto dokumentu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Cíl tohoto ročníkového projektu . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 5 5 5

2 Obecný rozbor – metody překladu 2.1 Specializované assemblery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Jednoduché tabulkově orientované assemblery . . . . . . . . . . . . . . . . . . . . 2.3 Tabulkou řízený assembler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 7 7 8

3 Návrh 3.1 Požadavky návrhu . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Vlastnosti cílového procesoru a jeho instrukcí . . . . . . . . 3.1.2 Specifikace syntaxe jazyka symbolických instrukcí . . . . . . 3.1.3 Generování kódu . . . . . . . . . . . . . . . . . . . . . . . . 3.1.4 Třídy operandů . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.5 Definice instrukcí . . . . . . . . . . . . . . . . . . . . . . . . 3.1.6 Prefixy instrukcí a operandů . . . . . . . . . . . . . . . . . 3.1.7 Podpora výrazů a symbolů v překládaném zdrojovém kódu 3.1.8 Módy procesoru . . . . . . . . . . . . . . . . . . . . . . . . 3.1.9 Podpora segmentace . . . . . . . . . . . . . . . . . . . . . . 3.2 Gramatika tabulkového popisu . . . . . . . . . . . . . . . . . . . . 3.3 Základní struktura a princip překladače . . . . . . . . . . . . . . . 3.4 Hierarchie tříd tabulkového popisu . . . . . . . . . . . . . . . . . . 3.4.1 Třída Table . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Abstraktní bázová třída Symbol . . . . . . . . . . . . . . . . 3.4.3 Třída Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.4 Abstraktní bázová třída OperandBase . . . . . . . . . . . . 3.4.5 Abstraktní bázová třída OperValueBase . . . . . . . . . . . 3.4.6 Abstraktní bázová třída Executable . . . . . . . . . . . . . . 3.4.7 Abstraktní bázová třída Expression . . . . . . . . . . . . . . 3.4.8 Třída ExprArgN . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Hierarchie tříd tabulkou řízeného překladače . . . . . . . . . . . . . 3.6 Problém opakování stejného operandu . . . . . . . . . . . . . . . . 3.7 Problém šířky operandů . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Tabulka symbolů překládaného zdrojového kódu . . . . . . . . . .

3

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

9 9 9 10 10 10 11 11 11 11 11 11 13 14 14 14 15 15 16 16 16 16 16 18 18 18

4 Implementace 4.1 Překlad a použití tabulkou řízeného assembleru 4.2 Vlastnosti implementovaného prototypu . . . . 4.3 Nejdůležitější stávající omezení a chyby . . . . 4.4 Přenositelnost . . . . . . . . . . . . . . . . . . . 4.5 Příklady přeložitelných instrukcí . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

19 19 20 20 21 21

5 Závěr

22

Literatura

23

A Příklad tabulky pro Intel x86

24

4

Kapitola 1

Úvod 1.1

Základní pojmy

Jazyk symbolických instrukcí – assembly language – člověkem přijatelnější symbolická reprezentace strojového kódu mikroprocesoru místo hexadecimálních kódů instrukcí [APC] Překlad (kompilace) – zobrazení L1 → L2 , kde L1 je zdrojový jazyk a L2 je cílový jazyk (viz. [ZAP]) Překladač – něco, co provádí překlad Assembler – překladač jazyka symbolických instrukcí do binárního (hexadecimálního) tvaru strojového kódu cílového procesoru

1.2

Struktura tohoto dokumentu

V této kapitole budou nastíněny metody používané při překladu jazyků symbolických instrukcí a stručně shrnuty jejich výhody a nevýhody. Potom bude rozveden cíl této práce v návaznosti na existující prostředky. V druhé kapitole se budeme zabývat vlastním návrhem tabulkami řízeného assembleru. Budou stanoveny základní požadavky na možnosti tabulkového popisu, návrh zpracování těchto tabulek a způsob překladu zdrojových souborů pomocí tabulkového popisu cílového procesoru. V třetí kapitole je popsán implementovaný prototyp tabulkami řízeného assembleru, jeho vlastnosti a omezení, co je nyní vlastně implementováno. Ve čtvrté kapitole jsou shrnuty dosažené výsledky, přínos získaný touto prací a možnosti dalšího vývoje.

1.3

Cíl tohoto ročníkového projektu

Cílem tohoto ročníkového projektu je vytvořit návrh assembleru, který používá tabulkový popis pro překlad jazyků symbolických instrukcí. Jedná se tedy o návrh vhodné struktury tabulkového popisu a překladače, který po zpracování této tabulky bude schopen podle ní překládat na definovaný procesor. Pro ověření správnosti návrhu jsem měl v rámci tohoto ročníkového projektu implementovat prototyp assembleru včetně příkladů tabulek instrukcí pro různé mikroprocesory. Konečným

5

cílem bude implementace plně funkčního tabulkou řízeného assembleru, který bude mít tyto vlastnosti: • plně objektově orientovaný návrh • naprostá univerzálnost assembleru díky možnosti definovat tabulkový popis jazyka symbolických instrukcí libovolného mikroprocesoru těmito prostředky: – definice vlastností cílového procesoru – specifikace syntaxe překládaného jazyka – prostředky pro řízení generování kódu – třídy operandů a jejich generování – definice instrukcí a jejich generování – podpora symbolů ve zdrojovém kódu1 – podpora obecných výrazů ve zdrojovém kódu1 – prefixy instrukcí a operandů1 – podpora více módů procesoru1 – podpora segmentace1 • implementace v jazyce C++ v normě ISO s použitím STL2 • volně šiřitelný pod licencí GPL3 • přenositelnost na různé platformy na zdrojové úrovni

1

V prototypu není implementováno Standard Template Library - popis viz. [STL] 3 GNU General Public License Version 2, Copyright (C) 1989, 1991 Free Software Foundation, Inc. 2

6

Kapitola 2

Obecný rozbor – metody překladu Existují různé metody pro překlad jazyků symbolických instrukcí, od specializovaných assemblerů až po naprosto univerzální. Vždy je možné použít objektově orientovaný přístup umožňující snadnější a přehlednější návrh překladače.

2.1

Specializované assemblery

Jednou z možností překladu jazyků symbolických instrukcí je použití specializovaného assembleru pro cílový procesor. Tento assembler je tedy zaměřen většinou na překlad jednoho jazyka symbolických instrukcí a to buď pouze pro jeden procesor nebo určitou množinu velmi příbuzných procesorů. Metody překladu požívané těmito typy překladačů jsou stejné jako pro překlad jiných programovacích jazyků, kde se také překládá jedním překladačem jen jeden jazyk (např. Pascal, C, C++). Těchto metod existuje samozřejmě více. Já zde uvedu jen ty nejpoužívanější: překlad metodou zdola nahoru (LR gramatiky) - zde se s výhodou používá konstruktorů Lex a Yacc, analýza rekurzivním sestupem, tj. překlad metodou z hora dolů (LL gramatiky) neboli tzv. predikční analýza, atd. Jako příklady tohoto typu assemblerů lze uvést např. NASM (The Netwide Assembler) nebo TASM (Turbo Assembler), které překládají jazyk symbolických instrukcí rodiny procesorů Intel x86.

2.2

Jednoduché tabulkově orientované assemblery

Jedná se zatím o ne moc rozšířený přístup. Existující tabulkou řízené assemblery mají většinou silná omezení, při kterých jsou použitelné pouze na překlad pro nejjednodušší mikroprocesory (jedno čipy - např. 8051, Motorola 68xx, Zilog Z80, . . . ). Tabulkou lze definovat množinu instrukcí, ale typy operandů, popřípadě i typy instrukcí jsou již napevno zabudované v překladači tak, že nelze přidat jiný typ instrukce bez nutnosti modifikace zdrojových souborů překladače a jeho rekompilace – např. TASM (The Telemark Assembler)1 . Dalším představitelem tohoto typu assemblerů je PCMAC (Universal Macro Assembler for PC)1 , který používá tabulku instrukcí definovaných v podstatě jako makra. Možnosti jeho 1

K dispozici je shareware verze na internetových serverech poskytujících tyto typy programů

7

makrojazyka pro definici tabulky instrukcí však nejsou dostatečně komplexní, aby bylo možné definovat tabulku např. pro mikroprocesory Intel x86. V některých případech jsou tyto tabulky přímo nedělitelnou součástí překladače a nelze je bez rekompilace překladače modifikovat vůbec.

2.3

Tabulkou řízený assembler

U tohoto typu assembleru se předpokládá překlad plně řízený tabulkovým popisem, který bude natolik komplexní, že bude možné definovat tabulku pro libovolný procesor bez nutnosti modifikace vlastního kódu překladače. Vzhledem k tomu, že natolik komplexní překladač se mi nikde na internetu nepodařilo najít, bude vyvíjený assembler jedinečný svou univerzálností. Pokud se podaří dosáhnout vytčeného cíle, pak už by nemuselo být nutné vytvářet specializované assemblery pro nové procesory nebo modifikovat existující, ale bude pouze stačit vytvoření tabulkového popisu pro nový procesor s okamžitou možností překladu.

8

Kapitola 3

Návrh 3.1

Požadavky návrhu

Následují požadavky včetně popisu na možnosti tabulky pro zajištění co největší volnosti popisu překladu jazyka symbolických instrukcí. Většina definic bude založena na principu regulárních výrazů pro umožnění automatického rozpoznávání instrukcí a operandů ve zdrojovém textu.

3.1.1

Vlastnosti cílového procesoru a jeho instrukcí

Překladač musí podporovat v tabulkovém popisu nastavení těchto vlastností architektury cílového mikroprocesoru: endianness – pořadí uložení bytů ve slovech šířka základních typů – šířka bytu (ne každý mikroprocesor má byte o šířce 8 bitů), popřípadě šířka slov, dvojslov, pokud to nejsou obvyklé násobky bytů, a pro zajištění naprosté universality možnost použití celočíselného typu s definovaným počtem bitů registry – kromě jejich názvů by mělo být možné definovat také jejich šířku pro možnost kontroly správnosti přímých hodnot formát instrukce – každá instrukce se obvykle skládá z více částí, zvláště pak u složitějších mikroprocesorů (např. nepovinná prefixová část, povinná oblast operačního kódu, oblast definující typ operandů, oblast přímé adresy a dat, . . . ) čítač instrukcí – IP (instruction pointer) – definice jeho šířky (tj. rozsah adresového prostoru) a definice jeho symbolického označení pro možnost generování relativního kódu použitím identifikátoru IP ve výrazu

9

3.1.2

Specifikace syntaxe jazyka symbolických instrukcí

Bude definovat strukturu překládaného zdrojového souboru a další záležitosti závisející na prostředí, jako např.: • syntaxe čísel v různých soustavách • syntaxe poznámek • případné oddělovače instrukcí • syntaxe a uložení řetězců • definice převodu znaku na číslo (ASCII kód, nebo jiný uživatelem definovaný převod) • nastavení druhu case sensitivity instrukcí, operandů, návěští • symbol čítače instrukcí v překládaném zdrojovém souboru

3.1.3

Generování kódu

Musí existovat prostředky pro definici generování kódu do zvolených částí instrukce na základě výrazů. Usoudil jsem, že pro získání obecnosti tabulkového popisu budou stačit tyto operace: • operace pro nastavení dané části instrukce na určitou hodnotu danou obecným výrazem včetně definování její šířky • operace pro přidání (a tím prodloužení) zvolené části instrukce (např. pro realizaci prefixů) • operace pro nastavení určitých bitů v určité části instrukce (jako nejvýhodnější se jeví operace OR, neboť existují procesory, u kterých by operace “nastav interval bitů” vedla k mnohem komplikovanější definici instrukcí – viz např. mikroprocesor Z80, jehož tabulkový popis jsem vytvořil1 podle [Z80]) • direktivy umožňující větvení generování na základě obecného výrazu (tedy něco jako konstrukce if-else) • operace pro vložení symbolu do tabulky symbolů překládaného zdrojového souboru pro umožnění definice návěští nebo paměťových proměnných

3.1.4

Třídy operandů

Tabulkový popis bude umožňovat definici tříd operandů spolu s možností generovat kód k danému typu operandu bez znalosti zpracovávané instrukce. Díky tomu bude možno na začátku tabulky definovat obecné operandy instrukcí a jejich překlad a v tabulce instrukcí potom budou tyto operandy pouze používány jako symboly s automatickým generováním. U instrukce se tedy pouze dogeneruje její operační kód. Překladač bude muset vnitřně podporovovat operand typu obecné hodnoty, která bude moci být i symbolická. Toto bude umožňovat použití symbolů jako návěští nebo proměnných uložených v paměti. Při překladu bude tedy tento operand využívat tabulky symbolů pro překládaný zdrojový soubor. 1

je přiložen u zdrojových kódů

10

3.1.5

Definice instrukcí

Samozřejmostí tabulky musí být definice instrukcí. Toto bude velmi usnadněno již definovanými třídami operandů. Akce u každé instrukce pouze vygeneruje její operační kód popřípadě nastaví ostatní příznaky definující konkrétní kombinaci obecných operandů.

3.1.6

Prefixy instrukcí a operandů

U každé definice prefixu bude možnost definice akce (tzn. co se vygeneruje), pokud bude tento prefix rozpoznán při zpracování zdrojového souboru v jazyku symbolických instrukcí. Pro umožnění překladu instrukcí s prefixy bude možnost definovat tyto typy prefixů: • obecný instrukční prefix, který se může vyskytnout před libovolnou instrukcí • prefix vztahující se k určitému typu operandu • prefix vztahující se pouze k určitým instrukcím

3.1.7

Podpora výrazů a symbolů v překládaném zdrojovém kódu

Tato podpora bude zajištěna zobecněním třídy rozeznávající čísla v překládaném zdrojovém souboru. Tato třída bude navíc rozpoznávat identifikátory. Její číselná hodnota bude reprezentována vytvořeným výrazovým stromem s případnými odkazy do tabulky symbolů překládaného zdrojového souboru.

3.1.8

Módy procesoru

Módy procesoru budou realizovány základní tabulkou instrukcí a operandů platných pro všechny módy procesoru a rozšiřujícími tabulkami instrukcí a operandů pro jednotlivé módy procesoru. Pro podporu těchto tabulek budou definovány další direktivy použitelné v generující části definice nebo operandu. Tyto direktivy potom umožní ruční přepnutí rozšířené tabulky. Pro automatický přechod do jiného módu procesoru bude možnost definovat akci, která se provede při tomto přechodu (např. vygenerování prefixu pro změnu šířky operandu u procesoru i386). Tento automatický přechod se provede v případě, že instrukce nebude nalezena v základní tabulce, ale v některé z rozšířených ano.

3.1.9

Podpora segmentace

Bude zajištěna přidáním příkazů pro definici segmentů, direktiv pro generování prefixů při přístupu k jiným segmentům a doplněním segmentové části ke každému symbolu ve zdrojovém souboru.

3.2

Gramatika tabulkového popisu

Příklad 3.1 gramatiky na straně 12 ukazuje základní koncepci tabulkového popisu pro řízení překladu jazyka symbolických instrukcí. Na straně 24 je ukázka použití této gramatiky při definici překladu pro procesory řady Intel x86 (příklad A.1). Nonterminály jsou v této gramatice všechny symboly, které jsou zapsány celé velkými písmeny. Ostatní symboly jsou terminální. Terminální symbol e reprezentuje prázdný řetězec.

11

TABLE TBLCMD

RETVAL ENUMS

OPTFORM PATTERN CODEBLOCK CODE STMNT ELSE MODIFCOD

PUT OR SET OPERLIST INSTRUCTS INSTR EXPR

→ → | | | | | | | | | | → | → | | | → | → | → → → | → → | | → → → → | → | → → | | | |

e | TABLE TBLCMD Endian ( IDENT ) ; Enum IDENT { ENUMS } ; InstFormat = { OPTFORM IDENT OPTFORM } ; Operand IDENT ( PATTERN ) CODEBLOCK ; OperValue IDENT ( pattern ) { CODE Return RETVAL ; } ; Option IDENT ( OPERLIST ) CODEBLOCK ; OperValOpt IDENT ( OPERLIST ) CODEBLOCK ; NumberBase IDENT ( NUMBER ) ; GInstPrefix ( STRING ) CODEBLOCK ; OperPrefix ( PATTERN ) CODEBLOCK ; Instructions { INSTRUCTS } ; $ NUMBER NUMBER STRING STRING = NUMBER ENUMS , STRING ENUMS , STRING = NUMBER [ IDENT ] OPTFORM [ IDENT ] STRING STRING , OPERLIST { CODE } e | CODE STMNT MODIFCOD If ( EXPR ) CODEBLOCK ELSE e | Else CODEBLOCK SET ( IDENT , EXPR ) ; PUT ( IDENT , EXPR ) ; OR ( IDENT , EXPR ) ; PutB | PutW | PutD | PutF | PutQ OrB | OrW | OrD | OrF | OrQ SetB | SetW | SetD | SetF | SetQ IDENT OPERLIST , IDENT INSTR INSTRUCTS INSTR ( PATTERN ) : CODEBLOCK EXPR BINOPER EXPR UNOPER EXPR ( EXPR ) $ NUMBER NUMBER

Příklad 3.1: Základní koncept gramatiky tabulkového popisu

12

V této gramatice nejsou rozgenerovány tyto nonterminály: IDENT – identifikátor STRING – řetězec znaků uzavřený z obou stran uvozovkami NUMBER – reprezentuje obecné číslo libovolné šířky UNOPER – standardní unární operátory BINOPER – reprezentuje standardní operátory jazyka C bez přiřazovacích operátorů, není zde naznačena priorita těchto operátorů, ale je stejná jako v jazyce C.

3.3

Základní struktura a princip překladače

Tabulkou řízený překladač lze rozdělit na několik základních modulů – viz obrázek 3.1. Tabulkový popis musí být nejdříve zpracován a přeložen do vnitřní reprezentace. To zajistí

Table

Source

TableCompiler

OperandsTree

InstructionsTree

Context

Compiler SymbolTable InstructionParts

IntermediateCode

BinaryCode Obrázek 3.1: Konceptuální struktura překladače

13

modul TableCompiler, který z tabulky vytvoří strom instrukcí a operandů. Překlad zdrojového souboru v tabulkou definovaném jazyku symbolických instrukcí bude prováděn modulem Compiler. Ten nejdříve požádá o kontext jedné instrukce ze zdrojového souboru. Čtení zdrojového souboru po požadovaných úsecích zajišťuje třída Context. Compiler bude tedy prohledávat strom instrukcí až nalezne určitou množinu instrukcí, které by mohly odpovídat překládané instrukci. Z této množiny nejpravděpodobnějších instrukcí se potom zkouší jednotlivé instrukce tak, že se překladač snaží přijmout operandy, které hledá ve stromu operandů. Protože je zaznamenáváno, na které pozici se ukončilo přijetí celé instrukce i s operandy, vybere se pro generování instrukce, jejíž přijetí skončilo na nejzazší pozici. Tím je zajištěn výběr správné instrukce. Pro vybranou instrukci se potom spustí generování kódu. Akce pro generování kódu jsou obsaženy jak v obecných operandech tak v instrukcích. Generování kódu se tedy provede grafovou interpretací stromu akcí překládané instrukce. Tím se modifikují patřičné části instrukce. Toto generování však ještě není konečné, jednotlivé části instrukce totiž mohou obsahovat nedopočítané výrazy, protože je nebylo možné spočítat. Důvodem pro to totiž může být, že překládaná instrukce obsahuje symbolický odkaz, jehož hodnota zatím není známá – ve výrazu se odkazuje do tabulky symbolů. Takto částečně vygenerovaná instrukce se přidá na konec generovaného mezikódu, který se může odkazovat do tabulky symbolů. Po zpracování celého zdrojového souboru by měly být známé hodnoty všech symbolů. To umožní překlad mezikódu do cílového binárního kódu dopočítáním nedopočítaných výrazů.

3.4

Hierarchie tříd tabulkového popisu

Na obrázku 3.2 na straně 15 je znázorněna hierarchie tříd umožňujících vnitřní reprezentaci tabulkového popisu. Nyní bude stručně popsán význam a přiblížena funkce nejdůležitějších tříd reprezentujících tabulkový popis jazyka symbolických instrukcí.

3.4.1

Třída Table

Tato třída zapouzdřuje tabulku instrukcí a operandů do jednoho celku. Díky tomuto zapouzdření nebude v budoucnu složité implementovat módy procesoru prostým zapouzdřením více podtabulek instrukcí a operandů spolu s doplněním metod pro jejich přepínání. Zavedením vlastností umožňujících implicitní přepínání mezi tabulkami bude potom možné realizovat i např. 32 bitové operandy v 16 bitovém módu procesoru Intel 386. Toto bude navenek efektivně skryto, protože stále bude používáno již definované rozhraní této třídy. Konkrétně jde o metody pro vložení instrukcí a operandů a metoda pro vyhledávání instrukcí.

3.4.2

Abstraktní bázová třída Symbol

Definuje rozhraní obecného symbolu překládaného zdrojového souboru v jazyku symbolických instrukcí. Od této třídy jsou odvozeny například třídy SubString, Pattern, OperandBase, atd. Rozhraní definuje dvě základní metody: TryContext() – Zkusí přijmout část vstupního řetězce z kontextu, vrací změněný kontext a nastavuje příznak o (ne)přijetí. Při prohledávání stromu instrukcí a operandů se pro vybrané instrukce (které jsou také odvozeny od třídy Symbol) vyvolává tato metoda a generuje se potom ta instrukce, jejíž přijetí zpracovalo největší část kontextu. 14

1+

1+

Table

Symbol

SymOperTable

InstrTable OperandBase

OperValueBase

OperNumeric Enum ExprArgN

OperOption

SubString

Pattern

Operand

OperValueOption

ExecPattern

Executable

OperValuePattern CmdIfElse

Commands

Expression CmdModifCode

ExprBinary

Instruction

ExprNumber

CmdNOP

ExprUnary

Obrázek 3.2: Hierarchie tříd reprezentujících tabulkový popis

WorkOut() – Tato metoda je velmi podobná předchozí pouze s tím rozdílem, že zde už se ví, která instrukce se má generovat. Tato metoda tedy znovu zpracovává původní kontext a po každém zpracování nějaké části provede následník třídy Symbol nějakou akci, odpovídající jeho charakteru (např. generování kódu, vytváření výrazového stromu, . . . ).

3.4.3

Třída Pattern

Tato třída je základním kamenem všech instrukcí a operandů. Váže k sobě libovolný počet symbolů, takže pokud se zpracovává vstupní řetězec, všechny symboly musí něco úspěšně přijmout aby se objekt této třídy označil za úspěšně přijatý. V tabulce, popisující jazyk symbolických instrukcí, je této třídy využito při definici operandů a instrukcí pomocí základního řetězce se zástupnými znaky, které budou potom nahrazeny symboly zapsanými za tímto řetězcem.

3.4.4

Abstraktní bázová třída OperandBase

Slouží jako rozhraní všech typů operandů. Definuje symbolické jméno operandu používané v tabulkovém popisu, podle kterého se také řadí ve stromu operandů. Protože je také odvozena od třídy Symbol, její následníci mohou být součástí vzorku definovaného objekty třídy Pattern.

15

3.4.5

Abstraktní bázová třída OperValueBase

Třídy odvozené od této bázové třídy reprezentují operand, který získává při zpracování kontextu určitou hodnotu. Tato třída definuje metodu, kterou se získá výrazový strom odpovídající získané hodnotě. Zděděním této třídy je tedy možné snadno vytvářet třídy jako Enum, třídy čísel v různých soustavách, atd. Obecnost jejího rozhraní v budoucnu navíc umožní snadné doplnění zpracování výrazů a symbolických hodnot v překládaném zdrojovém kódu. Dynamické přetypování ukazatele na třídu Symbol na ukazatel na tuto třídu se používá pro zjištění, zda jde o argument, který potom bude možno použít při generování kódu.

3.4.6

Abstraktní bázová třída Executable

Definuje rozhraní objektů s určitou akcí (generování kódu a podobně). Všechny instrukce a operandy osbahují ukazatel na strom kódu, který bude vykonán po přijetí operandu (instrukce). Vytvořením nového následníka této třídy lze relativně snadno přidat další příkazy použitelné v akční části definic operandů nebo instrukcí.

3.4.7

Abstraktní bázová třída Expression

Následníci této třídy realizují obecný výrazový aparát, který lze použít v tabulce při definici akcí operandů nebo instrukcí. V tabulce je tedy možné použít standartní operátory jazyka C, které nemodifikují argumenty. Priorita těchto operátorů je také v souladu s jazykem C.

3.4.8

Třída ExprArgN

Tato třída je zajímavá tím, že umožňuje použití operandů s hodnotou (tedy tříd odvozených od OperValueBase) ve výrazu, který je argumentem akce v definici operandu nebo instrukce v tabulce. Protože při zpracování (překladu) tabulkového popisu není možné při vyhodnocování zajistit nahrazení odkazu na parametr přímo tímto parametrem, je nutné před vyhodnocením výrazového stromu nahradit instance této třídy odkazem na konkrétní hodnoty zpracovávaných operandů při překladu instrukce ze zdrojového souboru. Tohoto přístupu bylo nutné použít proto, protože v jedné instrukci se může vyskytnout dvakrát tentýž operand. Při takovémto výskytu by použitím přímo symbolického jména ve výrazu nebylo možné odlišit, zda jde o první nebo o druhý argument instrukce. Proto jsem zvolil přístup k hodnotám operandů ve výrazech přes jejich indexy. Další informace viz. problém opakování argumentu v části 3.6 na straně 18.

3.5

Hierarchie tříd tabulkou řízeného překladače

Na obrázku 3.3 na straně 17 je znázorněna hierarchie tříd vlastního překladače řízeného tabulkou. Nyní bude stručně popsán princip funkce a význam nejdůležitějších tříd tohoto překladače. Source – Třída pro práci s překládaným vstupním souborem. Implementuje čtení souboru po řádcích, z nichž je vytvářen Context. Automaticky počítá řádky a zahrnuje v sobě také metody pro výpis chyb a varování vztahujících se k překládanému souboru. Allowed, Context – Tyto dvě třídy zajišťují efektivní zpracování vstupu po požadovaných úsecích. Objektem třídy Allowed se určí z jakých znaků se může skládat slovo, jež chceme 16

Allowed

Source Context

Table Compiler

-Instruction

1+

InstrToGenerate

InstPart

TargetCode

Output

CodeAtom

Expression

BitField

Obrázek 3.3: Hierarchie tříd překladače řízeného tabulkovým popisem

přečíst z objektu třídy Context. Dalším volitelným omezením je požadavek na znak následující za načteným slovem, který při uplatnění tohoto omezení, musí patřit do další množiny Allowed. Compiler – Třída řídící vlastní překlad - načte slovo z kontextu, získá iterátor na instrukce (objekty třídy Instruction) začínající načteným slovem z instance třídy Table a vyhledá nejpravděpodobnější instrukci třídy, kterou by šel přeložit vstupní kontext. Potom pro tuto instrukci vyvolá její zpracování a tím zajistí vygenerování mezikódu do částí InstPart instrukce IntstrToGenerate. Nakonec vygenerovaný mezikód přidá do TargetCode. Tento proces se opakuje dokud je co načítat ze vstupního souboru. Table – viz odstavec 3.4.1 na straně 14. TargetCode – reprezentuje generovaný mezikód, který může obsahovat ještě nedopočítané výrazy (třída Expression – viz odstavec 3.4.7 na straně 16) CodeAtom – je základní jednotkou mezikódu, zapouzdřuje v sobě bitové pole BitField, které už může mít vygenerovanou přímou hodnotu. Nebo je jeho hodnota reprezentována ještě nevypočítaným výrazovým stromem Expression. Output – definuje rozhraní mezi fyzickým výstupním binárním souborem a generovaným mezikódem. Po přeložení celého zdrojového souboru se dopočítají nedopočítané výrazy obsažené v mezikódu a bitová pole se převedou na byty, které se zapíšou do výstupního binárního souboru.

17

3.6

Problém opakování stejného operandu

U každé instrukce jsou pouze odkazy na její operandy ve stromu obecných operandů. Každý operand může být složen z více pod operandů, takže i ten se může odkazovat na jiné operandy ve stromu operandů. Při zpracování (překladu) instrukce, která má dva operandy ze stejné třídy nelze napřed zpracovat vstupní kontext a pak vygenerovat obsah operandů. Takto by se totiž hodnota prvního operandu přepsala hodnotou druhého a ve výsledné vygenerované instrukci by se tato hodnota vyskytla dvakrát. Hodnota prvního operandu by se tedy ztratila. Proto před generováním instrukce musí být vytvořen nový strom reprezentující instrukci s operandy. Toto se provádí při zpracování vstupního kontextu a postupně se nahrazují argumenty odkazující se na nějaký operand hodnotou, získanou ze vstupního kontextu. Generování instrukce se provede z tohoto nového stromu, který se potom smaže.

3.7

Problém šířky operandů

Tento problém vzniká tehdy, obsahuje-li tabulkou definovaný jazyk symbolických instrukcí dvě (více) instrukcí, které se liší pouze šířkou číselných operandů. Aby bylo možné vybrat správnou instrukci, bude nutné zavést určité ohodnocení zkoušených instrukcí. Potom instrukce, u které dojde k přetečení při zpracování číselného operandu, bude mít nižší ohodnocení, než instrukce, u které k přetečení nedojde. Správná instrukce pro generování pak bude vybrána podle nejvyššího ohodnocení.

3.8

Tabulka symbolů překládaného zdrojového kódu

Aby bylo možné používat ve výrazech překládaného zdrojového souboru symbolické hodnoty (odkazy na návěští a proměnné), bude nutné zavést tabulku symbolů pro překládaný zdrojový soubor. Toto by nemělo být příliš složité, jde pouze o vytvoření běžné tabulky symbolů a pár direktiv použitelných v tabulkovém popisu pro vkládání symbolů do této tabulky. Potom použití symbolických hodnot bude relativně snadno realizovatelné zobecněním třídy OperNumeric. Tato třída zatím reprezentuje čísla jako operandy ve zdrojovém souboru. Implementací aparátu pro zpracování výrazů do této třídy včetně umožnění odkazů do tabulky symbolů bude možné používat všechny možnosti běžných specializovaných překladačů jazyků symbolických instrukcí.

18

Kapitola 4

Implementace Prototyp tabulkou řízeného překladače jazyků symbolických instrukcí jsem implementoval v programovacím jazyku C++ v normě ISO. Při implementaci jsem využil integrovaného vývojového prostředí programu KDevelop v1.1 pod operačním systémem RedHat Linux 6.0. Pro ověření funkce implementovaného prototypu jsem vytvořil tabulkové popisy umožňující překlad podmnožiny instrukcí procesorů Intel x86 a Zilog Z80. Zdrojové testovací soubory pro tyto dva procesory jsou taktéž k dispozici.

4.1

Překlad a použití tabulkou řízeného assembleru

Kompilaci s případnou instalací provedeme posloupností těchto kroků: • příkazem cd se přesuneme do adresáře do kterého jsme předtím rozbalili zdrojové soubory • vyvoláme příkaz ./configure, kterým se zjistí konfigurace a vytvoří soubory nutné pro kompilaci • vlastní kompilaci zdrojových souborů provedeme příkazem make • příkazem make install lze provést instalaci spustitelného souboru do adresáře /usr/local/bin/ Použití: tdasm <sourcefile> kde tablefile je soubor s tabulkou popisující jazyk symbolických instrukcí sourcefile je zdrojový soubor, který chceme přeložit. Výsledkem úspěšného překladu bude binární soubor sourcefile.out. Při překladu se také generuje listing přeložených instrukcí včetně příslušných operačních kódů v hexadecimální formě. Listing se ukládá do souboru sourcefile.lst. Prozkoumáním tohoto souboru lze relativně snadno zjistit, jestli se zdrojový soubor přeložil správně.

19

4.2

Vlastnosti implementovaného prototypu

Implementovaný prototyp v tomto ročníkovém projektu je již použitelný pro překlad na jednodušší procesory. Umožňuje např.: • definici syntaxe čísel překládaného souboru v libovolné číselné soustavě • podporuje instrukce složené z více samostatných částí a jejich oddělené generování (např. část operačního kódu, část operandů, . . . ) • definice registrů a jejich hodnot které budou použity při generování kódu • operandy a instrukce je možné definovat pomocí aparátu podobnému regulárním výrazům • lze definovat obecné samo generující se operandy a ty použít u více instrukcí (přehlednější a snazší zápis, vytváření komplexních operandů) • je možné definovat množinu operandů z níž se vybere právě ten operand, který se hodí pro přeložení právě překládané instrukce – další možnost tvorby ještě více komplexnějších operandů • generování kódu je řešeno třemi základními operacemi zajišťující správnou modifikaci zvolené části instrukce • při definici generování kódu v tabulce je možno použít výrazů stejných jako v jazyce C

4.3

Nejdůležitější stávající omezení a chyby

Implementovaný prototyp obsahuje následující nedostatky: • chybný výběr instrukce existují-li dvě instrukce lišící se pouze šířkou přímého operandu – možnost správné implementace viz odstavec 3.7 na straně 18 • tabulka symbolů překládaného zdrojového souboru není implementována – možnost implementace viz odstavec 3.8 na straně 18 • překladač podporuje ve zdrojových souborech pouze čísla, ne výrazy – možnost implementace viz odstavec 3.8 • absence podpory prefixů – stačí rozšířit třídy Operand a Instruction a implementovat obecný prefix • není implementována podpora různých módů procesorů – možnost implementace viz odstavec 3.4.1 na straně 14 • překladač nepodporuje segmentaci – viz 3.1.9, str. 11

20

4.4

Přenositelnost

Protože překladač je napsán v jazyce ISO C++ a také proto, že pro reprezentaci čísel a ukládání generovaného kódu používá vlastní třídy (Number, BitField, . . . ), je tento překladač velmi dobře přenositelný na různé platformy. Pro úspěšné přeložení na libovolné platformě je nutný pouze překladač jazyka C++ splňující požadavky normy ISO, konstruktory yacc a lex a utilita sed. Přenositelnost jsem ověřil na následujících platformách: • Linux RedHat 6.0, Intel x86 kompatibilní procesor • Free BSD, procesor třídy Intel x86 • SunOS, Ultra Sparc procesor • MS-DOS (DJGPP) • MS-Widows 9x, NT (CygWin32)

4.5

Příklady přeložitelných instrukcí

Jako dodatek tohoto dokumentu jsem uvedl příklad části tabulkového popisu jazyka symbolických instrukcí procesorů Intel x86 – příklad A.1 na straně 24. Tento příklad ukazuje možnost definovat komplexní operandy charakteristické pro instrukce procesorů Intel x86. Z uvedeného příkladu tabulky je vidět, že definování operandů zabralo velkou část tabulky, ale na druhou stranu můžeme říci, že pro kompletní tabulku pro procesory Intel x86 by se to určitě vyplatilo, protože tyto operandy jsou používané u většiny instrukcí tohoto procesoru. V přiložené části tabulky jsou sice definované jen čtyři varianty pouze jedné instrukce, ale překladač dokáže zpracovat všechny základní adresovací módy a tudíž přeloží velké množství příbuzných instrukcí. Toto je dobře vidět v příkladu 4.1, který lze zpracovat tímto překladačem. ADC ADC ADC ADC ADC ADC ADC ADC ADC ADC ADC

cl, dl bh, al cx, dx bp, [0x1234] [0x5678], cx [bx], al cx, [bp] cx, [bx+di] [bp+si], bp cl, [bp+si]+0x22 [bx+di]+0x11, dh

Příklad 4.1: Ukázka zdrojového souboru zpracovatelného tímto překladačem

21

Kapitola 5

Závěr Přínos získaný touto prací Vypracováním tohoto projektu jsem získal cenné zkušenosti s tvorbou překladačů, zvláště pak s jejich objektově orientovaným návrhem. Při implementaci prototypu jsem se také výrazně zlepšil v programování v C++ a to hlavně ve využití standardní knihovny šablon (Standard Template Library – viz. [STL]) a v použití RTTI (Run Time Type Information - použito pro dynamické přetypování). Při psaní dokumentace k tomuto ročníkovému projektu jsem se naučil používat sázecí systém LATEX. V neposlední řadě jsem se také seznámil s různými vývojovými nástroji pod operačním systémem Linux.

Možnosti dalšího vývoje Možnosti dalšího vývoje tohoto projektu jsou velmi široké. Aby se tento překladač stal plně funkčním a naprosto univerzálním, existuje stále velmi mnoho vlastností, které je nutno implementovat – bližší informace viz. odstavec 4.3 na straně 20. Jedno z dalších (a zatím nediskutovaných) vylepšení by také mohla být přímá podpora instrukcí koprocesoru a čísel s pohyblivou desetinnou čárkou.

Zhodnocení dosažených výsledků Výsledek svojí práce, tedy návrh a implementaci prototypu assembleru řízeného tabulkou, považuji za velmi dobrý. Možnosti definice tabulky jsou už i u implementovaného prototypu velmi rozsáhlé. Již teď lze definovat překlad na celou řadu jednodušších procesorů. Návrh je podle mého názoru ve velmi dobrém stavu, tak že bude možné relativně snadno rozšiřovat implementovaný prototyp. Nejnovější verzi tohoto překladače spolu s tabulkami pro různé mikroprocesory a další informace naleznete na adrese http://www.penguin.cz/~niki/tdasm/ .

22

Literatura [APC] Ing. Vrátil Z.: Assembler PC, GETHON audio and computer, Sokolov, 1997 [Z80]

Ultrasoft, spol. s.r.o.: Príručka strojového kódu pre ZX Spectrum, Bratislava, 1991, ISBN 80-85440-00-8

[DP]

Dr. Gamma E., Dr. Helm R., Dr. Johnson R., Dr. Vlissides J.: Design patterns : Elements of Reusable Object-Oriented Software, 1998

[ZAP] Dr. Ing. Kolář D.: Compilers (přednášky předmětu základy překladačů), 1999 [STL]

Silicon Graphics Computer Systems, Inc.: Standard Template Libary Programmmer’s Guide, 1998, Dokument dostupný na URL: http://www.sgi.com/Technology/STL/index.html (květen 2000)

[TEX] Balvínová A., Bílý M.: Textové informační systémy, Sázecí systém LATEX - Cvičení, ČVUT 1995

23

Příloha A

Příklad tabulky pro Intel x86 Endian(LITTLE); NumberBase hexbase(16); OperValue number("0x*", hexbase) { Return $0; }; InstFormat = { [prefixes] opcode [modRM] [disp] [immd] }; Enum r8 { "al", "cl", "dl", "bl", "ah", "ch", "dh", "bh" }; Enum r16 { "ax", "cx", "dx", "bx", "sp", "bp", "si", "di" }; Enum bxbp { "bx", "bp" }; Enum sidi { "si", "di" }; Enum sidibx { "si", "di", "bx"=3 }; Enum baseregs { "si", "di", "bp", "bx" }; Operand bspbs("[*+*]", bxbp, sidi) { OrB(modRM, $1|($0<<1)); }; Operand base("[*]", baseregs) { OrB(modRM, 4|$0); }; Operand basenobp("[*]", sidibx) { OrB(modRM, 4|$0); }; Operand based16only("[*]", number) { SetW(disp, $0); OrB(modRM, 4|2); OperOption ea00(bspbs, basenobp, based16only) { }; Operand based8("*",number) { SetB(disp, $0); }; Operand bspbspd8("*+*", bspbs, based8) { }; Operand basepd8("*+*", base, based8) { }; OperOption ea01(bspbspd8, basepd8) { OrB(modRM, 1<<6); }; Operand ea11_r8("*", r8) { OrB(modRM, $0 | (3<<6)); }; Operand ea11_r16("*", r16) { OrB(modRM, $0 | (3<<6)); }; OperOption rm8(ea00, ea01, ea11_r8) { }; OperOption rm16(ea00, ea01, ea11_r16) { }; Instructions { ("ADC *,*", r8,rm8): { SetB(opcode, 0x12); OrB(modRM, $0<<3); ("ADC *,*", r16,rm16): { SetB(opcode, 0x13); OrB(modRM, $0<<3); ("ADC *,*", rm8,r8): { SetB(opcode, 0x10); OrB(modRM, $1<<3); ("ADC *,*", rm16,r16): { SetB(opcode, 0x11); OrB(modRM, $1<<3); }; Příklad A.1: Příklad definice části tabulky pro procesory řady Intel x86

24

};

} } } }