TILDA, ÖVNING 5 Syntax, bästaförstsökning **************************************************************** FRÅGOR 1. Syntax för kanadensare Olle sitter och rättar ett tentatal. Tentatalet går ut på att man ska sriva en grammatik för meddelanden av följande typ: Kanot 42, kanot 666, kanot 4711 och kanot 17 ska in! Kanot 1 och kanot 2 ska in! Kanot 13 ska in! Vilken eller vilka av följande fyra alternativ kan producera dessa meddelanden? Motivera med exempel varför de övriga inte kan producera dem. En del av alternativen kan producera oönskade meningar, man vill tex inte ha 'Kanot 1 och kanot 2, kanot 3 och kanot 4 ska in!' Vilket eller vilka av alternativen kan producera oönskade meningar? Ge exempel. ::= Kanot | kanot ::= och| ska in! | , ::= 1 | 2 | 3 | ... ::= Kanot ska in! | Kanot ::= och kanot ska in! | , kanot ::= 1 | 2 | 3 | ... ::= Kanot ::= ska in! | , kanot | och kanot ::= | 1 | 2 | 3 | ... ::= Kanot | kanot ::= ska in! | , | och ::= 1 | 2 | 3 | ... 2.000831: Värsta webbsyntaxen En webbfil innehåller dels webbsidans text, dels taggar för radbrytningar och indragningar. Taggen
ger ny rad och för att få indragning av ett textavsnitt skriver man taggen före och taggen efter. Exempelvis ger webbfilen Organismer
Djur
Flugor
Sillar
Svamp
Flugsvamp
Sillkremla
följande webbsideutseende: Organismer Djur Flugor Sillar Svamp Flugsvamp Sillkremla Skriv en syntax för webbfiler där endast dessa taggar och vanlig text förekommer. Du kan få använda för att beteckna godtycklig taggfri text. 3. SYNTAX FÖR TROENDE (Efter tildatenta 7 mars 1998, uppgift 6.) DU TROR INTE ATT JAG VET ATT DU INTE TROR ATT JAG TROR. Skriv en syntax för meningar av denna typ. Använd symbolerna , , , }. Endast ord ur exempelmeningen kan förekomma, men även den enkla meningen DU VET ska uppfylla syntaxen. Observera att INTE placeras olika i huvudsats och attsats. Beskriv i ord hur ett program kan undersöka om meningar följer din syntax! Vilka procedurer behövs? 4. 020406: Båtflytt Under en seglingstävling vill varje båt hitta den snabbaste vägen till målet. Problemet är att en segelbåt inte kan segla hur som helst och att den seglar olika snabbt beroende på vindriktning och styrka. Antag att havet förenklat består av en massa jämnt fördelade punkter med information om vindstyrka, vindriktning och vilka punkter som finns runt om. Beskriv utförligt en algoritm som på ett så effektivt sätt som möjligt tar reda på vilka punkter som ligger utefter den snabbaste seglingsvägen givet en startpunkt och en slutpunkt. Båtägaren är orolig att hans miljövänliga bottenfärg ska nötas bort och vill därför istället ta den väg som är kortast (dvs minst antal steg). Förklara utförligt vad som behöver ändras i din föregående algoritm. **************************************************************** LÖSNINGAR 1. Syntax för kanadensare Alternativ 1 och 2 kan producera alla meningarna. Alternativ 3 och fyra kan inte producera 'Kanot 1 och kanot 2 ska in!' Alternativ 1 och 4 godkänner felaktigt 'Kanot 4 och'. Alternativ 3 godkänner felaktigt 'Kanot och kanot 2'. 2. Värsta webbsyntaxen ::= | | |
::= "" ::= ""
::= "
" 3. SYNTAX FÖR TROENDE (Efter tildatenta 7 mars 1998, uppgift 6.) ::= . | INTE . ::= JAG | DU ::= TROR | VET ::= | ATT ::= ATT INTE from queue import Queue q=Queue() for ord in raw_input("Skriv en mening:").split(): if ord[-1]==".": q.put(ord[0:-1]) q.put(".") else: q.put(ord) def readmening(): readsubj() readpred() if q.peek()=="INTE": q.get() readattsats() readpunkt() def readattsats(): if q.peek()=="ATT": q.get() readsubj() if q.peek()=="INTE": q.get() readpred() readattsats() def readsubj(): ord = q.get() if ord=="JAG": return if ord=="DU": return raise Exception,"Fel subjekt:"+ord def readpred(): ord = q.get() if ord=="TROR": return if ord=="VET": return raise Exception, "Fel predikat:"+ord def readpunkt(): punkt=q.get() if punkt==".": return raise Exception, "Fel punkt:"+ord try: readmening() if q.isempty(): print "Följer syntaxen!" else: print "Överblivna ord på slutet:" while not q.isempty(): print q.get(), print except Exception,msg: print msg,"före", while not q.isempty(): print q.get(), print 4. 020406: Båtflytt Använd bästaförstsökning med en prioritetskö som prioriterar på lägsta seglade totaltiden. Låt varje nod innehålla total seglingstid samt ha en faderspekare (för rekursiv utskrift av vägen då lösning hittats). Princip för genomgång av problemträdet: 1.Lägg startpunktsnoden med totaltiden noll och tom faderspekare i priokön. 2.Upprepa punkterna 3-4 så länge kön inte är tom. 3.Plocka ut en fadersnod ur kön. Om detta är slutpunkten, skriv ut vägen rekursivt och avsluta. 4.Generera en son i taget genom att för varje punkt runt omkring fadersnoden skapa en sonnod med seglingstiden ökad beroende på vindstyrka, vindriktning och placering i förhållande till fadersnoden. Lägg in sonnoden i priokön. Om dumsonskoll ska utnyttjas måste det ta hänsyn till både punkten och totala seglingstiden till den punkten. Alla söner med sämre tider till samma punkt är då dumsöner. På det viset slipper algoritmen besöka samma punkt flera gånger - den blir effektivare. Eventuellt krävs någon snabb uppslagning av punkternas information, t ex med en hashtabell som hashar på punkternas nummer eller position. Noderna kan innehålla lägsta tid som uppnåtts för att tillåta dumsonkoll utan att kräva extra minne. För kortaste vägen, använd istället bredden först med en vanlig kö och blanda inte in totala seglingstiden i varje nod. I detta fall måste vi göra dumsons koll för att sökningen ska bli effektiv. Datastrukturer: Prioritetskö / kö Hashtabell Noder med seglingsdata