recursive_descent_parser.py

# S -> aSa | aa
def S(s, pos, depth):
    orig = pos
    # Try aSa
    print "%strying aSa @%d" % (' '*depth, pos)
    pos = a(s, pos, depth+1)
    if pos is not None:
        pos = S(s, pos, depth+1)
        if pos is not None:
            pos = a(s, pos, depth+1)
            if pos is not None:
                print "%sgot it, span: %r-%r" % (' '*depth, orig, pos)
                return pos
    print "%sfailed" % (' '*depth,)

    pos = orig
    # Try aa
    print "%strying aa @%d" % (' '*depth, pos)
    pos = a(s, pos, depth+1)
    if pos is not None:
        pos = a(s, pos, depth+1)
        if pos is not None:
            print "%sgot it, span: %r-%r" % (' '*depth, orig, pos)
            return pos
    print "%sfailed" % (' '*depth,)

    # Fail
    return None

def a(s, pos, depth):
    if pos >= len(s):
        return None
    if s[pos] == 'a':
        return pos + 1
    return None


def test(s):
    pos = S(s, 0, 0)
    if pos != len(s):
        print '%s fail' % s
    else:
        print '%s accepted' % s


if __name__ == '__main__':
    #test('aa')
    #test('aaaa')
    test('aaaaaa')
    #test('aaaaaaaa')

Question: http://ideone.com/Dkfa8o, posted on freenode/#programming 2013-04-09