Ett syntaxträd är ett allmänt träd, där de inre noderna är icke-slutsymboler och löven slutsymboler.
Välkänt exempel:
Språket som består av meningar av typen
JAG VET ATT DU TROR ATT JAG VET OCH JAG TROR ATT DU VET ATT JAG TROR
har följande syntax:
<Mening> ::= <Sats> | <Sats><Konj><Mening>
<Konj> ::= ATT | OCH
<Sats> ::= <Subj> <Pred>
<Subj> ::= JAG | DU
<Pred> ::= VET | TROR
I syntaxen ovan har vi fem 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).
Vi kan skapa ett syntaxträd för en given mening genom att parsa meningen
och identifiera delarna. Exempel:
JAG VET
är en mening, som i sin tur är en sats, som är subj följt av pred, där
subj är JAG och pred är VET.
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
I labb 7 ska du 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:
def __init__(self):
self.atom = "( )"
self.num = 1
self.next = None
self.down = None
Molekylen Si(C3(COOH)2)4(H2O)7 får följande utseende:
Sist i laboration 7 ska du också beräkna molekylernas vikt. För att göra det ska du använda hashtabellen du skrev laboration 5!
Kattis började i form av Marvin, som användes för att rätta inlämningarna i programmeringstävlingskursen
DD2458 (programmering och problemlösning under press), men används numera även i DD1352 (Algoritmer, Datastrukturer och Komplexitet) och DD2387 (Programsystemkonstruktion med C++).
Kattis är skrivet i en kombination av Python, PHP och SQL och körs på en Ubuntu-server. En specialbyggd säkerhetslösning används för att hindra fusk. All inskickad kod lagras också för att senare kunna kontrollera koden ifall det skulle behövas.
Den pedagogiska tanken med Kattis är att eleverna skall kunna sända in sin kod och snabbt få svar på huruvida koden fungerar. Kattis skall även ge eleverna övning i att söka efter buggar i koden. Kattis har utvecklats av följande personer:
from sys import stdin
from formelkollPaket import * #För att inte hela labben ska synas ;-)
def main():
#stdin = open("indata1.txt") #Lätt att ändra för att testa indata från fil
rad = stdin.readline()
while rad[0] != "#":
q = LinkedQ()
for tkn in rad:
q.put(tkn)
try:
readformel(q)
print("Formeln är syntaktiskt korrekt")
except Syntaxfel as felet:
rest = str(q).strip()
print(felet, "vid radslutet", rest)
rad = stdin.readline()
main()
print(x)
class Syntaxfel(Exception):
pass
def readformel(q):
...
raise Syntaxfel("Felaktig gruppstart")
Utnyttja gärna allmänhandledningen!
Fråga på KTH Social om du är helt säker på att ditt program
är klart och korrekt, men ändå inte blir godkänt av Kattis. Ange inskickningsid och mail där vi kan nå dig.