Föreläsning 9 - Syntax och automater

• Syntax
  • Syntax för formella språk
  • Rekursiv medåkning
  • Syntaxkontroll med stack
• Automater
  • Portkodsautomat
  • Textsökning
  • KMP-automat (Knuth-automat)
  • Boyer-Moore
  • Rabin-Karp
  • Sökning på webben
  • Reguljära uttryck
  • Modellering av grafiska gränssnitt

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

class Grammatikfel(Exception):
  #Miniklass för brott mot syntaxen
  pass

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 Grammatikfel,"Fel subjekt:"+ord       

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

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

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

try:                                  
  readmening()                                 
  print "Följer syntaxen!"      
except Grammatikfel,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 det här kan man lära sig i kursen DD2488, Compiler Construction.

Automater

1. Starttillstånd.
2. Knapptryckning D har just gjorts.
3. Knapptryckningarna DE har just gjorts.
4. Knapptryckningarna DEG har just gjorts. Låset öppnas.

  A B C D E F G H
1 1 1 1 2 1 1 1 1    Exempel: Om automaten är i tillstånd 3
2 1 1 1 2 3 1 1 1    och knapp D trycks ner övergår den till
3 1 1 1 2 1 1 4 1    tillstånd 2

Man kan också rita en graf med fyra noder (som representerar tillstånden) och en massa bokstavsmärkta pilar (som visar vilka övergångar som finns).

• Söka efter ett ord i en text (se KMP-automat nedan).
• Tolka reguljära uttryck.
• Beskriva grafiska gränssnitt.
• Kompilatorns analys av ditt program (se föreläsning om syntax).
• Komprimering.
• Morfologisk analys av ord (t ex o-ut-trött-lig-a).
• Analysera uttryck som beskriver öppettider (pågående exjobb).

Textsökning

i=1 # starttillståndet
while i<4:
  if i==0 or q.peek()==gud[i]): 
     i=i+1
     q.get()
  else: i=next[i];
}

 i next[i]
 1   0
 2   1
 3   1

 i next[i]
 1   0
 2   1
 3   0
 4   2

• next[1]=0.
• Annars är next[i]=1 om ordet inte upprepar sej.
• ...men om de j senaste bokstäverna vi sett bildar början på sökordet sätts next[i]=j+1.
• ...men om bokstav j+1 är samma som bokstav i sätts i stället next[i]=next[j+1].

Reglerna kan programmeras i några få satser och ger då den algoritm för textsökning som uppkallats efter Knuth, Morris och Pratt: KMP-automat.
Om den sträng vi söker efter är m tecken lång och texten vi söker i är n tecken lång kräver KMP-sökning aldrig mer än n+m teckenjämförelser och är alltså O(n+m). Metoden går igenom texten tecken för tecken - man kan alltså läsa ett tecken i taget t ex från en fil vilket är praktiskt om texten är stor.

Boyer-Moore

FÖRSTA MOSEBOKEN 1 I BEGYNNELSEN SKAPADE GUD HIMMEL OCH JORD...
  R  A  O  B  E  1  _  G (äntligen träff - då får vi jämföra närmare)
                       GY (tyvärr inget U, så hoppa vidare)
                          N  S  _  A  D (träff, jämför närmare)
                                     AD (tyvärr inget U, hoppa vidare)
                                         G (träff, jämför närmare)
                                         GUD (succé!)

Rabin-Karp

hash(MEN M)=8
 hash(EN MI)=9
  hash(N MIL)=3
   hash( MILD)=7
    hash(MILDA)=0
     hash(ILDA )=9
      hash(LDA M)=7
       hash(DA MA)=16
        hash(A MAT)=2
         hash( MATI)=1
          hash(MATIL)=12
           hash(ATILD)=9
            hash(TILDA)=6

Sökning på webben

Reguljära uttryck

Metatecken (t ex * och +) har särskild innebörd. Här följer några regler:

• a* matchar noll eller flera a:n
• a+ matchar ett eller flera a:n
• a? matchar ett eller inget a
• . matchar alla tecken utom radslut
• [a-zA-Z] matchar alla engelska bokstäver
• [abc] matchar a, b eller c
• [^abc] matchar vilket tecken som helst utom a, b eller c

Pythonmodulen re har funktionalitet för reguljära uttryck. Exempel:

   import re
   pattern="[Ll]abb?[1-7]"
   sometext="Lab5, labb 6, labb7 och lab8"
   print re.findall(pattern,sometext)
   # Utskriften blir ['Lab5', 'labb7']

Modellering av grafiska gränssnitt

Exempel:
I många grafiska gränssnitt kan man markera text genom att trycka ner musknappen och hålla den nedtryckt medan man drar musen över texten. Det här kan vi se som en automat med ett normaltillstånd och ett markeringstillstånd, där musknappstryck/släpp ger övergång mellan tillstånden.

Objektmodellering och tillståndsprogrammering kan man läsa mer om i kursen DD2385, Programutvecklingsteknik.

Länksamling

• Zerksis animation av rekursiv medåkning
• DD2488, Compiler Construction
• Boyer-Moores metod
• DH2418, Språkteknologi
• Pythonmodulen urllib
• Pythonmodulen re
• DD2372, Automata and languages
• DD2385, Programutvecklingsteknik