'''

This program implements a recursive descent parser for the CFG below:

1. S aA

2. S AB

3. A bA

4. A c

5. B aA

6. B b

'''

import math

class ParseError(Exception): pass

w = '' # the input string

i = 0 # index of the next (lookahead) token

p = 'S' # the current sentential form in the derivation

def read_token():

global i

i += 1

def look_ahead():

return w[i]

#==============================================================

# FRONT END PARSER

#==============================================================

def S():

if look_ahead() == 'a':

rule_1()

read_token()

A()

elif look_ahead() in ('b', 'c'):

rule_2()

A()

B()

else:

raise ParseError

def A(): # implement

def B(): # implement

#==============================================================

# BACK END PARSER (ACTION RULES)

#==============================================================

def rule_1():

global p

print('1')

p = p.replace('S', 'aA', 1)

print(p)

def rule_2(): # implement

def rule_3(): # implement

def rule_4(): # implement

def rule_5(): # implement

def rule_6(): # implement

#==============================================================

# User Interface Loop

#==============================================================

w = input(' Enter expression: ')

while w != '':

i = 0

w = w + '$' # EOF marker

print('S')

try:

S() # call the parser

except:

if look_ahead() == '$':

print('parse error: unexpected EOF')

else:

print('parse error: unexpected symbol')

print(w[:i], '|', w[i:])

w = input(' Enter expression: ')