Dugga 2 i TDP007 fredag 2 mars 2012 kl 15.15-17.00 -------------------------------------------------- Uppgift 1: Teorifrågor (5p) --------------------------- a) Vad är en lexer? (1p) b) På vilka sätt skiljer sig ett domänspecifikt språk (DSL) från ett "vanligt" programmeringsspråk (eng. general purpose language, GPL). (2p) c) 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) Uppgift 2: Constraint-nätverk (6p) ---------------------------------- I filen constraint_networks.rb finns de restriktionsnät som vi arbetat med under föreläsningar och seminarier. Din uppgift är att konstruera en ny constraint som kan slå ihop två strängar till en. Vi tänker oss att denna nya constraint tar två indata-strängar, a och b, och som resultat ger en utdata-sträng c som är en sammanslagning av dessa två strängar. Om vi har skapat tre "connectors" och satt ihop dessa med hjälp av vår nya constraint borde vi kunna skriva så här: >> a.user_assign("foo") => "ok" >> b.user_assign("bar") => "ok" >> c.value == "foobar" => true Vår nya constraint ska fungera åt båda hållen. Om vi t.ex. känner till värdet på a och c bör vi kunna räkna ut värdet på b. Förutom att konstruera en constraint ska du också skapa ett antal lämpliga och heltäckande testfall. Uppgift 3: DSL (7p) ------------------- 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 4: Parsning (7p) ------------------------ 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.