rolisz's site

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 to­k­eniză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 op­er­ați­ilor aparțin de sintaxă.

Cum reprezen­tă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 reprezen­tat 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.right

self.type este un mic artificiu ca să putem testa mai ușor tipul tokenilor, fără să avem un if special pt arbori.

Conform „metodolo­giei” 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 operator

Pentru parser vom implement Recursive Descent Parser, iar logica din spatele său este următoarea: căutăm operatorii în ordinea inversă a im­por­tanț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 name­spaceul 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 op­er­a­toru­lui 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 op­er­a­toru­lui le trecem iarăși prin această funcție. Dacă într-o listă de tokene nu avem atribuire, atunci trecem la parsarea paran­tezelor.

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)

Paran­tezele 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):<br></len(tokens):<br> 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 op­er­a­toru­lui 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].value

Funcț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 iden­ti­fi­ca­tor urmează sau un alt iden­ti­fi­ca­tor ( 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 in­ter­pretă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.

Fișierele sunt aici.

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 in­cre­mentare în funcția de parsare a paran­tezelor.