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

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

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)

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

# 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

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

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 syntaxanalys kan man lära sig i kursen 2D1373, Artificiella språk och syntaxanalys.