import simplefuzzer
G = {
'<S>': [
    ['<A>', '<S>', 'd'],
    ['<B>', '<S>'],
    ['g', 'p', '<C>'],
    []],
'<A>': [['a'], ['c']],
'<B>': [['a'], ['b']],
'<C>': ['c']
}

class Node:
    def __init__(self, L, j, children):
        self.L, self.i, self.children = L, j, children
    def __repr__(self):
        return str((self.L, self.i, self.children))

class GSS:
    def __init__(self):
        self.gss, self.P = {}, {}

    def get(self, L, i, children):
        my_label = (L, i)
        if my_label not in self.gss:
            self.gss[my_label] = Node(L, i, children)
            assert my_label not in self.P
            self.P[my_label] = []
        return self.gss[my_label]

    def add_to_P(self, u, j):
        label = (u.L, u.i)
        self.P[label].append(j)

    def __repr__(self):
        return str(self.gss)

class GLLParser:
    def create(self, L, u, j):
        v = self.gss.get(L, j, [u])
        if u not in v.children:
            v.children.append(u)
            label = (L, j)
            for k in self.gss.P[label]:
                self.add(L, u, k)
        return v

    def add(self, L, u, j):
        if (L, u) not in self.U[j]:
            self.U[j].append((L, u))
            assert (L,u,j) not in self.R
            self.R.append((L, u, j))

    def pop(self, u, j):
        if u != self.u0:
            self.gss.add_to_P(u, j)
            for v in u.children:
                self.add(u.L, v, j)
        return u


    def __init__(self, input_str):
        self.R = []
        self.gss = GSS()
        self.I = input_str
        self.m = len(self.I) # |I| + 1
        self.u1 = self.gss.get('L0', 0, [])
        self.u0 = self.gss.get('$', self.m, [])
        self.u1.children.append(self.u0)

        self.U = []
        for j in range(self.m): # 0<=j<=m
            self.U.append([]) # U_j = empty

def gll(parser):
    c_u = parser.u1
    i = 0
    L = 'LS' # starting state
    while True:
        if L == 'L0':
            if parser.R:
                (L, c_u, i), *parser.R = parser.R
                continue
            else:
                if ('L0', parser.u0) in parser.U[parser.m-1]: return 'success'
                else: return 'failed'
        elif L == 'L_':
            c_u = parser.pop(c_u, i)
            L = 'L0'
            continue
        elif L == 'LS':
            #if I[i] in {'a', 'c'}:
            parser.add('LS1_0', c_u, i)
            #if I[i] in {'a', 'b'}:
            parser.add('LS2_0', c_u, i)
            #if I[i] in {'d', '$'}:
            parser.add('LS3_0', c_u, i)
            parser.add('LS4_0', c_u, i)
            L = 'L0'
            continue
        elif L == 'LS1_0':
            c_u = parser.create('LS1_1', c_u, i)
            L = 'LA'
            continue
        elif L == 'LS1_1':
            c_u = parser.create('LS1_2', c_u, i)
            L = 'LS'
            continue
        elif L == 'LS1_2':
            if parser.I[i] == 'd':
                i = i+1
                L = 'L_'
            else:
                L = 'L0'
            continue
        elif L == 'LS2_0':
            c_u = parser.create('LS2_1', c_u, i)
            L = 'LB'
            continue
        elif L == 'LS2_1':
            c_u = parser.create('LS2_2', c_u, i)
            L = 'LS'
            continue
        elif L == 'LS2_2':
            L = 'L_'
            continue
        elif L == 'LS3_0':
            if parser.I[i] == 'g':
                i = i+1
                L = 'LS3_1'
            else:
                L = 'L0'
                continue
        elif L == 'LS3_1':
            if parser.I[i] == 'p':
                i = i+1
                L = 'LS3_2'
            else:
                L = 'L0'
                continue
        elif L == 'LS3_2':
            c_u = parser.create('LS3_3', c_u, i)
            L = 'LC'
            continue
        elif L == 'LS3_3':
            L = 'L_'
            continue
        elif L == 'LS4_0':
            L = 'L_'
            continue
        elif L == 'LC':
            parser.add('LC1_0', c_u, i)
            L = 'L0'
            continue
        elif L == 'LC1_0':
            if parser.I[i] == 'c':
                i = i+1
                L = 'L_'
            else:
                L = 'L0'
            continue
        elif L == 'LA':
            #if I[i] == 'a':
            parser.add('LA1_0', c_u, i)
            #if I[i] == 'c':
            parser.add('LA2_0', c_u, i)
            L = 'L0'
            continue
        elif L == 'LA1_0':
            if parser.I[i] == 'a':
                i = i+1
                L = 'L_'
            else:
                L = 'L0'
            continue
        elif L == 'LA2_0':
            if parser.I[i] == 'c':
                i = i+1
                L = 'L_'
            else:
                L = 'L0'
            continue
        elif L == 'LB':
            #if I[i] == 'a':
            parser.add('LB1_0', c_u, i)
            #if I[i] == 'b':
            parser.add('LB2_0', c_u, i)
            L = 'L0'
            continue
        elif L == 'LB1_0':
            if parser.I[i] == 'a':
                i = i+1
                L = 'L_'
            else:
                L = 'L0'
            continue
        elif L == 'LB2_0':
            if parser.I[i] == 'b':
                i = i+1
                L = 'L_'
            else:
                L = 'L0'
            continue
        else:
            assert False

def compile_def(g, definition):
    for rule in definition:
        compile_rule(rule)

def compile_rule(g, rule):
    res = []
    for i, t in enumerate(rule):
        if (t[0],t[-1]) == ('<', '>'):
            r = compile_nonterminal(t, i)
            res.append(r)
        else:
            r = compile_terminal(t, i)
            res.append(r)

def compile_terminal(t, i):
    return '''
            if parser.I[i] == '%s':
                i = i+1
                c_u = parser.pop(c_u, i)
            L = 'L0'
            continue
''' % t


g = GLLParser('gpc$')
assert gll(g) == 'success' # Success
f = g.gss.gss[(g.u1.L, g.u1.i)]
print(f)
g = GLLParser('ad$')
assert gll(g)  == 'success' # Success
f = g.gss.gss[(g.u1.L, g.u1.i)]
print(f)
g = GLLParser('aad$')
assert gll(g)  == 'success' # Success
g = GLLParser('aaadd$')
assert gll(g)  == 'success' # Success
g = GLLParser('bd$')
assert gll(g)  == 'failed' # Error

gf = simplefuzzer.LimitFuzzer(G)
for i in range(1000):
    s = gf.iter_fuzz(key='<S>', max_depth=100)
    print(s)
    g = GLLParser(s+'$')
    assert gll(g) == 'success'
    print(g.gss)