A revised lexical scanner that can tokenize simple mathematical expressions

Introduction

Here is a revised version of the finite state machine (FSM) for simple mathematical expressions proposed previously. It corrects the bug found before and recognizes negative signs as well. However, names for mathematical functions such as sine and logarithms still cannot be identified by the algorithm.

Example for valid expressions

17-5*28.9, 0.2736+2.1^0.333, -2+7^(2.5/33.86), -(2-5.9)/70.24*(5-(0.18+4.9)), -(-(2+5.9)*4)/9.3*(5-(0.2+6)).

Example for detecting invalid expressions

3+, -4*(5-+2.7/6), (3+4.2).52, (3+4)52.

Remarks

1. A class for the finite state machine is given so that a FSM can easily be created by submitting it with a human readable script that includes states and transition arcs. The above FSM can be created by the script below:
   

   eng = FSM()
   # states
   [A,B,C,D,E,F] = ['A','B','C','D','E','F']
   eng.initialState = A    # initial state
   eng.finalStates = [C,D,E,F]  # final states
   # transition arcs
   # (startState, tokenList, endState, action)
   eng.addArc(A,'-('        ,A,FSM.storeToken)
   eng.addArc(A,'123456789' ,C,FSM.buildToken)
   eng.addArc(A,'0'         ,D,FSM.buildToken)
   eng.addArc(B,'('         ,B,FSM.storeToken)
   eng.addArc(B,'123456789' ,C,FSM.buildToken)
   eng.addArc(C,'+-*/^'     ,B,FSM.storeToken)
   eng.addArc(C,'0123456789',C,FSM.buildToken)
   eng.addArc(C,')'         ,F,FSM.storeToken)
   eng.addArc(C,'.'         ,E,FSM.buildToken)
   eng.addArc(B,'0'         ,D,FSM.buildToken)
   eng.addArc(D,'+-*/^'     ,B,FSM.storeToken)
   eng.addArc(D,'.'         ,E,FSM.buildToken)
   eng.addArc(E,'0123456789',E,FSM.buildToken)
   eng.addArc(E,')'         ,F,FSM.storeToken)
   eng.addArc(E,'+-*/^'     ,B,FSM.storeToken)
   eng.addArc(F,')'         ,F,FSM.storeToken)
   eng.addArc(F,'+-*/^'     ,B,FSM.storeToken)
   

2. Minus sign is accepted by this algorithm. Expressions such as -3, -(4+5) and -(-(-0.278+5)*3) are valid.
3. Expression such as .3 is considered as invalid, not 0.3.
4. Pair check for brackets is not yet implemented as the function of the algorithm is to tokenize expressions. Whether an expression is mathematically correct or not is the responsibility of later stages of parsing.

Source Code

# finite state machine class FSM: # action for transitional arc buildToken = 0 # build token storeToken = 1 # store tokens to token list def __init__(self): # public properties self.initialState = None self.finalStates = [] # # private properties self._arcList = [] # current state self._currState = None # current token self._currTok = '' # token list self._tokens = [] def addArc(self, pStart, pToken, pEnd, pAction): self._arcList.append([pStart, pToken, pEnd, pAction]) def tokenize(self, pStr, Trace=False): self._currState = self.initialState for mi in pStr: mNewState = 'Err' mAction = -1 for mArc in self._arcList: if mArc[0]==self._currState and \ mi in mArc[1]: mNewState = mArc[2] mAction = mArc[3] break if Trace: print('Tok:%s [%s -> %s]'% \ (mi, self._currState, mNewState)) self._currState = mNewState if self._currState == 'Err': break if mAction==self.buildToken: self._currTok += mi elif mAction==self.storeToken: if self._currTok != '': self._tokens.append(self._currTok) self._tokens.append(mi) self._currTok = '' if self._currTok != '': self._tokens.append(self._currTok) self._currTok = '' mtokens = self._tokens self._tokens = [] mexitState = self._currState if mexitState not in self.finalStates: mexitState = 'Err' return (mexitState, mtokens) # define a finite state machine # -------------------------------------------- eng = FSM() # states [A,B,C,D,E,F] = ['A','B','C','D','E','F'] eng.initialState = A # initial state eng.finalStates = [C,D,E,F] # final states # transition arcs # (startState, tokenList, endState, action) eng.addArc(A,'-(' ,A,FSM.storeToken) eng.addArc(A,'123456789' ,C,FSM.buildToken) eng.addArc(A,'0' ,D,FSM.buildToken) eng.addArc(B,'(' ,B,FSM.storeToken) eng.addArc(B,'123456789' ,C,FSM.buildToken) eng.addArc(C,'+-*/^' ,B,FSM.storeToken) eng.addArc(C,'0123456789',C,FSM.buildToken) eng.addArc(C,')' ,F,FSM.storeToken) eng.addArc(C,'.' ,E,FSM.buildToken) eng.addArc(B,'0' ,D,FSM.buildToken) eng.addArc(D,'+-*/^' ,B,FSM.storeToken) eng.addArc(D,'.' ,E,FSM.buildToken) eng.addArc(E,'0123456789',E,FSM.buildToken) eng.addArc(E,')' ,F,FSM.storeToken) eng.addArc(E,'+-*/^' ,B,FSM.storeToken) eng.addArc(F,')' ,F,FSM.storeToken) eng.addArc(F,'+-*/^' ,B,FSM.storeToken) # -------------------------------------------- # Test cases trials = ['17-5*28.9', '0.2736+2.1^0.333', '-2+7^(2.5/33.86)', '-(2-5.9)/70.24*(5-(0.18+4.9))', '-(-(2+5.9)*4)/9.3*(5-(0.2+6))'] errTrials = ['3+','-4*(5-+2.7/6)', '(3+4.2).52', '(3+4)52', '(3+4).52', '(3+4.2)52'] for mi in trials: print("Input : "+mi) mResults = eng.tokenize(mi) print("Exit State : "+mResults[0]) print("Token List : ") print(mResults[1]) print('') # erroneous cases for mi in errTrials: print("Input : "+mi) mResults = eng.tokenize(mi) print("Exit State : "+mResults[0]) print("Token List : ") print(mResults[1]) print('')

Output

Input : 17-5*28.9 Exit State : E Token List : ['17', '-', '5', '*', '28.9'] Input : 0.2736+2.1^0.333 Exit State : E Token List : ['0.2736', '+', '2.1', '^', '0.333'] Input : -2+7^(2.5/33.86) Exit State : F Token List : ['-', '2', '+', '7', '^', '(', '2.5', '/', '33.86', ')'] Input : -(2-5.9)/70.24*(5-(0.18+4.9)) Exit State : F Token List : ['-', '(', '2', '-', '5.9', ')', '/', '70.24', '*', '(', '5', '-', '(', '0.18', '+', '4.9', ')', ')'] Input : -(-(2+5.9)*4)/9.3*(5-(0.2+6)) Exit State : F Token List : ['-', '(', '-', '(', '2', '+', '5.9', ')', '*', '4', ')', '/', '9.3', '*', '(', '5', '-', '(', '0.2', '+', '6', ')', ')'] Input : 3+ Exit State : Err Token List : ['3', '+'] Input : -4*(5-+2.7/6) Exit State : Err Token List : ['-', '4', '*', '(', '5', '-'] Input : (3+4.2).52 Exit State : Err Token List : ['(', '3', '+', '4.2', ')'] Input : (3+4)52 Exit State : Err Token List : ['(', '3', '+', '4', ')'] Input : (3+4).52 Exit State : Err Token List : ['(', '3', '+', '4', ')'] Input : (3+4.2)52 Exit State : Err Token List : ['(', '3', '+', '4.2', ')']

Prolog Version

A prolog version of the above FSM is given below. Only the states and transactions are implemented, the actions of storing tokens and building tokens are not implemented. Furthermore, whether the exit state of an expression is one of the valid final states is not checked by the script.

Source Code

% Token classes % operators opr(X) :- member(X,['+','-','*','/','^']). % minus mns('-'). % open bracket opnBrc('('). % close bracket clsBrc(')'). % non-zero digits nZD(X) :- atom_number(X,N), member(N,[1,2,3,4,5,6,7,8,9]). % zero dight zro(X) :- atom_number(X,N), N=0. % digits d(X) :- zro(X). d(X) :- nZD(X). % dot dot('.'). % arc(start, input, end) arc('A',X,'C') :- nZD(X), !. arc('A',X,'D') :- zro(X), !. arc('A',X,'A') :- mns(X), !. arc('A',X,'A') :- opnBrc(X), !. arc('C',X,'C') :- d(X), !. arc('C',X,'E') :- dot(X), !. arc('C',X,'B') :- opr(X), !. arc('C',X,'F') :- clsBrc(X), !. arc('D',X,'E') :- dot(X), !. arc('D',X,'B') :- opr(X), !. arc('B',X,'B') :- opnBrc(X), !. arc('B',X,'C') :- nZD(X), !. arc('B',X,'D') :- zro(X), !. arc('E',X,'E') :- d(X), !. arc('E',X,'B') :- opr(X), !. arc('E',X,'F') :- clsBrc(X), !. arc('F',X,'F') :- clsBrc(X), !. arc('F',X,'B') :- opr(X), !. transverse(S, [T|Token], [S|Path]) :- arc(S, T, P), transverse(P, Token, Path). transverse(S, [], [S]). go:- writeln('Input an expression, press [Enter]: '), read_line_to_codes(user_input, Codes), % input as codes atom_codes(Atm, Codes), % convert codes into atom atom_chars(Atm, As), % split atom into atoms transverse('A',As, Path), writeln(Path).

Output (Prolog version)

?- go. Input an expression, press [Enter]: |: (3+2.5)/4 [A,A,C,B,C,E,E,F,B,C] true ; false. ?- go. Input an expression, press [Enter]: |: (0.5-3)*9 [A,A,D,E,E,B,C,F,B,C] true ; false. ?- go. Input an expression, press [Enter]: |: -(2-5.9)/70.24*(5-(0.18+4.9)) [A,A,A,C,B,C,E,E,F,B,C,C,E,E,E,B,B,C,B,B,D,E,E,E,B,C,E,E,F,F] true ; false.