Kompilatorer och interpretatorer
för Dataingenjörsprogrammet m fl
fredag 8 januari 2016
Gäller som tentamen för:
DT3030 Datateknik C, Kompilatorer och interpretatorer, provkod 0100
Hjälpmedel: | Inga hjälpmedel. |
Poängkrav: |
Maximal poäng är 36.
För godkänt betyg krävs totalt minst 21 poäng, varav minst 8 poäng på uppgift 1. |
Resultat: | Meddelas på kursens hemsida eller via e-post senast fredag 29 januari 2016. |
Återlämning av tentor: | Efter att resultatet meddelats kan tentorna hämtas på universitetets centrala tentamensutlämning. |
Examinator och jourhavande: | Thomas Padron-McCarthy, telefon 070 - 73 47 013. |
A är en icke-terminal, men x och y står för godtyckliga konstruktioner som består av terminaler och icke-terminaler.A -> A x | y
Regeln ersätts av följande två regler (eller, korrektare uttryckt, tre produktioner), som beskriver samma språk men som inte är vänsterrekursiva:
A -> y R R -> x R | empty
A är en icke-terminal, men x, y och z står för godtyckliga konstruktioner som består av terminaler och icke-terminaler.A -> x y | x z
Skriv om till dessa tre produktioner:
A -> x R R -> y | z
a = 0; b = 14; if (a == c) { while (a != d) { a = c - d - 2; c = c + 1; } d = 4; } else { c = c * 2 + 1; d = 3; }Översätt ovanstående programavsnitt till två 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
c) treadresskod
Observera: Det finns tre deluppgifter i uppgiften ovan. Välj ut och besvara (högst) två av dessa. (Skulle du svara på alla tre, räknas den med högst poäng bort.) |
#include <stdlib.h> #include <stdio.h> int a = 10, b = 20; int g(int a) { int z; int *p; if (a == 0) return 1000; z = a - 1; p = malloc(sizeof(int)); *p = 2000; printf("z = %d\n", z); z = g(z); return z; } int f(int x, int y) { int z; int *p; x = x + y; z = 100; p = malloc(sizeof(int)); *p = 200; a = g(x); return a; } int main(void) { int a, c; a = 1; b = 2; c = 3; a = f(a, b); return 0; }
hälsning -> hej | hej på dig
a)
Här är ett utdrag ur en prediktiv recursive-descent-parser, skriven i C, för hälsningar:
Det finns ett problem med den parsern. Förklara vad problemet är, och hur man kan lösa det.void halsning() { if (lookahead == HEJ) { match(HEJ); } else if (lookahead == HEJ) { match(HEJ); match(PA); match(DIG); } else { error(); } }
b)
Här är ett utdrag ur en Bison-fil för att skapa en parser för samma hälsningar som ovan:
halsning : HEJ | HEJ PA DIG ;
Finns samma problem här som med recursive-descent-parsern ovan? Varför, eller varför inte?
#include <stdlib.h> #include <stdio.h> #include "tokenkoder.h" // Ovanstående ger tokenkoderna: // STARTA PA GA METER I RIKTNING TAL TILL KLART extern int scan(); int lookahead; 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 program(), startkommando(), gakommandon(), gakommando(), vart(); void program() { startkommando(); gakommandon(); match(KLART); } void startkommando() { match(STARTA); match(PA); match(TAL); match(TAL); } void gakommandon() { if (lookahead == GA) { gakommando(); gakommandon(); } else { /* tomt */ } } void gakommando() { match(GA); vart(); } void vart() { if (lookahead == TAL) { match(TAL); match(METER); match(I); match(RIKTNING); match(TAL); } else if (lookahead == TILL) { match(TILL); match(TAL); match(TAL); } else if (lookahead == GA) { match(GA); match(GA); } else if (lookahead == PA) { match(PA); } else { error(); } } void parse() { lookahead = scan(); program(); printf("Ok.\n"); } int main() { printf("Mata in inmatningen.\n"); printf("Avsluta med \"klart\" och EOF.\n"); parse(); } /************Inte med!*************/ // Behövs för Lex int yywrap() { return 1; }
Du hittar också en scannerspecifikation för Flex, som hör till parsern ovan, och som ser ut enligt nedan:
%{ #include "tokenkoder.h" %} %% [\n\t ] { /* Ignorera whitespace */ } "starta" { return STARTA; } "på" { return PA; } "gå" { return GA; } "meter" { return METER; } "i" { return I; } "riktning" { return RIKTNING; } "till" { return TILL; } "klart" { return KLART; } [0-9]+(\.[0-9]+)? { return TAL; } . { fprintf(stderr, "Ignorerar felaktigt tecken: '%c'\n", *yytext); } %% int scan() { return yylex(); }