#include <stdlib.h> #include <stdio.h> int a, b, c; void f(int d) { int a; int* p; a = 1; b = 2; c = 3; p = malloc(sizeof(int)); *p = d; if (d < 1) f(d + 1); printf("Här!\n"); } int main(void) { int a; int* p; a = 4; b = 5; c = 6; p = malloc(sizeof(int)); *p = 8; f(0); }
När programexekveringen för första gången kommer fram till raden med utskriften "Här!", så antar vi att vi stoppar programmet och tittar på vilka olika variabler som finns i minnet.
I minnet kommer det då att finnas ett antal heltalsvariabler och andra lagringsutrymmen för heltal, som innehåller olika tal. Rita upp en skiss över dessa variabler och lagringsutrymmen, med innehåll, och förklara vad som är vad. Din förklaring bör bland annat innehålla termerna "statiska data", "stack", "heap", "aktiveringspost" och "parametrar".
Aktiveringsposterna innehåller plats för lokala variabler och funktionens parametrar.
Den globala variabeln a (med C-terminologi har den "lagringsklassen extern") får startvärdet noll, eftersom statiska data i C initieras till noll. (Vanliga lokala variabler, med C-terminologi "lagringsklassen auto"), har odefinierat startvärde i C.)
Översätt ovanstående programavsnitt till två av följande tre typer av mellankod.a = 1; if (b < a - b - c * d) { while (i * 2 > j * 3) { if (i % 4 == 5) i = i + 6; b = 7; } a = 8; }
a) ett abstrakt syntaxträd (genom att rita upp trädet!)
En kommentar:
b) postfixkod för en stackmaskin
lvalue a push 1 = rvalue b rvalue a rvalue b - rvalue c rvalue d * - lt gofalse ELSE-START-1 label WHILE-START: rvalue i push 2 * rvalue j push 3 * gt gofalse AFTER-WHILE rvalue i push 4 % push 5 eq gofalse ELSE-START-2 lvalue i rvalue i push 6 + = goto AFTER-IF-2 label ELSE-START-2: label AFTER-IF-2: lvalue b push 7 = goto WHILE-START label AFTER-WHILE: lvalue a push 8 = goto AFTER-IF-1 label ELSE-START-1: label AFTER-IF-1:
Två kommentar:
c) treadresskod
a = 1 temp1 = a - b temp2 = c * d temp3 = temp1 - temp2 if (b >= temp3) goto ELSE-START-1 label WHILE-START: temp4 = i * 2 temp5 = j * 3 if (temp4 <= temp5) goto AFTER-WHILE temp6 = i % 4 if (temp6 != 5) goto ELSE-START-2 i = i + 6 label ELSE-START-2: label AFTER-IF-2: b = 7 goto WHILE-START label AFTER-WHILE: a = 8 goto AFTER-IF-1 label ELSE-START-1: label AFTER-IF-1:
Två kommentar:
a) Vi använder referensräkning. Ange värdet på referensräknaren för vart och ett av dataobjekten.
1: 0, 2: 0, 3: 2, 4: 0, 5: 0, 6: 0, 7: 1, 8: 3, 9: 4, 10: 1, 11: 2, 12: 1, 13: 1, 14: 1, 15: 0, 16: 0
b) Vilka av dataobjekten kommer att tas bort?
15 och 16
c) Antag att vi i stället använder skräpsamling med mark-and-sweep. Vilka av dataobjekten kommer att tas bort av skräpsamlaren?
Här är tre varianter. Den första hanterar bara engelska bokstäver (A-Z), den andra hanterar även svenska ÅÄÖ, och den tredje fungerar förmodligen inte (men det kan bero på vilket regexp-bibliotek och vilka språkinställningar man har).
\"[-A-Za-z0-9 ]*\"
\"[-A-ZÅÄÖa-zåäö0-9 ]*\"
\"[-A-Öa-ö0-9 ]*\"
Kommentar: I Flex måste citationstecknen skrivas som \" ovan, men i en del andra sammanhang kan man utelämna bakåtstrecken.
b) (2p) Vilka andra terminaler, förutom textsträng, behövs för att man ska kunna skriva en grammatik för köpen?
Nyckelorden start och klart, samt enhet och tal.
köp -> start varurader klart
varurader -> varurad varurader | ingenting
varurad -> tal valfri_enhet sträng
valfri_enhet -> enhet | ingenting
ingenting står för en tom produktion, och brukar oftast skrivas med en liten "e"-symbol, som tyvärr inte verkar fungera överallt i HTML.
start 1 "apelsin" 2 "äpple" klart
Ladda ner: kopparser.c, plus en hjälpfil i form av en Lex-scannerspecifikation kop.l, och en Bison-version av grammatiken kop.y
void match(int expected) { if (lookahead != expected) error(); else lookahead = scan(); } void kop(void) { match(start); varurader(); match(klart); } void varurader(void) { if (lookahead == tal) { varurad(); varurader(); } else { /* empty */ } } void varurad(void) { match(tal); valfri_enhet(); match(strang); } void valfri_enhet(void) { if (lookahead == enhet) { match(enhet); } else { /* empty */ } } void parse() { lookahead = scan(); kop(); printf("Ok.\n"); }
Påstående | Sant | Falskt |
---|---|---|
Den första fasen i kompilatorn är den lexikaliska analysatorn, även kallad scanner. | X | |
Scannern gör om en sekvens av tokens till en sekvens av tecken. | X | |
Den andra fasen i kompilatorn är den syntaktiska analysatorn, även kallad parser. | X | |
I de flesta vanliga programmeringsspråk tolkas de tre tecknen 123 som ett heltal, vilket är en typ av token. För heltalet 123 är lexemet de tre tecknen 1, 2 och 3. | X | |
För heltalet 123 är det lexikaliska värdet talet 123. | X | |
Parsern analyserar programmet enligt källspråkets grammatik. | X | |
Utdata från parsern är ofta ett syntaxträd, men det är inte säkert att man faktiskt bygger upp trädet, med pekare i minnet eller på annat sätt. | X | |
Semantisk analys analyserar programmets betydelse, dvs om det stämmer med källspråkets grammatik. | X | |
Det är den semantiska analysatorn som avgör vad additionen i deluttrycket x+y egentligen innebär, till exempel om det är addition av heltal eller om det är sammanslagning av strängar. | X | |
Det är den semantiska analysen som lägger in symboler i symboltabellen. | X | |
Mellankodsgeneratorn genererar mellankod ("intermediärkod"). Mellankoden skickas vidare till nästa fas som textrader, till exempel t2 = x + t1, och så körs scannern på nytt för att läsa in dem, men de är så enkla att parsern inte behövs. | X | |
Maskinoberoende kodoptimering gör programmet mindre och snabbare (eller en av dessa). Det kan hända att det optimerade programmet blir större än utan optimering, till exempel med looputrullning. | X | |
Kodgeneratorn genererar målkoden, som till exempel kan bestå av maskininstruktioner för en fysisk processor. | X | |
Målkoden kan vara i form av text, till exempel assemblerinstruktioner som ADD R1, R2. | X | |
Den maskinberoende optimeraren gör optimeringar som bara kan göras på målkodsnivå, till exempel sammanslagning av assemblerinstruktioner. | X | |
Om scannern är implementerad i form av en funktion som heter scan, och parsern är implementerad i form av en funktion som heter parse, kommer funktionen scan alltid att anropas före funktionen parse. | X | |
Den semantiska analysen resulterar i mellankod, som den maskinoberoende kodoptimeraren sen omvandlar till ett syntaxträd. | X | |
Kodoptimeraren i vanliga programmeringsspråk som C och C# kan omvandla 1+2 till 3. | X | |
Kodoptimeraren i vanliga programmeringsspråk som C och C# kan ibland omvandla en loop till ett konstant värde. | X | |
Kodoptimeraren i vanliga programmeringsspråk som C och C# kan omvandla en länkad lista till en hashtabell. | X |