Språket Q Projekt i Översättarteknik Fredrik Simonsson d94fs@efd.lth.se Stefan ivcovi d94sz@efd.lth.se för Institutionen för Datalogi och Numeriskanalys vid Lunds Tekniska Högskola 16 juni 1997 1 Abstract This document describes the constructing of the programing language q and building a compiler for the very same language,generating SparcTM assembly- code. The project was carried out as a part of the course compilers and inter- preters. 2 Innehåll 1 Inledning 4 1.1 Disposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * *. 4 2 Teori 4 3 Genomförande 4 3.1 Lexikaliska analysen . . . . . . . . . . . . . . . . . . . . . . . . .* * 4 3.2 Syntaktiska analysen . . . . . . . . . . . . . . . . . . . . . . . . .* * 5 3.3 Semantiska analysen . . . . . . . . . . . . . . . . . . . . . . . . . * * 5 3.3.1 Statiska variabler . . . . . . . . . . . . . . . . . . . . . . .* * 5 3.4 Kodgenerering . . . . . . . . . . . . . . . . . . . . . . . . . . . .* * 5 3.4.1 Treadress och Assemblerkodgenerering . . . . . . . . . . . 6 3.5 Hårdvaruutnytjande . . . . . . . . . . . . . . . . . . . . . . . . . * * 6 3.5.1 CPU-register i Sparc implementationen . . . . . . . . . . 6 3.5.2 Funktionsanrop . . . . . . . . . . . . . . . . . . . . . . . . * * 7 3.5.3 Begin och End . . . . . . . . . . . . . . . . . . . . . . . . 7 3.5.4 Texthantering . . . . . . . . . . . . . . . . . . . . . . . . . * * 7 4 Brister och kommentarer 7 A Referenser 8 B EBNF för programspråket 9 C Förenklad syntax 10 D Tralala kod, program och programlistor 11 3 1 Inledning Man önskar konstruera ett programerings språk och till detta bygga en kompi- lator . För detta ändamål konstrurerades en gramatiker av typen LL(1) vilken beskrivs i EBNF i appendix. Språket,som döptes till q efter en namntävling på internet beskrivs nedan i detalj. 1.1 Disposition Teori avsnittet beskriver mycket kortfattat vad kompilatorns arbetsfaser,i av- snittet Genomförande beskrivs detta hur det påverkat vårt projekt i mer i de- talj för de olika stegen.I Brister och kommentarer diskuteras de brister som q-kompilatorn fortfarande har. I appendix återfinns listningar av program kod till kompilatorn,Flera testprogram med både dess assemly och treadress avbil- der. För att öka läsbarheten till språket q bifogas även en Förenklad beskrivni* *ng av syntaxen tillsammans med EBNF beskrivningen. 2 Teori En kompilater parsar igenom ett källkods program i flera omgångar sk pass där varje pass genererar utdata till nästa. Den lexikaliskaanalysen konverterar reserverade ord och variabel namn till tokens vilkas ordning kontrolleras i den syntaktiskaanalysen. Den semantiskaanalysen kontrollerar att funktioner anro- pas med rätt antal parametrar. Kodgenerering och skapande av treadress sker i samtidigt men in genereringen av assemblykod tyder de direktiv som kodas som flera instruktioner själva ut sig till flera. 3 Genomförande För att bygga kompilatorn så valde vi att använda verktyget Tralala som tolkar grammatiken lexekalist och syntaktiskt, man kan också ange action efter tolkade symboler. Vi valde simulaversionen av Tralala som generera simulakod, med andra ord tralala översätter vår tralala infil (.tra) till en parser skriven i * *simula, den kompilerades sedan med en vanlig simulakompilator. Tralala tillåter också att man kan koppla ihop två tralala filer för att på * *sätt slippa generera en massa mellan filer, det har vi utnyttjat i kopplingen mellan den lexikaliska analysen och syntaktiska analysen. Q-kompilatorn är uppbyggd i tre delar, en lexikaliska, övrigt och en del som tar hand om treadress- och assembler-kodgenereringen. Vi har delat upp projektet i två Tralala filer och en simulafil, dessa beskrivs mer nedan. 3.1 Lexikaliska analysen Här tar vi en infil och delar upp den i olika "tokens", detta görs i Tralala fi* *l ett (Se appendix under lex.tra). 4 3.2 Syntaktiska analysen Här kollar vi så att programmets "token" följer grammatiken detta görs med "ren"1 tralala kod, som fixar denna biten till oss. Övriga analyser och även ko* *d- genereringen tillhör tralala fil två (Se appendix under syn.tra). Under kursens gång förstod vi att man inte kan skilja på boolska och heltals opperationer i d* *en syntaktiska analysen utan att detta måste skutas upp till senare. 3.3 Semantiska analysen För att lösa den Semantiska analysen skapade vi "ACTIONS" i tralalakoden där vi fyllde i typkoll av variabler och parametrar. Vi använde oss av den tillhan- dahållna SymbolTable.sim som vi endast behövde modifiera lite. Vi typkollar även anropen, Ett problem vi hade var att alla variablerna automatiskt hamnar i temporär registerna när dom användes så vi var även tvungna att typkontrolera temporärvariablerna. 3.3.1 Statiska variabler De statiska variabler man deklarerar med ' i huvud programmet är att betrakta som globala då de kan nås och modifieras från hela alla block i programmet. De statiska variabler som deklareras i andra block än huvudprogrammet blir på samma sätt globala för alla underliggande block och funktioner. 3.4 Kodgenerering Kodgenereringen är inkluderad i samma fil som syntaktiska och semantiska ana- lysen och består av kodgenererings kommandon (se nedan under "Treadress och Assemblerkodgenerering") ifylld i alla de "ACTIONS" som finns där. Globala variabler och Strängar genereras i "data" segmentet alla övriga variabler läggs på från stacken tilldelat utrymme. De statiska variabler som deklareras i ett block kan nås från det blocket dess underblock samt alla funktioner som dekla- rerats i dessa. Alla funktioner kan om man så önskar returnera ett värde med en ooperation denna returnerar ett 32 bitars heltal,Detta för att underlätta de si- tuationer då ett heltal kan betraktas som boolean som tillexempel felkoder från funktioner. För allas bekvämlighet infördes om typkonverteringsoperatorerna $ och # enligt ______________________________ | | $ E G|ör om E till boolean | | |_|_#_E_G|ör_om_E_till_heltal_ | | Vi lyckades med lite snirklig tralala programmering se till att först lägga * *in alla variabler och konstanter med ett "MOVE" till ett temporärtregister innan vi använder dessa, detta medförde att det var endast i "MOVE" som vi behöver ta hand om alla de olika förflyttningar som tex Temp-register->variabel, global- variabel->register, constant->Temp-register Stack-variabel->Temp-register. En load/store arkitektur som Sparc har särskilda instruktioner för minnes adresse- ring så därför var det praktiskt att alla beräkningar skedde mellan register. Eftersom assemblern inte har den nivåindelning som man får i högra pro- gramspråk via "begin, end" metoden så var vi tvungna att generera unika namn ____________________________1 med ren avses tralala kod utan actions 5 på alla funktioner och globala variabler.För att kunna ha labelnamn i språket q måste alla lägen i assemblykoden få unika namn i US-ASCII därför valdes att skapa nya unika namn till alla funktioner,dessa genereras av bokstaven "L" följt av ett löpnummer. 3.4.1 Treadress och Assemblerkodgenerering För att på ett smidigt sätt kunna skapa treadresskod som det senare skall ge- nereras tex Sparc-Assembler utav, så skapade vi ett system med klasser som tar hand om Argumenten och en bunke klasser som tar hand om instruktio- nerna (instruktions klasserna är underklass till link så att man kan lägga in dom i en lista). Klasserna har operatorn "treasm" och "asm" som genererar en outtext till rätt fil med sitt innehåll, tex så finns klassen StIdArg som hante* *rar en identifierare sparad på stacken, när man anropar "treasm" så genererar den namnet på variabeln men när man anropar "asm" så genereras [%g7 + relpos]. På samma sätt finns instruktionerna, tex klassen "Add" som har tre inparamet- rar (p1,p2,p3), alla tre av typen Arg (se ovan), i proceduren "treasm" genereras först "add" och sedan anropas p1.treadd, p2.treadd och p3.treadd. Och likadant sker i "asm" fast med p*.treadd utbytt mot p*.asm. Andra treadress direktiv kan generera flera assemblerinstruktioner, tex MOVE genererar en massa olika assembler instruktioner beroende på vilka underklasser inparametrarna är av. Klassystemet är lätt utbyggt och kan tex generera vad man vill som tex C++ eller något mer exotiskt språk som perl, amos, blitzbasic eller till och med matlabTM script även om det som framförallt är aktuellt är assemblerkod för andra arkitekturer som xpTM ,MIPSTM ,PPCTM eller MC68000. När vi ska generera ett treadress direktiv så skapas en instans av den klass som motsvarar det direktiv och lägger en i en länkad lista, vilken anropas med operationerna "treasm" och "fixasm" (ibland behöver man utföra en del saker i assemblergenereringen innan man skriver ut programmet på fil, detta görs i så fall nu) på den, nu har vi genererat en treadess kod, assembler'n kan vi inte generera innan allt är klart eftersom eventuella strängar och globala variabler ska ligga före programkoden i slutet. 3.5 Hårdvaruutnytjande Minnet används på ett sådant sätt att det reserveras plats för alla statiska2 variabler och en stor stack till övriga variabler vilka används under runtime. Därför blir de variabler som inte är initierade fyllda med gamla skräptecken ur minnes arean. De instruktioner som hanterar minnet vid stackoperationer har en gemensam definition på hur stort ett dataord är varför man lätt kan öka register storleken till 64 bitar. 3.5.1 CPU-register i Sparc implementationen Vi_har_delat_upp_cpu-registerna_enligt_följande:_ | | Temporära variabler%|l0 - %l7, %g1 - %g6 | | | | Parameteröverföring%|i0 - %i4, %o1 - %o5 | | |_|_Stackpekare_______%g|7_________________|_| 2globala 6 3.5.2 Funktionsanrop Eftersom det i språket q inte går att komma åt variabler som inte var deklarera* *de globalt utanför en procedur samt att vi överför parametrar via register, så be- hövde vi inte den föreslagna "framepointer"/aktiveringsposts arkitekturen utan det enda vi egentligen behöver spara på stacken innan ett anrop är återhoppsa- dressen. I verkligheten så sparas alla register undan också innan återhoppsvär- det lagras för att inte temporär variablerna ska förstöras. Parametrarna läggs i lämpliga register för överföringen. I början av varje funktion reserveras det plats på stacken3 för alla identif* *i- erarna och för den temporära returnvariablern, dessa laddas sedan med värden från de registerna sim inparametrarna ligger i. Sedan utförs alla instruktioner* *na i blocket, innan återhopp läggs den temporära variabeln för return värdet i re- gister %o0 och stacken rättas till, alla allokerade variabler avallokeras. Däre* *fter plockas återhoppsadressen från stacken och man hoppar tillbaka. Väl tillbaka så läggs alla registerna tillbaka, och programmet fortsätter. 3.5.3 Begin och End Eftersom vårt språk tillåter att men kan deklarera identifierare i början av al* *la block så måste plats reserveras på stacken vid begin ("{") om det skulle behöva* *s, som senare vid end ("}") återlämnas. 3.5.4 Texthantering Eftersom texter egentligen inte behövde finnas i programspråket så har vi inga texthanterings metoder, mer in print (""" ), och scanInt ("""), booleanustskrif* *ter skriver bara ut 0 eller -1, medan heltal skrivs ut med sitt värde, och strängar skrivs rätt ut och radbryts med tecknet "nn" 4 Brister och kommentarer Implementationen av q är mycket beroende av CPU registerna och har inga funktioner för att hantera kedjade uttryck som kräver att mer än ca 12 värden mellan lagras, i praktiken sker detta nästan aldrig då temporär register omedel- bart frigörs när de har använts. Att ha parameter överföringen till funktioner i register är ett försök till effektivare funktions anrop tyvärr spolieras detta * *ge- nom sparandet av alla temporär variablerna till minnet.Detta kan förmodligen i optimeras i deflesta fall genom att bara spara de temporär register som används när en funktion anropas. En annan brist är avsaknaden av biblioteks rutiner,för att ett språk skall vara användbart måste möjligheter att anropa rutiner i ope- rativsystem och dess omgivning finnas, för detta saknar q helt stöd. ____________________________3 Stacken växer neråt i minnet för att förenkla SparcTM implementationen 7 A Referenser 1. Översättarteknik, Göran Eriksson (Institutionen för Datalogi och Nume- risk Analys vid LTH, 1984), KFS AB, Lund 1996 2. TRALALA TRAnsLAtor LAnguage, Göran Eriksson (Institutionen för Datalogi och Numerisk Analys vid LTH, 1992), KFS AB, Lund 1996 3. Objektorienterad programmering och Simula, Per Holm (Institutionen för Datalogi och Numerisk Analys vid LTH, 1992), 2:a upplagan, KFS AB, Lund 1992 Information har också hämtats från: 4. http://math.holycross.edu/odube/courses/cs181/SPARC/inst.html 8 B EBNF för programspråket < P ROGRAM >=< SAT S > < BLK >=0f0< DEF >< F UNC > ~ < SAT S > ~0g0 < DEF >= (((0:]0id(0;0id)~)=(0:$0id(0;0id)~)=(0']0id(0;0id)~))=(0'$0id(0;0id)~)* *)0;0)~ < SAT S >=< BLK > = < IDN >0;0= < COND > = < SY SOUT > = = < RET URN > < COND >=< IF > = < W HILE > < E0 >=< E > ((0=?0< E > =0>?0< E > =0)=$) < E >=< ET > ((0+0< ET >)=(0`0< ET >)=(0j0< ET >))~ < ET >=< NBR > ((0~0< NBR >)=(0=0< NBR >)=(0&0< NBR >))~ < NBR >= (0(0< E0 >0)0)= < IDN > =(0`0 < NBR >)=(0n0 < NBR > )=0const0= < BOOLCONST ANT > =0]0< E0 > =0$0< E0 > = < SY SIN > < F UNC >=0@0id0(0< DEF >0)0< SAT S > < IDN >= id((0(0((< E0 > (0;0< E0 >)~)=$)0)0)=((0=0< E0 >)=($))) < RET URN >=0o0< E0 >0;0 < IF >=0?0< E0 > (0:)0< SAT S > =$)(0: (0< SAT S > =$) < W HILE >=0!0< E0 >0:)0< SAT S > < SY SIN >=0fl0 < SY SOUT >=0fi0(< E0 > =0string0)0;0 9 C Förenklad syntax ______________________________________________________________________ |_|_Opperationer____________|Funktion________________|_Typ____________| | | | @ id (dekl) |funktion |deklaration | | | | :]id |lokal heltalsvariabel de|klaration | | | | ']id |statisk heltalsvariabel de|klaration | | | | :$ id |lokal boolskvariabel d|eklaration | | |_|_'$_id___________________|statisk_boolskvariabel____d|eklaration___ | | | | =? |likhet |logisk | | | | >? |större än |logisk | | | |