Datorn gissar alltså hela tiden på talet 7, tills användaren ger upp och svarar "ja"!Tänk på ett tal och tryck ENTER. Är det 7? nej Är det 7? nej Är det 7? va? Svara ja eller nej! Är det 7? sluta Svara ja eller nej! Är det 7? nej Är det 7? ja Jag vann!
Vi skriver spelet i form av ett C-program, men det blev tyvärr inte helt korrekt, och när vi försöker bygga och köra det får vi de angivna fel- och varningsmeddelandena. I vilka av kompilatorns faser, eller vid andra tidpunkter, upptäcks vart och ett av de olika felen och varningarna?
(Man kan behöva åtgärda en del av felen för att komma vidare och få de andra felen.)
Programmet | Meddelanden | Svar |
#include <stdio.h> int question(void) { char svar[10]; while (true) { gets(svar); if (strcmp(svar, "ja") == 0) return 1; @ else if (strcmp(svar, nej) == 0) return 0; else { printf("Svara ja eller nej!\n"); return; } } } int Main(void) { printf("Tänk på ett tal\n"); printf("och tryck ENTER.\n"); while (getchar() != "\n") ; do { printf("Är det 7?\n"); } while (question() != 1e); printf("Jag vann!\n") } /* main |
'true' undeclared implicit declaration of 'strcmp' stray '@' in program 'nej' undeclared 'return' with no value undefined reference to 'main' comparison between pointer and integer exponent has no digits expected ';' before '}' token unterminated comment |
semantisk analys semantisk analys scanner semantisk analys semantisk analys länkaren semantisk analys scanner parser scanner |
---|
if (a - b < c * d * e) { while (a < b) { c = d * e + f; d = e * f * g; } } else { a = b; }
Ö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!)
b) postfixkod för en stackmaskin
rvalue a rvalue b - rvalue c rvalue d * rvalue e * < gofalse ELSE-START label WHILE-START: rvalue a rvalue b < gofalse AFTER-WHILE lvalue c rvalue d rvalue e * rvalue f + = lvalue d rvalue e rvalue f * rvalue g * = jump WHILE-START label AFTER-WHILE: goto AFTER-IF label ELSE-START: lvalue a rvalue b = label AFTER-IF:
c) treadresskod
temp1 = a - b temp2 = c * d temp3 = temp2 * e if temp1 >= temp3 goto ELSE-START label WHILE-START: if a >= b goto AFTER-WHILE temp4 = d * e c = temp4 + f temp5 = e * f d = temp5 * g goto WHILE-START label AFTER-WHILE: goto AFTER-IF label ELSE-START: a = b label AFTER-IF:
Förklara hur detta påverkar var och en av faserna i kompilatorn!
Scannern påverkas inte alls. Scannern arbetar med enskilda tokens i källprogrammet, och det har inget med oändliga loopar att göra.
Parsern påverkas inte alls. Parsern jämför källprogrammet med källspråkets grammatik, och grammatiken säger (normalt) inget om värden på loopvillkor och andra uttryck.
Den semantiska analysen påverkas förmodligen inte alls. Den semantiska analysfasen arbetar med vad programmet betyder, och det har mycket att göra med datatyper, till exempel vilken jämförelseoperator man egentligen använder i loopvillkoret. Man kan möjligen tänka sig ett språk där man låter variablers konstans (om de ändras eller inte) vara en del av datatypen, men det gäller normalt sådant som const-deklarationer i C och C++, och inte en analys som kan avgöra om ett loopvillkor ändras.
Mellankodsgeneratorn påverkas inte alls. Den gör en ganska enkel översättning av källprogrammet till mellanformatet, och genererar mellankod som motsvarar loopen.
Den maskinoberoende optimeraren kan analysera hur variabler ändras, och det är i den här fasen kompilatorn kan upptäcka att villkoret alltid är sant, och att loopen blir oändlig. I så fall kan hela resten av programmet optimeras bort! Alternativt kan optimeraren upptäcka att villkoret alltid är falskt, och då kan loopen optimeras bort.
Kodgeneratorn genererar målkod baserat på resultatet från den maskinoberoende optimeringen. Om delar av programmet optimerats bort, kommer ingen kod att genereras för dem.
Den maskinberoende optimeraren gör ganska enkla förbättringar av den genererade målkoden. Eventuella optimeringar som innebär att delar av källprogrammet försvinner och inte har någon motsvarighet i målprogrammet är redan gjorda, så denna fas påverkas inte, mer än att den förstås slipper arbeta med dessa bortoptimerade delar.
En följd av instruktioner, till exempel i treadresskod, där det inte sker några hopp vare sig in i eller ut ur blocket, med undantag för att hopp kan ske till den första instruktionen i blocket, och att den sista instruktionen kan vara ett (villkorligt eller ovillkorligt) hopp.
b) Definitionen av basic block innehåller en del begränsningar av vilka hopp som är tillåtna. Varför finns dessa begränsningar?
För att underlätta för optimeraren. Man vet att alla instruktionerna utförs, i den ordning de står, så det är mycket enklare att analysera vilka värden variablerna har, än om hopp kan ske hur som helst.
[A-Za-z]+
b) Vilka andra terminaler, förutom ord, behövs för att man ska kunna skriva en grammatik för språket?
"=", radslut och nyckelorden candidate, vote, alias och result
c) Skriv en scanner som kan dela upp inmatningen i tokens. Du får själv välja om du ska använda Flex eller skriva den för hand i C, C++ eller ett liknande språk. Scannern ska bestå av en funktion som returnerar en token-kod. Du kan anta att token-koderna finns definierade i form av makron, ungefär som Bison gör när man har en Bison-grammatik med %token-deklarationer.
Här är en Flex-fil (election.l):
%{ #include "election.tab.h" %} %% [\t ] { /* Ignorera whitespace utom radslut */ } \n { return END_OF_LINE; } "candidate" { return CANDIDATE; } "alias" { return ALIAS; } "vote" { return VOTE; } "result" { return RESULT; } [a-zA-Z]+ { return WORD; } "=" { return EQUALS; } . { fprintf(stderr, "[Ignorerar felaktigt tecken: '%c']\n", *yytext); } %%
inmatning -> kommandon resultatkommando
kommandon -> kommando kommandon | tomt
kommando -> kandidatkommando | aliaskommando | rostningskommando
flera-ord -> ord flera-ord | ord
kandidatkommando -> candidate flera-ord radslut
aliaskommando -> alias ord = flera-ord radslut
rostningskommando -> vote flera-ord radslut
resultatkommando -> result radslut
tomt markerar en tom produktion.
candidate Kim Jong Un vote Kim Jong Un result
Grammatiken i uppgift 6 har en FIRST()-konflikt, så vi behöver först vänsterfaktorisera:
flera-ord -> ord flera-ord | ord
blir i stället:
flera-ord -> ord noll-eller-flera-ord | ord
noll-eller-flera-ord -> ord noll-eller-flera-ord | ord
En nedladdningsbar komplett fil finns här: election-parser.c
void match(int expected) { if (lookahead != expected) error(); else lookahead = scan(); } void inmatning(void) { kommandon(); resultatkommando(); } void kommandon(void) { if (lookahead == CANDIDATE || lookahead == ALIAS || lookahead == VOTE) { kommando(); kommandon(); } else { /* Tomt */ } } void kommando(void) { if (lookahead == CANDIDATE) { kandidatkommando(); } else if (lookahead == ALIAS) { aliaskommando(); } else if (lookahead == VOTE) { rostningskommando(); } else { error("Det här kan inte hända"); } } void flera_ord(void) { match(WORD); noll_eller_flera_ord(); } void noll_eller_flera_ord(void) { if (lookahead == WORD) { match(WORD); noll_eller_flera_ord(); } else { /* Tomt */ } } void kandidatkommando(void) { match(CANDIDATE); flera_ord(); match(END_OF_LINE); } void aliaskommando(void) { match(ALIAS); match(WORD); match(EQUALS); flera_ord(); match(END_OF_LINE); } void rostningskommando(void) { match(VOTE); flera_ord(); match(END_OF_LINE); } void resultatkommando(void) { match(RESULT); match(END_OF_LINE); } void parse() { lookahead = scan(); inmatning(); printf("Ok.\n"); } int main() { printf("Mata in ett kommando. Avsluta med EOF.\n"); parse(); }