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-Naur-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 i dokumentationen:

assignment_stmt ::=  (target_list "=")+ (expression_list | yield_expression)
target_list     ::=  target ("," target)* [","]
target          ::=  identifier
                     | "(" target_list ")"
                     | "[" target_list "]"
                     | attributeref
                     | subscription
                     | slicing
                     | "*" target

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) assertIsNone(x) assertRaises()

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