F19 Syntax Dtd Xml Rekursiv Medakning Unittestning
- 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 (Länkar till en externa sida.)-Naur (Länkar till en externa sida.)-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
Med hjälp av den rekursiva definitionen av Mening har vi plötsligt fått en syntax som beskriver en oändlig massa meningar!
Syntaxen för programspråk beskrivs ofta i BNF. Så här beskrivs Pythons tilldelningssatser (Länkar till en externa sida.) i dokumentationen:
assignment_stmt ::= (target_list (Länkar till en externa sida.) "=")+ (expression_list (Länkar till en externa sida.) | yield_expression (Länkar till en externa sida.)) target_list ::= target (Länkar till en externa sida.) ("," target (Länkar till en externa sida.))* [","] target ::= identifier (Länkar till en externa sida.) | "(" target_list (Länkar till en externa sida.) ")" | "[" target_list (Länkar till en externa sida.) "]" | attributeref (Länkar till en externa sida.) | subscription (Länkar till en externa sida.) | slicing (Länkar till en externa sida.) | "*" target (Länkar till en externa sida.)
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> "'"
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 lab6.pyc).
Den första delen av syntaxanalysen, 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 du använda dig av i labb 8: 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:
- readMening()
- readSats()
- readSubj()
- readPred()
- readKonj()
Flergrenade definitioner kräver tjuvtitt medq.peek() som vi har lagt till i klassen WordQueue. 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.
# Syntaxkontroll
from wordqueue import WordQueue
class Grammatikfel(Exception):
pass
def readMening(q):
readSats(q)
if q.peek() == ".":
q.dequeue()
else:
readKonj(q)
readMening(q)
def readSats(q):
readSubj(q)
readPred(q)
def readSubj(q):
word = q.dequeue()
if word == "JAG":
return
if word == "DU":
return
raise Grammatikfel("Fel subjekt: " + word)
def readPred(q):
word = q.dequeue()
if word == "TROR":
return
if word == "VET":
return
raise Grammatikfel("Fel predikat: " + word)
def readKonj(q):
word = q.dequeue()
if word == "ATT":
return
if word == "OCH":
return
raise Grammatikfel("Fel konjunktion: " + word)
def printQueue(q):
while not q.isEmpty():
word = q.dequeue()
print(word, end = " ")
print()
def storeSentence(mening):
q = WordQueue()
mening = mening.split()
for ordet in mening:
q.enqueue(ordet)
q.enqueue(".")
return q
def kollaGrammatiken(mening):
q = storeSentence(mening)
try:
readMening(q)
return "Följer syntaxen!"
except Grammatikfel as fel:
return str(fel) + " före " + str(q)
def main():
q = WordQueue()
mening = input("Skriv en mening: ")
resultat = kollaGrammatiken(mening)
print(resultat)
if __name__ == "__main__":
main()
DTD, SGML, XML, HTML, XMLschema
DTD - document type definition är ett annat sätt att definiera hur dokument ser ut. Det var tidigare del av SGML (Standard Generalized Markup Language) som är föregångare till HTML och XML.
HTML version 1 till version 4 är definierat med DTD. Här ett utdrag från HTML 4.01 Links to an external site. om anchor-taggen, den man använder för att länka.
<!--================== The Anchor Element ================================--> <!ENTITY % Shape "(rect|circle|poly|default)"> <!ENTITY % Coords "CDATA Links to an external site." -- comma-separated list of lengths --> <!ELEMENT A Links to an external site. - - (%inline; Links to an external site.)* -(A) -- anchor --> <!ATTLIST A %attrs; Links to an external site. -- %coreattrs Links to an external site., %i18n Links to an external site., %events Links to an external site. -- charset Links to an external site. %Charset; Links to an external site. #IMPLIED -- char encoding of linked resource -- type Links to an external site. %ContentType; Links to an external site. #IMPLIED -- advisory content type -- name Links to an external site. CDATA Links to an external site. #IMPLIED -- named link end -- href Links to an external site. %URI; Links to an external site. #IMPLIED -- URI for linked resource -- hreflang Links to an external site. %LanguageCode; Links to an external site. #IMPLIED -- language code -- rel Links to an external site. %LinkTypes; Links to an external site. #IMPLIED -- forward link types -- rev Links to an external site. %LinkTypes; Links to an external site. #IMPLIED -- reverse link types -- accesskey Links to an external site. %Character; Links to an external site. #IMPLIED -- accessibility key character -- shape Links to an external site. %Shape; Links to an external site. rect -- for use with client-side image maps -- coords Links to an external site. %Coords; Links to an external site. #IMPLIED -- for use with client-side image maps -- tabindex Links to an external site. NUMBER Links to an external site. #IMPLIED -- position in tabbing order -- onfocus Links to an external site. %Script; Links to an external site. #IMPLIED -- the element got the focus -- onblur Links to an external site. %Script; Links to an external site. #IMPLIED -- the element lost the focus -- >
En tag är det som är består av start och sluttag. T.ex. om man vill ha fetstilad text
<b>fetstil</b>
eller om man vill länka använder man anchor-taggen <a
<a href="www.kth.se">kth</a>)
Där HTML är taggar för webbläsare så är XML taggar för generell data.
<lagervaror>
<laptop>
<name>Superlaptop</name>
<antal>14</antal>
</laptop>
...
XML-schema är ett XML-dokument som kan kontrollera om en XML-fil är valid ungefär som en syntax kan kontrollera om ett program är syntaktisk korrekt. Att kunna validera data är oerhört viktigt i system som ska "prata" med andra system.
Testa med unittest
Här är ett exempel på hur man kan testa den rekursiva medåkningen med unittest (mer om testning på föreläsningen efter tentaveckan).
import unittest
from syntax import *
class SyntaxTest(unittest.TestCase):
def testSubjPred(self):
""" Testar Subj och Pred """
self.assertEqual(kollaGrammatiken("JAG VET"), "Följer syntaxen!")
def testFelKonj(self):
self.assertEqual(kollaGrammatiken("JAG VET MEN"), "Fel konjunktion: MEN före . ")
if __name__ == '__main__':
unittest.main()
Man kan översätta assert med "make certain that". Det finns flera assert-anrop man kan använda t.ex. assertNotEqual(a, b) (Länkar till en externa sida.) assertIsNone(x) (Länkar till en externa sida.) assertRaises() (Länkar till en externa sida.)
Tester består av hårdkodade startvärden och ett förväntat utfall som man jämför med. Om testutfallen stämmer med de förväntade utfallen så har testet lyckats.
Om man skrivit ett program som ber användaren mata in värden så kan man testa det med hårdkodade värden genom att skicka fördefinierade invärden i en indatafil med |
Skapa en indata fil som heter indata.txt och en fil med förväntade svarsvärden facit.txt
| indata.txt | facit.txt |
| JAG VET ATT DU TROR | Följer syntaxen! |
Mata in indata till programmet med |
> more indata.txt | python3 mittsyntaxprogram.py
Resultatet skrivs ut på skärmen. För att jämföra om resultatet gick bra behöver du spara ner utfallet på disk och jämföra filerna med t.ex. diff
> more indata.txt | python3 mittsyntaxprogram.py > utfall.txt
> diff utfall.txt facit.txt
En fördel med att använda unit-test är att man kan samköra och administrera många programmerares tester på samma sätt.
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 fel: 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.