<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 A Recursive Parser for Arithmetic Expressions
In this notebook we implement a simple recursive descend parser for arithmetic expressions.
This parser will implement the following grammar
Step1:  The function tokenize receives a string s as argument and returns a list of tokens.
The string s is supposed to represent an arithmetical expression. 
Note
Step2:  Implementing the Recursive Descend Parser
The function parse takes a string s as input and parses this string according to the recursive grammar
shown above.  The function returns the floating point number that results from evaluation the expression given in s.
Step3:  The function parseExpr implements the following grammar rule
Step4:  The function parseExprRest implements the following grammar rules
Step5:  The function parseProduct implements the following grammar rule
Step6:  The function parseProductRest implements the following grammar rules
Step7:  The function parseFactor implements the following grammar rules
Step8:  Testing
<ASSISTANT_TASK:>
Python Code:
import re
Explanation: A Recursive Parser for Arithmetic Expressions
In this notebook we implement a simple recursive descend parser for arithmetic expressions.
This parser will implement the following grammar:
$$
  \begin{eqnarray}
  \mathrm{expr}        & \rightarrow & \mathrm{product}\;\;\mathrm{exprRest}            \[0.2cm]
  \mathrm{exprRest}    & \rightarrow & \texttt{'+'} \;\;\mathrm{product}\;\;\mathrm{exprRest}   \
                       & \mid        & \texttt{'-'} \;\;\mathrm{product}\;\;\mathrm{exprRest}   \
                       & \mid        & \varepsilon                                      \[0.2cm]
  \mathrm{product}     & \rightarrow & \mathrm{factor}\;\;\mathrm{productRest}          \[0.2cm]
  \mathrm{productRest} & \rightarrow & \texttt{''} \;\;\mathrm{factor}\;\;\mathrm{productRest} \
                       & \mid        & \texttt{'/'} \;\;\mathrm{factor}\;\;\mathrm{productRest} \
                       & \mid        & \varepsilon                                      \[0.2cm]
  \mathrm{factor}      & \rightarrow & \texttt{'('} \;\;\mathrm{expr} \;\;\texttt{')'}                \
                       & \mid        & \texttt{NUMBER} 
  \end{eqnarray*}
$$
Implementing a Scanner
We implement a scanner with the help of the module re.
End of explanation
def tokenize(s):
    '''Transform the string s into a list of tokens.  The string s
       is supposed to represent an arithmetic expression.
    '''
    lexSpec = r'''([ \t]+)        |  # blanks and tabs
                  ([1-9][0-9]*|0) |  # number
                  ([()])          |  # parentheses 
                  ([-+*/])        |  # arithmetical operators
                  (.)                # unrecognized character
               '''
    tokenList = re.findall(lexSpec, s, re.VERBOSE)
    result    = []
    for ws, number, parenthesis, operator, error in tokenList:
        if ws:        # skip blanks and tabs
            continue
        elif number:
            result += [ number ]
        elif parenthesis:
            result += [ parenthesis ]
        elif operator:
            result += [ operator ]
        else:
            result += [ f'ERROR({error})']
    return result
tokenize('1 + (2 + @ 34 - 2**0)/7')
Explanation: The function tokenize receives a string s as argument and returns a list of tokens.
The string s is supposed to represent an arithmetical expression. 
Note: 
1. We need to set the flag re.VERBOSE in our call of the function findall
   below because otherwise we are not able to format the regular expression lexSpec the way 
   we have done it.
2. The regular expression lexSpec contains 5 parenthesized groups.  Therefore,
   findall returns a list of 5-tuples where the 5 components correspond to the 5
   groups of the regular expression.
End of explanation
def parse(s):
    TL           = tokenize(s)
    result, Rest = parseExpr(TL)
    assert Rest == [], f'Parse Error: could not parse {TL}'
    return result
Explanation: Implementing the Recursive Descend Parser
The function parse takes a string s as input and parses this string according to the recursive grammar
shown above.  The function returns the floating point number that results from evaluation the expression given in s.
End of explanation
def parseExpr(TL):
    product, Rest = parseProduct(TL)
    return parseExprRest(product, Rest)
Explanation: The function parseExpr implements the following grammar rule:
$$ \mathrm{expr} \rightarrow \;\mathrm{product}\;\;\mathrm{exprRest} $$
It takes a token list TL as its input and returns a pair of the form (value, Rest) where
- value is the result of evaluating the arithmetical expression
  that is represented by TL and
- Rest is a list of those tokens that have not been consumed during the parse process.
End of explanation
def parseExprRest(Sum, TL):
    if TL == []:
        return Sum, []
    elif TL[0] == '+':
        product, Rest = parseProduct(TL[1:])
        return parseExprRest(Sum + product, Rest)
    elif TL[0] == '-':
        product, Rest = parseProduct(TL[1:])
        return parseExprRest(Sum - product, Rest)
    else:
        return Sum, TL
Explanation: The function parseExprRest implements the following grammar rules:
$$
  \begin{eqnarray}
  \mathrm{exprRest}    & \rightarrow & \texttt{'+'} \;\;\mathrm{product}\;\;\mathrm{exprRest}   \
                       & \mid        & \texttt{'-'} \;\;\mathrm{product}\;\;\mathrm{exprRest}   \
                       & \mid        & \;\varepsilon                                      \[0.2cm]
  \end{eqnarray}
$$
It takes two arguments:
- Sum is the value that has already been parsed,
- TL is the list of tokens that still need to be consumed.
It returns a pair of the form (value, Rest) where
- value is the result of evaluating the arithmetical expression
  that is represented by TL and
- Rest is a list of those tokens that have not been consumed during the parse process.
End of explanation
def parseProduct(TL):
    factor, Rest = parseFactor(TL)
    return parseProductRest(factor, Rest)
Explanation: The function parseProduct implements the following grammar rule:
$$ \mathrm{product} \rightarrow \;\mathrm{factor}\;\;\mathrm{productRest} $$
It takes one argument:
- TL is the list of tokens that need to be consumed.
It returns a pair of the form (value, Rest) where
- value is the result of evaluating the arithmetical expression
  that is represented by TL and
- Rest is a list of those tokens that have not been consumed while trying to parse a product.
End of explanation
def parseProductRest(product, TL):
    if TL == []:
        return product, []
    elif TL[0] == '*': 
        factor, Rest = parseFactor(TL[1:])
        return parseProductRest(product * factor, Rest)
    elif TL[0] == '/':
        factor, Rest = parseFactor(TL[1:])
        return parseProductRest(product / factor, Rest)
    else:
        return product, TL
Explanation: The function parseProductRest implements the following grammar rules:
$$
  \begin{eqnarray}
  \mathrm{productRest} & \rightarrow & \texttt{''} \;\;\mathrm{factor}\;\;\mathrm{productRest} \
                       & \mid        & \texttt{'/'} \;\;\mathrm{factor}\;\;\mathrm{productRest} \
                       & \mid        & \;\varepsilon    \                                
  \end{eqnarray*}
$$
It takes two arguments:
- product is the value that has already been parsed,
- TL is the list of tokens that still need to be consumed.
It returns a pair of the form (value, Rest) where
- value is the result of evaluating the arithmetical expression
  that is represented by TL and
- Rest is a list of those tokens that have not been consumed while trying to parse the rest of a product.
End of explanation
def parseFactor(TL):
    if TL[0] == '(': 
        expr, Rest = parseExpr(TL[1:])
        assert Rest[0] == ')', 'Parse Error: expected ")"'
        return expr, Rest[1:]
    else: 
        return float(TL[0]), TL[1:]
Explanation: The function parseFactor implements the following grammar rules:
$$
  \begin{eqnarray}
  \mathrm{factor}      & \rightarrow & \texttt{'('} \;\;\mathrm{expr} \;\;\texttt{')'}                \
                       & \mid        & \;\texttt{NUMBER} 
  \end{eqnarray}
$$
It takes one argument:
- TL is the list of tokens that still need to be consumed.
It returns a pair of the form (value, Rest) where
- value is the result of evaluating the arithmetical expression
  that is represented by TL and
- Rest is a list of those tokens that have not been consumed while trying to parse a factor.
End of explanation
def test(s):
    r1 = parse(s)
    r2 = eval(s)
    assert r1 == r2
    return r1
test('11+22*(33-44)/(5-10*5/(4-3))')
test('0*11+22*(33-44)/(5-10*5/(4-3))')
Explanation: Testing
End of explanation
<END_TASK>