DV3: Kompilatorns första faser - automater och grammatik (ST-14): moment 2

Laboration - Framsida av kompilator


Sista inlämningsdag fredag 2014-08-15 17:00

Denna laboration får utföras parvis eller enskilt

I denna laboration ska framsidan av en kompilator, fram till och med mellankodsgenerering konstrueras. Språket som ni ska skriva kompilatorn till är ett Pascal-liknande språk. Uppgiften löses lämpligtvis med någon variant av Yacc, t.ex. yacc eller bison.

För er som inte är bekanta med Pascal är det ett imperativt språk, i likhet med C, men med en del skillnader. Den största skillnaden mellan C och Pascal är att man i Pascal kan ha nästade funktioner, d.v.s. funktioner inuti funktioner.

Grammatik

Språkets grammatik ser ut enligt följande

    prog        ->  program id ; dekllist fndekllist compstat .
    dekllist    ->  dekllist dekl
                |   dekl
    dekl        ->  type idlist ;
    type        ->  integer
    idlist      ->  idlist , id
                |   id
    fndekllist  ->  fndekllist fndekl
                |   
    fndekl      ->  fnhead dekllist fndekllist compstat ;
    fnhead      ->  function fname ( parlist ) : type ;
    parlist     ->  dekllist
                |   
    fname       ->  id
    compstat    ->  begin statlist end
    statlist    ->  statlist stat
                |   stat
    stat        ->  compstat
                |   if expr then stat else stat
                |   while expr do stat
                |   write ( exprlist ) ;
                |   read ( idlist ) ;
                |   id assop expr ;
                |   fname assop expr ;
    exprlist    ->  exprlist , expr
                |   expr
    expr        ->  aexp relop aexp
                |   aexp
    aexp        ->  aexp addop aexp
                |   aexp mulop aexp
                |   fname ( arglist )
                |   ( expr )
                |   id
                |   num
    arglist     ->  exprlist
                |   

Orden i fetstil är tokens som lexikalanalysatorn känner igen. Vissa av dessa står för en mängd språksymboler, t.ex. id. (Om fetstil inte fungerar så finns samma grammatik med understrykningar istället för fetstil här.)

Grammatiken innehåller några konstruktioner som kanske inte fungerar så bra och måste lösas genom att antingen skriva om grammatiken lite eller lägga in lämpliga actions. (tex är det tillåtet att skriva v1 := a < b;, detta ska antingen resultera i ett felmeddelande eller så ska vettig kod genereras)

Ett lämpligt första steg kan vara att mata in grammatiken i en Yacc-fil samt alla nödvändiga rutiner och definitioner. Sedan kompileras filen till ett program och, om allt blivit rätt, bör det genererade programmet kunna kontrollera om syntaxen i ett program är korrekt.

Ni ska utöka grammatiken med en repeat-until-sats.

    stat  ->  repeat stat until expr ;

Ett tips kanske kan vara att implementera originalgrammatiken först och sedan, när den fungerar, lägga till utökningen.

Det är tillåtet att skriva om grammatiken så länge den är semantiskt ekvivalent med ovanstående grammatik. Det kan därför vara bra att se om vissa omskrivningar kan göra resten av arbetet enklare.

Språket är, i jämförelse med Pascal, tämligen begränsat. Värt att notera speciellt är att

  • Funktioner är den enda typen av under program. Procedurer existerar inte. Funktioner får nästas
  • Variablerna i språket kan endast vara av heltalstyp.

Lexikalanalys

Ni behöver inte konstruera en egen lexikalanalysator, även om det är tillåtet att göra det. Den lexikalanalysator som tillhandahålls är skriven för gflex. Koden hittar ni i filen lab.l längst ned i denna specifikation.

Följande symboler känns igen av lexikalanalysatorn, och behöver alltså inte kännas igen av er Yacc-fil.

	relop	->  = | <> | <= | >= | < | >
	addop	->  + | -
	mulop	->  * | /
	assop	->  :=
	id	-> letter (letter | digit | _)*
	num	-> digit digit*

				

Scannerns huvudrutin är funktionen yylex() som returnerar en heltalskod för aktuell tokentyp. De token som kan förekomma är, förutom de vanliga ascii-tecknen, precis de tokens ni deklarerar i er Yacc-fil. För vissa tokens returneras också ett värde. Detta värde kan i denna laboration vara en sträng eller ett heltal. Strängar sparas i yylval.name (t.ex. en identifierares lexeme) och heltal i yylval.val (t.ex. vilken typ av relop som returneras). För att konstruera er Yacc-fil med korrekta namn på tokens måste ni titta i Lex-koden. Exempelvis blir compstat något i stil med

	compstat    : BEGINSY statlist ENDSY
	            ;
				

Mellankodsgenerering

Huvuduppgiften i denna laboration är att generera mellankod, genom att lägga in actions i er Yacc-kod. Denna uppgift kan delas in i flera deluppgifter som symboltabellshantering, typkontroller och själva mellankodsgenereringen.

För att minska mängden kodande tillhandahålls en del rutiner som kan underlätta arbetet. De flesta semantiska actions ni kommer att behöva finns beskrivna i översättningsschemana för satser och boolska uttryck. Dessa finns beskrivna i avsnitt 6.7 i som ni fått utdelat.

Ni ska använda er av filerna lab.h och table.c, vilka återfinns längst ned i denna specifikation.

Den mellankod som ska genereras är ett mellanting mellan kvadrupler och tripler. Exakt hur en mellankodsinstruktion ser ut kan ses i strukturen _mcode i lab.h. Varje instruktion består av fyra fält, operation, arg1, arg2 och target.

  • operation är den mellankodsoperation som ska utföras
  • arg1 och arg2 är de två operanderna, utom vid tilldelning då arg1 är resultatet. En eller båda dessa kan vara 0
  • target är en hoppadress till en mellankodsinstruktion. Denna används endast till goto operationer och "testa relationsoperationer och hoppa"-instruktioner.

Skillnaden mot kvadrupler är att instruktionen själv representerar sitt resultat, d.v.s. det finns inget fält result. Detta liknar tripler, men ändå används temporära variabler för att referera till resultat av tidigare mellankodsinstruktioner.

De temporära variablerna lagras inte i symboltabellen. Istället används en i table.c en array tempvars, där plats för sex temporära variabler finns. Dessa är av samma typ som de vanliga variablerna i symboltabellen. Det är meningen att de temporära variablerna ska återanvändas, vilket redan finns inprogrammerat i funktionen emit.

Mellankoden lagras i en array mcode[MAXCODE] med element av typen mcode i table.c. För att sätta in kod i arrayen anropas funktionen emit(operator, arg1, arg2, target). Dessutom finns funktionerna makelist, merge och backpatch som används för att utföra olika operationer på mellankoden.

Antagligen kommer det någonstans (t.ex. aexp -> aexp MULOP aexp där aexp är deklarerad som %type <exp> aexp) att stå något i stil med

	$$.place = emit($2, $1.place, $3.place, 0);
				

Mellankoden för funtionsanrop bör man fundera över. En enkel variant är att ha mellankodsinstruktionerna FSTART och FEND som får symbolisera start respektive slut, men andra varianter är tillåtna. Ett litet tillägg skulle kunna vara att kontrollera att antalet parametrar är korrekt.

Symboltabellen

Varje symbol i symboltabellen representeras av en struktur _symbol, vilket kan ses i lab.h. Även konstanter lagras i symboltabellen, vilket inte är optimalt, men det blir ganska enkelt. Om ni vill så kan ni anta att det bara finns ett namespace. Observera dock att ett felmeddelande ska skrivas ut om man försöker använda en variablel som inte är deklarerad. Om ni känner att symboltabellen behöver omarbetas är detta tillåtet. Se dock till att redogöra för alla justeringar ni gjort och varför ni gjort dem. Ni behöver inte implementera typkontroll.

Övrig information

Ytterligare saker som finns i lab.h och table.c är

  • struct _expression kan man ha nytta av när deklarationer av vilka typer grammatiksymbolerna kan ha (i %union-deklarationen)
  • printmcode och printsymbtab skriver ut vilken mellankod som genererats, respektive innehållet i symboltabellen. Utskrifter görs i den fil ptree refererar till, vilket normalt är standard output

Givna filer

  • lab.l   koden för lexikalanalysatorn
  • lab.h   innehåller nödvändiga definitioner
  • table.c   funktioner för hantering av symboltabellen
  • Makefile   underlättar kompilering
  • ok1.prg   exempelprogram
  • ok1_2.out   resultat till ovanstående
  • ok2.prg   exempelprogram
  • ok2_2.out   resultat till ovanstående
  • ok3.prg   exempelprogram
  • ok3_2.out   resultat till ovanstående
  • ok4.prg   exempelprogram
  • ok4_2.out   resultat till ovanstående
  • fel.prg   syntaktiskt felaktigt exempelprogram
  • fel.out   resultat av ovanstående exempelprogram
  • fel_2.out   annan variant av resultat till ovanstående

Notera att exempelutdatan inte behöver stämma precis med er utdata. Den exakta formen på utdatan styrs av hur kompilatorn implementerats. Dessutom är det felaktiga programmet eventuellt inte felaktigt, beroende på hur ni implementerat ert name space.

Fråga gärna om något är oklart eller om ni tycker att jag glömt något.

Redovisning

Ett på våra Linux-maskiner exekverbart program, en välskriven laborationsrapport (i pappersformat) samt välkommenterad kod (tillsammans med labrapporten).