import re

"""
Explanation: A Shift-Reduce Parser for Arithmetic Expressions
In this notebook we implement a generic shift reduce parser.  The parse table that we use will
implement the following grammar for arithmetic expressions:
$$
  \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
In order to parse, we need a scanner.  We will use the same scanner that we have already used for our top down parser that was presented in the notebook Top-Down-Parser.ipynb.
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 ]
        else:
            result += [ f'ERROR({error})']
    return result

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

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


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     += ['EOF']
    while True:
        q = States[-1]
        t = TL[index]
        print('Symbols:', ' '.join(Symbols + ['|'] + TL[index:]).strip())
        action = self.mActionTable.get((q, t), 'error') # undefined interpreted as error
        if action == 'error': 
            return False
        elif action == 'accept':
            return True
        elif action[0] == 'shift': # action = ('shift', s)
            s        = action[1]
            Symbols += [t]
            States  += [s]
            index   += 1
        elif action[0] == 'reduce': # action = ('reduce', r)
            head, body = action[1]
            n       = len(body)
            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.ipynb

"""
Explanation: Assume a grammar $G = \langle V, T, R, S \rangle$ is given.  A  shift-reduce parser
is defined as a 4-Tuple
$$P = \langle Q, q_0, \texttt{action}, \texttt{goto} \rangle$$
where
- $Q$ is the set of states of the shift-reduce parser.  
For the purpose of the shift-reduce-parser, states are purely abstract. 
- $q_0 \in Q$ is the start state.
- $\texttt{action}$ is a function taking two arguments. The first argument is a state $q \in Q$
  and the second argument is a terminal $t \in T$.  The result of this function is an element from the set
  $$\texttt{Action} :=
       \bigl{ \langle\texttt{shift}, q\rangle  \mid q \in Q \bigr}               \cup 
       \bigl{ \langle\texttt{reduce}, r\rangle \mid r \in R \bigr} \cup 
       \bigl{ \texttt{accept} \bigr}                        \cup
       \bigl{ \texttt{error}  \bigr}.                       
  $$
  Here shift, reduce, accept, and error are strings that serve to
  distinguish the different kinds of result of the function 
  action.  Therefore the signature of the function \texttt{action} is given as follows:
  $$\texttt{action}: Q \times T \rightarrow \texttt{Action}.$$
- goto is a function that takes a state $q \in Q$ and a syntactical variable
  $v \in V$ and computes a new state.  Therefore the signature of goto is as follows:
  $$\texttt{goto}: Q \times V \rightarrow Q.$$
The class ShiftReduceParser maintains two tables as dictionaries:
- mActionTable encodes the function $\texttt{action}: Q \times T \rightarrow \texttt{Action}$.
- mGotoTable encodes the function $\texttt{goto}: Q \times V \rightarrow Q$.
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
"""


