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
=> <FormatParser:0x2ad5f0 ... >
>> 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.