Observera att detta är förslag på lösningar.
Det kan finnas andra lösningar som också är korrekta.
Det kan hända att en del av lösningarna är mer omfattande än vad som krävs för full poäng på uppgiften,
eller att de bara hänvisar till var man kan läsa svaren.
Dessutom har det inträffat i världshistorien att lärare skrivit fel i lösningsförslagen.
Uppgift 1 (10 p)
En kompilators arbete brukar delas in i ett antal faser.
Ange vilka det är, och förklara kort vad varje fas gör.
Vad är in- och utdata från respektive fas?
- Lexikalisk analys ("scanner"), som delar upp programmets källkodstext i tokens
- Syntaktisk analys ("parser"), som analyserar programmet (i form av tokens) enligt källspråkets grammatik
- Semantisk analys, som analyserar programmets betydelse, främst med avseende på datatyper ovh typkorrekthet (typkontroll)
- Generering av mellankod ("intermediärkod")
- Maskinoberoende kodoptimering, som gör programmet (i form av mellankod) mindre och snabbare (eller en av dessa)
- Kodgenerator som genererar målkoden
- Maskinberoende kodoptimering, som gör optimeringar som bara kan göras på målkodsnivå, till exempel sammanslagning av assemblerinstruktioner
In- och utdata:
- Källkod i form av text, dvs en sekvens av tecken
- (Fas 1: Lexikalisk analys ("scanner"))
- En sekvens av tokens, med par av tokentyp och lexikaliskt värde
- (Fas 2: Syntaktisk analys ("parser"))
- Ett syntaxträd (som inte behöver ha konstruerats explicit)
- (Fas 3: Semantisk analys)
- Samma syntaxträd, men kanske dekorerat med (främst) datatyper
- (Fas 4: Generering av mellankod ("intermediärkod"))
- Mellankod, inte som text utan t ex treadresskod i form av kvadrupler
- (Fas 5: Maskinoberoende kodoptimering)
- Samma mellankod, men mindre och snabbare
- (Fas 6: Kodgenerator)
- Målkod skriven i målspråket (t ex assembler), ibland som text
- (Fas 7: Maskinberoende kodoptimering)
- Samma målkod, men mindre och snabbare
Se också boken eller
föreläsningsanteckningarna,
särskilt
den här figurern,
med tillägget att den maskinberoende optimeringen ger som utdata målkod i målspråket,
men mindre och snabbare jämfört med den kod som är utdata från kodgeneratorn.
Uppgift 2 (3 p)
När vi "bygger" (dvs kompilerar och länkar) och till sist (efter att ha rättat kompileringsfelen)
provkör följande C-program,
får vi de angivna fel- och varningsmeddelandena.
I vilken av kompilatorns faser (eller på annan plats) upptäcks vart och ett av dessa fel och varningar?
-
invalid suffix "andra" on integer constant
Lexikalisk analys ("scannern")
-
expected ',' or ';' before 'sqrt'
Syntaktisk analys ("parsern")
-
unused variable 'z'
(Maskinoberoende) kodoptimering, eller kanske semantisk analys
-
'y' is used uninitialized in this function
(Maskinoberoende) kodoptimering, eller kanske semantisk analys
-
missing declaration of function 'printf'
Semantisk analys
-
return makes integer from pointer without a cast
Semantisk analys
Uppgift 3 (7 p)
Det här är ett programavsnitt i ett C-liknande språk:
if (a < b)
c = a;
else
c = b;
while (a < b) {
a = a * 2 + 3 * d;
b = b - d - 1;
}
Översätt ovanstående programavsnitt till var och en av följande tre typer av mellankod.
a) ett syntaxträd, även kallat abstrakt syntaxträd (genom att rita upp trädet!)
b) postfixkod för en stackmaskin
rvalue a
rvalue b
lt
gofalse 1
lvalue c
rvalue a
assign
goto 2
label 1:
lvalue c
rvalue b
assign
label 2:
label 3:
rvalue a
rvalue b
lt
gofalse 4
lvalue a
rvalue a
push 2
*
push 3
rvalue d
*
+
assign
lvalue b
rvalue b
rvalue d
-
push 1
-
assign
goto 3
label 4:
c) treadresskod
if (a ≥ b) goto 1
c = a
goto 2
label 1:
c = b
label 2:
label 3:
if a ≥ b goto 4
t1 = a * 2
t2 = 3 * d
t3 = t1 + t2
a = t3
t4 = b - d
t5 = t4 - 1
b = t5
goto 3
label 4:
Man kan redan här optimera bort (eller snarare låta bli att generera)
temporärvariabler i tilldelningar, så att exempelvis de två instruktionerna
"t3 = t1 + t2"
och
"a = t3"
ovan i stället blir
"a = t1 + t2".
Uppgift 4 (5 p)
Här är ett C-program.
Ett programs adressrymd kan delas upp i fyra delar: programkod och konstanter, statiska data, heap och stack.
Rita upp hur stacken (med aktiveringsposter), heapen och statiska data ser ut
när programkörningen kommer till utskriften av "Här!".
Scenario till de övriga uppgifterna
En struct i C är ett dataobjekt som innehåller ett eller flera andra dataobjekt.
Structar kallas också för poster.
Vi ska skriva den del av en C-kompilator som läser (förenklade) struct-deklarationer,
Här är ett exempel på en struct som innehåller tre dataobjekt,
nämligen ett heltal och två flyttal:
struct Punkt {
int nummer;
float x, y;
};
I de förenklade struct-deklarationer som vårt program ska klara
finns bara de två datatyperna int och float.
Här är ett annat exempel på en struct-deklaration,
som visar att C-kod kan skrivas på fritt format,
dvs att man kan stoppa in extra mellanslag och radbrytningstecken:
struct Banan { float pris;
float vikt;
int
banannummer;
float pos1, pos2, pos3, pos3b; };
Uppgift 5 (3 p)
a)
Ange vilka terminaler, dvs typer av tokens, som behövs för att man ska kunna skriva en grammatik för
struct-deklarationer.
Vänsterklammer ({),
högerklammer (}),
kommatecken (,),
semikolon (;),
namn/identifierare,
samt nyckelorden struct, int och float.
b)
Ange reguljära uttryck för de terminaler som inte har ett fast utseende.
namn/identifierare: [A-Za-z_][A-Za-z_0-9]*
Uppgift 6 (4 p)
Skriv en grammatik för struct-deklarationer.
Startsymbolen ska vara deklaration,
som representerar en enda struct-deklaration enligt scenariot ovan.
deklaration -> struct namn { medlemmar } ;
medlemmar -> medlem medlemmar | medlem
medlem -> datatyp variabler ;
datatyp -> int | float
variabler -> namn , variabler | namn
Egentligen kan en struct vara helt tom i C,
men för att uppgift 8 ska bli roligare har jag gjort grammatiken så att en struct måste ha minst en medlemsvariabel.
Uppgift 7 (3 p)
Rita upp parse-trädet (även kallat konkret syntaxträd)
för nedanstående inmatning,
enligt grammatiken i uppgiften ovan:
struct Vara {
int nummer;
float pris, vikt;
};
Uppgift 8 (7 p)
Skriv en prediktiv recursive-descent-parser för struct-deklarationer,
i ett språk som åtminstone liknar C, C++, C# eller Java.
Du behöver inte skriva exakt korrekt programkod,
men det ska framgå vilka procedurer som finns,
hur de anropar varandra, och vilka jämförelser med tokentyper som görs.
Du kan anta att det finns en funktion som heter scan,
och att den returnerar typen på nästa token.
Det finns FIRST()-konflikter i produktionerna för medlemmar
och i produktionerna för variabler,
så grammatiken måste först skrivas om med hjälp av två vänsterfaktoriseringar:
deklaration -> struct namn { medlemmar } ;
medlemmar -> medlem fler-medlemmar
fler-medlemmar -> medlemmar | ingenting
medlem -> datatyp variabler ;
datatyp -> int | float
variabler -> namn fler-variabler
fler-variabler -> , variabler | ingenting
ingenting står för en tom produktion.
Ladda ner:
structparser.c,
plus en hjälpfil i form av en Lex-scannerspecifikation struct.l
#include <stdlib.h>
#include <stdio.h>
#include "struct.tab.h" // Bara för att få tokenkoderna
// Från Bison: %token STRUCT INT FLOAT NAMN
extern int yylex(void);
int lookahead;
int scan(void) {
return yylex();
}
void error() {
printf("Det har tyvärr uppstått ett fel.\n");
exit(EXIT_FAILURE);
}
void match(int expected) {
if (lookahead != expected)
error();
else
lookahead = scan();
}
void deklaration(void),
medlemmar(void),
fler_medlemmar(void),
medlem(void),
datatyp(void),
variabler(void),
fler_variabler(void);
void deklaration(void) {
match(STRUCT); match(NAMN); match('{'); medlemmar(); match('}'); match(';');
}
void medlemmar(void) {
medlem(); fler_medlemmar();
}
void fler_medlemmar(void) {
if (lookahead == INT || lookahead == FLOAT)
medlemmar();
else
; /* Ingenting */
}
void medlem(void) {
datatyp(); variabler(); match(';');
}
void datatyp(void) {
if (lookahead == INT)
match(INT);
else if (lookahead == FLOAT)
match(FLOAT);
else
error();
}
void variabler(void) {
match(NAMN); fler_variabler();
}
void fler_variabler(void) {
if (lookahead == ',') {
match(','); variabler();
}
else {
/* Ingenting */
}
}
void parse() {
lookahead = scan();
deklaration();
printf("Ok.\n");
}
int main() {
printf("Mata in kommandon. Avsluta med KLART-kommandot och EOF.\n");
parse();
}
// Behövs för Lex
int yywrap(void) {
return 1;
}
Thomas Padron-McCarthy
(thomas.padron-mccarthy@oru.se)
20 oktober 2014