import re

"""
Explanation: A Shift-Reduce 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{expr}\;\;\texttt{'+'}\;\;\mathrm{product}   \
                       & \mid        & \mathrm{expr}\;\;\texttt{'-'}\;\;\mathrm{product}   \
                       & \mid        & \mathrm{product}                                    \[0.2cm]
  \mathrm{product}     & \rightarrow & \mathrm{product}\;\;\texttt{''}\;\;\mathrm{factor} \
                       & \mid        & \mathrm{product}\;\;\texttt{'/'}\;\;\mathrm{factor} \
                       & \mid        & \mathrm{factor}                                     \[0.2cm]
  \mathrm{factor}      & \rightarrow & \texttt{'('} \;\;\mathrm{expr} \;\;\texttt{')'}     \
                       & \mid        & \texttt{NUMBER} 
  \end{eqnarray*}
$$
Implementing a Scanner
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\n]+)      |  # 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 ]
        elif error:
            result += [ f'ERROR({error})']
    return result

tokenize('1 + 2 * (3 - 4)')

class ShiftReduceParser():
    def __init__(self, actionTable, gotoTable):
        self.mActionTable = actionTable
        self.mGotoTable   = gotoTable

def parse(self, TL):
    index   = 0      # points to next token
    Symbols = []     # stack of symbols
    States  = ['s0'] # stack of states, s0 is start state
    TL     += ['$']
    while True:
        q = States[-1]
        t = TL[index]
        print('Symbols:', ' '.join(Symbols + ['|'] + TL[index:]).strip())
        p = self.mActionTable.get((q, t), 'error')
        if p == 'error': 
            return False
        elif p == 'accept':
            return True
        elif p[0] == 'shift':
            s = p[1]
            Symbols += [t]
            States  += [s]
            index   += 1
        elif p[0] == 'reduce':
            head, body = p[1]
            n       = len(body)
            if n > 0:
                Symbols = Symbols[:-n]
                States  = States [:-n]
            Symbols = Symbols + [head]
            state   = States[-1]
            States += [ self.mGotoTable[state, head] ]

ShiftReduceParser.parse = parse
del parse

%run parse-table.py

"""
Explanation: The function tokenize transforms the string s into a list of tokens. See below for an example.
End of explanation
"""


def test(s): 
    parser = ShiftReduceParser(actionTable, gotoTable)
    TL     = tokenize(s)
    print(f'tokenlist: {TL}\n')
    if parser.parse(TL):
        print('Parse successful!')
    else:
        print('Parse failed!')

test('(1 + 2) * 3')

test('1 * 2 + 3 * (4 - 5) / 2')

test('11+22*(33-44)/(5-10*5/(4-3))')

test('1+2*3-')

"""
Explanation: Testing
End of explanation
"""


