Till KTH:s startsida Till KTH:s startsida

Föreläsning 14

Kattis, syntaxträd, tentagenomgång

  • Syntaxträd
  • Om testning på Kattis
  • Labb 6
  • Labb 7

Laborationerna

I labb 6 ska du skriva ett program som kollar att molekyler som användaren matar in via tangentbordet följer en given syntax.

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äd

När man använder en syntax för att tolka text (indata, programkod etc) brukar man skapa ett syntaxträd som datastruktur för den parsade texten.

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 

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: Givet följande BNF-grammatik för vanliga taluttryck med operationerna + - * /.

<Uttryck> ::= <Term> | <Term> + <Uttryck> | <Term> - <Uttryck>

<Term> ::= <Faktor> | <Faktor> * <Term> | <Faktor> / <Term>

<Faktor> ::= TAL | -<Faktor> | (<Uttryck>)

Rita upp ett syntaxträd för uttrycket 2*(3+4*5).

Lösning:

     |
     *
   /   \
  2    ( )
        |
        +
      /   \
     3     *
         /   \
        4     5
          

Syntaxträdet i labb7 ska representeras av ett allmänt träd där varje nod (motsvarar en ruta i bilden nedan) kan representeras med ett objekt av 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:

Si(C3(COOH)2)4(H2O)7

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

Kattis: Ett automatiskt system för rättning av labbar

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++) med flera.

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:

  • Fredrik Niemelä
  • Gunnar Kreitz
  • Per Austrin

Övriga som hjälpt till är:

  • Johanna Eriksson
  • Mattias de Zalenski
  • Pehr Söderman

Hur ska jag göra?

  1. Följ länken: Kattis
  2. Logga in (längst upp till höger) med ditt KTH-id
  3. Välj "COURSES" i övre menyn
  4. Välj "tilda15" (långt ner i listan)
  5. Klicka på "I am a student taking this course and I want to register for it on Kattis."
  6. Välj "Problemlista".
    Här finns två testproblem (hello och different) och labb 6 (formelkoll2)
  7. Välj "SUBMIT" för att komma till inskickningssidan.
  8. Fyll i fälten "Problem ID" och "Language"
  9. Välj en fil (ditt python-program)
  10. Tryck på knappen "Skicka in"
  11. Uppdatera webbsidan för att få se Domarstatus.

Använd testproblemen för att lista ut hur Kattis fungerar innan du skickar in din lösning till labb6!

Indata

Programmen du skickar till Kattis ska läsa indata från stdin.
Det fungerar som att läsa från fil! Exempel:

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()

Utdata

Utdata ska du skriva ut med print som vanligt.

print(x)

Syntaxfel

Definiera ditt eget särfall som en subklass till Exception. Du behöver inte göra egna metoder - allt som finns i Exception ärvs av din klass.
Exempel (Python 3):

class Syntaxfel(Exception):
    pass

def readformel(q):
    ...
        raise Syntaxfel("Felaktig gruppstart")

Moment LAB1

Du måste bli godkänd på laborationsdelen (dvs redovisa alla tio labbarna) för att bli godkänd på kursen.

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 mailadress där vi kan nå dig.