Datortentamen i TDP007 Konstruktion av datorspråk 2012-08-18 ------------------------------------------------------------ Instruktioner ------------- Tentan genomförs kl. 14:00 till 18:00. Ni kommer att få köra på särskilda datortentakonton där ni har tillgång till en mycket begränsad miljö. Alla filer som ni behöver för att lösa uppgifterna finns i katalogen given_files, inklusive tentauppgifterna. Där finns också en PDF-version av boken som ni gärna får använda er av. Öppna den med kommandot acroread. Svar på frågor skrivs i vanliga textfiler och programkod skrivs i rb-filer. Ni behöver inte göra något särskilt för att lämna in, utan alla filer som ligger kvar i den katalog där ni startade kommer att behandlas när tentan rättas. OBS! För att filerna ska sparas ordentligt måste ni klicka på EXIT för att logga ut. Tentan består av fyra uppgifter (några indelade i deluppgifter) som totalt kan ge 32 poäng. För godkänt krävs 50%, dvs minst 16 poäng. För betyg 4 krävs minst 21 poäng och för 5 minst 26 poäng. Inga poäng från duggor kan räknas tillgodo, utan tentan bedöms helt på egen hand. Uppgift 1: Grundläggande Ruby och teorifrågor (8p) -------------------------------------------------- a) I Ruby kan man lägga till eller ändra metoder i en redan definierad klass. Nämn någon fördel och någon nackdel med detta! (1p) b) Vad är en iterator? Förklara i ord och ge ett belysande kodexempel! (1p) c) Skriv en funktion som med hjälp av ett reguljärt uttryck kan dela upp en webbadress i server, katalog och fil enligt följande exempel. (2p) >> split-url("http://www.ida.liu.se/~TDP007/material/lectures.sv.shtml") => ["www.ida.liu.se", "/~TDP007/material/", "lectures.sv.shtml"] d) När ska man använda strömparsning (SAX) och när ska man använda trädparsning (DOM)? Ge ett exempel på användningsområde och förklara kort varför den ena metoden skulle kunna vara bättre. (2p) e) Den här uppgiften innehåller mycket text, men ska förhoppningsvis inte vara allt för svår. Den testar att du förstår ett antal grundläggande begrepp inom objektorientering i allmänhet och Ruby i synnerhet. Skriv fullständig och körbar kod enligt följande långrandiga specifikation. (2p) - Skapa en klass Publication som har tre instansvariabler: title, author och year. Instansvariablerna ska vara läsbara, men inte skrivbara. Ge klassen en initieringsfunktion som tar tre parametrar motsvarande dessa instansvariabler och som sparar värdena i instansvariablerna. De två första variablerna är tänkta att innehålla strängar, den sista ett heltal. - Skapa en klass Book som utökar klassen Publication. Den ska ha ytterligare en instansvariabel publisher som är läsbar men inte skrivbar. Initieringsfunktionen ska ha totalt fyra parametrar som precis som för Book ska innehålla värden till instansvariablerna. De tre som är gemensamma för Book ska initieras med superklassens initieringsfunktion. Klassen Book ska dessutom ha en överlagrad jämförelseoperator som endast jämför titel och författare, inte de övriga två instansvariablerna. Uppgift 2: Textfiler och XML (12p) --------------------------------- Denna uppgift består av fyra deluppgifter, där de senare bygger vidare på den första. Läs igenom hela uppgiften innan du börjar. Det är möjligt att lösa och få poäng för uppgifterna separat, men det blir naturligtvis svårt att testa. Centrala Spioneringsnämnden (CSN) övervakar olika typer av nätverks- kommunikation. Eftersom det är en oöverstiglig uppgift behöver de olika programvaror som kan analysera stora mängder information och identifiera vad som behöver kollas upp manuellt. Just nu behöver de ett program som kan gå igenom stora mängder e-post och lista ut vilka personer som ska hamna på deras stora svarta lista. I en textfil ordlista.txt finns en lista med bra och dåliga ord. Den börjar så här: terrorism 1 knark 2 cannabis 2 fred -1 kanin -1 Varje e-postmeddelande får poäng beroende på vilka ord det innehåller. För att få poäng räcker det att ordet finns med en gång. Ett meddelande med texten "knark knark knark fred" borde alltså få 1 poäng. Observera att man kan få minuspoäng. Trevliga ord kan uppväga dåliga. a) (1p) Skriv en funktion read_wordlist som läser in en poängsatt ordlista enligt ovan till någon lämplig datastruktur som funkar för resten av uppgifterna. b) (3p) Skriv en funktion classify_text som tar en sträng samt en poängsatt ordlista. Funktionen ska returnera hur många poäng texten får enligt ovanstående metod. Exempel: >> classify_text("knark knark knark fred",wordlist) => 1 >> classify_text("Jag vill ha fred och bananer!",wordlist) => -3 CSN vill även kunna hålla koll på vilka personer som skriver eller tar emot brev med höga poäng. Deras metod för att göra detta funkar så här: Avsändaren av brevet, liksom alla mottagare, samlar på sig de poäng som brevet har tilldelats. Sedan räknar man för varje person ut en medelpoäng. Säg t.ex. att Kalle har varit sändare eller mottagare för fem brev med följande poäng: Brev nr Poäng ---------------- 1 3p 2 5p 3 0p 4 -1p 5 2p Summerar man ihop dessa poäng och delar med 5 får man 1,8 poäng. Det är alltså Kalles poäng. c) (4p) I filen brev.txt finns ett antal olika e-postmeddelanden. Skriv en funktion process_mail som givet en sådan fil med brev samt en fil med ordlista, kan poängsätta alla personer som står som sändare eller mottagare. Så här ska det se ut: >> process_mail("brev.txt","ordlista.txt") kalle@acme.se 1.8 pelle@acme.se -4.0 stina@acme.se 0.5 lisa@acme.se 0.75 olle@acme.se 3.0 => nil Från den här listan kan CSN lätt lista ut att Olle behöver bevakas extra noga, medan Pelle verkar vara en mycket snäll typ som kanske i framtiden ska rekryteras. Angående filen brev.txt kan det vara bra att känna till att olika e-postmeddelanden separeras från varandra med två blankrader. Brevhuvudet (alla rader med From, To, m.m.) separeras från själva texten i brevet med en blankrad. Det är bara texten i brevet som ska räknas. d) (4p) I filen mailbox.xml finns samma e-postmeddelanden, men nu i XML-format. Skriv en funktion process_mail2 som givet en fil med brev i detta format kan poängsätta alla personer som står som sändare eller mottagare. Resultatet ska vara detsamma som i föregående uppgift. Uppgift 3: DSL (6p) ------------------- I filen my_world.rb finns en karta över en spelvärld uttryckt i ett enkelt domänspecifikt språk. Kartan beskrivs genom att man går runt i världen och observerar olika objekt. Med hjälp av kommandon som motsvarar de fyra väderstrecken flyttas man runt. Om kommandot får en tal som parameter förflyttas man det antal steg som anges, annars endast ett steg. Alla övriga kommandon är namn på saker som finns på den aktuella positionen. Dessa namn kan vara vilket ord som helst. Filen börjar så här: north east house Det innebär alltså att i en punkt nordost om startpunkten finns ett hus. Din uppgift är att skriva ett program som kan läsa in en karta som är beskriven på det här sättet. Kartan ska läsas in till ett format så att den kan skrivas ut med hjälp av funktionen i filen print_map.rb. Tanken är att det ska se ut så här, om allt fungerar: >> print_map(MapReader.load("my_world.rb")) -------- -------- -------- house -------- sword -------- -------- -------- -------- -------- dragon -------- -------- treasure => nil I uppgiften ingår alltså att först förstå hur funktionen print_map fungerar. Jämför det som står i filen med utskriften ovan. Därefter ska du skapa klassen MapReader som kan läsa in en karta i det givna formatet. Du ska använda dig av någon av de tekniker för domänspecifika språk i Ruby som vi har gått igenom i kursen. Uppgift 4: Parsning (6p) ------------------------ Om man vill skriva ut saker snyggt kan man använda formatterad utskrift med t.ex. funktionen format. Man börjar med en s.k. formatsträng, som innehåller olika koder för vad som ska skrivas ut och hur det ska se ut. Exempel: >> format("%08b '%4s'", 123, 123) => "01111011 ' 123'" Formatsträngens koder i exemplet ovan talar om att första argumentet (talet 123) ska skrivas ut i binärform med åtta tecken och fyllas ut med nollor vid behov. Vidare ska nästa argument (också talet 123) skrivas ut som en högerjusterad sträng med totalt fyra tecken. I denna uppgift ska du utgå från den parser som vi arbetat med i kursen och som finns i rdparse.rb. Du ska skriva en ny parser som kan tolka ett mycket begränsat utbud av formatsträngar. Detta är ett exempel på hur din kod ska funka: >> fp=FormatParser.new => >> fp.format("Hello %s! %d is %x in hex.", "Peter", 42, 42) => "Hello Peter! 42 is 2a in hex." Du ska alltså implementera en ny parser FormatParser som har en metod format som tar en formatsträng och ett godtyckligt antal extra parametrar. Formatsträngen ska parsas och följande koder kan användas: %s Skriv ut motsvarande argument som en sträng %d Skriv ut motsvarande argument som ett tal %x Skriv ut motsvarande argument som ett hexadecimalt heltal Redovisa koden för FormatParser samt eventuella ändringar i originalparsern.