DD1320 Tillämpad Datalogi

Syntax, rekursiv medåkning

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>
<target_list>     ::= <target> ("," <target>)* [","]
<target>          ::= <identifier> 
                      | "(" <target_list> ")" 
                      | "[" <target_list> "]" 
                      | <attributeref> 
                      | <subscription> 
                      | <slicing>

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

Den första delen av sytaxanalysen, 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 6: 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: Flergrenade definitioner kräver tjuvtitt med q.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

class Grammatikfel(Exception):
    pass

def readMening():
    readSats()                                     
    if q.peek() == ".": 
        q.get()
    else:                              
        readKonj()                                   
        readMening()                                 

def readSats():
    readSubj()                                  
    readPred()                                 

def readSubj():
    ordet = q.get()                    
    if ordet == "JAG":
        return                  
    if ordet == "DU":  
        return                  
    raise Grammatikfel("Fel subjekt:" + ordet)       

def readPred():
    ordet = q.get()                    
    if ordet == "TROR": 
        return                 
    if ordet == "VET":  
        return                 
    raise Grammatikfel("Fel predikat:" + ordet)      

def readKonj():
    ordet = q.get()                    
    if ordet == "ATT": 
        return                  
    if ordet == "OCH": 
        return                  
    raise Grammatikfel("Fel konjunktion:" + ordet)          

def main():
    q = WordQueue()
    mening = input("Skriv en mening:")
    mening = mening.split()
    for ordet in mening:
        q.put(ordet)
    try:                                  
        readMening()                                 
        print("Följer syntaxen!")      
    except Grammatikfel as fel:                            
        print(fel, "före", end ="")
        while not q.isempty():
          print(q.get(), end = "")
        print()

main()

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:
  1. Skapa en tom stack
  2. Slinga som läser symboler (här:tecken) tills inmatningen tar slut
  3. 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.
  1. 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.
  2. Inuti kommentaren - läser bort tecken. Återgår till tillstånd 1 om kommentaren tar slut.
  3. 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