Dokumentace projektu
Interpret jazyka IFJ2011
Tým číslo 093, varianta b/3/I:
20 % bodů: Cupák Michal (xcupak04) – vedoucí týmu
20 % bodů: Číž Miloslav (xcizmi00)
20 % bodů: Černá Tereza (xcerna01)
20 % bodů: Hradecký Michal (xhrade08)
20 % bodů: Latta Martin (xlatta00)
11. 12. 2011
VYSOKÉ UČENÍ TEHNICKÉ V BRNĚ, FAKULTA INFORMAČNÍCH TECHNOLOGIÍ
Obsah
1.
2.
Implementace ............................................................................................................................................ 2
1.1
Lexikální analyzátor ........................................................................................................................... 2
1.2
Tabulka symbolů ............................................................................................................................... 3
1.3
Syntaktický analyzátor....................................................................................................................... 4
1.4
Interpret ............................................................................................................................................ 5
1.5
Řetězcové algoritmy .......................................................................................................................... 6
Práce v týmu .............................................................................................................................................. 6
2.1
Organizace ......................................................................................................................................... 6
2.2
Problémy ........................................................................................................................................... 6
2.3
Rozdělení práce ................................................................................................................................. 7
3.
Metriky ....................................................................................................................................................... 7
4.
Použité zdroje ............................................................................................................................................ 7
1
1. Implementace
Překladač se skládá z částí popsaných na přednáškách předmětu IFJ a je spojen do celku programem
zapsaným v souboru main.c.
1.1 Lexikální analyzátor
Lexikální analyzátor je částí projektu zpracovávající bezprostředně zdrojový kód vstupního programu. Je
důležitý především svou funkcí scanner_dalsi_token, která načítá a vrací následující typ tokenu včetně jeho
řetězcové reprezentace (komentáře v souboru jsou automaticky přeskakovány). Funkce rovněž vrací pozici
tokenu v souboru kvůli případnému chybovému výpisu. Chyba alokace paměti pro interní řetězec je indikována
vrácením speciálního typu tokenu TYP_CHYBA_ALOKACE. Zbývající dvě funkce lexikálního analyzátoru slouží k
otevření a zavření zdrojového souboru.
Lexikální analyzátor je implementován jako konečný automat, jehož funkce je popsána níže uvedeným
grafem. Automat rozezná základní typ tokenu, načež se může stát, že ten bude dále upřesněn – např. klíčové
slovo se nejprve načte jako identifikátor a až posléze se porovnáním s každým z množiny daných řetězců
dospěje k tomu, že se jedná o klíčové slovo. Podobným způsobem se řeší korektnost načteného řetězcového
literálu. Tento způsob implementace byl zvolen za cílem redukovat jinak zbytečně velký počet stavů konečného
automatu.
Načítání teoreticky nekonečného řetězce je vyřešeno alokací místa v paměti o určité konstantní velikosti
(tedy klasický načítací buffer). Na toto místo se postupně načítají znaky a při dosažení hranice vymezeného
prostoru je paměťový prostor navýšen opět o konstantní velikost.
Obrázek 1 - konečný automat lexikálního analyzátoru
2
1.2 Tabulka symbolů
Tabulka symbolů slouží v programu k ukládání informací o proměnných a funkcích. Využívá se jak
v syntaktické a sémantické analýze, tak při interpretaci. Skládá se ze dvou částí implementovaných jako binární
vyhledávací stromy, kde klíčem uzlu je textový řetězec. Tyto dvě části jsou:


globální tabulka symbolů – uchovává informace o funkcích
lokální tabulka symbolů – uchovává informace o proměnných
Obrázek 2 – tabulka symbolů
každá položka globální tabulky obsahuje jedinečný identifikátor funkce a počet jejích parametrů, aby bylo
možné během syntaktické analýzy určit, kolik parametrů se má při volání funkce doplnit, popř. ignorovat. Dále
má každá položka svou vlastní lokální tabulku, tzn. každá funkce si uchovává informace o svých proměnných
(do těchto proměnných se počítají i parametry funkce). Tabulka jakožto abstraktní datový typ definuje množinu
funkcí pro práci s ní, např. pro vkládání, vyhledávání pomocí klíče, nebo výpis celé tabulky včetně všech
lokálních tabulek pro případné ladění.
Obdobně se do lokální tabulky ukládají identifikátory proměnných, stejně jako jejich datové typy a hodnoty
(tyto informace se však využijí až při interpretaci). Lokální tabulka rovněž nabízí funkce pro vkládání,
vyhledávání, ukládání hodnot, výpis, apod.
3
1.3 Syntaktický analyzátor
Syntaktický analyzátor kontroluje syntaktickou správnost zdrojového programu a řídí jeho překlad do námi
navrženého tříadresného kódu (přeskakujeme tedy generování abstraktního syntaktického stromu). Kvůli
jednoduchosti sémantické analýzy jazyka IFJ2011 se navíc stará i o ni (kontrola datových typů a již
deklarovaných proměnných). Tato část programu je nejsložitější a proto je rozdělena na dvě úzce provázané
části:


obecný syntaktický analyzátor
syntaktický analyzátor výrazů
Obecný syntaktický analyzátor (dále jen obecný SA) zpracovává obdržené tokeny rekurzivním sestupem
podle následující LL gramatiky:
START
->
FUNC
->
FUNC
->
PARAMS
->
PARAMS
->
PARZBYT
->
PARZBYT
->
DEKLARACE ->
DEKLARACE ->
LOCALZBYT ->
LOCALZBYT ->
FORMAT
->
FORMAT
->
FPARAM
->
FPARAM
->
FPARAMZBYT ->
FPARAMZBYT ->
PRIKAZY
->
PRIKAZY
->
PRIKAZY
->
PRIKAZY
->
PRIKAZY
->
PRIKAZY
->
IDRZBYT
->
IDRZBYT
->
IDRZBYT
->
VV
->
VV
->
VZ
->
VZ
->
FUNC ;
function id-funkce ( PARAMS ) DEKLARACE PRIKAZY end FUNC
e
id PARZBYT
e
, id PARZBYT
e
e
local id LOCALZBYT
; DEKLARACE
= literal ; DEKLARACE
retezec
cislo
literal-id FPARAMZBYT
e
, literal-id FPARAMZBYT
e
e
id = IDRZBYT
write ( VV ) ; PRIKAZY
if VYRAZ then PRIKAZY else PRIKAZY end ; PRIKAZY
while VYRAZ do PRIKAZY end ; PRIKAZY
return VYRAZ ; PRIKAZY
read ( FORMAT ) ; PRIKAZY
VYRAZ ; PRIKAZY
id-funkce ( FPARAM ) ; PRIKAZY
VYRAZ VZ
e
, VYRAZ VZ
e
4
Syntaktický analyzátor výrazů (dále jen SA výrazů) pracuje zdola-nahoru, a to metodou precedenční
syntaktické analýzy. Využívá k tomu níže uvedenou gramatiku a precedenční tabulku. SA výrazů je volán
obecným SA vždy, když je na vstupu očekáván výraz. SA výrazů tento výraz analyzuje ze syntaktického i
sémantického hlediska a vytvoří příslušné instrukce tříadresného kódu. Obecnému SA vrátí výsledek výrazu
(přesněji vrátí odkaz na místo vytvořené v tabulce symbolů, kam se při samotné interpretaci uloží výsledek
daného výrazu).
I -> CISLO
I -> ID
E -> E / E
E -> E > E
I -> RETEZEC
E -> I
E -> E + E
E -> E <= E
I -> TRUE
E -> (E)
E -> E – E
E -> E >= E
I -> FALSE
E -> E ^ E
E -> E .. E
E -> E == E
I -> NIL
E -> E * E
E -> E < E
E -> E ~= E
Obrázek 3 - precedenční tabulka
1.4 Interpret
Interpret zajišťuje provádění vygenerovaného tříadresného kódu. Jako součást projektu přímo navazuje na
syntaktický analyzátor (optimalizátor i generátor vnitřního kódu jsme se rozhodli vynechat, abychom zachovali
jednoduchost). V případě úspěchu syntaktické analýzy je interpretu předán lineární seznam instrukcí námi
navrženého tříadresného kódu, jenž může obsahovat následující instrukce:
INSTRUKCE_MOCNINA
INSTRUKCE_SOUCET
INSTRUKCE_MENSI
INSTRUKCE_VETSI_ROVNO
INSTRUKCE_TYPE
INSTRUKCE_SORT
INSTRUKCE_RETURN
INSTRUKCE_LABEL
INSTRUKCE_READ_POCET
INSTRUKCE_READ_L
INSTRUKCE_NASOBENI
INSTRUKCE_ROZDIL
INSTRUKCE_VETSI
INSTRUKCE_NEROVNOST
INSTRUKCE_SUBSTR
INSTRUKCE_PRIRAZENI
INSTRUKCE_PUSH
INSTRUKCE_GOTO
INSTRUKCE_KONEC
INSTRUKCE_READ_A
5
INSTRUKCE_DELENI
INSTRUKCE_KONKATENACE
INSTRUKCE_MENSI_ROVNO
INSTRUKCE_ROVNOST
INSTRUKCE_FIND
INSTRUKCE_CALL
INSTRUKCE_POP
INSTRUKCE_GOTOIF
INSTRUKCE_WRITE
INSTRUKCE_READ_N
Každá instrukce dále obsahuje tři obecné ukazatele – dvě adresy operandů a jednu adresu výsledku. Jedná
se většinou o adresy proměnných v lokální tabulce, ale může jít i o jiný typ ukazatele (např. ukazatel do globální
tabulky v případě volání funkce). Důležité je, že každá instrukce očekává přesně daný typ ukazatelů, který se
nesmí porušit.
Předávání parametrů při volání funkcí je řešeno pomocí zásobníku, na který se ukládají kopie uzlů lokální
tabulky (tedy hodnoty proměnných). Stejným zásobníkem je řešeno i předávání návratových hodnot (před
každým příkazem return ve funkci se tedy provádí instrukce INSTRUKCE_PUSH nad návratovou hodnotou a po
každém volání se provádí INSTRUKCE_POP). Volání funkcí navíc vyžaduje zajištění návratu na správnou adresu
po příkazu return, k čemuž slouží zásobník návratových adres, do nějž lze zároveň ukládat ukazatele na kopie
lokálních tabulek vznikajících při případném rekurzívním volání.
1.5 Řetězcové algoritmy
Řazení pole znaků je řešeno algoritmem Shell sort, pracuje tedy in situ a není nutné alokovat další prostor
pro samotné řazení, jenom je nutné mít právo přepisování předané paměti. Nestabilita této metody nám
nevadí, jelikož se neřadí složitější struktury, ale pouze znaky.
K vyhledávání podřetězci byl využit Boyer-Mooreův algoritmus. Inspirací nám byla verze ze studijní opory
k předmětu IAL, nicméně jsme ji napsali podle vlastního pochopení této metody.
2. Práce v týmu
2.1 Organizace
Náš tým pořádal nepravidelná setkání průměrně jednou každý týden. To nám pomohlo pravidelně
diskutovat aktuální problémy, programovat ve více lidech apod. Jako nástroj komunikace mimo školu jsme
používali IM program. Zdrojové kódy jsme sdíleli přes program Dropbox, který se ale příliš neosvědčil, zejména
kvůli zmatku v souborech. Příště bychom použili některý z programů specializovaných na správu verzí. Se
značnou částí návrhu nám pomohla konzultace s odborným asistentem.
Rozdělování práce neprobíhalo striktně, všichni členové týmu si pomáhali navzájem. Při práci na projektu
jsme navíc zjistili, jak důležité je testování, kterým jsme strávili podstatnou a velmi poučnou část projektu.
Rovněž návrh a dodržování rozhraní v rámci programu byli velmi důležité. Velmi nám pomohlo soustředit se na
dokončení určité části překladače do termínu pokusného odevzdání, protože bychom se nejspíš potýkali
s mnohem většími časovými problémy, kdybychom začali na programu pracovat později.
Dále jsme se snažili psát čitelný a dostatečně komentovaný kód dodržující zavedená pravidla tvoření
identifikátorů napomáhající k větší přehlednosti a vůbec dodržovat obecné zásady efektivního programování.
Do jisté míry jsme se snažili zachovávat i zapouzdřenost jednotlivých částí programu, i když se nám to ne vždy
povedlo.
2.2 Problémy
Projekt byl pro nás problematický především v tom, že jsme až do pozdního stadia semestru neznali princip
všech částí překladače, přičemž v té době jsme ho již měli velkou část implementovanou. Z toho plynuly
problémy se změnou rozhraní nebo i celé funkčnosti již napsaných částí, přepisování nebo i zahazování již
napsaných částí kódu. To vše umocňoval časový stres těsně před odevzdáním, kdy jsme projektu museli všichni
věnovat dvě až šest hodin denně, abychom vše stihli.
Stejně tak jsme se potýkali s nevhodným návrhem některých částí překladače, což byla většinou čistě naše
chyba. V závěru jsme museli řešit například nevhodně navržené předávání parametrů funkcím, přičemž jsme
nakonec dospěli ke klasickému předávání pomocí zásobníku. Jeho implementace se nicméně nezdařila příliš
6
efektivně, protože nám návrh lokální tabulky neumožňuje vkládat na zásobník pouze hodnoty, což by
postačovalo, ale nutí nás ukládat celé uzly lokální tabulky. Příště bychom tedy datovou strukturu, představující
proměnnou, zcela oprostili od způsobu implementace lokální tabulky.
2.3 Rozdělení práce
Úkoly v týmu byly zhruba rozděleny takto:
Martin Latta - obecný syntaktický analyzátor, celková syntaktická analýza
Michal Cupák - syntaktický analyzátor pro výrazy, organizace a vedení týmu
Michal Hradecký – interpret, pom. práce na ostatních částech
Miloslav Číž - lexikální analyzátor, tabulka symbolů, dokumentace
Tereza Černá – řetězcové algoritmy, tabulka symbolů, pom. práce na ostatních částech
3. Metriky
počet všech zdrojových souborů: 20
celkový počet řádků: 5555
velikost spustitelného programu (bez debugovacích informací, Linux 64bit): 83 376 bytů
velikost spustitelného programu (bez debugovacích informací, Windows 64bit): 90 409 bytů
4. Použité zdroje



přednášky a studijní opora předmětu IFJ
přednášky a studijní opora předmětu IAL
konzultace s odborným asistentem
7
Download

Interpret jazyka IFJ2011