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 | OCHPlö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-9Duger 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
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.
readsats()
readsubj()
readpred()
readmening()
readkonj()
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 syntaxen ovan.
# 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(), printI labb 6 ska ni bygga vidare på programmet från labb 5 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
{
), lägg den på stacken.
}
), titta på stacken.
Om stacken är tom eller om den symbol som poppar ut inte matchar slutsymbolen
har vi ett syntaxfel.
Mer om syntaxanalys kan man lära sig i kursen 2D1373, Artificiella språk och syntaxanalys.