Datortentamen i TDP007 fredag 21 mars 2014 kl 14:00-18:00 --------------------------------------------------------- Tentan startar kl. 14:00 och pågår till 18:00. Ni kommer att få köra på begränsade datortentakonton. Instruktioner för att logga in på dessa lämnas i salen. Alla filer som ni behöver för att lösa uppgifterna finns i hemkatalogen när ni har loggat in. Där finns också en PDF-version av en tidig utgåva av kursboken 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. En fil per huvuduppgift ska produceras, totalt alltså sex filer. Ingen särskild inlämning behöver göras. När man är färdig loggar man ut och lämnar salen. Tentan består av sex 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. Om man redan har fått ett betyg genom duggan eller tidigare tentor kan det aldrig sänkas, bara höjas. Uppgift 1: Teorifrågor (5p) --------------------------- a) Vad är poängen med klassen Enumerable? Förklara med egna ord, alltså inte bara det som står i kursboken eller i manualen! (1p) b) Förklara kortfattat vad en DTD är och hur den förhåller sig till ett XML-dokument! (1p) c) Vad är den principiella skillnaden mellan trädparsning (DOM) och strömparsning (SAX)? (2p) d) Vad menas med begreppet token (i parser-sammanhang)? (1p) Uppgift 2: Behandling av data i textfiler (5p) ---------------------------------------------- I filen ingredienser.txt finns information om olika livsmedelsprodukter. Vi är nu intresserade av att med hjälp av reguljära uttryck ta fram vissa delar av denna information. För det första är vi intresserade av alla E-nummer som finns i ingredienslistan. För det andra är vi intresserade av närings- innehållet. Vi vill ha en funktion som kan läsa in den här informationen från filen till en hash-tabell så att det ser ut så här: >> read_ingredients("ingredienser.txt") {"Produkt 1"=>{"E"=>["E491", "E471", "E202", "E270", "E211", "E160a", "E101", "E330"], "Protein"=>"6.2", "Fett"=>"8.9", "Kolhydrater"=>"54.3", "Fiber"=>"1.8", "Natrium"=>"0.22"}, "Produkt 2"=>{"E"=>["E471", "E472e", "E300"], "Protein"=>"9.8", "Fett"=>"7.3", "Kolhydrater"=>"51.9", "Fiber"=>"3.9", "Natrium"=>"0.37"}, "Produkt 3"=>{"E"=>["E471", "E330", "E440", "E202", "E211", "E472e", "E331", "E300"], "Protein"=>"4.3", "Fett"=>"5.8", "Kolhydrater"=>"18.5", "Fiber"=>"1.8", "Natrium"=>"0.15"}} Funktionen ska fungera på vilka textfiler som helst som är uppbyggda på detta sätt, d.v.s. den ska inte bara funka för just denna fil. (Om det av någon anledning är svårt att hantera svenska tecken är det okej att ta bort eller modifiera dessa i datafilen.) Uppgift 3: XML (6p) ------------------- I filen tidtabeller.xml finns information om några av busslinjerna i en mindre stad. Informationen är uppdelad i tre delar: först information om de olika linjerna, därefter information om vid vilka tidpunkter de olika linjerna startar och sist information om busshållplatserna. a) Definiera en klass BusSystem som läser in information från en XML-fil strukturerad enligt samma format som i exempelfilen. Klassen ska ha två metoder get_stop_name som givet ett id för en hållplats ger namnet, samt get_line_description som givet ett id för en linje ger beskrivningen av densamma. Tanken är att det ska funka så här: >> bs = BusSystem.new("tidtabeller.xml") # >> bs.get_stop_name('igelg') "Igelgatan" >> bs.get_line_description('2') "Resecentrum-Violgatan-Resecentrum" Klassen BusSystem behöver i denna deluppgift inte klara av något mer än detta. (2p) b) Utöka klassen BusSystem med en funktion print_line som givet ett id för en linje skriver ut en formatterad tidtabell för linjen. Det ska funka så här: >> bs.print_line('2') Resecentrum 08.25 08.45 09.05 09.25 09.45 10.05 10.25 10.45 Drottninggatan 08.28 08.48 09.08 09.28 09.48 10.08 10.28 10.48 Lilla torget 08.32 08.52 09.12 09.32 09.52 10.12 10.32 10.52 Violgatan 08.34 08.54 09.14 09.34 09.54 10.14 10.34 10.54 Sippgatan 08.36 08.56 09.16 09.36 09.56 10.16 10.36 10.56 Badplatsen 08.42 09.02 09.22 09.42 10.02 10.22 10.42 11.02 Shoppingcentret 08.49 09.09 09.29 09.49 10.09 10.29 10.49 11.09 Resecentrum 08.52 09.12 09.32 09.52 10.12 10.32 10.52 11.12 Kolumnerna med tider motsvarar de olika starterna för linjen (som återfinns i 'tours'). (4p) Uppgift 4: DSL (5p) ------------------- 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 5: Icke-deterministisk programmering (5p) ------------------------------------------------- Georg Stenåker arbetar med att sätta ihop musiklistor till radiokanalen Max Megatönt som spelar den sämsta blandningen av gamla och ännu äldre låtar. I filen playlist.txt finns en lista med ett antal låtar som han har valt ut som möjlig utfyllnad i ännu ett helt meningslöst radioprogram. Han vill välja ut fyra olika låtar av dessa. För att få en blandning vill han dessutom att varje låt ska komma från ett annat årtionde än låten som kommer omedelbart innan. På hur många sätt kan man välja ut fyra låtar från denna lista enligt dessa förutsättningar? Lös problemet genom att först skriva en funktion som läser in låtlistan på valfritt sätt. Använd därefter problemlösaren i filen amb_test.rb för att hitta alla möjliga kombinationer. Uppgift 6: Parsning (6p) ------------------------ Det rykande färska språket STRIMLA (String Manipluation Language) är ett enkelt interpreterat språk för att manipulera textsträngar på olika sätt. Ett uttryck i STRIMLA kan se ut på fem olika sätt, vilket illustreras med följande exempel: [Hejsan] En enkel sträng anges med hakparenteser och den kan innehålla i princip vad som helst, förutom hakparenteser. 3x[banan] Detta skapar en sträng som innehåller banan tre gånger, d.v.s. "bananbananbanan". 2#[abc] Flyttar respektive tecken två steg framåt, d.v.s. resultatet är "cde". (Lös detta på enklast möjliga valfria sätt. Det behöver inte nödvändigtvis wrappas på något snyggt sätt heller.) [foo]&[fie] Slår ihop två strängar, d.v.s. "foofie". (2x[oh])&[hai] Parenteser kan användas för att bestämma prioriteten. I det här fallet blir resultatet "ohohhai". Alternativt skulle man kunna uttrycka syntaxen med en BNF-regel så här: EXPRESSION ::= STRING | INTEGER 'x' EXPRESSION | INTEGER '#' EXPRESSION | EXPRESSION '&' EXPRESSION | '(' EXPRESSION ')' Alla strängar måste omges med hakparenteser. Talet som står framför 'x' måste vara positivt, medan talet som står framför '#' även kan vara negativt. Din uppgift är att, med utgångspunkt från parsern i rdparse.rb, konstruera en parser för STRIMLA som kan hantera det språk som beskrivs ovan. Språket får inte utökas på något sätt som gör parsern enklare. Följande exempel visar hur det kan se ut: >> StrimlaParser.new.repl [STRIMLA] 4x[boom] => boomboomboomboom [STRIMLA] [I haz a ]&[pony!] => I haz a pony! [STRIMLA] (2x[HEJ ])&[MON]&-1#[JDB] => HEJ HEJ MONICA