Dugga 2 i TDP007 tisdag 10 mars 2014 kl 09.30-11.30 --------------------------------------------------- Duggan startar kl. 09.30 och pågår till 11.30. 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 t.ex. kommandot okular. Svar på frågor skrivs i vanliga textfiler och programkod skrivs i rb-filer. En fil per huvuduppgift ska produceras, totalt alltså fyra filer. Ingen särskild inlämning behöver göras. När man är färdig loggar man ut och lämnar salen. Duggan består av fyra uppgifter (några indelade i deluppgifter) som totalt kan ge 25 poäng. Dessa poäng summeras ihop med poängen från den första duggan. Uppgift 1: Teorifrågor (7p) --------------------------- a) Vad är skillnaden på lexikalisk och syntaktisk analys? (1p) b) Under en av föreläsningarna tittade vi på icke-deterministisk programmering. Då implementerade vi en problemlösare med hjälp av s.k. continuations. Vad är en continuation och vilken information finns gömd i den? Ge ett enkelt kodexempel som visar hur en continuation skapas och används! (2p) c) Hur fungerar parsern som finns i filen rdparse.rb? Förklara i grova drag hur den arbetar, t.ex. med utgångspunkt i exemplet DiceRoller. (2p) d) På vilka sätt skiljer sig ett domänspecifikt språk (DSL) från ett "vanligt" programmeringsspråk (eng. general purpose language, GPL). (2p) Uppgift 2: Constraint-nätverk (6p) ---------------------------------- a) Berra har ett bageri där hand bland annat bakar semlor. Han testar just nu en ny typ av jäst som ska få bullarna att bli extra stora. Storleken beror dock inte bara av jästen, utan på hur tätt bullarna står på plåten i ugnen. Leverantören av jästen hävdar att de har beräknat att höjden på bullarna varierar med avståndet till närmaste bulle enligt följande matematiska formel: h(x) = 7 + 4x - x^2 I den här formeln är x hur tätt bullarna sitter, och om man räknar ut formeln får man ut hur hög varje bulle kommer bli. Berra vill ju gärna räkna ut det här, men matte är inte riktigt hans favoritgrej. Han vill istället att du ska bygga ett constraint-nätverk för den här formeln, så att han kan testa den lite lättare. Alltså, med utgångspunkt från koden i constraint_networks.rb, bygg upp ett constraint-nätverk som motsvarar den här formeln. (Koden är behäftad med samma fel som koden inför seminarie 4, men det behöver inte påverka lösningen, och du behöver inte korrigera koden.) (3p) b) Berra är väldigt intresserad av hur höga bullarna kan bli som mest, och vad det optimala avståndet mellan bullarna är. Han vill att du ska skriva en funktion som testar det här constraint-nätverket och provar lite olika värden tills den hittar det största. (3p) Den metod som han föreslår är följande: Börja räkna ut vad h(x) blir för något bra startvärde på x. Pröva sedan att öka x lite grann och se om h(x) blir större. Om det blir större är vi på rätt väg och kan fortsätta att öka x lite grann. I annat fall backar vi tillbaka och försöker öka x lite mindre istället. Så där fortsätter man tills det steg som man ökar x med i varje omgång har blivit så litet att man är nöjd. Omvandlat till någon slags pseudokod kan det se ut så här: 1) Börja testa med x=1 och steg=1. Spara värdet av h(x). 2) Om steg är tillräckligt litet är vi klara. 3) Annars ökar vi x med steg och kollar vad h får för värde för x+steg. Är det större än det förra, sparade värdet på h? 3a) Ja. Spara det här nya h-värdet och gå tillbaka till punkt 2. 3b) Nej. Backa tillbaka genom att minska x med steg. Halvera sedan steg och försök igen på punkt 2. Uppgift 3: DSL (6p) ------------------- Rebeckas Restaurangservice utvecklar programvaror som används av caféer, restauranger och liknande inrättningar. En av deras produkter är ett kassa- och bokningssystem som ritar upp en schematisk bild av restaurangen på skärmen där man kan se alla bord. Servitörerna kan klicka på borden på skärmen för att mata in beställningar eller ordna kvitton. Rebecka vill gärna att restaurangägarna ska kunna konfigurera systemet själv, om man bygger om eller flyttar runt borden. Därför vill hon ha ett enkelt domänspecifikt språk för att specificera hur restaurangen ser ut. I filen pelles.rb finns ett exempel på en layout för Pelles Pizzeria. Varje fil börjar alltid med raden size , som anger hur stor bilden av restaurangen på skärmen ska vara i antal tecken. Därefter kan man använda kommandot table , , , för att definiera ett bord. Varje bord har ett unikt nummer och storleken avser hur många personer som kan sitta vid det. Koordinaterna pekar ut var på bilden bordet ska ritas ut. Man kan rita upp väggar eller andra hinder med kommandot wall , , , som innebär att man ritar ut en fyrkant på skärmen där den första koordinaten är övre vänstra hörnet och den andra är nedre högra. Alla andra kommandon, vilka som helst, innebär att namnet skrivs ut med stora bokstäver på skärmen med början på den koordinat som anges. Din uppgift är nu att med hjälp av de tekniker för DSL som vi har tittat på i Ruby skriva kod som kan tolka Rebeckas domänspecifika språk och bygga upp en datastruktur som motsvarar restauranglayouten. Vi vill kunna åstadkomma två saker: utskrift av restauranglayouten med enkel teckengrafik och lagring av information om respektive bord. Exempel: >> r = Restaurant.new("pelles.rb") # >> r.print .----------------------------------------. | | | ##### ENTRANCE ####################### | | | | | | .----. .----. .----. | | | 1 | | 8 | | 9 | | | '----' '----' '----' | | | | .----. .----. | | | 2 | | 10 | | | '----' '----' | | | | .----. | | | 3 | | | '----' ##################### | | # | | .----. .----. .----. .----. # | | | 4 | | 5 | | 6 | | 7 | # | | '----' '----' '----' '----' # | | | '----------------------------------------' >> r[5].size 4 Här har vi alltså tolkat koden i filen pelles.rb, vilket har resulterat i ett objekt r av klassen Restaurant. Vi kan skriva ut layouten med r.print samt kolla storleken på bord 5 med r[5].size. Skriv kod som gör detta möjligt. Uppgift 4: Parsning (6p) ------------------------ Cascading Style Sheets (CSS) är en teknik för att specificera hur en webbsida ska se ut. Tanken är att dokumentets struktur och innehåll ska ligga i en HTML-fil och att utseendet bestäms av en CSS-fil. På så sätt kan man separera innehåll och utseende, vilket ger många fördelar. Lite förenklat kan man säga att en CSS-fil specificerar för varje HTML-tagg hur den ska presenteras på skärmen. Följande korta exempel finns i filen example.css: h1 { font-weight: bold; font-size: 12px } p { font-size: 12px } /* px */ em { color: red } Detta säger att all text som taggas med

...

ska presenteras som fetstil i 12 punkters storlek, etc. CSS-filer kan se lite mer komplicerade ut, men för den här uppgiften utgår vi från att den består av en uppsättning regler som börjar med namnet på en tagg och fortsätter med en egenskapslista, inramad av { ... }. Egenskapslistan består av ett antal egenskaper där namnet skiljs från värdet med ett kolon. Om listan består av flera egenskaper ska det vara ett semikolon mellan egenskaperna, dock inte sist. Förutom detta kan det finnas kommentarer som inramas av /* ... */. Din uppgift är att utgå från den parser som finns i rdparse.rb och bygga en enkel parser som kan läsa in och tolka CSS-filer. Resultatet av parsningen ska vara någon form av datastruktur som innehåller de stilmallar som finns i filen, t.ex. i form av en hashtabell. Du behöver inte hantera mer komplicerade CSS-filer än filen example.css. Följande körexempel visar hur det skulle kunna se ut: irb(main):180:0> cp=CSSParser.new # irb(main):181:0> cp.load "example.css" (-klipp-) {"p"=>{"font-size"=>"12px"}, "em"=>{"color"=>"red"}, "h1"=>{"font-weight"=>"bold", "font-size"=>"12px"}}