Föreläsning 10: Syntax, rekursiv medåkning, testning
- Syntax för formella språk
- Rekursiv medåkning
- Syntaxkontroll med stack
Syntax för formella språk
Ett formellt språk är en väldefinierad uppsättning textsträngar som kan vara oändligt stor, till exempel alla Python-program, eller ändligt stor, till exempel alla månadsnamn. Det bästa sättet att definiera ett språk är med en syntax (observera betoning på sista stavelsen!), det vill säga en grammatik. En så kallad kontextfri grammatik kan beskrivas i Backus Links to an external site.-Naur Links to an external site.-form (BNF).
Exempel: Språket som består av satserna JAG VET, JAG TROR, DU VET och DU TROR definieras av syntaxen
<Sats> ::= <Subj> <Pred>
<Subj> ::= JAG | DU
<Pred> ::= VET | TROR
I syntaxen ovan har vi tre omskrivningsregler. Varje regel består av ett vänsterled med en icke-slutsymbol (t ex <Sats> ovan) och ett högerled som talar om vad man kan ersätta vänsterledet med. I högerledet får det förekomma både icke-slutsymboler och slutsymboler (t ex JAG i exemplet ovan). Tecknet | betyder eller.
Meningar av typen
JAG VET ATT DU TROR ATT JAG VET OCH JAG TROR ATT DU VET ATT JAG TROR definieras nu så här:
<Mening> ::= <Sats> | <Sats><Konj><Mening> <Konj> ::= ATT | OCH
Med hjälp av den rekursiva definitionen av Mening har vi plötsligt fått en syntax som beskriver en oändlig massa meningar!
Syntaxen för programspråk beskrivs ofta i BNF. Så här beskrivs Pythons tilldelningssatser Links to an external site. i dokumentationen:
assignment_stmt ::= (target_list Links to an external site. "=")+ (expression_list Links to an external site. | yield_expression Links to an external site.) target_list ::= target Links to an external site. ("," target Links to an external site.)* [","] target ::= identifier Links to an external site. | "(" target_list Links to an external site. ")" | "[" target_list Links to an external site. "]" | attributeref Links to an external site. | subscription Links to an external site. | slicing Links to an external site. | "*" target Links to an external site.
Man kan förstås beskriva syntaxen för BNF i BNF, och det ser ut så här:
<syntax> ::= <regel> | <regel> <syntax> <regel> ::= "<" <regelnamn> ">" "::=" <uttryck> <radslut> <uttryck> ::= <lista> | <lista> "|" <uttryck> <radslut> ::= <RETURTECKEN> | <radslut> <radslut> <lista> ::= <term> | <term> <lista> <term> ::= <slutsymbol> | "<" <regelnamn> ">" <slutsymbol> ::= '"' <text> '"' | "'" <text> "'"
En kompilator fungerar ungefär så här:
källkod --> lexikal analys --> syntaxanalys --> semantisk analys --> --> kodgenerering --> målkod
- Under en lexikal analys sållas oväsentligheter såsom blanktecken och kommentarer bort samtidigt som symboler vaskas fram.
- Syntaxanalysen (parsningen) kontrollerar att programmet följer syntaxen och skapar ett syntaxträd.
- Sen följer semantisk analys där kompilatorn ser efter vad programmet betyder.
- Sist sker kodgenerering där programmet översätts till målkod (t ex lab6.pyc).
Den första delen av syntaxanalysen, att kontrollera om ett program följer syntaxen, kan göras med rekursiv medåkning eller med en stack.
Rekursiv medåkning (recursive descent)
Denna metod för syntaxanalys ska du använda dig av i labb 8: Formelkoll
För varje symbol i grammatiken skriver man en inläsningsmetod. Om vi vill analysera grammatiken vi började med behöver vi alltså metoderna:
- readMening()
- readSats()
- readSubj()
- readPred()
- readKonj()
Flergrenade definitioner kräver tjuvtitt medq.peek() som vi har lagt till i klassen WordQueue. När något strider mot syntaxen låter vi ett särfall skickas iväg. Här följer ett program som undersöker om en mening följer vår syntax.
# Syntaxkontroll from wordqueue import WordQueue class Grammatikfel(Exception): pass def readMening(q): readSats(q) if q.peek() == ".": q.dequeue() else: readKonj(q) readMening(q) def readSats(q): readSubj(q) readPred(q) def readSubj(q): word = q.dequeue() if word == "JAG": return if word == "DU": return raise Grammatikfel("Fel subjekt: " + word) def readPred(q): word = q.dequeue() if word == "TROR": return if word == "VET": return raise Grammatikfel("Fel predikat: " + word) def readKonj(q): word = q.dequeue() if word == "ATT": return if word == "OCH": return raise Grammatikfel("Fel konjunktion: " + word) def printQueue(q): while not q.isEmpty(): word = q.dequeue() print(word, end = " ") print() def storeSentence(mening): q = WordQueue() mening = mening.split() for ordet in mening: q.enqueue(ordet) q.enqueue(".") return q def kollaGrammatiken(mening): q = storeSentence(mening) try: readMening(q) return "Följer syntaxen!" except Grammatikfel as fel: return str(fel) + " före " + str(q) def main(): q = WordQueue() mening = input("Skriv en mening: ") resultat = kollaGrammatiken(mening) print(resultat) if __name__ == "__main__": main()
Testa med unittest
Här är ett exempel på hur man kan testa programmet med unittest (mer om testning på föreläsningen efter tentaveckan).
import unittest from syntax import * class SyntaxTest(unittest.TestCase): def testSubjPred(self): """ Testar Subj och Pred """ self.assertEqual(kollaGrammatiken("JAG VET"), "Följer syntaxen!") def testFelKonj(self): self.assertEqual(kollaGrammatiken("JAG VET MEN"), "Fel konjunktion: MEN före . ") if __name__ == '__main__': unittest.main()
Man kan översätta assert med "make certain that". Det finns flera assert-anrop man kan använda t.ex. assertNotEqual(a, b)
Links to an external site. assertIsNone(x)
Links to an external site. assertRaises()
Links to an external site.
Tester består av hårdkodade startvärden och ett förväntat utfall som man jämför med. Om testutfallen stämmer med de förväntade utfallen så har testet lyckats.
Om man skrivit ett program som ber användaren mata in värden så kan man testa det med hårdkodade värden genom att skicka fördefinierade invärden i en indatafil med |
Skapa en indata fil som heter indata.txt och en fil med förväntade svarsvärden facit.txt
indata.txt | facit.txt |
JAG VET ATT DU TROR | Följer syntaxen! |
Mata in indata till programmet med |
> more indata.txt | python3 mittsyntaxprogram.py
Resultatet skrivs ut på skärmen. För att jämföra om resultatet gick bra behöver du spara ner utfallet på disk och jämföra filerna med t.ex. diff
> more indata.txt | python3 mittsyntaxprogram.py > utfall.txt
> diff utfall.txt facit.txt
En fördel med att använda unit-test är att man kan samköra och administrera många programmerares tester på samma sätt.
Syntaxkontroll med stack
Ett alternativt sätt att kontrollera om inmatningen följer en syntax är att använda en stack. Som exempel tar vi upp en vanlig källa till fel: omatchade parenteser. Så här kan man använda en stack för att hålla reda på parenteserna:
- Skapa en tom stack
- Slinga som läser symboler (här:tecken) tills inmatningen tar slut
- Om symbolen är en startsymbol (t ex[), lägg den på stacken.
- Om symbolen är en slutsymbol (t ex ]), titta på stacken. Om stacken är tom eller om den symbol som poppar ut inte matchar slutsymbolen har vi ett syntaxfel.
- När inmatningen tar slut - kolla om stacken är tom. Om den inte är tom har vi fått ett syntaxfel.
Men vad händer om man lagt in parenteser inuti en kommentar? Vi vill att alla tecken inuti kommentaren ska läsas bort. Lösningen är att låta programmet bete sig som en automat med flera tillstånd.
- Letar parenteser att lägga på stacken. Övergår till tillstånd 2 om den upptäcker en kommentar, till tillstånd 3 om inmatningen tar slut.
- Inuti kommentaren - läser bort tecken. Återgår till tillstånd 1 om kommentaren tar slut.
- När inmatningen tar slut - kollar om stacken är tom. Om den inte är tom har vi fått ett syntaxfel.
Den som vill skriva sitt eget programmeringsspråk måste först skriva en syntax för språket, och sedan ett program som kan tolka språket.
Titta på en animation av rekursiv medåkning Links to an external site.