Föreläsning 13: Syntaxträd

• Syntaxträd
• Labb 8
• Labb 9
• Labb 10

Laborationerna

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

I labb 10 ska du bygga vidare på programmet från labb 9 så att det även skapar ett syntaxträd (och ritar upp det med hjälp av en färdig grafikmodul, molgrafik.py).

Labb 8: En enkel syntax

Labb 9: Formelkoll

Denna labb fortsätter direkt på labb 8. Syntaxen är utbyggd för att kunna kontrollera längre molekylformler, t ex "Zn5H3" eller "Li(Fe2S4)5Ag"

<formel>::= <mol> \n
<mol>   ::= <group> | <group><mol>
<group> ::= <atom> |<atom><num> | (<mol>) <num>
<atom>  ::= <LETTER> | <LETTER><letter>
<LETTER>::= A | B | C | ... | Z
<letter>::= a | b | c | ... | z
<num>   ::= 2 | 3 | 4 | ...

Du ska också kontrollera att atomerna är verkliga atomer (från en given lista), men du ska inte kontrollera om molekylen är rimlig ur kemisk synvinkel.

Några nya felutskrifter tillkommer:

• Okänd atom vid radslutet

• Saknad högerparentes vid radslutet

• Felaktig gruppstart vid radslutet

Denna labb brukar upplevas som den svåraste i kursen. Goda råd:

• Följ syntaxen strikt. Varje funktion ska ha sin egen uppgift, och funktionerna ska inte bli långa.
• Använd bara de utskrifter som är givna i uppgiften (Kattis förstår inte annars).
• Hitta på många egna testfall. Övning: testfall Ladda ner Övning: testfall
• Skriv ett unittest-program för testfallen, så går det snabbare för dig att provköra.

Det program du skickar in till Kattis ska läsa all indata från stdin, se programmet nedan. Om du vill provköra med en fil kan du tillfälligt sätta om stdin med stdin = open("indata1.txt") Men glöm inte att kommentera bort den raden innan du skickar in till Kattis.

Huvudprogram

from sys import stdin


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

Labb 10: 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. 

För den lite längre meningen JAG VET OCH DU TROR ATT DU VET får vi:

Hur blir syntaxträdet för syntaxen i labb 9?

<formel>::= <mol> \n
<mol>   ::= <group> | <group><mol>
<group> ::= <atom> |<atom><num> | (<mol>) <num>
<atom>  ::= <LETTER> | <LETTER><letter>
<LETTER>::= A | B | C | ... | Z
<letter>::= a | b | c | ... | z
<num>   ::= 2 | 3 | 4 | ...

I labb10 ska syntaxträdet 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:

Klassen Molgrafik är given, och låter dig rita upp syntaxträdet enligt ovan. Vi tar ett litet exempel: molekylen C(OH)2. Det fullständiga syntaxträdet ser ut så här:

Vi förenklar i två steg genom att

1. Ta bort inre noder
2. Göra om till ett allmänt träd:

Det allmänna trädet är alltså uppbyggt av Ruta-noder med down- och next-pekare på följande vis:

#Demonstrerar klasserna Ruta och Molgrafik
from molgrafik import *

class Ruta:
    def __init__(self, atom="( )", num=1):
        self.atom = atom
        self.num = num
        self.next = None
        self.down = None

#Bygger upp träd för "C(OH)2"
ruta1 = Ruta("C")
ruta2 = Ruta(num=2)
ruta1.next = ruta2
ruta3 = Ruta("O")
ruta2.down = ruta3
ruta4 = Ruta("H")
ruta3.next = ruta4

molekyl = ruta1

mg = Molgrafik()
mg.show(molekyl)

Sist i laboration 10 ska du också beräkna molekylernas vikt. 

Labbar för högre betyg på LAB1

När du blivit godkänd på labb 1-10 får du betyg E på kursens labbdel LAB1.

Om du redovisat labbarna i tid så får du tillgång till labb C, och har möjlighet att höja betyget.

När du redovisat labb C får du tillgång till labb A. 

Mer info om högrebetygslabbarna kommer på föreläsningen efter tentaveckan!