#!/usr/bin/env python

TS_A = 'a'
TS_B = 'b'
TS_PLUS = '+'
TS_MULT = '*'
SYM_END = object()
NTS_E = 1
NTS_T = 2
NTS_F = 3

# 1. E -> E + T
# 2. E -> T
# 3. T -> T * F
# 4. T -> F
# 5. F -> 'a'

# 1. E -> T F
# 2. F -> '+' T F
# 3. F ->
# 4. T -> 'b'
# 5. T -> 'a'

table = {
    NTS_E : {
        TS_A: 1,
        TS_B: 1,
    },
    NTS_F : {
        TS_PLUS: 2,
        SYM_END: 3
    },
    NTS_T : {
        TS_A: 4,
        TS_B: 5
    }
}

def tparse(text):
    stack = []
    stack.append(NTS_E);
    while len(stack) > 0:
        if len(text) == 0:
            c = SYM_END
        else:
            c = text[0]
        if c == stack[-1]:
            text = text[1:]
            stack.pop()
        else:
            try:
                rule = table[stack[-1]][c]
            except KeyError:
                print("Unexpected %s" % c)
                return
            if rule == 1:
                stack.pop()
                stack.append(NTS_F)
                stack.append(NTS_T)
            elif rule == 2:
                stack.pop()
                stack.append(NTS_F)
                stack.append(NTS_T)
                stack.append(TS_PLUS)
            elif rule == 3:
                stack.pop()
            elif rule == 4:
                stack.pop()
                stack.append(TS_A)
            elif rule == 5:
                stack.pop()
                stack.append(TS_B)
            else:
                print("Unexpected %s" % (text[0]))
                return
            print("Applied rule %d" % rule)

if __name__ == '__main__':
    tparse("b+a+b+b+a")