'''Recursive Parser of Ariphmetic Formulas''' import re import math # Lexeme types NUMBER = 0 NAME = 1 PLUS = 2 MINUS = 3 MUL = 4 DIV = 5 POW = 6 LPAR = 7 RPAR = 8 X = 9 Y = 10 ENDLINE = 11 ILLEGAL = 12 regExpressions = [ (r"[0-9]+(\.[0-9]*)?((e|E)(\+|\-)?[0-9]+)?", NUMBER), (r"[a-zA-Z][a-zA-Z0-9]*", NAME), (r"\+", PLUS), (r"\-", MINUS), (r"\^|(\*\*)", POW), (r"\*", MUL), (r"\/", DIV), (r"\(", LPAR), (r"\)", RPAR) ] whiteSpace = re.compile(r"\s+") # Table of standard functions (dictionary) standardFunctions = { "sin": math.sin, "cos": math.cos, "exp": math.exp, "log": math.log, "sqrt": math.sqrt, "tan": math.tan, "abs": math.fabs, "fabs": math.fabs, "atan": math.atan, "asin": math.asin, "acos": math.acos, "sinh": math.sinh, "cosh": math.cosh, "tanh": math.tanh, "gamma": math.gamma, "erf": math.erf, "acosh": math.acosh, "asinh": math.asinh, "atanh": math.atanh } class Token: def __init__(self, lextype, text="", number=0.): self.lextype = lextype self.text = text self.number = number self.func = None def __str__(self): s = "(" if self.lextype == NUMBER: s += "NUMBER" elif self.lextype == NAME: s += "NAME" elif self.lextype == PLUS: s += "PLUS" elif self.lextype == MINUS: s += "MINUS" elif self.lextype == MUL: s += "MUL" elif self.lextype == DIV: s += "DIV" elif self.lextype == POW: s += "POW" elif self.lextype == LPAR: s += "LPAR" elif self.lextype == RPAR: s += "RPAR" elif self.lextype == X: s += "X" elif self.lextype == Y: s += "Y" elif self.lextype == ENDLINE: s += "ENDLINE" elif self.lextype == ILLEGAL: s += "ILLEGAL" else: assert(False) s += ", \"" s += self.text s += "\", " s += str(self.number) s += ")" return s def __repr__(self): return "Token" + str(self) class ParserException(Exception): def __init__(self, text = "Parser error"): self.text = text def __str__(self): return self.text def __repr__(self): return str(self) class Parser: def __init__(self): self.text = "" self.tokens = [] self.textPos = 0 self.tokensPos = 0 self.rpn = [] self.x = 0. self.y = 0. self.scannerRules = [] self.compileScannerRules() self.stack = [] self.compiled = False def compileScannerRules(self): self.scannerRules.clear() for (expr, lexType) in regExpressions: e = re.compile(expr) self.scannerRules.append((e, lexType)) def setParseLine(self, text): self.text = text self.tokens.clear() self.textPos = 0 self.tokensPos = 0 self.rpn.clear() def scan(self): self.textPos = 0 self.tokens.clear() self.tokensPos = 0 textLen = len(self.text) while self.textPos < textLen: # Skip space m = whiteSpace.match(self.text[self.textPos:]) if m != None: (lexBeg, lexEnd) = m.span() self.textPos += lexEnd continue ruleFound = False for (expr, lexType) in self.scannerRules: s = self.text[self.textPos:] m = expr.match(s) if m != None: ruleFound = True (lexBeg, lexEnd) = m.span() assert(lexEnd - lexBeg > 0) lexText = m.group() t = Token(lexType, lexText) if lexType == NAME: if lexText == "x" or lexText == "X": t.lextype = X elif lexText == "y" or lexText == "Y": t.lextype = Y elif lexText == "pi" or lexText == "PI": t.lextype = NUMBER t.number = math.pi elif lexText == "e" or lexText == "E": t.lextype = NUMBER t.number = math.e elif lexType == NUMBER: t.number = float(lexText) self.tokens.append(t) self.textPos += lexEnd - lexBeg break if not ruleFound: break # Illegal beginning of text self.tokens.append(Token(ENDLINE)) #------------------------------------------------ # Grammar rules: # S -> F \$ # F -> T | F + T | F - T # T -> M | T * M | T / M # M -> E | M ^ E # E -> Func | NUMBER | ( F ) # Func -> NAME ( F ) #------------------------------------------------ # Transform the grammar to recursive form # S -> F ENDLINE # F -> T Ftail # Ftail -> + T Ftail | - T Ftail | empty # T -> M Ttail # Ttail -> * M Ttail | / M Ttail | empty # M -> E Mtail # Mtail -> ^ E Mtail | empty # E -> Func | NUMBER | ( F ) | X | Y # Func -> NAME ( F ) #------------------------------------------------ def parse(self): self.tokensPos = 0 self.rpn.clear() try: self.processS() self.compiled = True return (True, "OK") except ParserException as e: self.compiled = False return (False, str(e)) # S -> F ENDLINE def processS(self): if self.tokensPos >= len(self.tokens): raise ParserException("Empty formula") self.processF(); self.skip(ENDLINE) def skip(self, lextype = (-1)): if self.tokensPos >= len(self.tokens): raise ParserException("Syntax error") if lextype >= 0: if self.peekToken().lextype != lextype: raise ParserException("Syntax error") self.tokensPos += 1 def peekToken(self): if self.tokensPos >= len(self.tokens): raise ParserException("End of formula") return self.tokens[self.tokensPos] # F -> T Ftail def processF(self): self.processT() self.processFtail() # Ftail -> + T Ftail | - T Ftail | empty def processFtail(self): if self.tokensPos >= len(self.tokens): return if self.peekToken().lextype == PLUS: self.skip(PLUS) self.processT() self.rpn.append(Token(PLUS)) self.processFtail() elif self.peekToken().lextype == MINUS: self.skip(MINUS) self.processT() self.rpn.append(Token(MINUS)) self.processFtail() # T -> M Ttail def processT(self): self.processM() self.processTtail() # Ttail -> * M Ttail | / M Ttail | empty def processTtail(self): if self.tokensPos >= len(self.tokens): return if self.peekToken().lextype == MUL: self.skip(MUL) self.processM() self.rpn.append(Token(MUL)) self.processTtail() elif self.peekToken().lextype == DIV: self.skip(DIV) self.processM() self.rpn.append(Token(DIV)) self.processTtail() # M -> E Mtail def processM(self): self.processE() self.processMtail() # Mtail -> ^ E Mtail | empty def processMtail(self): if self.tokensPos >= len(self.tokens): return if self.peekToken().lextype == POW: self.skip(POW) self.processE() self.processMtail() self.rpn.append(Token(POW)) # E -> Func | NUMBER | ( F ) | X | Y def processE(self): if self.tokensPos >= len(self.tokens): raise ParserException("Syntax error") if self.peekToken().lextype == NAME: self.processFunc() elif self.peekToken().lextype == NUMBER: self.rpn.append(self.peekToken()) self.skip(NUMBER) elif self.peekToken().lextype == LPAR: self.skip(LPAR) self.processF() self.skip(RPAR) elif self.peekToken().lextype == X: self.rpn.append(self.peekToken()) self.skip(X) elif self.peekToken().lextype == Y: self.rpn.append(self.peekToken()) self.skip(Y) else: raise ParserException("Syntax error") # Func -> NAME ( F ) def processFunc(self): if self.tokensPos >= len(self.tokens): raise ParserException("Syntax error") t = self.peekToken() # Function name if t.text in standardFunctions: t.func = standardFunctions[t.text] self.skip(NAME) self.skip(LPAR) self.processF() self.skip(RPAR) self.rpn.append(t) # Add the function call def compile(self): self.scan() (success, message) = self.parse() return (success, message) def evaluate(self, x = 0., y = 0.): self.stack.clear() for t in self.rpn: if t.lextype == NUMBER: self.stack.append(t.number) elif t.lextype == PLUS: b = self.stack.pop() a = self.stack.pop() self.stack.append(a + b) elif t.lextype == MINUS: b = self.stack.pop() a = self.stack.pop() self.stack.append(a - b) elif t.lextype == MUL: b = self.stack.pop() a = self.stack.pop() self.stack.append(a * b) elif t.lextype == DIV: b = self.stack.pop() a = self.stack.pop() self.stack.append(a / b) elif t.lextype == POW: b = self.stack.pop() a = self.stack.pop() self.stack.append(a ** b) elif t.lextype == X: self.stack.append(x) elif t.lextype == Y: self.stack.append(y) elif t.lextype == NAME: a = self.stack.pop() res = 0. if t.func != None: res = (t.func)(a) self.stack.append(res) return self.stack[0] def main(): parser = Parser() while True: vx = input("Enter the value of x: ") try: x = float(vx) except ValueError: break text = input("Enter an expression (\"q\" for the end):\n") if text == "q": break parser.setParseLine(text) (success, errorText) = parser.compile() if not success: print(errorText) try: v = parser.evaluate(x=x) print("=", v) except Exception as e: print(e) if __name__ == "__main__": main()