Datortentamen i TDP007 fredag 7 juni 2013 kl 08:00-12:00 --------------------------------------------------------- Duggan startar kl. 08:00 och pågår till 12: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. Uppgift 1: Grundläggande Ruby och teorifrågor (5p) -------------------------------------------------- a) Konstruera ett reguljärt uttrycksom kan matcha olika stavningar av efternamnet "Ohlsson", med eller utan "h", med ett eller två "s", eller med "z"! (1p) b) 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 vara bättre. (2p) c) På vilka sätt skiljer sig ett domänspecifik språk (DSL) från ett "vanligt" programmeringsspråk? (2p) Uppgift 2: Behandling av data i textfiler (5p) ---------------------------------------------- I filen bnp.txt finns en tabell som visar Sveriges BNP (bruttonationalprodukt) för åren 1958-2008. BNP är värdet av alla produkter och tjänster som producerats i landet under ett givet år. I tabellen visas BNP i miljoner kronor. Det tredje talet per rad är folkmängden i tusental personer. Skriv ett Ruby-program som läser in tabellen och lagrar den i en lämplig datastruktur. Inläsningen ska vara såpass generell att den fungerar även om mindre justeringar i formatet görs. Beräkna därefter BNP per capita, d.v.s. per person, för varje år i tabellen. Definiera sedan två olika funktioner som kan hämta ut information ur tabellen enligt följande: Den första funktionen ska skriva ut den procentuella ökningen av BNP per capita från ett år till ett annat. Det första året i originaltabellen kan alltså inte vara med i det här resultatet. Utskriften ska vara korrekt formatterad enligt följande: 1959 6.0% 1960 8.3% 1961 8.3% 1962 7.8% 1963 7.6% 1964 10.7% Ovanstående utskrift ska tolkas så att BNP per capita ökade med 6.0% från 1958 till 1959. Den andra funktionen ska enbart skriva ut de årtal som BNP per capita var lägre än året innan. Uppgift 3: XML (6p) ------------------- I filen library.xml finns uppgifter om ett antal böcker. Utdata kommer från den svenska nationella biblioteksdatabasen Libris som man hittar på webben på adressen http://libris.kb.se/ och det är i det standardiserade formatet MARC-XML. MARC är ett format som funnits i biblioteksvärlden under lång tid och MARC-XML är helt enkelt denna information överförd till XML. Stora delar av det här formatet är obegripligt för oss som inte är i biblioteksbranschen, men genom att titta lite på filen kan man rätt snart komma fram till huvuddragen. Filen består av en 'collection' som i sin tur är uppbyggd av ett antal 'record'. Varje 'record' motsvarar en bok och innehåller bl.a. ett antal 'datafield' som i sin tur kan bestå av 'subfield'. Varje 'datafield' har en standardiserad 'tag' och varje 'subfield' har en 'code'. Det är dessa siffror och bokstäver som talar om vilken information som faktiskt finns i filen. Följande tabell summerar vad vi behöver veta för att lösa uppgiften. datafield tag subfield code innehåll ------------------------------------------------------- 100 a Författarens namn 245 a Bokens titel 260 c Utgivningsår Uppgiften är att skriva en funktion som kan läsa igenom filen och skriva ut en enkel lista över de fjorton böcker som finns i filen. Det ska alltså se ut ungefär så här: >> print_library("library.xml") Coupland, Douglas (2004) Eleanor Rigby Coupland, Douglas (1992) Generation X ... I uppgiften ingår dessutom att "städa upp" den textinformation som finns i XML-filen, så att inga onödiga tecken (som inte kan antas finnas med i författare, titel och år) skrivs ut. Uppgiften kan lösas antingen med REXML-paketet (trädparsning) eller med strömparsning. Lite hjälp för båda dessa metoder finns i filerna rexml.txt samt sax_example.rb. Samtliga böcker i listan är för övrigt mycket läsvärda. Uppgift 4: DSL (5p) ------------------- I textfilen relations.rb finns ett antal faktapåstående om relationer kodade. Alla dessa faktapåståenden inleds med namnet på relationen, följt av de två saker/personer/begrepp som har denna relation. Det första exemplet i filen är: father "Anders", "Pelle" father "Pelle", "Lisa" Med detta menar vi att Anders är far till Pelle och att Pelle är far till Lisa. (Åt vilket håll relationen är riktad får vi själva hålla reda på. I det här fallet står pappan först och barnet sedan.) I den här uppgiften ska du betrakta filen relations.rb som programkod i ett litet internt DSL (domänspecifikt språk). Du ska skriva en metod som kan läsa in all information från filen, som om den vore programkod, och spara den i en lämplig datastruktur. Lösningen ska klara av vilka namn på relationer som helst, inte bara de som finns i detta exempel. Därefter ska du skriva en metod find som kan ta reda på saker med hjälp av informationen som lästs in. Metoden find ska ta tre argument: namnet på relationen samt två saker som vi tror kanske har den här relationen. En av sakerna kan vara nil, och i så fall hittar vi alla möjliga matchningar. Exempel: >> r=Relations.load("relations.rb") => # >> r.find("is_a","Apple","Fruit") => [["Apple", "Fruit"]] >> r.find("father","Pelle",nil) => [["Pelle", "Lisa"], ["Pelle", "Stina"]] >> r.find("boss",nil,"Bob") => [["Roger", "Bob"]] Första anropet till find ger oss en Array med paret "Apple" och "Fruit", vilket innebär att det faktiskt är så att äpple är en frukt (enligt vad filen påstår i alla fall). Det andra anropet till find tar reda på alla som Pelle är far till (Lisa och Stina). Det tredje anropet hittar vem som är Bobs chef (Roger). Om det inte finns något svar ska någonting tomt returneras, t.ex. nil eller en tom Array. Datastrukturen behöver inte nödvändigtvis vara en Array, även om den är det i detta exempel. Uppgift 5: Constraint-nätverk (5p) ---------------------------------- I filen constraint_networks.rb finns kod för att bygga restriktionsnät som vi diskuterade i samband med seminarie 4. Vi tänker oss att du har löst seminarieuppgifterna och kan skapa ett nät för att omvandla mellan Celsius och Fahrenheit. Användningen av denna omvandlare kunde se ut ungefär så här: irb(main):176:0> c,f=create_temperature_network [#, #] irb(main):177:0> c.user_assign 0 "ok" irb(main):178:0> f.value 32 Antag att vi vill använda intervall istället för heltal. Vad blir 18-20 grader Celsius i Fahrenheit? Då vill vi kunna göra så här: irb(main):179:0> c.user_assign 18..20 "ok" irb(main):180:0> f.value 64..68 irb(main):181:0> Vad behöver göras för att uppnå detta? Du behöver inte implementera temperaturomvandlingen igen, utan skriv bara kod som gör att de constraints som finns i filen kan hantera även intervall. När vi skriver 18..20 avses alltså en instans av klassen Range. Uppgift 6: Parsning (6p) ------------------------ En grundskola vill ha ett enkelt system för att träna elever att räkna på engelska. Vi ska bara använda talen 0 till 20 och bara operationerna plus och minus. Tanken är att eleverna ska skriva in meningar på engelska och få svar uträknade. I princip kan man göra två saker: räkna ut vad någonting blir eller göra en jämförelse. Följande körexempel illustrerar allt man kan göra: >> np=NumberParser.new => # >> np.log(false) => 2 >> np.repl [NumberParser] one plus two => 3 [NumberParser] two plus three is five => yes [NumberParser] four minus three is greater than four => no [NumberParser] one plus one plus one => 3 [NumberParser] one minus two is negative one => yes [NumberParser] negative three plus three is zero => yes Resultaten av en beräkning ska vara ett tal (med siffror) och resultatet av en jämförelse ska vara antingen 'yes' eller 'no'. Man kan använda negativa tal genom att skriva 'negative' framför. Vad som händer om man råkar gå utanför intervallet -20 till +20 är odefinierat, d.v.s. det spelar ingen roll. Grammatiken för det här lilla språket ser ut så här: VALID ::= EXPR | COMP EXPR ::= NUMBER | EXPR plus EXPR | EXPR minus EXPR COMP ::= EXPR is EXPR | EXPR is less than EXPR | EXPR is greater than EXPR NUMBER ::= NUM | negative NUM NUM ::= one | two | three | ... | twenty Din uppgift är att, med utgångspunkt från exempelparsern i filen rdparse.rb, konstruera en parser för den här begränsade delen av engelska språket. Observera att reglernas ordning - både i lexern och parsern - kan spela roll! Om du vill får du utöka språket, men inte på ett sätt som gör uppgiften lättare. Omvandligen mellan tal som strängar ('one', 'two', etc) och siffror (1, 2, etc) gör du lämpligen inte i parserreglerna. Det är dock helt okej att ha en hårdkodad tabell.