Datortentamen i TDP007 Konstruktion av datorspråk 2012-05-22 ------------------------------------------------------------ Uppgift 1: Grundläggande Ruby och teorifrågor (5p) -------------------------------------------------- a) Vad är det för skillnad på om ett XML-dokument är "valid" respektive "well-formed"? (1p) b) Vad är en lexer och hur fungerar den i grova drag? (1p) c) Vad är skillnaden på att skriva var, @var respektive @@var? (1p) d) Konstruera ett reguljärt uttryck som kan matcha en korrekt e-postadress! (2p) Uppgift 2: Reguljära uttryck och textfiler (6p) ----------------------------------------------- a) LIX eller läsbarhetsindex är ett mått på hur lätt- eller svårläst en text är. Metoden utvecklades på 1960-talet av pedagogen Carl-Hugo Björnsson. Formeln för att beräkna LIX för en text är följande: O L*100 LIX = --- + ------- M O O = antalet ord i texten M = antalet meningar i texten L = antalet långa ord (över 6 bokstäver) Följande tabell visar LIX-värden för olika typer av texter: -25 Barnböcker 25-30 Enkla texter 30-40 Normaltext (skönlitteratur) 40-50 Sakinformation (t.ex. uppslagsverk) 50-60 Facktexter 60- Svåra facktexter (t.ex. forskningsartiklar) Skriv en metod som kan läsa in en textfil och beräkna LIX för texten. För att ha något att öva på finns filerna lagerlof.txt som innehåller första kapitelet av "Gösta Berlings saga" och strindberg.txt som innehåller första kapitlet av "Röda Rummet". Man kan givetvis testa med den textfil som innehåller tentauppgifterna också. (3p) b) Skriv en metod som kan läsa in en textfil och räkna ut vilka de fem vanligaste orden är, oavsett om det är stora eller små bokstäver. (3p) Uppgift 3: XML (5p) ------------------- Sture driver en liten kiosk som heter "Stures kiosk" kort och gott. Stures revisor har flera gånger påpekat att Sture borde göra en uppskattning av hur mycket allt godis i kiosken är värt, åtminstone en gång i veckan. Det skulle vara bra, både för Stures bokföring och för Stures försäkringsbolag. Eftersom det inte riktigt håller att räkna alla grejer vill Sture hitta på ett annat sätt. Han har ett datoriserat kassasystem som kan mata ut en XML-fil med information om hur mycket kassasystemet tror att det finns i kiosken. Det kan duga som underlag. Dock behöver varorna i XML-filen summeras så att man vet vad allt är värt tillsammans. Det är här som du kommer in i bilden. Din uppgift är att skriva ett Ruby-program som kan läsa igenom XML-filen med uppgift om godiset i Stures kiosk och tala om vad allt är värt. Sture är inte jättenoga med om det blir en SAX- eller DOM-lösning, så du får välja. Du har lite hjälp av filerna sax_example.rb eller rexml.txt. Tanken är att när allt är klart så ska Sture kunna skriva så här vid Ruby-prompten: >> value("lager.xml") => 2665.0 Svaret innebär alltså att det totala värdet av allt godis som finns i kiosken är 2665 kr. Uppgift 4: DSL (5p) ------------------- Bob Arlington, även känd som "Bob the Builder", äger en kedja av bygg- och järnaffärer runt om i USA. En gång per månad vill han ha en sammanställning av hur mycket som har sålts i alla affärer. Hans utvecklingsavdelning har lyckats skriva ett program som kan generera rapporter från de olika affärerna och ett exempel på en sådan månadsrapport finns i filen sales.rb. Det som behöver göras nu är att gå igenom rapporten och summera hur många som sålts av varje vara. Bob vill att du ska göra detta med hjälp av någon teknik för domänspecifika språk i Ruby. Du ska alltså betrakta den här textfilen som källkod och skriva ett litet program som kan köra filen och därmed få fram statistiken som Bob vill ha. Som du ser i filen finns det tre huvudtyper av artiklar som Bob säljer. Han vill veta vilken artikel i varje kategori som säljer bäst. I praktiken innebär det att han vill att det ska funka ungefär så här: >> s=SalesAccumulator.load("sales.rb") => # >> s.most_popular For tool the most popular item is pliers (61) For fixing the most popular item is shank_nail (97) For other the most popular item is ear_plugs (82) => nil Definiera klassen SalesAccumulator som kommer fungera som en enkel interpretator för det lilla domänspecifika språket. Klassen ska kunna läsa in och summera artiklar, samt tala om vilken som säljer bäst i varje kategori. Klassen ska utformas på ett sådant sätt att det inte blir några problem om Bob börjar sälja andra artiklar, dvs hårdkoda så lite som möjligt. Uppgift 5: Constraint-nätverk (5p) ---------------------------------- Den här uppgiften ska vi så småningom lösa genom att bygga ett constraint-nätverk, men först en introduktion till problemet. Två bilar A och B startar samtidigt i två olika städer som vi också kan kalla A och B. De kör mot varandra på samma väg och kommer, om inget oförutsett inträffar, att mötas någonstans på ungefär halva vägen. För enkelhets skull antar vi att bilarna kör med konstant hastighet hela tiden, den ena något fortare än den andra. Huvudfrågan är var någonstans på vägen de kommer att mötas. Förhållandet mellan sträcka, hastighet och tid kan uttryckas med formeln s = h*t. För att hålla reda på de två bilarna lägger vi till A och B efter, och får alltså två formler: sA = hA*tA och sB = hB*tB. Bilarna kommer mötas samtidigt, dvs när tA = tB, och vi kan då slå ihop formlerna till en enda: sA/hA = sB/hB Vi vet också att summan av sA och sB måste vara hela vägens sträcka, som vi kan kalla s. Vi skulle alltså kunna skriva: sA/hA = (s-sA)/hB Detta kan vi i olika steg omvandla så här: sA*hB/hA = s-sA sA*(1+hB/hA) = s Din uppgift är att bygga upp ett constraint-nätverk som motsvarar ovanstående formel, med utgångspunkt i koden i constraint_networks.rb. Uppgift 6: Parsning (6p) ------------------------ Med utgångpunkt från parsern som finns i filen rdparse.rb ska du bygga en parser som kan tolka textsträngar som innehåller kemiska formler. Parsern ska bygga upp någon form av datastruktur som motsvarar den molekyl som formeln betecknar. Denna datastruktur ska innehålla uppgifter om hur många av respektive atomslag som ingår i molekylen. Här är ett exempel på hur det ska funka: >> cp=ChemicalParser.new => # >> cp.parse("C2H5OH") => [#, #, #] Formeln C2H5OH betecknar etanol, dvs vanlig sprit. Den innehåller två st kolatomer (C), fem st väteatomer (H) och därefter en syreatom (O) och ytterligare en väteatom (H). Parsern har räknat ihop alla dessa och svarar med en array som innehåler tre structar, och där ser vi att alla väteatomerna har räknats ihop till 6 st. Den datastruktur som din lösning skapar behöver inte se ut exakt så här, så länge samma information finns med och den summerar ihop alla atomer av varje slag. En kemisk formel består av ett eller flera atomslag. Om det inte står något tal direkt efter symbolen betyder det att det endast är en atom, annars är det så många som talet anger. Samma atomslag kan förekomma flera gånger i formeln, men får bara förekomma en gång i den resulterande datastrukturen. Din parser ska åtminstone klara av följande grundämnen: Symbol Engelskt namn Svenskt namn ------------------------------------- H Hydrogen Väte B Boron Bor C Carbon Kol N Nitrogen Kväve O Oxygen Syre Cl Chlorine Klor Ba Barium Barium Här är exempel på några formler som din parser ska klara av: Formel Namn -------------------------------- C2H5OH Etanol (vanlig sprit) BaC2O4 Bariumoxalat CHCl3 Kloroform CH2O Formaldehyd BN Bornitrid Namnen ska inte hanteras av parsern. De är bara med för att det är kul.