Simplu calculator în Python - partea 2
Acest post face parte dintr-o serie în care eu fac un mic calculator în Python
Data trecută ne-am ocupat de împărțirea stringului rezultat în bucăți elementare. Acum vom trece la următoarea parte: parsarea. Aceasta ne va da structura expresiei pe care vrem să o evaluăm. Dacă în urma tokenizării obțineam erori dacă stringul conținea caractere invalide, acum vom obține erori dacă tokenele noastre nu sunt în ordinea potrivită (dacă avem doi operatori unul după altul de exemplu) sau dacă nu sunt suficienți operanzi (numărul de paranteze deschise nu coincide cu cele închise). Este important de menționat că deocamdată nu atribuim semantică tokenelor, ci doar sintaxă. Regulile de ordine de efectuare a operațiilor aparțin de sintaxă.
Cum reprezentăm în memorie expresia? Cu un arbore binar. Fiecare operație se va reprezenta în felul următor: valoarea nodului este operatorul, ramura stângă va fi operandul stâng, iar ramura dreaptă va fi operandul drept. În cazul în care unul din operanzi este altceva decât un simplu token, acesta va fi reprezentat la rândul lui printr-un arbore binar.
class tree:
def __init__(self,value = None,left = None,right = None):
self.value = value
self.left = left
self.right = right
self.type = 'node'
def __eq__(self, other):
return isinstance(other,tree) and self.value == other.value and
self.left == other.left and self.right == other.rightself.type este un mic artificiu ca să putem testa mai ușor tipul tokenilor, fără să avem un if special pt arbori.
Conform „metodologiei” TDD, scriem mai întâi o suită de teste pentru parserul nostru.
from tree import tree, parseTree,ExpressionError
from tokenizer import token, Tokenizer
pT = parseTree()
tok = Tokenizer()
assert(pT.buildParseTree(tok.tokenize("1+2")) == tree('+','1','2'))
assert(pT.buildParseTree(tok.tokenize("(x+(y*z+2))-3*((5+x)/2-4)"))
==
tree('-',tree('+','x',tree('+',tree('\*','y','z'),'2')),tree('\*','3',tree('-',tree('/',tree('+','5','x'),'2'),'4'))))
assert (pT.buildParseTree(tok.tokenize("sin(x)+ln(y)\*3")) ==
tree('+',tree('sin','x'),tree('\*',tree('ln','y'),'3')))
assert (pT.buildParseTree(tok.tokenize('x^y*2-3')) ==
tree('-',tree('\*',tree('^','x','y'),'2'),'3'))
assert (pT.buildParseTree(tok.tokenize('x=y=5\*3-20\*sin(x+y)')) ==
tree('=','x',tree('=','y',tree('-',tree('*','5','3'),tree('*','20',tree('sin',tree('+','x','y')))))))
try: # teste pentru erori
Tree = pT.buildParseTree(tok.tokenize('x\*\*\*y'))
assert(False)
except ExpressionError:
assert(True)
try:
Tree = pT.buildParseTree(tok.tokenize('x===y'))
assert(False)
except ExpressionError:
assert(True)
try:
Tree = pT.buildParseTree(tok.tokenize('x+++y'))
assert(False)
except ExpressionError:
assert(True)
try:
Tree = pT.buildParseTree(tok.tokenize('+x\*3'))
assert(False)
except ExpressionError:
assert(True)
assert(pT.buildParseTree(tok.tokenize('5+(-3)')) == tree('+','5','-3'))
# unary operatorPentru parser vom implement Recursive Descent Parser, iar logica din spatele său este următoarea: căutăm operatorii în ordinea inversă a importanței lor și apoi parsăm ce este în partea lor stângă și separat ce este în partea lor dreaptă. Nu este cea mai rapidă metodă, dar pentru un calculator care va calcula expresii de maxim 1 rând, it does the trick.
Pentu a nu polua namespaceul global, băgăm totul într-o clasă:
class parseTree:
def buildParseTree(self,tokens):
return self.parseAssignment(tokens)
def parseAssignment(self,tokens):
for i in range(len(tokens)):
if token('operator','=') == tokens[i]:
if i == 0: raise ExpressionError("Assignement is not done this way")
return tree('=',tokens[:i][0],self.parseAssignment(tokens[i+1:]))
return self.parseParens(tokens)Primul operator de care ne ocupăm e cel de atribuire. La stânga operatorului de atribuire ar trebui să avem un singur token, altfel e un caz patologic (sau atribuim ceva la nimica, sau avem prea multe semne de adunare unul după celălalt). Cum vrem să putem face mai multe atribuiri într-o singură mișcare, elementele din dreapta operatorului le trecem iarăși prin această funcție. Dacă într-o listă de tokene nu avem atribuire, atunci trecem la parsarea parantezelor.
def parseParens(self,tokens):
i = 0
while i < len(tokens):
if tokens[i] == token('operator','('):
openCount = 1
start = i
i +=1
while i < len(tokens) and openCount:
if tokens[i] == token('operator','('):
openCount+=1
if tokens[i] == token('operator',')'):
openCount-=1
if openCount == 0:
tokens[start:i+1] = [self.parseParens(tokens[start+1:i])]
i = start
i+=1
if openCount != 0:
raise ExpressionError("Parens problem")
i +=1
return self.parseAdditive(tokens)Parantezele le parsăm și pe ele recursiv: în momentul în care întâlnim o paranteză deschisă, mergem până întâlnim paranteza pe care o închide (dacă pe parcurs întâlnim alte paranteze deschise, mărim contorul openCount), iar apoi înlocuim în lista de tokene conținutul dintre paranteze cu parsarea sa. Dacă în listă nu avem paranteze, atunci trecem la operația de adunare.
def parseAdditive(self,tokens):
i = 1
while i<len(tokens):
if tokens[i] in ['+','-']:
return tree(tokens[i].value,self.parseMultiplicative(tokens[:i]),self.parseAdditive(tokens[i+1:]))
i+=1
if len(tokens) == 2 and tokens[0] in ['+','-']:
return token(tokens[1].type,"".join([tokens[0].value,tokens[1].value]))
return self.parseMultiplicative(tokens)
def parseMultiplicative(self,tokens):
i = 0
while i< len(tokens):
if tokens[i].value in ['\*','/','%']:
return tree(tokens[i].value,self.parsePower(tokens[:i]),self.parseMultiplicative(tokens[i+1:]))
i+=1
if len(tokens) > 1:
return self.parsePower(tokens)
if not len(tokens):
raise ExpressionError("Addition is not done this way")
if tokens[0].type not in ['identifier','number','node']:
raise ExpressionError("Operator + operator? Not good")
return tokens[0]La adunare mergem până la prima operație aditivă și apoi parsăm partea dreapta, respectiv stângă. Dacă nu găsim operație aditivă decât pe prima poziție, asta înseamnă că în acest caz avem operație unară (negație deobicei, dar pentru simetrie am lăsat și +) și atunci returnăm tokenul anterior prefixat cu semnul său. Dacă nu întâlnim operație, atunci parsăm tokenele pentru înmulțire.
La înmulțire, avem cazul clasic, în care la întâlnirea operatorului parsăm cele două ramuri. Dacă nu avem operator, atunci parsăm tokenele acestea pentru operații de nivel mai înalt (ridicare la putere). Dacă nu mai avem tokene, înseamnă că mai sus avem un operator de adunare fără ambii operanzi. Dacă tokenul rămas este operator, nici aia nu îi bine.
def parsePower(self,tokens):
i = 0
while i< len(tokens):
if tokens[i] == token('operator','^'):
return tree(tokens[i].value,self.parseFunctions(tokens[:i]),self.parseFunctions(tokens[i+1:]))
i+=1
if len(tokens) > 1:
return self.parseFunctions(tokens)
if not len(tokens):
raise ExpressionError("Multiplication is not done this way")
if tokens[0].type not in ['identifier','number','node']:
raise ExpressionError("Operator and operator? Not good")
return tokens[0]
def parseFunctions(self,tokens):
i = 0
while i < len(tokens)-1:
if tokens[i].type == 'identifier' and tokens[i+1].type in ['node','identifier','number'] :
return tree(tokens[i].value,tokens[i+1])
i+=1
if len(tokens) > 1:
raise ExpressionError("Bad function call")
if tokens[0].type == 'node':
return tokens[0]
return tokens[0].valueFuncția pentru parsarea de puteri, e identică cu cea de înmulțire, diferă doar operatorul la care corespunde. Ea este o funcție separată pentru că are altă prioritate decât înmulțirea și împărțirea.
Funcțiile matematice pe care le admitem acceptă un singur parametru, așa că avem două cazuri: după un identificator urmează sau un alt identificator ( sin x ) sau un nod (deci sin(x) ). Dacă avem mai mult de 3 tokene, îi bai. Dacă avem un singur token, atunci nu a fost funcție ci doar un simplu operand.
Punând toate cap la cap obținem un parser pentru expresii aritmetice. Mai rămâne să dă și semantică expresie, adică sa interpretăm arborele pe care l-am făcut acum și îi gata teoretic calculator. Mai trebuie să facem doar rotițele de legătura. Dar acestea... later.
Update: Am schimbat două chestioare micuțe la funcția de parsare a funcțiilor: 1) să poată accepta un număr direct ca parametru, 2) puterile să poată fi mai complexe. Și am șters o incrementare în funcția de parsare a parantezelor.