typ, slut, sportnamn, semikolon
b) (1p)
[0-9][0-9][0-9][0-9]-[0-1][0-9]-[0-3][0-9]
Ovanstående räcker för full poäng, även om uttrycker tillåter "datum" som 2009-13-35, 2009-04-31 och 2009-02-29. (Och det är nog synnerligen tveksamt om reguljära uttryck är rätt verktyg för att kontrollera om ett år är skottår.)
c) (2p)
([0-9]+:)?[0-5]?[0-9]:[0-5]?[0-9](\.[0-9]+)?
Uttrycket för att matcha tider går att göra ganska komplicerat, men ovanstående räcker för full poäng, även om det kanske skulle vara snyggare att bara tillåta tider som 3:09:09, och inte 3:9:9.
dagbok -> satser slut semikolon
satser -> satser sats | empty
sats -> typsats | träningssats
typsats -> typ sportnamn semikolon
träningssats -> datum sportnamn semikolon | datum sportnamn tid semikolon
b) (2p)
De två produktionerna
träningssats -> datum sportnamn semikolon | datum sportnamn tid semikolon
ger en FIRST()-konflikt, och måste vänsterfaktoriseras till:
träningssats -> datum sportnamn valfri-tid semikolon
valfri-tid -> tid | empty
(Enligt receptet kommer semikolon med i valfri-tid, men det här tycker jag blir snyggare.)
Produktionen
satser -> satser sats
innehåller vänsterrekursion. Om vi använder det vanliga receptet för eliminering av vänsterrekursion kan vi skriva om dessa två produktioner:
satser -> satser sats | empty
till:
satser -> fler-satser
fler-satser -> sats fler-satser | empty
vilket förstås kan förenklas till:
satser -> sats satser | empty
Färdig grammatik:
dagbok -> satser slut semikolon
satser -> sats satser | empty
sats -> typsats | träningssats
typsats -> typ sportnamn semikolon
träningssats -> datum sportnamn valfri-tid semikolon
valfri-tid -> tid | empty
void error() {
printf("Ledsen error.\n");
exit(EXIT_FAILURE);
}
void match(int expected) {
if (lookahead != expected)
error();
else
lookahead = scan();
}
extern void dagbok(void), satser(void), sats(void), typsats(void), traningssats(void), valfri_tid(void);
void dagbok(void) {
satser(); match(SLUT); match(SEMIKOLON);
}
void satser(void) {
if (lookahead == TYP || lookahead == DATUM) {
sats(); satser();
}
else {
/* Empty! */
}
}
void sats(void) {
if (lookahead == TYP)
typsats();
else if (lookahead == DATUM)
traningssats();
else
error();
}
void typsats(void) {
match(TYP); match(SPORTNAMN); match(SEMIKOLON);
}
void traningssats(void) {
match(DATUM); match(SPORTNAMN); valfri_tid(); match(SEMIKOLON);
}
void valfri_tid(void) {
if (lookahead == TID)
match(TID);
else {
/* Empty! */
}
}
void parse() {
lookahead = scan();
dagbok();
printf("Ok.\n");
}
b) postfixkod för en stackmaskin
lvalue i
push 0
=
lvalue j
push 10
=
lvalue n
push 0
=
label 1:
rvalue i
rvalue j
<
gofalse 2
rvalue i
push 2
%
push 0
==
gofalse 3
lvalue i
rvalue i
push 2
+
=
goto 4
label 3:
lvalue j
rvalue j
push 1
-
=
label 4:
lvalue n
rvalue j
rvalue i
-
push 1
-
push 2
/
=
goto 1
label 2:
c) treadresskod
i = 0;
j = 10;
n = 0;
label 1:
if (i >= j) goto 2;
temp1 = i % 2;
if (temp1 != 0) goto 3;
i = i + 2; // Eller via en temp-variabel
goto 4;
label 3:
j = j - 1; // Eller via en temp-variabel
label 4:
temp2 = j - i;
temp3 = temp2 - 1;
n = temp3 / 2; // Eller via en temp-variabel
goto 1
label 2:
while-sats -> while ( uttryck ) sats
b)
Här är (en del av) en syntax-styrd definition för att generera ett syntaxträd.
| Produktion | Semantisk regel |
|---|---|
| while-sats -> while ( uttryck ) sats | while-sats.träd = skapa-trädnod(WHILE, uttryck.träd, sats.träd) |
Här är (en del av) en syntax-styrd definition för att generera postfixkod för en stackmaskin.
| Produktion | Semantisk regel |
|---|---|
| while-sats -> while ( uttryck ) sats |
while-sats.label-före = skapa-ny-label()
while-sats.label-efter = skapa-ny-label() while-sats.kod = instruktion( label while-sats.label-före ) + uttryck.kod + instruktion( gofalse while-sats.label-efter ) + sats.kod + instruktion( jump while-sats.label-före ) + instruktion( label while-sats.label-efter ) |
Skräpsamling beyder att run-time-systemet automatiskt letar upp data som inte längre kan nås av programmet. Eftersom dessa data inte går att använda, kommer de heller inte att användas. De kan då, fortfarande automatiskt, tas bort, och minnesutrymmet kan återanvändas till annat. Det är något man gör vid exekveringstillfället, alltså medan programmet kör, och inte i förväg vid kompileringen.
(Men jämför detta med hur optimeraren i kompilatorn till exempel kan optimera bort variabler. Kompilatorn kan göra en del analys i förväg, och till exempel räkna ut att efter den här punkten i programmet kommer dessa data garanterat inte att användas mer, och därför kan kompilatorn lägga in instruktioner som vid exekveringstillfället då tar bort dessa data, utan att köra någon skräpsamlingsalgoritm. Men eftersom man inte har all information om indata, vägval och liknande i förväg, blir den analysen mycket begränsad, jämfört med vad en normal skräpsamlare kan göra. Den skräpsamlaren har ju tillgång till de riktiga data som ska analyseras, som de faktiskt ser ut vid den tidpunkten i programkörningen.)
b)
När det gäller själva programkörningen är det normalt tvärtom: att köra ett program som är kompilerat till maskinkod går för det mesta mycket snabbare än att köra det interpeterat. Det beror på att instruktionerna i maskinoden körs direkt av processorn, medan interpretatorn först måste köra en del kod för att räkna ut vilken maskininstruktion (om vi nu antar att det finns en direkt överensstämmelse) som ska köras. Den uträkningen i interpretatorn kan kräva hundratals eller tusentals maskininstruktioner, så det interpreterade programmet kan mycket väl vara tusen gånger långsammare än det kompilerade.
Å andra sidan tar själva kompileringen också tid, och om man räknar in kompileringen kan det mycket väl vara så att kompilering plus exekvering av ett program tar längre tid än att interpretera det direkt. Scriptspråk brukar interpreteras snarare än kompileras, bland annat för att man vill att det ska gå att göra små ändringar i scriptet och sen provköra det direkt. Då vill man inte behöva vänta i flera sekunder på en kompilering, innan programmet startar.
c)
Det är oftast farligt. Shift/reduce-konflikter brukar bero på att grammatiken är tvetydig, dvs att samma sekvens av tokens kan tolkas på två eller flera sätt, och då kan parsern inte veta hur inmatningen ska tolkas!
Exempel på en tvetydig grammatik:
uttryck -> uttryck - uttryck | tal
Inmaningen 7 - 3 - 2, som ger upphov till tokensekvensen tal, -, tal, -, tal, kan nu grupperas ihop antingen som (7 - 3) - 2, som blir 2, eller som 7 - (3 - 2), som blir 6.
Bison bygger en parser som arbetar med en stack, som kan ses som en sorts väntelista som innehåller dels tokens som den hittat i inmatningen, dels icke-terminaler, som grupperar ihop noll eller flera sådana tokens under ett gemensamt namn. Man säger att de "reducerats" till den icke-terminalen. Till exempel kan tre tokens, 7, - och 3, grupperas ihop ("reduceras") till icke-terminalen uttryck. Parserns stack innehåller tokens och icke-terminaler som står på tur att grupperas ihop (reduceras) till andra icke-terminaler.
När parsern studerar nästa token som den hittat i inmatningen, kan den antingen skifta denna token, dvs lägga den på stacken, eller så kan den vänta med att ta hand om denna token, och i stället ta en eller flera tokens och icke-terminaler från stacken, och reducera dessa till en ny icke-terminal. Oftast finns det bara ett möjligt val. Om stacken till exempel innehåller två tokens, 7 och -, går de (med grammatiken ovan) inte att reducera, utan man måste skifta in nästa token på stacken. Om nästa token är 3 kan man skifta den, varefter stacken innehåller 7, + och 3, vilka därefter kan reduceras till icke-terminalen uttryck.
Ibland finns det två olika möjligheter. Om stacken innehåller 7, - och 3, och nästa token är -, kan man antingen reducera innehållet på stacken till icke-terminalen uttryck, eller så kan man skifta in -, för att senare reducera 3, - och 2 till uttryck. Det är det som är en shift/reduce-konflikt.
En shift/reduce-konflikt beror alltså ofta på att grammatiken är tvetydig. Skiftning kommer att leda till en tolkning, reducering till en annan. Då visar shift/reduce-konflikten från Bison på tvetydigheten i grammatiken, och man bör ändra grammatiken så tvetydigheten försvinner. Annars vet man ju inte hur ens indata kommer att tolkas!
(Förutom att Yacc och Bison genrerar en parser som vid en shift/reduce-konflikt alltid väljer att skifta, så om man håller sig till dessa verktyg så är beteendet väldefinierat!)
En shift/reduce-konflikt kan också bero på att den Bison-genererade parsern bara har en enda tokens lookahead när den bestämmer hur den ska tolka indata, dvs den tittar bara på en token i taget i indatat. En del grammatiker kräver mer lookahead, och ger därför shift/reduce-konflikter trots att de inte är tvetydiga. Exempel:
tallista -> tal | tal semikolon | tallista semikolon tal
Frågeställaren berättade dessutom att hon har "en massa" shift/reduce-konflikter, och det tyder på att hon kanske gjort flera missar när hon skrev grammatiken. Hon bör laga detta! En bra början är att titta på prioritet och associativitet för operatorerna.