#include <stdlib.h> #include <stdio.h> int a = 1, b = 2; void f(int c) { int* p; p = malloc(sizeof(int)); *p = c; if (c < 3) f(c + 1); else printf("Här!\n"); } void g(int d) { int a, e; int *p; a = 4; b = 5; e = 6; p = malloc(sizeof(int)); *p = d; f(1); } int main(void) { int a, f; a = 7; b = 8; f = 9; g(10); }
När programexekveringen kommer fram till raden med utskriften "Här!", 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".
Svar:
|
De olika delarna av minnet, som statiska data och heap, kan komma i en annan ordning,
och de som växer kan växa åt ett annat håll än på bilden.
En del av parametrarna och de lokala variablerna kan placeras i register av kompilatorn,
men måste normalt ändå ha platser i minnet, så de kan sparas där vid anrop till en annan funktion
(så den funktionen kan använda registren).
c är en parameter till funktionen f,
och d är en parameter till funktionen g.
|
(Man kan behöva åtgärda en del av felen för att komma vidare och få de andra felen.)
Programmet Meddelanden #include <stdlib.h> #include <stdio.h> int a = 1, b = 2; int f(int c) { int* p; *p = c; if (c < 3) f(c + 1); else printf("Här!\n"); } void g(int d) { int a, e; int *p; a = 4; b = 5; e = 6; p = malloc(sizeof(int); *p = d; f(); } int main(void) { int a, f; a = 7; b = 8; f = 9; h(10); }
Svar:
|
(1) Vid programkörningen ("exekvering", "run-time")
(2) Semantisk analys (3) Syntaktisk analys ("parser") (4) Semantisk analys (5) Länkning |
a = b; c = d; while (e < f + g + h * i + j) { k = m + n; } if (o < p) { q = r; } else { s = t; u = v; } w = x;
Översätt ovanstående programavsnitt till två av följande tre typer av mellankod. (Skulle du svara på alla tre, räknas den med högst poäng bort.)
a) ett abstrakt syntaxträd (genom att rita upp trädet!)
Svar:
|
Man kan avsluta ";-listorna"
med NULL i stället för den sista satsen i listan.
Det blir lite mer att rita, men kan vara lite enklare programmeringsmässigt.
|
b) postfixkod för en stackmaskin
Svar:
lvalue a
rvalue b
=
lvalue c
rvalue d
=
label WHILE-START:
rvalue e
rvalue f
rvalue g
+
rvalue h
rvalue i
*
+
rvalue j
+
<
gofalse AFTER-WHILE
lvalue k
rvalue m
rvalue n
+
=
goto WHILE-START
label AFTER-WHILE:
rvalue o
rvalue p
<
gofalse ELSE-START
lvalue q
rvalue r
=
goto AFTER-ELSE
label ELSE-START:
lvalue s
rvalue t
=
lvalue u
rvalue v
=
label AFTER-ELSE:
lvalue w
rvalue x
|
c) treadresskod
Svar:
a = b
c = d
label WHILE-START:
temp1 = f + g
temp2 = h * i
temp3 = temp1 + temp2
temp4 = temp3 + j
if e ≥ temp4 goto AFTER-WHILE
k = m + n
goto WHILE-START
label AFTER-WHILE:
if (o ≥ p) goto ELSE-START
q = r
goto AFTER-ELSE
label ELSE-START:
s = t
u = v
label AFTER-ELSE:
w = x
|
Vi ska bygga en databas för att lagra data om gator och hus, och därför behöver vi ett särskilt inmatningsspråk. Med kommandona gata, hus och korsning ska man kunna mata in en beskrivning av vilka gator och hus som finns, och hur gatorna hänger ihop med varandra. Här är ett exempel på en inmatning:
Här har vi matat in att det finns ett antal gator, var och en med ett namn som Granvägen eller Brickebergsvägen. Namn är alltid ett enda ord utan mellanslag, så namn som Elof Ljunggrens väg är inte tillåtna. Vi har också matat in att det finns ett antal hus, till exempel Granvägen 6A och Granvägen 6B. Dessutom anger vi hur gatorna sitter ihop med varandra i olika vägkorsningar, som att Granvägen och Barkvägen sitter ihop i en korsning. Notera att efter nyckelordet korsning kan det komma fler än två gator, exempelvis för att Åstadalsvägen, Stenåsvägen och Brickebergsvägen sitter ihop med varandra i en korsning. Hela inmatningen ska avslutas med ett klart-kommando, enligt ovan.
Inmatningen kan skrivas på fritt format. Exempelvis är nedanstående inmatning syntaktiskt ekvivalent med den i exemplet ovan.
Svar:
| Gatunamn, husnummer, semikolon samt nyckelorden klart, gata, hus och korsning |
b) En del av terminalerna har inte fixa lexem, utan kan se olika ut. Skriv, för varje sådan terminal, ett reguljärt uttryck som beskriver hur den får se ut!
Svar:
|
gatunamn: [A-ZÅÄÖ][a-zåäö]*
husnummer: [1-9][0-9]*[A-Z]? |
En kommentar: Beroende på implementationen, språkinställningar med mera kan det vara besvärligt att få svenska tecken att fungera i reguljära uttryck.
Svar:
|
inmatning -> kommandon klartkommando
klartkommando -> klart semikolon kommandon -> kommandon kommando | ingenting kommando -> gatukommando | huskommando | korsningskommando gatukommando -> gata gatunamn semikolon huskommando -> hus gatunamn husnummer semikolon korsningskommando -> korsning gatulista semikolon gatulista -> gatunamn gatunamn flergator flergator -> flergator gatunamn | ingenting |
Svar:
|
Svar:
|
I grammatiken som vi skrivit ovan finns två vänsterrekursioner
som först måste elimineras.
Vi kan skriva om grammatiken så vi får en ny grammatik som
beskriver samma språk:
inmatning -> kommandon klartkommando
Ladda ner: gatuparser.c, plus en hjälpfil i form av en Lex-scannerspecifikation, gator.l, och en Bison-version av grammatiken, gator.y. Det finns också en Makefile för att bygga parsern. Token-typer: KLART GATA HUS KORSNING GATUNAMN HUSNUMMER SEMIKOLON
|
