Introduktion - varför, vad, och hur?

Denna laboration är praktiskt inriktad. Vi tittar på en viktig tillämpning av automatateori för programvaruframställning.

Varför? En viktig praktisk tillämpning av automatateori är för konstruktion av olika slags program som tar text som indata och från denna konstruerar något slags strukturerad information som sedan bearbetas vidare. Indata kan vara ett program i ett programmeringsspråk som C++, Java eller ML, en text i ett typsättningsspråk som T_EX, en sida i HTML, en mening i ett naturligt språk, eller något helt annat.

Betrakta t.ex. en kompilator för ett språk som C eller Java. En typisk sådan kompilator kan delas upp i två delar: framstycket och bakstycket (frontend/backend på engelska). Framstycket kontrollerar att indata är syntaktiskt korrekt och omvandlar det till en mer strukturerad form, en mellanrepresentation som t.ex. kan vara något slags träd. Bakstycket producerar sedan assembler eller maskinkod från mellanrepresentationen. För att hjälpa till med kodningen av framstycket finns det kraftfulla verktyg baserade på automatateori, ofta kallade parser-generatorer. Sådana verktyg tar en beskrivning av framstycket formulerat i automatateoretiska termer som indata och producerar ett program som utdata.

Målet med den här laborationen är att ge en uppfattning om hur ett sådant verktyg kan se ut och hur det används, fast i en mer användarvänlig och hanterlig variant än i praktiken.

Vad? Laborationen går ut på att konstruera en liten miniräknare som klarar av parenteser, att multiplikation går före addition, och så vidare. Givet indata (2 + 3)*4 + 2*11 ska miniräknaren ge svaret 42. Vidare ska naturligtvis felaktiga indata upptäckas.

Hur? Miniräknaren ska delas upp i ett framstycke och ett bakstycke, mellanrepresentationen ska vara ett parse-träd. I AAAAA finns funktioner (motsvarande en kombination av Unix-verktygen Lex och Yacc) för att konstruera framstycket automatiskt från en beskrivning bestående av ett antal reguljära uttryck och en sammanhangsfri grammatik. Dessutom finns ett färdigskrivet bakstycke för en miniräknare tillgängligt (som den verkligt intresserade studenten givetvis kan modifiera). Det som återstår att göra är alltså att konstruera beskrivningen av framstycket. Grammatiken som ska konstrueras är en vanlig sammanhangsfri grammatik i grunden, men den måste ha en hel del speciella egenskaper för att det hela ska fungera, och laborationen går igenom dessa steg för steg.

Om du efter denna laboration vill veta mer om verktygen Lex och Yacc, se A Guide to Lex & Yacc.

Teori

Från ett träd till ett tal. Ett sätt att strukturera upp ett aritmetiskt utryck är i form av ett träd. Trädets struktur kan då koda parenteser och underförstådda parenteser, så dessa behöver inte anges explicit. Det är också enkelt att givet trädet för ett uttryck, räkna ut värdet av utrycket:

Miniräknarens bakstycke (som finns inbyggt i AAAAA) kan utföra beräkningar av ovanstående typ givet ett parse-träd.

Att hitta rätt träd. Låt oss börja med en förenklad miniräknare där inputalfabetet är {+, * , 2}. En rättfram grammatik för aritmetiska uttryck över nämnda alfabet kan t.ex. se ut som

Denna grammatik duger bra om vi bara vill kontrollera om en sträng finns med i språket eller inte, men för vår miniräknare vill vi ju ha ett parse-träd som hjälper oss att räkna ut rätt svar. Om strängen t.ex. skulle vara 2*2 + 2 så vill vi först utföra multiplikationen och sedan additionen, som i det första trädet ovanför. Tyvärr är även det andra trädet ett möjligt parse-träd för denna grammatik. Det finns helt enkelt inget i grammatiken som säger att multiplikation borde räknas ut före addition. Lösningen på problemet är att skriva en ny grammatik som bara har ett möjligt parse-träd för varje given inputsträng, och där det unika parseträdet ger önskat svar när man "räknar ut trädet''. Här är en sådan grammatik som till skillnad från den förra särbehandlar multiplikativa uttryck från additiva:

Denna grammatik (som fortsättningsvis kallas G) beskriver aritmetiska uttryck på ett hierarkiskt sätt:

Ju längre fram i kedjan, ju närmare löven och desto hårdare binder operatorerna som förekommer i reglerna.

Övningar

Starta AAAAA och klicka "New''. Välj "Regular lexer + LR(1) parser'' från menyn. Mata in ovanstående grammatik G, med E som startsymbol. I det nedre fältet, mata in det reguljära uttrycket Ø. Innehållet i dessa fält är indata till AAAAA:s parser-generator.

Klicka nu "Build Parser''. Detta motsvarar att köra parser-generatorn. Resultatet bör nu bli ett nytt fönster "LR(1) parser for -L1-'' (om språket var -L1-). Detta är det program som parser-generatorn genererade, alltså själva parsern. I dess textruta kan nu ett uttryck som 2*2+2 matas in. (Obs! Inga blankslag eller radbrytningar är tillåtna i inputsträngen. Vi ska strax åtgärda detta.) Klicka "Parse'' och ett parse-träd ritas upp. Klicka över radio-knappen från värdet "Show parse tree'' till "Show values'' och uträkningen visas. Om du ändrar beskrivningen och vill göra "Build Parser'' fast i samma fönster som förra gången, så kan du klicka "Update''. (Inte att förväxla med "Reinitialize''.)

Naturligtvis har miniräknaren så här långt ett antal brister. Mest påfallande är att det enda tillåtna talet är 2, andra brister är att det bara finns multiplikation och addition, inga parenteser, subtraktion, unärt minus eller division. Dessutom tillåts inga blanktecken eller radbrytningar. Allt detta ska åtgärdas.

UPPGIFT 1 Utöka grammatiken G med parenteser och unärt minus. Unärt minus ska binda hårdare än både addition och multiplikation, så -2+2 betyder (-2)+2, och -2*2 betyder (-2)*2. Om din grammatik inte är entydig, eller AAAAA inte kan inse att den är entydig (tekniskt att den inte tillhör grammatik-klassen LR(1), som är en delmängd av alla CFGer), så kommer AAAAA att visa ett fönster med titeln "LR(1) Parsing Conflicts'' som försöker beskriva var problemet uppstår. Ändra i så fall grammatiken så att ingen konflikt uppstår. Notera att det i vissa fall är möjligt att använda en grammatik med konflikter, men att sådana inte kommer att godkännas i denna laboration. Denna grammatik ska vara del av rapporten, så spara språket under namnet G.

UPPGIFT 2 När det gäller en operation som subtraktion måste man tänka på vilken av två subtraktioner som ska utföras först. 2-2-2 betyder (2-2)-2, inte 2-(2-2). Vi säger att subtraktion associerar till vänster. Division associerar också till vänster. I matematik är addition och multiplikation associativa, så det borde inte spela någon roll om man definierade dem som att de associerade till vänster eller höger. I programmeringsspråk har det däremot viss betydelse för flyttal p.g.a. den begränsade precisionen, och det är brukligt att associera till vänster även för dessa. Konstruera en version av den ursprungliga grammatiken G där addition och multiplikation associerar till höger istället för till vänster. Gör detta genom att i AAAAA först skapa en kopia av G, och sedan modifiera kopian. Spara resultatet under namnet G2.

UPPGIFT 3 En fullfjädrad kalkylator ska förstås kunna hantera samtliga fyra elementära binära räkneoperationer. Vår kalkylator klarar inte av subtraktion och division. Det ska vi åtgärda.
Skapa därför (i AAAAA) ännu en kopia av G, och utöka sedan kopian med regler för subtraktion och division. Spara resultatet under namnet G3.

UPPGIFT 4 När nu kalkylatorn kan hantera alla elementära räkneoperationer, så återstår det att se till att den även kan räkna med andra tal än 2.
Din uppgift är här att utöka (en kopia av) G3 så att godtyckliga naturliga tal kan ges i indatat till kalkylatorn. Det kan åstadkommas genom att terminalen 2 ersätts med ett reguljärt uttryck som beskriver godtyckliga naturliga tal.
Vi vill f.ö. att kalkylatorn inte skall tillåta inmatning av siffersträngar med onödiga inledande nollor som t.ex. 041. Tänk på det, när du konstruerar ett reguljärt uttryck för naturliga tal.
ANM. För att sätta in ett reguljärt uttryck i AAAAA:s grammatik omgjärdas uttrycket av mustaschparanteser, som i regeln F→{0∪1}. I syfte att förenkla beteckningen förser oss AAAAA förresten med kortnotationen 0...9 för unionen 0∪1∪2∪3∪4∪5∪6∪7∪8∪9. Spara din utökning av G3 under namnet G4.

UPPGIFT 5 Här skall du modifiera kalkylatorn så att den nonchalerar eventuella förekomster av blanktecken (ASCII-tecken 32), tabulatortecken (ASCII 9), radbrytningstecken (ASCII 10), och carriage return (ASCII 13) i indatat. Detta åstadkommes mycket enkelt genom att Ø i den nedre rutan byts mot unionen av #32, #9, #10 och #13. Spara din modifiering under namnet G5.

UPPGIFT 6 Till sist skall kalkylatorn ges kompetens att handskas inte bara med hela tal utan även med decimaltal som t.ex. 0.25 och 3.14. Utöka således G5 på lämpligt sätt och spara resultatet under namnet G6.