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

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

Plötsligt har vi fått en syntax som beskriver en oändlig massa meningar!

Syntaxen för programspråk beskrivs ofta i BNF. Så här kan man visa hur Javas tilldelningssatser ser ut:

<Assignment> ::= <Identifier> = <Expression> ;
<Identifier> ::= <Letter> | <Letter> <Digit> | <Letter> <Identifier>
<Letter>     ::= a-z | A-Z | _ | $
<Digit>      ::= 0-9

Duger denna syntax eller behöver den förbättras?

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

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)

Denna metod för syntaxanalys ska ni använda er 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:

readsats()
readsubj()
readpred()
readmening()
readkonj()

Flergrenade definitioner kräver tjuvtitt med q.peek(). 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.

# coding:iso-8859-1
# Syntaxkoll

from queue import Queue

def readmening():
  readsats()                                     
  if q.peek()==".": 
    q.get()
  else:                              
    readkonj()                                   
    readmening()                                 

def readsats():
  readsubj()                                  
  readpred()                                 

def readsubj():
  ord = q.get()                    
  if ord=="JAG": return                  
  if ord=="DU":  return                  
  raise Exception,"Fel subjekt:"+ord       

def readpred():
  ord = q.get()                    
  if ord=="TROR": return                 
  if ord=="VET":  return                 
  raise Exception, "Fel predikat:"+ord      

def readkonj():
  ord = q.get()                    
  if ord=="ATT": return                  
  if ord=="OCH": return                  
  raise Exception, "Fel konjunktion:"+ord          

q=Queue()
for ord in raw_input("Skriv en mening:").split():
  q.put(ord)

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

Laborationer

I labb 6 ska ni skriva ett program som kollar att molekyler som användaren matar in via tangentbordet följer en syntax. I labb 7 ska ni 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:          
    atom="( )"
    num=1    
    next=None
    down=None

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

Sist i laboration 7 ska ni också beräkna molekylernas vikt (finns även som frivillig uppgift i laboration 6). För att göra det ska ni använda hashtabellen från laboration 5.

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 kompileringsfel: 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.

Mer om syntaxanalys kan man lära sig i kursen 2D1373, Artificiella språk och syntaxanalys.