Grammatiker för datorspråk

Av Thomas Padron-McCarthy (e-post: Thomas.Padron-McCarthy@oru.se). Senaste ändring: 3 september 2009.

Ett datorspråk är ett språk som är skapat för att läsas och förstås av datorer. Det kan vara ett programmeringsspråk som C++, Java eller Visual Basic, men det kan också vara ett betydligt enklare språk, som till exempel beskriver vad man kan skriva i en konfigurationsfil, eller vad man kan mata in i en inmatningsruta.

En grammatik för ett språk beskriver språket, och talar om hur man kan sätta samman meningar och andra konstruktioner i det språket.

Datorspråk och naturliga språk

Ett datorspråk, till exempel C++, är skapat för att läsas och förstås av datorer.

Det finns också naturliga språk som svenska och engelska. De naturliga språken brukar vara mycket friare än datorspråken, så att man till exempel kan vända på ordföljden. Gränsen mellan rätt och fel brukar också vara lite flytande i de naturliga språken.

Eftersom datorer är mycket dummare än människor, måste man vara mycket mer noggrann när man skriver något som en dator ska läsa och förstå. En människa kan ofta förstå en mening trots att det, finns ett kommatecken på fel ställe. Men om man skriver ett kommatecken på fel ställe i ett program, så kommer datorn för det mesta att göra antingen inget alls, eller något helt annat än vad man tänkt sig.

Grammatik

En grammatik för ett språk beskriver språket, och talar om hur man kan sätta samman ord och andra symboler i språket till meningar och andra konstruktioner.

Grammatiken för språket svenska säger till exempel att man kan skapa en mening bland annat genom att först skriva ett substantiv och sen ett verb, och avsluta med en punkt. Den regeln skulle man kunna skriva så här:

mening -> substantiv verb .

Man kan alltså ta ett substantiv, vilket som helst, följt av ett verb, vilket som helst, och en punkt, och detta bildar en mening.

Eftersom naturliga språk som svenska är ganska fria, är det svårt eller omöjligt att skriva en fullständig och korrekt grammatik, som verkligen beskriver allt man kan säga på svenska.

Det är mycket lättare att skriva en grammatik för ett datorspråk. Dels brukar datorspråk vara mycket enklare än naturliga språk, och dessutom är de mycket mer exakt bestämda. Det finns inga (nåja, nästan inga) tveksamma fall, utan om man skriver något i ett datorspråk som Java så är det antingen rätt eller fel. Inte som i svenska, där man kan diskutera ganska länge om ett uttryck är rätt eller fel, och där det i slutänden kanske visar sig vara en smaksak.

Ett enkelt språk: hälsningar

Vi tänker oss att vi ska skriva en grammatik för språk där man kan uttrycka följande fyra olika hälsningar: Så här kan grammatiken se ut:
hälsning -> hej | god morgon | god middag | god kväll
En hälsning kan alltså vara antingen hej, god morgon, god middag eller god kväll. Symbolen "|" betyder "eller". Symbolen "->" kan läsa som "kan ersättas med" eller "kan expanderas till".

Det här är en annan grammatik, som beskriver precis samma språk:

hälsning -> hej | god tidsspecifikation
tidsspecifikation -> morgon | middag | kväll
En hälsning är alltså antingen bara hej, eller också ordet god, följt av en tidsspecifikation, och den tidsspecifikationen kan vara antingen morgon, middag eller kväll.

I stället för att använda eller-tecknet "|" för att visa att en tidsspecifikation kan vara någon av flera olika saker, kan man skriva flera olika regler:

hälsning -> hej
hälsning -> god tidsspecifikation
tidsspecifikation -> morgon
tidsspecifikation -> middag
tidsspecifikation -> kväll

"Terminaler", "icke-terminaler" och "produktioner"

En terminal är något som man skriver i själva språket. I hälsningsspråket ovan har vi fem olika terminaler, nämligen de fem orden hej, god, morgon, middag och kväll. Här skriver vi terminaler med fetstil.

I grammatiken använder vi också namnen hälsning och tidsspecifikation. De förekommer inte i hälsningsspråket, utan finns bara i grammatiken. De kallas icke-terminaler, och vi skriver dem med kursiv stil.

En "terminal" är något som finns på slutet av något. På slutet av en busslinje finns en bussterminal. Där stannar bussen, och busspassagerarna kliver av. Om jag har en icke-terminal, som hälsning, så kan jag fortsätta och ersätta den, enligt reglerna i grammatiken, men när jag kommit till en terminal, som morgon, så kan jag inte ersätta den med något annat, utan jag måste stanna där.

En produktion är en regel i grammatiken, som säger att en viss icke-terminal kan ersättas med något annat. Till exempel är det här en produktion som säger att icke-terminalen hälsning kan ersättas med terminalen god och icke-terminalen tidsspecifikation:

hälsning -> god tidsspecifikation
Notera också att det här inte är en produktion, utan tre:
tidsspecifikation -> morgon | middag | kväll
"Eller"-tecknet "|" är bara ett kortare sätt att skriva flera olika produktioner, och i stället för det ovanstående kan man skriva ut dem:
tidsspecifikation -> morgon
tidsspecifikation -> middag
tidsspecifikation -> kväll

Startsymbolen

Vi utgick från att man ville skriva hela hälsningar, så att man till exempel kan säga god kväll, men inte bara kväll. Men i grammatiken hade vi ju två icke-terminaler: hälsning och tidsspecifikation. Hur vet man vilken det är som beskriver hela uttrycket?

Jo, när man skriver en grammatik räcker det inte med att ange vilka terminaler, icke-terminaler och produktioner som finns, utan man måste också ange vad det egentligen är för saker man vill säga i språket, om det till exempel är hela hälsningar eller bara tidsspecifikationer. Det gör man genom att ange en startsymbol.

För vårt hälsningsspråk är det hälsning som är startsymbol, inte tidsspecifikation.

Grammatiken för hälsningsspråket

Som vi såg kunde vi beskriva hälsningsspråket med flera olika grammatiker, som alla beskriver samma språk. Vi väljer en av dem, och för att vara fullständiga räknar vi upp vilka terminaler, icke-terminaler och produktioner som finns i språket och dess grammatik, och vad som är startsymbolen. Så här:

Terminaler:

Icke-terminaler:

Produktioner:

Startsymbol:

Vad är ett språk?

Hälsningsspråket som vi pratat om består av följande fyra fraser, eller sekvenser av terminaler, som är tillåtna i det språket: Språket innehåller alltså fyra fraser. Andra fraser, till exempel god god kväll, är inte tillåtna, och ingår inte i språket.

När vi i fortsättningen talar om ett språk, så menar vi mängden av alla tillåtna sekvenser av terminaler. Det här enkla språket innehåller fyra tillåtna sekvenser, men ett språk som C++ innehåller förstås många fler - kanske till och med oändligt många.

Hur tar man reda reda på vilket språk som en grammatik beskriver?

Man kan generera alla tillåtna sekvenser av terminaler i ett språk genom att utgå från startsymbolen, och sen i tur och ordning expandera alla icke-terminaler. Ta till exempel grammatiken i förra exemplet, med startsymbolen hälsning och de här produktionerna: Börja med startsymbolen, hälsning:

Startsymbolen

Det finns två olika sätt att expandera den:

Två möjliga expansioner av startsymbolen hälsning

hej kan inte expanderas, så där kommer vi inte vidare, men icke-terminalen tidsspecifikation kan expanderas på tre olika sätt:

Tre möjliga expansioner av icke-terminalen tidsspecifikation

Nu kommer vi inte längre.

Vi har bildat ett träd, och språket, dvs vilka sekvenser av terminaler som är tillåtna, hittar vi genom att titta på löven i trädet.

En grammatik för ett oändligt stort språk

Ett språk kan vara oändligt stort, i den betydelsen att det innehåller oändligt många tillåtna sekvenser: Om det är summa som är startsymbolen, kan vi expandera den så här:

Expansion av ett oändligt språk

Trots att grammatiken för det här språket bara innehåller två terminaler, en icke-terminal och två produktioner, innehåller språket oändligt många tillåtna sekvenser:

En grammatik för summor

I exemplet ovan kunde vi uttrycka summor, men tyvärr bara summor av talet 3. Vi ska försöka skriva en grammatik som klara även andra summor, med siffror och plustecken, till exempel: Det kan kanske vara förvånande att 7 räknas som en summa, men vi väljer att ta med fallet med ett enda tal. När vi sen går vidare med riktiga matematiska uttryck, ska vi nämligen (förstås!) tillåta att man skriver uttryck som bara består av ett tal.

Det finns flera sätt att skriva en sån här grammatik, men vi väljer att tänka så här: En summa är antingen en ensam siffra, eller så har man en summa (som kan vara en ensam siffra) där man adderar en ny siffra på slutet, så att det blir en ny summa.

Ett första försök:

Den grammatiken fungerar, men blev otymplig. Det blir enklare om vi inför icke-terminalen siffra: Alternativt kan vi göra siffra till en terminal. Då blir det den lexikaliska analysatorns ("scannerns") ansvar att känna igen "0", "1", "2" och så vidare, och att skicka vidare till den syntaktiska analysatorn ("parsern") att den hittat en siffra i inmatningen.

Då blir grammatiken ännu enklare:

Nu syns det kanske lite tydligare hur vi tänkte: En summa är antingen en ensam siffra, eller så har man en summa (som kan vara en ensam siffra) där man hänger på ett plustecken och en ny siffra på slutet, så att det blir en ny summa.

Lexikalisk analys och syntaktisk analys

De första två faserna i en kompilator kallas lexikalisk analysator (eller "scanner") och syntaktisk analysator (eller "parser").

Källprogrammet som ska kompileras består normalt av text, dvs en följd av tecken:

x = nedre_koordinat + 14;
Scannern läser källprogrammets text, och skapar i stället en sekvens av terminaler, eller "tokens", som skickas vidare till parsern:
identifierare, likhetstecken, identifierare, plustecken, heltal, semikolon
Notera dels att mellanslagen försvann, för de har ingen egen betydelse utan används bara för att skilja terminalerna åt, och dels att flera tecken (som 1 och 4) kan bilda en enda terminal.

Normalt skickar scannern också med information om vilka identifierare och heltal som den hittade, så här nånting:

identifierare (x), likhetstecken, identifierare (nedre_koordinat), plustecken, heltal (14), semikolon
Parsern läser denna sekvens av tokens, jämför med grammatiken, och avgör om det är en tillåten sekvens av tokens enligt grammatiken, och vilka av produktionerna i grammatiken som behövs för att generera denna sekvens.

När man konstruerar en kompilator kan man ibland välja om man vill placera en viss del av arbetet i scannern eller i parsern. Till exempel såg vi ju här ovan att man kunde låta parsern ha en regel för att en "siffra" är någon av 0 till 9, eller så kunde man låta scannern sköta om att känna igen att 0 till 9 är siffror.

Parsning och kompilatorer

Det finns olika metoder att skriva en parser, som till exempel ska ingå i en kompilator. Man kan skriva den för hand i form av vanlig programkod i C, Java eller liknande språk, eller så kan man använda en så kallad parser-generator, till exempel Yacc. I så fall skriver man inget program, utan skriver bara upp grammatiken för språket, och parser-generatorn läser filen med grammatiken, och genererar sen den programkod (till exempel i C eller Java) som utgör parsern.

Parse-träd

När parsern läser sekvensen av tokens som kommer från scannern, den jämför den sekvensen med produktionerna i grammatiken, så bygger den upp ett så kallat parse-träd, ibland också kallat konkret syntax-träd. Lövnoderna i trädet är tokens, och de inre noderna är icke-terminaler. Rotnoden är grammatikens startsymbol.

Parse-träd

Fast det där var inte riktigt sant. Det är egentligen inte säkert att parsern bygger upp något parse-träd, i alla fall inte som en datastruktur i minnet. I stället är det så att parsern går igenom produktionerna i grammatiken i en ordning så att den skulle kunna bygga upp ett parse-träd.

Man kan förenkla parse-trädet genom att (1) ta bort de inre noder som bara har en under-nod, och (2) flytta upp operatorer till noden ovanför, där de ersätter icke-terminalen:

Att göra om ett parse-träd till ett syntax-träd

Då bildas ett så kallat syntax-träd, ibland också kallat abstrakt syntax-träd:

Syntax-träd

Det enklare syntaxträdet innehåller all information som behövs för att beräkna uttrycket (eller köra programmet), men har inte med den information om grammatikens struktur som fanns i parse-trädet.

Samma språk men med en sämre grammatik: tvetydighet!

När vi skapade grammatiken för summorna ovan, tänkte vi så här: En summa är antingen en ensam siffra, eller så har man en summa (som kan vara en ensam siffra) där man adderar en ny siffra på slutet, så att det blir en ny summa.

Ett annat sätt att tänka är detta: En summa är antingen en ensam siffra, eller två summor som man adderar:

Den här grammatiken beskriver samma språk som den förra, och genererar alltså precis samma mängd av tillåtna tokensekvenser, men den har nackdelen att den är tvetydig.

Att en grammatik är tvetydig betyder att samma sekvens av tokens kan beskrivas med (minst) två olika parse-träd, enligt den grammatiken. Notera hur 3+4+5 kan beskrivas på två sätt:

Två olika parse-träd för 3+4+5

Om man grupperar additionerna med parenteser, motsvarar detta de två uttrycken (3+4)+5 respektive 3+(4+5).

Man kan förstå undra om det spelar någon roll, och för addition gör det inte det. Bägge summorna ger resultatet 12, och en addition ger alltid samma resultat oavsett i vilken ordning man adderar termerna. Men om vi i stället för addition haft subtraktion, så hade de två uttrycken blivit (3-4)-5 respektive 3-(4-5). De ger helt olika resultat.

Motsatsen till en tvetydig grammatik är en entydig grammatik. En grammatik för ett datorspråk bör vara entydig, för en tvetydig grammatik gör ju att ett källprogram kan tolkas på olika sätt, och det är svårt för datorn att med någon sorts "sunt förnuft" veta vilken av de olika tolkningarna som är den avsedda.

En grammatik för riktiga uttryck

Vi vill skapa en grammatik för enkla matematiska uttryck, och börjar med en som bara klarar addition (plus) och multiplikation (gånger). Den ska klara uttryck som: Vad blir 1 + 2 * 3? Jo, det ska tolkas som 1 + (2 * 3), vilket blir 7, och inte som (1 + 2) * 3, vilket blir 9. Det beror på att multiplikation ska utföras före addition. Man säger att multiplikationsoperatorn har högre prioritet, ibland kallat precedens, än additionsoperatorn.

Ett första försök att skriva grammatiken:

"U" står förstås för "uttryck".

Samma grammatik kan också skrivas så här, om man vill trycka ihop det lite:

"F" står för "faktor" och "T" står för "term". "U" står fortfarande för "uttryck". Den här grammatiken säger att ett uttryck kan bestå av bara ett tal, eller av två andra uttryck som man adderar, eller av två andra uttryck som man multiplicerar.

Det där är en tvetydig grammatik (prova själv!). Nästa försök:

Den här grammatiken säger att ett uttryck består av en addition av två termer. En term består i sin tur av en multiplikation av två faktorer. En faktor, till sist, består av ett tal.

Det är bättre, men den klarar bara uttryck på formen tal * tal + tal * tal.

Vi vill kunna multiplicera ihop godtyckligt många tal till en term, och addera ihop godtyckligt många termer till ett uttryck. Då måste både term-regeln och uttrycks-regeln hantera det. Vi använder det vi lärde oss tidigare om hur man kan kedja ihop summor genom att hela tiden lägga till + siffra till en summa.

Nu är grammatiken riktig, och den säger följande: Notera:

Yacc

I Yacc kan man skriva regler som ser ut ungefär som ovan, och så gör Yacc en parser för den grammatiken.