View All Pages

Föreläsning 12: Syntax

  • 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 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.

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 kompletterande 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
    • 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.
  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 Links to an external site.

  • Syntaxträd
  • Om testning på Kattis
  • Labb 8
  • Labb 9
  • Labb 10

Laborationerna

I labb 8 och 9 ska du skriva ett program som kollar att molekyler som användaren matar in via tangentbordet följer en given syntax.

I labb 10 ska du bygga vidare på programmet från labb 9 så att det även skapar ett syntaxträd (och ritar upp det med hjälp av en färdig grafikmodul, molgrafik.py).

Syntaxträd

När man använder en syntax för att tolka text (indata, programkod etc) brukar man skapa ett syntaxträd som datastruktur för den parsade texten.

Ett syntaxträd är ett allmänt träd, där de inre noderna är icke-slutsymboler och löven slutsymboler.

Välkänt exempel:
Språket som består av meningar av typen
JAG VET ATT DU TROR ATT JAG VET OCH JAG TROR ATT DU VET ATT JAG TROR har följande syntax:
<Mening> ::= <Sats> | <Sats><Konj><Mening>
<Konj> ::= ATT | OCH
<Sats> ::= <Subj> <Pred>
<Subj> ::= JAG | DU
<Pred> ::= VET | TROR

Vi kan skapa ett syntaxträd för en given mening genom att parsa meningen och identifiera delarna. Exempel:
JAG VET
är en <Mening>, som i sin tur är en <Sats>, som är <Subj> följt av <Pred>, där <Subj> är JAG och <Pred> är VET.

Uppgift: Givet följande BNF-grammatik för vanliga taluttryck med operationerna + - * /.

<Uttryck> ::= <Term> | <Term> + <Uttryck> | <Term> - <Uttryck>

<Term> ::= <Faktor> | <Faktor> * <Term> | <Faktor> / <Term>

<Faktor> ::= TAL | -<Faktor> | (<Uttryck>)

Rita upp ett syntaxträd för uttrycket 2*(3+4*5).

 

Lösning:

     |
     *
   /   \
  2    ( )
        |
        +
      /   \
     3     *
         /   \
        4     5

Syntaxträdet i labb10 ska representeras av ett allmänt träd där varje nod (motsvarar en ruta i bilden nedan) kan representeras med ett objekt av klassen Ruta nedan:

class Ruta:          
    def __init__(self):
       self.atom = "( )"
       self.num = 1    
       self.next = None
       self.down = None

Molekylen Si(C3(COOH)2)4(H2O)7 får följande utseende:

Si(C3(COOH)2)4(H2O)7

Sist i laboration 10 ska du också beräkna molekylernas vikt. För att göra det ska du använda hashtabellen du skrev i laboration 7!