Uppgifter för dugga 2 i TDP007 2011-03-11 ----------------------------------------- Uppgift 1: Teorifrågor (5p) --------------------------- a) Vad menas med begreppet token (i parser-sammanhang)? (1p) b) Vad är ett domänspecifikt språk? Vad kan man hoppas uppnå genom att skapa ett sådant? (2p) c) I uppgift 3 längre ner i duggan ska man hitta alla möjliga kombinationer med hjälp av problemlösaren i filen amb.rb. Vad är poängen med att använda den istället för att bara sätta upp en massa for-loopar eller liknande? (2p) Uppgift 2: Domänspecifika språk (5p) ------------------------------------ Elinor arbetar på ett företag som utvecklar affärssystem, alltså programvara som företag använder för att hålla ordning på allt, t.ex. lager, fakturor, beställningar, kassakvitton. Deras programvara är utvecklad i Ruby. Varje företag som installerar deras system måste konstruera en fil med inställningar som innehåller olika basuppgifter om företaget. I version 2.3 ser den här filen ut så här: company: Lennarts ostlager AB store: Ost-Lennart manager: Lennart Abrahamsson greeting: Välkommen åter önskar Lennart med medarbetare! Elinor har nu läst en del om domänspecifika språk och kommit fram till att det vore jättebra att ändra på de här inställningsfilerna inför version 3.0. Hon vill att man ska betrakta inställningsfilen som ett domänspecifikt språk. Hennes tanke är att man med rätt små modifikationer kan skriva så här istället: company "Lennarts ostlager AB" store "Ost-Lennart" managerfn "Lennart" managersn "Abrahamsson" greeting "Välkommen till #{store} önskar #{managerfn} med medarbetare!" manager "#{managerfn} #{managersn}" Som man ser i exemplet kan man återanvända inställningar längre ner, eftersom det här i praktiken är någon slags anpassad Ruby-kod. Elinor vill i slutändan att det ska funka ungefär så här: >> c=Configuration.load("config.rb") => ... >> c.manager => "Lennart Abrahamsson" Konstruera klassen Configuration som kan läsa in den här typen av (nya) konfigurationsfiler och lagra informationen i attribut. För full poäng ska du konstruera en lösning som klarar av vilka inställningar som helst. För halva poängen kan du istället välja att göra en lösning som enbart funkar med de inställningar som finns i exemplet ovan. Uppgift 3: 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.rb för att hitta alla möjliga kombinationer. Uppgift 4: Constraint-nätverk (5p) ---------------------------------- a) Monica, som driver företaget Monicas Handelsträdgård, ska sätta en massa lökar för att driva upp amaryllis (en stor klockliknande blomma som folk gärna köper till jul). Leverantören av lökarna hävdar att höjden på växterna beror på hur tätt man sätter dem. Han har till och med en matematisk formel som säger hur höga de blir: h(x) = 5 + 3x - x^2 I den här formeln är x hur tätt lökarna sitter, och om man räknar ut formeln får man ut hur hög varje växt kommer bli. Monica vill ju gärna räkna ut det här, men matte är inte riktigt hennes favoritgrej. Hon vill istället att du ska bygga ett constraint-nätverk för den här formeln, så att hon 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) Monica är väldigt intresserad av hur höga blommorna kan bli som mest, och vad det optimala avståndet mellan plantorna är. Hon 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. (2p) Den metod som hon 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 5: Parsning (5p) ------------------------ 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: irb(main):189:0> 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