Simplu calculator în Python - partea 1

De mai multă vreme tot mă bate gândul să fac ceva in­ter­pre­ta­tor pentru un limbaj mai simplu. Ca o primă aventurare în lumea in­ter­pretării șirurilor de caractere ca in­strucți­u­ni pentru calculator, m-am decis să fac un simplu „cal­cu­la­tor” în Python, care să aibă și suport pentru câteva funcții matematice și pentru variabile.

Basically, ce urmăresc eu e să am un mic progrămel care știe să facă ur­mă­toarele:

7+10*sin(pi/2)/2-3^2  # să dea 3
x = 127-30*ln(e)      # x să aibă valoarea 97
y = x^2 - 60/30*(6+x) # y să aibă 9203

Definiția riguroasă a sintaxei pe care o acceptă programul este următoarea:

<Number> = [0-9]+.?[0-9]* <Identifier> = [a-zA-Z][a-zA-Z0-9_]* <Operator> = [+*/%()^-]

<Function> = <Identifier> (<Identifier> | <Term>)
<Term> = <Number> | <Identfier> | LPAREN <Sum> RPAREN |
<Function>
<PowProduct> = <Term> (^ <Term>)?
<Product> = <PowProduct> ((*|/|%) <PowProduct>)*
<Sum> = <Product> ((+|-) <Product>)*
<Expression> = <Sum> | <Identifier> = <Expression>

Programul va avea 3 părți: un tokenizer, care va împărți stringul în bucăți elementare, un parser, care verifică corec­ti­tudinea datelor de intrare și apoi con­stru­iește un arbore de parsare, și în final un in­ter­pre­ta­tor, care parcurge arborele și evaluează expresia.

În acest post mă voi ocupa de prima parte, de tokenizer.

Vom avea ur­mă­toarele tipuri de tokene:

• numere întregi (10) sau cu zecimale (15.34)
• operatori (+,-,/,*,^,=,(,) )
• iden­ti­fi­ca­tori de variabile (x,y,rezultat) sau funcții (sin,ln,cos)

În primul rând avem nevoie de o clasă care să reprezinte tokenele, pe care o punem într-un fișier tokenizer.py:

    class token:

    def __init__(self,type,value = None):
        self.type = type
        self.value = value

    def __str__(self):
        return self.type + " " + self.value

    def __eq__(self, other):
        if isinstance(other,token):
            return self.type == other.type and self.value == other.value
        elif isinstance(other,str):
            return str(self.value) == other
        else:
            return False

Nu e prea complicată această clasă. Primește ca parametrii tipul și valoarea tokenului. Egalitatea între doi tokeni înseamnă că ambii au același tip și aceași valoare. Pentru a ne scurta un pic codul, permite și testarea cu un string, în acest caz având egalitate dacă valoare tokenului este egală cu stringul. Funcția __str__ o să o folosim doar la afișare.

Pentru că suntem dez­volta­tori moderni și grijulii, vom aplica Test Driven De­vel­op­ment, așa că mai întâi vom scrie câteva teste pentru cum ar trebui să funcționeze to­k­enizerul (la clasa token nu avem ce să testăm). Testele le punem în alt fișier (ideal ar fi în alt modul, nu ne complicăm cu asta acuma), tokenizerTest.py:

    import tokenizer
    t = tokenizer.Tokenizer()
    assert (t.tokenize("1+2") == ['1',"+",'2'])
    assert (t.tokenize("(x+y)\*2/4") ==
    ["(","x","+","y",")","\*","2","/","4"])
    assert(t.tokenize("(x+(y\*z+2))-3\*((5+x)/2-4)") ==
    ["(","x","+","(","y","\*","z","+","2",")",")","-","3","\*","(","(","5","+","x",")","/","2","-","4",")"
    ])
    assert(t.tokenize(" x + y ") == ['x','+','y'])
    try:
        t.tokenize("_&x+y") \# test for invalid symbols
        assert(False)
    except tokenizer.TokenizerError:
        assert(True)

To­k­enizerul va parcurge pe rând fiecare caracter din șirul de caractere și la fiecare pas va încerca să găsească ce tip de token se potrivește. Dacă la un punct nu găsește un token potrivit, înseamnă că șirul dat nu este o expresie validă. Așa că în fișierul tokenizer.py adăugăm clasa Tokenizer. Folosim o clasă doar ca să încapsulăm funcțiile să nu poluăm name­spaceul general:

    class TokenizerError(Exception): # exceptie speciala pentru cazul in care nu se recunoaste un caracter
        pass

    class Tokenizer:

        def tokenize(self,string):
            self.string = string
            self.tokens = []

            self.index = 0
            match = False # am gasit un token iteratia asta
            while self.index < len(self.string):
                token = self.operator()
                if token:
                    self.tokens.append(token)
                    match = True

                token = self.identifier()
                if token:
                    self.tokens.append(token)
                    match = True

                token = self.number()
                if token:
                    self.tokens.append(token)
                    match = True

                if self.skipWhite(): # sarim peste spatiile libere
                    match = True
                if not match: # daca nu am gasit token iteratia aceasta inseamna ca
                              # avem simboluri incorecte
                    raise TokenizerError('Invalid simbol found:'+self.string[self.index])
                    match = False
            return self.tokens

Ca să detectăm un operator pur și simplu comparăm caracterul cu operatorii posibili:

def operator(self):
    if self.index < len(self.string) and self.string[self.index] in '+-/\*()%^=':
        t = token('operator',self.string[self.index])
        self.index +=1
        return t
    else:
        return None

Detectare unui iden­ti­fi­ca­tor e un pic mai complicată, deoarece poate avea lungime variabilă și poate fi formată din tot felul de caractere: începe doar cu litere, dar apoi pot fi și cifre sau liniuțe de subliniere, în afara literelor. Vom folosi un regex pentru aceasta (acuma nu o să explic ce este un regex, doar pe scurt ce face fiecare componentă: ^[a-zA-Z][a-zA-Z0-9_]*$. ^ face ca potrivirea să se facă la începutul stringului, [a-zA-Z] corespunde unei litere, [a-zA-Z0-9_] corespunde unei litere, cifre sau unui underscore, iar * face repetitivă și opțională ultima chestie. Iden­ti­fi­ca­torul, dacă există, va fi dat de match.group():

def identifier(self):
    pattern = '^[a-zA-Z][a-zA-Z0-9_]\*'
    match = re.match(pattern,self.string[self.index:])
    if match:
        t = token('identifier',match.group())
        self.index = self.index + match.end()
        return t
    return None

Pentru a identifica un număr, facem aceași chestie, doar că schimbăm regexul: [0-9]+.?[0-9]. + face ca termenul anterior să se repete, dar să fie cel puțin o dată, . face "escaping" la ., care este caracter special în regexuri, iar ? face ca termenul anterior să fie opțional.

def number(self):
    pattern = "^[0-9]+\\.?[0-9]\*"
    match = re.match(pattern,self.string[self.index:])
    if match:
        t = token('number',match.group())
        self.index = self.index + match.end()
        return t
    return None

Funcția skipWhite face un singur lucru: sare peste spații și returnează True dacă a sărit peste ceva.

def skipWhite(self):
    match = False
    while self.index < len(self.string) and self.string[self.index] == " ":
        self.index+=1
        match = True
    return match

Punând toate acestea împreună, avem un simplu tokenizer pentru expresii matematice. Stay tuned for part 2, the parser.

Codul sursă se poate descărca de aici.