import sys
def add(L, u, j, R):
    R.append((L, u, j))

def pop(s, i, R):
    s, (L, i_) = s # pop(s, i, R)
    add(L, s, i, R) # check and add
    return s, R

def push(s, t):
    return (tuple(s), t)

def gll(I):
    i = 0
    R = []
    s = push([], ('L0', 0))
    L = 'LS'
    while True:
        if L == 'L0':
            if R:
                (L, s1, j), *R = R # remove(L, si, j) from R
                if L == 'L0' and s1 == () and j == len(I)-1: # discount $
                    return "success"
                else:
                    s = s1
                    i = j
                    #L = 'L' # goto L
                    continue
            else:
                return "error"
        elif L == 'LS':
            #if I[i] in {'a', 'c'}:
            add('LS1', s, i, R)
            #if I[i] in {'a', 'b'}:
            add('LS2', s, i, R)
            #if I[i] in {'d', '$'}:
            add('LS3', s, i, R)
            add('LS4', s, i, R)
            L = 'L0' # fall through
            continue

        elif L == 'LS1':
            s = push(s, ('L1', i))
            L = 'LA'
            continue
        elif L == 'L1':
            s = push(s, ('L2', i))
            L = 'LS'
            continue
        elif L == 'L2':
            if I[i] == 'd':
                i = i+1
                s, R = pop(s, i, R)
            L = 'L0'
            continue
        elif L == 'LS2':
            s = push(s, ('L3', i))
            L = 'LB'
            continue
        elif L == 'L3':
            s = push(s, ('L4', i))
            L = 'LS'
            continue
        elif L == 'L4':
            s, R = pop(s, i, R)
            L = 'L0'
            continue
        elif L == 'LS3':
            s, R = pop(s, i, R)
            L = 'L0'
            continue
        elif L == 'LS4':
            if I[i] == 'd':
                i = i+1
            #s = push(s, ('L5', i))
            L = 'LS4.1'
            continue

        elif L == 'LS4.1':
            if I[i] == 'g':
                i = i+1
            s = push(s, ('L5', i))
            L = 'LC'
            continue

        elif L == 'L5':
            s, R = pop(s, i, R)
            L = 'L0'
            continue
        elif L == 'LC':
            add('LC1', s, i, R)
            L = 'L0'
            continue
        elif L == 'LA':
            add('LA1', s, i, R)
            add('LA2', s, i, R)
            L = 'L0'
            continue
        elif L == 'LA1':
            if I[i] == 'a':
                i = i+1
                s, R = pop(s, i, R)
            L = 'L0'
            continue
        elif L == 'LA2':
            if I[i] == 'c':
                i = i+1
                s, R = pop(s, i, R)
            L = 'L0'
            continue
        elif L == 'LB':
            add('LB1', s, i, R)
            add('LB2', s, i, R)
            L = 'L0'
            continue
        elif L == 'LB1':
            if I[i] == 'a':
                i = i+1
                s, R = pop(s, i, R)
            L = 'L0'
            continue
        elif L == 'LB2':
            if I[i] == 'b':
                i = i+1
                s, R = pop(s, i, R)
            L = 'L0'
            continue
        elif L == 'LC1':
            if I[i] == 'c':
                i = i+1
                s, R = pop(s, i, R)
            L = 'L0'
            continue
        else:
            assert False
I = 'dgc$'
assert gll(I) == 'success'

#I = 'aad$'
#assert gll(I) == 'success'
#I = 'aaadd$'
#assert gll(I) == 'success'
#I = 'bd$'
#assert gll(I) == 'error'
#print('.')


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

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