recursive-descent-parser.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import string

'''
Grammar:
E -> A(E, E)
E -> epsilon
A -> a|b|...|z

First(E) = {a, b, ... , z, epsilon}
First(A) = {a, b, ... , z}

Follow(E) = {',', )}
Follow(A) = {(}

Select(E -> A(E, E)) = {a, b, ... , z}
Select(E -> epsilon) = {',', )}
Select(A -> a|b|...|z) = {a, b, ... , z}
'''

def error(reason):
    print("Error occured: %s" % reason)
    exit(1)

def precedure_E(token):
    global p
    print("Precedure of E involved")
    if token in [',', ')']:
        print("Production: E -> epsilon")
        '''
        E -> epsilon should not consume a token in token list
        '''
        p -= 1
        return
    elif token in string.lowercase:
        print("Production: E -> A(E, E)")
        precedure_A(token)

        token = getToken()
        if token != '(':
            error("'(' excepted, got %r" % (token))

        token = getToken()
        precedure_E(token)

        token = getToken()
        if token != ',':
            error("',' excepted, got %r" % (token))

        token = getToken()
        precedure_E(token)

        token = getToken()
        if token != ')':
            error("')' excepted, got %r" % (token))
    else:
        error("',' / ')' or lower case letter excepted, got %r" % (token))


def precedure_A(token):
    print("Precedure of A involved")
    print("Production: A -> a|b|...|z")
    if token in string.lowercase:
        print("A = %r" % (token))
        return
    else:
        error("lower case letter excepted, got %r" % (token))


data = 'a(b(,c(,)),d(,))'
data = 'a(b(,c(,)),d(,),)'
data = 'a(b(,c(,)),d(,)'
p = 0

def getToken():
    global p
    if p < len(data):
        token = data[p]
        print("Token %r dispatched" % (token))
        p += 1
        return token
    return ''


def main():
    print("Data: %s" % (data))
    precedure_E(getToken())

if __name__ == "__main__":
    main()