##
## prec.py - Precedence Climbing Parser
##	 Scheme version is prec.scm
##
##   3RD DRAFT  CURRENT
##

import re

##
## Error handling
##

class Error(Exception):
	"""Base class for custom exceptions."""
	pass
class MySyntaxError(Error): pass

##
## A simple Lexical Scanner - for basic infix expressions
##

regex = re.compile(r"(?ix) \d+ | [a-z_]\w* | [-+*/^()=,]")

def scan(src):
	return regex.findall(src)

def scangen(src):
	for token in scan(src):
		yield token

##
## Precedence Climbing Parser
##

PREC = {
	'=':2,
	'+':3, '-':3,
	'*':5, '/':5,
	'^':6,
}

UNARY_PREC = { '+':4, '-':4 }

def prec(op):
	return PREC[op]

def unary_prec(op):
	return UNARY_PREC[op]

def leftAssoc(op):
	return op not in ['^', '=']

def isBinary(op):
	"isBinary(X): True if X is a valid operator allowed in a BINARY context." 
	return op in PREC

def isUnary(op):
	"isUnary(X): True if X is a valid operator allowed in a UNARY context." 
	return op in ['+','-']


def consume():
	global next, tokens
	cur = next
	try:
		next = tokens.next()
	except StopIteration:
		next = None
	return cur

def expect(token):
	# This should just be inlined...
	if next != token:
		raise MySyntaxError, "Expected '%s', got '%s'" % (token, next)
	else:
		consume()

def P():
	"P(): Parse a parenthesized expression, unary operation, or leaf node."

	def brackets():
		consume()  ;"("
		tree = []
		while next != ")":
			e = expr(0)
			tree.append(e)
			#if STRICT: expect "," or ")"
			if next == ",": consume()
		consume() ;")"
		return tree
	
	if isUnary(next):
		# Any operator we see here is being USED in a unary context
		op = consume()
		q = unary_prec(op)
		tree = expr(q)
		return (op, tree)
	elif next == "(":
		tree = brackets()
		#print "BRACKETS() ==>", len(tree), tree
		if len(tree)==1 and type(tree[0])==list:
			tree=tree[0]
		return tree
	elif next and re.match(r'[0-9]', next):			# NUMBER
		return consume()
	elif next and re.match(r'[a-zA-Z_]', next):		# VARIABLE
		var = consume()
		if next == "(":
			args = brackets()
			return [var]+args   # THIS IS RIGHT
		else:
			return var
	else:
		if next is None:
			raise MySyntaxError, "P(): Unexpected EOF"
		else:
			raise MySyntaxError, "P(): Unexpected: '%s'" % next

def expr(n):
	tree = P()
	while next is not None and isBinary(next) and prec(next) >= n:
		op = consume()
		q = prec(op)
		if leftAssoc(op): q += 1
		tree = [op, tree, expr(q)]
	#print "expr(%d) ->" % n, tree
	return tree

def parse(src):
	global next, tokens
	
	#print "scan() ->", list( scan(src) )   # Debug the scanner
	
	# Prime the pump
	tokens = scangen(src)
	next = None
	consume()

	E = expr(0)
	expect(None)
	
	print src, '==>', printTree(E)
	print
	return E



##
## Tests
##

def printTree(t):
	if type(t) in [list, tuple]:
		return "(%s)" % " ".join([printTree(i) for i in t])
	else:
		return str(t)

for x in open("tests.txt").readlines():
	x = x.rstrip()
	if x and not x.startswith(';'):
		parse(x)