Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva
Prevođenje programskih jezika
Dokumentacija o izgradnji i radu ostvarenog jezičnog procesora
Voditelj: Leo Osvald
Grupa: 03
Lovro Biočić
Ana Grđan
Josip Juričić
Saša Ledinščak
Hrvoje Novak
Marin Pranjić
Matko Raguž
Marko Sršan
Zagreb, siječanj 2011. godine
UVOD
Ova tehnička dokumentacija je nastala kao rezultat laboratorijskih vježbi iz kolegija Prevođenje programskih jezika na Fakultetu elektrotehnike i računarstva. Tokom laboratorijskih vježbi se izgrađivao vlastiti jezični procesor koje prevodi zadani podskup jezika C u mnemonički jezik vrlo sličan FRISC-u, a sve s ciljem boljeg razumijevanja kako jezični procesor radi.
Lovro Biočić - testiranje izgradnje automata na temelju regularnih izraza (pisanje JUnit testova)
Ana Grđan - testiranje leksičke analiza (pisanje primjera ulaz/izlaz), pomoć pri pisanju JUnit testova za testiranje generacije tablice parsiranja
Josip Juričić - testiranje izgradnje regularnih izraza, pisanje testova za parsiranje, testiranje raznih stvari oko generacije koda (uglavnom pisanje JUnit testova), pisanje primjera raznih programa, pomoć u kodiranju
Saša Ledinščak - testiranje leksičke analiza (pisanje primjera ulaz/izlaz), pisanje pisanej JUnit testova za testiranje pretvorbe NKA u DKA kod generatora parsera, debugiranje pretvorbe NKA u DKA
Hrvoje Novak - učitavanje kod generatora leksera, debugiranje leksičkog analizatora, izrada GUI-ja za kompajler
Marin Pranjić - pisanje koda vezanog uz generaciju koda na temelju već izgrađenih opisnika (*Descriptor), pisanje koda za pretvorbu NKA sa LR1 stavkama u DKA sa LR1 stavkama
Matko Raguž - pisanje testova za parsiranje
Marko Sršan - izrada prvog dijela dokumentacije (općenite stvari)
Leo Osvald - ostatak (skoro svo programiranje, ostatak testiranja i dokumentacije)
Jezični procesori se dijele u dvije skupine ovisno o tome dali generiraju ciljni program za računalo koje prevodi izvorni program ili za neko drugo računalo. Uobičajeno je da jezični procesor generira ciljni program koji se izvodi na istom računalu. No, premosni prevoditelji su jezični procesori koji prevode izvorni u ciljni program na jednom računalu, a generirani ciljni program se izvodi na drugom računalu.
Jezični procesor je program koji se gradi primjenom jednog od programskih jezika. Većina današnjih jezičnih procesora gradi se primjenom viših programskih jezika ili primjenom posebno izgrađenih programskih alata koji su namijenjeni upravo izgradnji jezičnih procesora.
Jezični procesori (eng. compiler) su računalni programi koji služe prevođenju iz nekog izvornog u istovjetni ciljni programski jezik, što je prikazano sljedećom slikom.
Izrađeni jezični procesor u potpunosti je implementiran u programskom jeziku Java. Izvorni jezik Li je nalik na programski jezik C, međutim, s ograničenom funkcionalnošću. Ciljni jezik Lc jezičnog procesora jest mnemonički jezik vrlo sličan FRISC-u.
Slika 1 - Pogled na arhitekturu prevoditelja
Leksička analiza je prvi korak u radu jezičnog procesora. To je proces čitanja znakova izvornog programa te njihovog raščlanjivanja u osnovne elemente jezika koji se nazivaju leksičke jedinke (eng. lexical tokens). Leksička analiza vrši se pomoću programa leksičkog analizatora. Leksički analizator grupira ulazne znakove u leksičke jedinke, provjerava leksička pravila, zapisuje leksičke jedinke u tablicu znakova i generira niz uniformnih znakova leksičkih jedinki, koji se potom predaje na sintaksnu analizu koja čini drugi korak u radu jezičnog procesora.
Za potrebe leksičke analize, bilo je potrebno izgraditi generator leksičkog analizatora po uzoru na program Lex. Razlog za izgradnju općenitog generatora leksičkog analizatora leži u činjenici da sama izgradnja daje bolji uvid u način rada leksičke analize bilo kojeg programskog jezika.
Slika 2 – Način rada leksičkog analizatora
Način rada generatora leksičkog analizatora prikazan je Slikom 2. Generator leksičkog analizatora kojeg je potrebno ostvariti treba prihvaćati opis procesa leksičkog analizatora zadan tekstualnom datotekom (dalje Ulazna Datoteka). Izlaz iz generatora leksičkog analizatora treba biti izvorni kod leksičkog analizatora napisan u jeziku izgradnje (koji je proizvoljan). Ulazna Datoteka bit će zadana u sljedećem formatu:
regularne definicije
%X stanja leksičkog analizatora
%L imena leksičkih jedinki
pravila leksičkog analizatora
Izlaz iz generatora leksičkog analizatora je izvorni kod leksičkog analizatora pisan u jeziku izgradnje jezičnog procesora. Dio koda leksičkog analizatora potpuno je neovisan o Ulaznoj Datoteci.
Sintaksna analiza je središnji dio analize programa. Sintaksni analizator čita uniformne znakove leksičkih jedinki, grupira ih u sintaksne cjeline, stvara hijerarhiju sintaksnih cjelina te provjerava sintaksna pravila. Osnovne sintaksne cjeline su izrazi, naredbe, blokovi naredbi i program. Sintaksna pravila odreduju dopuštene strukture naredbi, izraza te čitavog programa. Ukoliko program ne zadovoljava sintaksna pravila, sintaksni analizator odredi mjesto pogreške, ispiše opis pogreške te nastavi s daljnjom analizom.
Generator sintaksnog analizatora se izgradio po uzoru na program Yacc, ali u bitno pojednostavljenom obliku. Generirani sintaksni analizator za parser koristi LR(1) kanonski parser koji je odabran zbog jednostavnije izgradnje generatora. Slično kao kod leksičke analize, izgrađenim generatorom sintaksnog analizatora se uz odgovarajuću ulaznu datoteku generira sintaksni analizator za podskup jezika C.
Slika 3 – način rada sintaksnog analizatora
Generator sintaksnog analizatora prihvaća opis procesa sintaksnog analizatora zadan tekstualnom datotekom dok je izlaz iz generatora sintaksnog analizatora izvorni kod sintaksnog analizatora napisan u jeziku izgradnje. Pritom je ulazna datoteka zadana u sljedećem formatu:
%V nezavršni znakovi gramatike
%T završni znakovi gramatike
%Syn sinkronizacijski završni znakovi
produkcije gramatike
Uloga sintaksnog analizatora je parsiranje niza uniformnih znakova - sintaksni analizator treba provjeravati zadovoljava li napisani program sintaksna pravila zadana gramatikom u Ulaznoj Datoteci te konstruirati generativno stablo za dani program. Konstruirano generativno stablo će se koristiti u daljnjim fazama rada jezičnog procesora. Tablica znakova se neće mijenjati, već će se iz nje isključivo dohvaćati grupirani nizovi znakova koji odgovaraju određenom uniformnom znaku u nizu uniformnih znakova.
Semantički analizator ključan je dio postupka prevođenja programskog jezika. Dvije su glavne zadaće semantičkog analizatora – provjera semantičkih pravila napisanog programa te obilježavanje sintaksnih cjelina semantičkim obilježjima. Semantička obilježja koriste se prilikom faze generiranja međukoda koja prethodi fazi generiranja ciljnog programa. Semantička analiza je most koji povezuje fazu analize izvornog programa s fazom sinteze ciljnog programa. Pritom se najvažnijim korakom smatra određivanje značenja svih elemenata jezika, počevši od onih najjednostavnijih leksičkih jedinki, do najsloženijih sintaksnih struktura kao što su izrazi i naredbe.
Da bi se cjelokupni projekt mogao kompajlirati, potrebno je imati instalirano sljedeće:
Na operacijskim sustavima Ubuntu Linux, Debina GNU/Linux (ili nekim drugim *NIX-om koji koristi apt sustav ), moguće je oboje instalirati sa sljedećom naredbom:
$ sudo apt-get install sun-java6-jdk maven2
dok je na ostalim operacijskim sustavim mogu skinuti potrebni alati na sljedećim web adresama:
Pretpostavimo da se gore navedeni alati nalaze u sistemskoj putanje (engl. system path-u).
$ unzip spocc-src.zip
$ mvn package
Ovaj korak može potrajati i do par minuta, budući da se najprije kompajlira, zatim se pokreću svi testovi, i konačno se pripremaju izvršne .jar datoteke. Ako je sve dobro prošlo, ispis bi trebao završavati sa nečim poput sljedećeg:
----------------------------------------------------------------
[INFO] BUILD SUCCESSFUL
[INFO] ----------------------------------------------------------------
[INFO] Total time: 58 seconds
[INFO] Finished at: Sun Jan 09 19:35:31 CET 2011
[INFO] Final Memory: 61M/325M
[INFO] ----------------------------------------------------------------
Ovime su se izgenerirale izvršne .jar datoteke unutar odgovarajućeg target direktorija za svaki od programa koji se može pokretati. Međutim, bez specificiranja classpath-a na biblioteke i ostale dependency-je moguće je pokretati samo one koje završavaju sa .one-jar.jar, dakle:
One predstavljaju program jezičnog procesora za podskup jezika C (komandno-linijski), grafičko sučelje za njega, program generator leksičkog analizatora, program generator sintaksnog analizatora, respektivno.
Bilo da smo kompajlirali po gore napisanoj uputi ili jednostavno uzeli gotove izvršne .jar datoteke, sada imamo na raspolaganju sljedeće programe koji se mogu pokrenuti na uobičajen način pokretanja Java programa zapakiranih u .jar arhive:
Primjer pokretanja jezičnog procesora (spocc-core):
$ java -jar spocc-core.jar
Usage: Spocc source-file [{-a, --assembly-file} file] [--symbol-table file] [--token-list file] [--parse-tree file] [--parse-tree-human-readable] [--ignore-lexical-errors] [{-v, --verbose}]
Note: instead of file "-" (without quotes) can be put to print to standard out
Na analogan način se pokreću i ostala dva programa (generatori).
U sklopu projekta napravljen je samostalni program generator leksičkog analizatora.
To je komandno linijski program koji ima sličnu namjenu kao program LEX, s razlikom da ovaj generira izvorni kod u programskom jeziku Java.
$ java -jar spocc-lag.jar
Usage: Main lexical-rules-file [{-o, --output-dir} path]
$ java -jar spocc-lag.jar /tmp/srbljic-151-lexical-rules.def -o /tmp/src
Ovime će se u direktoriju /tmp/src izgenerirati kod za ostavrenje leksičkog analizatora, koristeći sintakstna pravila definirana u datoteci /tmp/srbljic-151-lexical-rules.def.
/tmp/src
`-- hr
`-- fer
`-- spocc
|-- lexer
| |-- action
| | |-- _Action1.java
| | |-- _Action2.java
| | |-- _Action3.java
| | |-- _Action4.java
| | |-- _Action5.java
| | |-- _Action6.java
| | |-- _Action7.java
| | `-- _Action8.java
| |-- _GeneratedMain.java
| |-- _LexerDescriptorFactory.java
| |-- nfa
| | |-- _NfaFactory1.java
| | |-- _NfaFactory2.java
| | |-- _NfaFactory3.java
| | |-- _NfaFactory4.java
| | |-- _NfaFactory5.java
| | |-- _NfaFactory6.java
| | |-- _NfaFactory7.java
| | `-- _NfaFactory8.java
| `-- _State.java
`-- _TokenType.java
Generator će prije generiranja koda počistite sve poddirektorije direktorije odredišnog direktorija unutar kojeg će stvoriti bar jednu izvornu datoteku. Ovo služi da ako se više puta generira u isti direktorij kod za jezik s drugim leksičkim pravilima, da nema konflikata.
GeneratedMain_ je generirani program koji obavlja leksičku analizu, ali obzirom na svoju ograničenost najčešće nije od pretjerane koristi. Od ključnog značaja je izgenerirana klasa _LexerDescriptorFactory - upravo instancu tog objekta traži apstraktna implementacija leksičkog analizatora AbstractLexer u svom konstruktoru. Jednom kad se stvori objekt ove klase, može se pomoću implementacija sučelja Lexer (npr. DefaultLexer koji nasljeđuje AbstractLexer) ostvariti leksički analizator za jezik opisan leksičkim pravilima u datoteci koja je predana putem komandne linije u generatoru.
U sklopu projekta napravljen je samostalni program generator sintaksnog analizatora, odnosno njegovih dijelova. To je komandno linijski program koji ima sličnu namjenu kao program YACC,, s razlikom da ovaj generira izvorni kod u programskom jeziku Java.
$ java -jar spocc-sag.jar
Usage: Main syntax-rules-file [{-o, --output-dir} path] [{-t, --generate-token-types}] [{-c, --use-c-precomputed}] [{-v, --verbose}]
$ java -jar spocc-sag.jar /tmp/srbljic-151-syntax-rules.def -o /tmp/src --generate-token-types
Ovime će se u direktoriju /tmp/src izgenerirati kod za ostavrenje sintaksnog analizatora, koristeći sintaksna pravila definirana u datoteci /tmp/srbljic-151-lexical-rules.def.
U slučaju da već imamo izgenerirane izvorne datoteke za potrebe ostvarenja leksičkog analizatora, sada bismo imali sljedeće datoteke:
/tmp/src/
`-- hr
`-- fer
`-- spocc
|-- lexer
| |-- action
| | |-- _Action1.java
| | |-- _Action2.java
| | |-- _Action3.java
| | |-- _Action4.java
| | |-- _Action5.java
| | |-- _Action6.java
| | |-- _Action7.java
| | `-- _Action8.java
| |-- _GeneratedMain.java
| |-- _LexerDescriptorFactory.java
| |-- nfa
| | |-- _NfaFactory1.java
| | |-- _NfaFactory2.java
| | |-- _NfaFactory3.java
| | |-- _NfaFactory4.java
| | |-- _NfaFactory5.java
| | |-- _NfaFactory6.java
| | |-- _NfaFactory7.java
| | `-- _NfaFactory8.java
| `-- _State.java
|-- parser
| |-- _Filler0.java
| `-- _ParsingTableFactory.java
`-- _TokenType.java
Kad ne bismo prethodno generirali kod i s generatorom leksičkog analizatora, dodali bi opciju “-t” (odnosno “--generate-token-types”)
$ java -jar spocc-sag.jar /tmp/srbljic-151-syntax-rules.def -o /tmp/src --generate-token-types
pa bi nam to osiguralo da imam sljedeće datoteke:
/tmp/src/
`-- hr
`-- fer
`-- spocc
|-- parser
| |-- _Filler0.java
| `-- _ParsingTableFactory.java
`-- _TokenType.java
Ključna klasa koja se izgenerira jest _ParsingTableFactory - to je implementacija sučelja ParsingTableFactory. Pozivom metode
ParsingTable<TokenType> createParsingTable()
Dobivamo tablicu parsiranja koju koristi LR1Parser (ili bilo koja implementacija sučelja Parser koja nasljeđuje apstraktnu (AbstractParser)) kako bi parsirao u skladu s sintaksnim pravilima definiranim u ulaznoj datoteci čije smo ime predali u generatoru kod poziva iz komandne linije.
Budući da jezični procesor SPOCC još nema implementiranu semantiku i generaciju koda, on je naprosto generički kompajler kojemu se po-želji može mijenjati leksički analizator i sintaksni analizator. Dovoljno je pomoću gore opisana dva generatora izgenerirati kod u direktorij src/generated/java od ovog projekta, te ga ponovno rekompajlirati. Jedino mjestu u izvornom kodu ovog jezičnog procesora (spocc-core) je u implementaciji kompajlera - klasa DefaultCompiler:
class DefaultCompiler extends AbstractCompiler {
@Override
protected LexerDescriptorFactory createLexerDescriptorFactory() {
return new _LexerDescriptorFactory();
}
@Override
protected ParsingTableFactory createParsingTableFactory() {
return new _ParsingTableFactory();
}
...
}
$ java -jar spocc-core.jar
Usage: Spocc source-file [{-s, --symbol-table} file] [{-t, --token-list} file] [{-p, --parse-tree} file] [{-h, --parse-tree-human-readable}] [{-i, --ignore-lexical-errors}] [{-v, --verbose}]
Sljedeći primjeri dobiveni su ubacivanjem sintaksnih i leksičkih pravila za jezik definiran gramtikom sa dna strane 148 u knjizi od prof. Srbjlića (151 potječe od toga što je tablica parsiranja na 151. strani).
Primjer ispisa sintaksnog stablo u obliku čitljivom za ljude:
$ java -jar spocc-core.jar ../src/test/resources/151-02.source --parse-tree - --parse-tree-human-readable
<A>( <B>( a <B>( b ) ) <A>( ) )
Ako želimo isto stablo iscrtati (npr. pomoću programa GraphViz koji crta grafove u jeziku DOT), onda ćemo napisati:
$ java -jar spocc-core.jar ../src/test/resources/151-02.source -parse-tree /tmp/151-02.gv
Naknadnim pokretanjem naredbe
$ dot -Tpng /tmp/151-02.gv > /tmp/151-02.png
dobivamo .png sliku koja izgleda ovako:
Evo i nešto kompliciranijeg primjera u istom jeziku:
$ java -jar spocc-core.jar ../src/test/resources/151-03.source --parse-tree - --parse-tree-human-readable
<A>( <B>( a <B>( a <B>( b ) ) ) <A>( <B>( a <B>( a <B>( b ) ) ) <A>( <B>( b ) <A>( ) ) ) )
Primjeri korištenja za jezik koji je podskup jezika C
U ovom poglavlju biti će pokazani primjeri programa jezičnog procesora.
java -jar spocc-core.jar c-simple-01.source --parse-tree c-simple-01.gv
Primjer kompajliranja programa:
c-simple-02.source |
struct P { char m, tp; int fk; }; |
$ java -jar spocc-core.jar c-simple-02.source -p - -h
<prijevodna_jedinica>( <vanjska_deklaracija>( <deklaracija>( <specifikatori_deklaracije>( <specifikator_tipa>( <struct_specifikator>( KR_STRUCT IDN L_VIT_ZAGRADA <struct_lista_deklaracija>( <struct_lista_deklaracija>( <struct_deklaracija>( <lista_specifikatora_kvalifikatora>( <specifikator_tipa>( KR_CHAR ) ) <struct_lista_deklaratora>( <struct_lista_deklaratora>( <struct_deklarator>( <deklarator>( <izravni_deklarator>( IDN ) ) ) ) ZAREZ <struct_deklarator>( <deklarator>( <izravni_deklarator>( IDN ) ) ) ) TOCKAZAREZ ) ) <struct_deklaracija>( <lista_specifikatora_kvalifikatora>( <specifikator_tipa>( KR_INT ) ) <struct_lista_deklaratora>( <struct_deklarator>( <deklarator>( <izravni_deklarator>( IDN ) ) ) ) TOCKAZAREZ ) ) D_VIT_ZAGRADA ) ) ) TOCKAZAREZ ) ) )
Spocc-ide je minimalističko grafičko sučelje za kompajler koje u sebi sadrži i uređivač teksta. Trenutna verzija ima dosta bugova, pa se ne preporuča osim za demonstracijske svrhe (za razliku od spocc-core komandno-linijskog programa).
$ java -jar spocc-ide.jar
Primjer korištenja opcije crtanja sintaksnog stabla za jednostavan jezik.
Pogledati u arhivu u “sample-programs” direktorij i u prethodno poglavlje.
[1] Siniša Srbljić: «Prevođenje programskih jezika», 1. izdanje, Zagreb: Element, 2007.
[2] «Jezični prevoditelj », «Jezični prevoditelj – Wikipedia», http://hr.wikipedia.org/wiki/Jezi%C4%8Dni_prevoditelj, 5.1.2011.
