Föreläsning 10 - Syntax, rekursiv medåkning

• Läs i boken: kap 5.5.1
• Syntax för formella språk
• Rekursiv medåkning
• Syntaxkontroll med stack

Syntax för formella språk

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

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> "'" 

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

Uppgift: Skriv en BNF-grammatik för vanliga taluttryck med operationerna + - * /. Den vanliga prioritetsordningen (* och / går före + och -) ska gälla mellan operatorerna. Man ska också kunna använda parenteser i taluttrycken.

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

Lösning:

<Uttryck> ::= <Term> | <Term> + <Uttryck> | <Term> - <Uttryck>
<Term>    ::= <Faktor> | <Faktor> * <Term> | <Faktor> / <Term>
<Faktor>  ::= TAL | -<Faktor> | (<Uttryck>)


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

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)

• readSats()
• readSubj()
• readPred()
• readMening()
• readKonj()

# Syntaxkoll

from queue import WordQueue

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          

q = WordQueue()
for ordet in raw_input("Skriv en mening:").split():
    q.put(ordet)

try:                                  
    readMening()                                 
    print "Följer syntaxen!"      
except Grammatikfel,msg:                            
    print msg,"före",
    while not q.isempty():
      print q.get(),
    print

Syntaxkontroll med stack

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.

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.

Mer om hur det ser ut bakom kulisserna kan man lära sig i kursen DD2377, Maskinnära programmering och datorarkitektur.

Laborationerna

I labb 7 ska du bygga vidare på programmet från labb 6 så att det även skapar ett syntaxträd (och ritar upp det med hjälp av en färdig grafikmodul, molgrafik.py). Syntaxträdet är ett allmänt träd där varje nod (motsvarar en ruta i bilden) kan representeras med ett objekt från klassen Ruta nedan:

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

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