#coding=latin1

grammaires = [
    [['S', list("aSb")], ['S', []]],
    [["S", list("aSbS")], ["S", []]]
]

def nonterminal(s):
    return s.isupper()

def terminal(s):
    return s.islower()

def prefixeTerminal(l):
    """Version récursive"""
    if len(l)==0 : return []
    if nonterminal(l[0]): return []
    return [l[0]] + prefixeTerminal(l[1:])

def t_prefixeTerminal():
    res = [("abc", list("abc")), ("AS", []), ("abScF", list("ab"))]
    for (input, result) in res:
        x = prefixeTerminal(input)
        if x != result:
            print "Problème : avec %s, on trouve %s, on devrait trouver %s" % (input,x,result)

def nbTerminal(l):
    "renvoie le nombre de terminaux du mot"
    c = 0
    for s in l:
        c += terminal(s)
    return c

def t_nbTerminal():
    "Pour teste la fonction nbTerminal"
    res = [("abc", 3), ("AS", 0), ("abScF", 3), ("SaBabTaa",5) ]
    for (input, result) in res:
        x = nbTerminal(input)
        if x != result:
            print "Problème : avec %s, on trouve %d, on devrait trouver %d" % (input,x,result)

def decoupeNonTerminalG(l):
    """renvoie un triplet avec le préfixe terminal, 
    le non terminal, et le reste"""
    if len(l) ==0: return ("", '*', "")
    i = 0
    while i < len(l) and terminal(l[i]) :
        i += 1
    if i == len(l): 
        return ("", '*', l)
    return (l[:i], l[i], l[i+1:])

def t_decoupeNonTerminalG():
    "pour tester les cas limite du découpage"
    res = [("abScF",("ab", 'S', "cF")),
           ("", ("",'*',"")),
           ("SabcFR", ("", 'S', "abcFR")),
           ("abcde", ("", '*', "abcde"))]
    for (input, result) in res:
        x = decoupeNonTerminalG(input)
        if x != result:
            print "Problème : avec %s, on trouve %s, on devrait trouver %s" % (input,x,result)

def td_trop_naif(gram, proto, mot):
    """Version trop naïve, qui ne peut s'arrêter que si on place une
    limite en dur dans la récursion. Ici on s'arrête si le nombre de
    terminaux du proto mot est supérieur à la longueyr du mot"""
#    print "%20s , %20s" % (proto[:20],mot)    ## Pour débogage
    # Conditions d'arrêt : échec
    if nbTerminal(proto) > len(mot): 
        return False
    #                      réussite
    if proto == list(mot): 
        return True
    # on coupe le proto-mot en 3 parties
    (u, A, gamma) = decoupeNonTerminalG(proto)
    # pour chaque règle, d'origine A, on relance avec un nouveau proto-mot
    for (lhs, rhs) in gram:
        if lhs == A:
            new_proto = list(u) + rhs + list(gamma)
            if td_trop_naif(gram, new_proto, mot): return True
    return False


def t_td_trop_naif():
    "On suppose que l'axiome est toujours S"
    res = [ (grammaires[0], "aabb", True), (grammaires[0], "aabc", False),
            (grammaires[0], "", True)]
    for (g,m,r) in res:
        x = td_trop_naif(g,"S",m)
        if x != r:
            print "Problème : avec %s (grammaire %s), on trouve %s, on devrait trouver %s" % (m,g,x,r)