#!/usr/bin/python
import sys
import re

tag_tokens = [
	('\s*([a-zA-Z]\w*)',	'TAG_NAME'),
	('\s*([^}]+)',		'TAG_PARAM'),
	('\s*(})',		'RIGHT_BRACKET')
]

rule_tokens = [
	('\s*{\s*(\d+)\s*}',	'REPEAT'),
	('\s*({)',		'LEFT_BRACKET'),
	('\s*([_a-zA-Z]\w*)\s*\(','TERMINAL_GENERATOR_START'),
	('\s*([_a-zA-Z]\w*)',	'VARIABLE'),
	('\s*\'(.*?)\'',	'TERMINAL'),
	('\s*(::=)',		'TAKES'),
	('\s*(;)',		'SEMI_COLON'),
	('(\s)$',		'EOF'),
]

terminal_generator_tokens = [
	('\s*\'(.*?)\'',	'STRING'),
	('\s*([0-9]*\.[0-9]+)',	'FLOAT'),
	('\s*([0-9]+)',		'INTEGER'),
	('\s*(,)',		'COMMA'),
	('\s*(\))',		'TERMINAL_GENERATOR_END'),
]

class Lexical_analyzer:

	def __init__(self,input_string):
		'''
		Purpose
			create a lexical analyzer that tokenizes input_string.
		Precondition
			input_string is a string.
		'''
		global tag_tokens,rule_tokens,terminal_generator_tokens

		self.input_string = input_string

		# used to track the current position in input_string
		self.offset = 0

		# True if we want to match embedded code False otherwise
		self.match_embedded_code = False

		# create pattern matchers for terminal generator tokens
		self.terminal_generator_matchers = []
		for token in terminal_generator_tokens:
			self.terminal_generator_matchers.append( \
			 (re.compile(token[0]), token[1]) )

		# create pattern matchers for rule tokens + "{" token
		self.rule_matchers = []
		for token in rule_tokens:
			self.rule_matchers.append( (re.compile(token[0]),\
			 token[1]) )

		# create pattern matchers for tag tokens
		self.tag_matchers = []
		for token in tag_tokens:
			self.tag_matchers.append( (re.compile(token[0]),\
			 token[1]) )

		# create pattern matchers for comments
		self.comment_matcher = re.compile('\s*[#].*\n')

		# initially, we want to match rule tokens
		self.matchers = self.rule_matchers

	def next(self):
		'''
		Purpose
			return the next token in input_string or a None type
			 token if input_string does not have any more tokens.
			a token has the form: (token value, token type, line
			 number) where both token value and type are strings.
		'''
		line_number = self.input_string.count('\n',0,self.offset) + 1
		none_token = ('','None',line_number)

		# return a None type token if we are at the end of input_string
		if self.offset == len(self.input_string):
			return none_token

		if self.match_embedded_code:
			# match embedded code
			self.match_embedded_code = False
			return (self.next_embedded_code(),'TAG_PARAM',\
			 line_number)

		# ignore comments
		match = self.comment_matcher.match(self.input_string,\
		 self.offset)
		while match:
			self.offset = match.end()
			match = self.comment_matcher.match(self.input_string,\
			 self.offset)

		# pattern match the next token and update the current position
		# accordingly
		next_token = none_token
		for matcher in self.matchers:
			match = matcher[0].match(self.input_string,self.offset)
			if match:
				self.offset = match.end()
				line_number = self.input_string.count('\n',0,\
				 self.offset) + 1
				next_token = (match.group(1),matcher[1],\
				 line_number)
				break

		if next_token[1] == 'LEFT_BRACKET':
			self.matchers = self.tag_matchers
			return self.next()
		elif next_token[1] == 'RIGHT_BRACKET':
			self.matchers = self.rule_matchers
			return self.next()
		elif next_token[1] == 'TAG_NAME' and next_token[0] in \
		 ['global_precode','global_postcode','precode','postcode']:
			self.match_embedded_code = True
		elif next_token[1] == 'TERMINAL_GENERATOR_START':
			self.matchers = self.terminal_generator_matchers
		elif next_token[1] == 'COMMA':
			return self.next()
		elif next_token[1] == 'TERMINAL_GENERATOR_END':
			self.matchers = self.rule_matchers

		return next_token

	def next_embedded_code(self):
		'''
		Purpose
			return the next block of embedded code in input_string.
		'''
		offset = self.offset
		embedded_code = ''
		while offset < len(self.input_string) and \
		 self.input_string[offset] != "}":
			# process escape characters
			if self.input_string[offset] == "\\" and \
			 self.input_string[offset+1] in ["}","\\"]:
				offset += 1

			embedded_code += self.input_string[offset]
			offset += 1

		self.offset = offset
		return embedded_code
class Parser:
	'''
	parse a YouGen grammar that has the following structure:
		grammar = {(tag|rule)} .
		tag = tag_name tag_param .
		rule = variable "::=" {term} ";" .
		term = (variable|terminal) .
	'''

	def __init__(self,input_string):
		'''
		Purpose
			create a parser that parses input_string.
		Precondition
			input_string is a string.
		'''
		self.lexical_analyzer = Lexical_analyzer(input_string)
		self.token = None
		self.tag_rule_list = []

	def get_token(self):
		'''
		Purpose
			get the next token in input_string and save it in
			 self.token.
		'''
		self.token = self.lexical_analyzer.next()

	def accept(self,token_type):
		'''
		Purpose
			if self.token has type equal to token_type then return
			 True and get the next token.
			otherwise, return False.
		Precondition
			token_type is a string.
		'''
		if self.token[1] == token_type:
			self.get_token()
			return True
		return False

	def expect(self,token_type):
		'''
		Purpose
			exit the program if self.token does not have type equal
			 to token_type.
		Precondition
			token_type is a string.
		'''
		if not self.accept(token_type):
			self.error(self.token[1],token_type,self.token[2])

	def error(self,actual_token_type,expected_token_type,line_number):
		'''
		Purpose
			print to stderr that the token at line_number should
			 have type expected_token_type but instead token of
			 type actual_token_type is found.
			exit the program after the error message is printed.
		Precondition
			actual_token_type is a string.
			expected_token_type is a string.
			line_number is a non-negative integer.
		'''
		print >> sys.stderr,'found ' + actual_token_type + \
		 ' token at line ' + str(line_number) + '; expect ' + \
		 expected_token_type + ' token.'
		sys.exit(1)

	def grammar(self):
		'''
		Purpose
			parse the grammar rule.
		'''
		self.get_token()

		while self.token[1] not in ['EOF','None']:
			if self.token[1] == 'TAG_NAME':
				self.tag()
			elif self.token[1] == 'VARIABLE':
				self.rule()
			else:
				self.error(self.token[1],\
				 'TAG_NAME or VARIABLE',self.token[2])

	def tag(self):
		'''
		Purpose
			parse the tag rule.
		'''
		tag_name = self.token[0]
		self.expect('TAG_NAME')

		tag_param = self.token[0]
		self.expect('TAG_PARAM')

		self.tag_rule_list.append( ['tag',tag_name,tag_param] )

	def rule(self):
		'''
		Purpose
			parse the rule rule.
		'''
		rule_lhs = self.token[0]
		self.expect('VARIABLE')

		self.expect('TAKES')

		rule_rhs = []
		while self.token[1] in ['VARIABLE','REPEAT','TERMINAL',\
		 'TERMINAL_GENERATOR_START']:
			if self.token[1] == 'TERMINAL_GENERATOR_START':
				name = self.token[0]
				self.get_token()

				rule_rhs.append( (\
				 self.terminal_generator(name),
				 'TERMINAL_GENERATOR') )
			elif self.token[1] == 'REPEAT':
				if len(rule_rhs) > 0 \
				 and rule_rhs[-1][1] == 'VARIABLE':
					repeat = int(self.token[0])-1
					rule_rhs.extend([rule_rhs[-1]]*repeat)
					self.term()
				else:
					self.error(self.token[1],\
					 'VARIABLE or TERMINAL',self.token[2])
			else:
				rule_rhs.append( (self.token[0],self.token[1]) )
				self.term()

		self.expect('SEMI_COLON')

		self.tag_rule_list.append( ['rule',rule_lhs,rule_rhs] )

	def term(self):
		'''
		Purpose
			parse the term rule.
		'''
		if self.accept('VARIABLE'):
			pass
		elif self.accept('REPEAT'):
			pass
		elif self.accept('TERMINAL'):
			pass
		else:
			self.error(self.token[1],\
			 'VARIABLE or TERMINAL',self.token[2])

	def terminal_generator(self,name):
		'''
		Purpose
			parse the terminal generator rule.
		'''
		parameters = []
		while self.token[1] in ['STRING','INTEGER','FLOAT']:
			if self.token[1] == 'STRING':
				parameters.append( self.token[0] )
			elif self.token[1] == 'INTEGER':
				parameters.append( int(self.token[0]) )
			elif self.token[1] == 'FLOAT':
				parameters.append( float(self.token[0]) )

			self.get_token()

		self.expect('TERMINAL_GENERATOR_END')

		return [name,parameters]

class Code_generator:

	def __init__(self,tag_rule_list):
		'''
		Purpose
			create a code generator for producing an API version
			 of the grammar, as defined by tag_rule_list.
		Precondition
			tag_rule_list is a list containing tags and rules.
		Example
			tag_rules_list = [
				['tag','count','2'],
				['rule','Zeros',
				 [('0','TERMINAL'),('Zeros','VARIABLE')]],
				['rule','Zeros',[('0','TERMINAL')]]
				['rule','Zeros',[(
				 ['List',['a','b','c']],
				 'TERMINAL_GENERATOR')]]
			]
		'''
		self.tag_rule_list = tag_rule_list
		self.precodes = {}
		self.postcodes = {}

	def generate_global_precode(self):
		'''
		Purpose
			generate code for global_precode tag.
		'''
		global_precode = ''
		for e in self.tag_rule_list:
			if e[0] == 'tag':
				if e[1] == 'global_precode':
					global_precode = e[2]
		return global_precode

	def generate_global_postcode(self):
		'''
		Purpose
			generate code for global_postcode tag.
		'''
		global_postcode = ''
		for e in self.tag_rule_list:
			if e[0] == 'tag':
				if e[1] == 'global_postcode':
					global_postcode = e[2]
		return global_postcode

	def generate_precodes(self):
		'''
		Purpose
			generate code for precode tags.
		'''
		generated_rules = []
		precode = ''
		code = ''
		for e in self.tag_rule_list:
			if e[0] == 'tag':
				if e[1] == 'precode':
					precode = e[2]
			elif e[0] == 'rule':
				if len(precode) != 0:
					rule_id = e[1] + \
					 str(generated_rules.count(e[1]))
					code += 'def ' + rule_id + \
					 '_precode():' + precode + '\n'
					self.precodes[rule_id] = \
					 rule_id + '_precode'

				generated_rules.append(e[1])
				precode = ''
		return code

	def generate_postcodes(self):
		'''
		Purpose
			generate code for postcode tags.
		'''
		generated_rules = []
		postcode = ''
		code = ''
		for e in self.tag_rule_list:
			if e[0] == 'tag':
				if e[1] == 'postcode':
					postcode = e[2]
			elif e[0] == 'rule':
				if len(postcode) != 0:
					rule_id = e[1] + \
					 str(generated_rules.count(e[1]))
					code += 'def ' + rule_id + \
					 '_postcode(s):' + postcode + '\n'
					self.postcodes[rule_id] = \
					 rule_id + '_postcode'

				generated_rules.append(e[1])
				postcode = ''
		return code

	def generate_rules(self):
		'''
		Purpose
			generate code for instantiating rules.
		'''
		generated_rules = []
		tags = ''
		code = ''
		for e in self.tag_rule_list:
			if e[0] == 'tag':
				if e[1] == 'rdepth':
					tags += "'rdepth':" + e[2] + ','
				elif e[1] == 'depth':
					tags += "'depth':" + e[2] + ','
				elif e[1] == 'count':
					tags += "'count':" + e[2] + ','
				elif e[1] == 'cov':
					tags += "'cov':" + e[2] + ','
				elif e[1] == 'global_precode':
					pass
				elif e[1] == 'global_postcode':
					pass
				elif e[1] == 'precode':
					pass
				elif e[1] == 'postcode':
					pass
				else:
					print >> sys.stderr,e[1] + \
					 ' tag is not supported.'
			elif e[0] == 'rule':
				rule_id = e[1] + \
				 str(generated_rules.count(e[1]))

				# add precode to rule
				if self.precodes.has_key(rule_id):
					tags += "'precode':" + \
					 self.precodes[rule_id] + ','

				# add postcode to rule
				if self.postcodes.has_key(rule_id):
					tags += "'postcode':" + \
					 self.postcodes[rule_id] + ','

				# add rule to grammar
				code += "G.append_rule( Rule( \\\n" 
				code += "\t{" + tags[:-1] + "}, \\\n"
				code += "\t'" + e[1] + "', ["
				for term in e[2]:
					if term[1] == 'VARIABLE':
						code += "V('" + \
						 term[0] + "'),"
					elif term[1] == 'TERMINAL':
						code += "T('" + \
						 term[0] + "'),"
					elif term[1] == 'TERMINAL_GENERATOR':
						code += term[0][0] + '(' + \
						 str(term[0][1]) + '),'
				code = code[:-1]
				code += "] ) \\\n"
				code += ")\n\n"

				generated_rules.append(e[1])
				tags = ''
		return code

	def generate(self,gentree_file):
		'''
		Purpose
			generate code for 1. running the grammar and 2.
			 writing the generation tree to gentree_file.
		Precondition
			gentree_file is the name of a file.
		'''
		code = '''
from youGen_NG import *

G = Grammar()
$global_precode
$precodes
$postcodes
$rules

G.set_gentree_file('$gentree_file')

if __name__ == '__main__':
	for s in generate_language(G,'$start_symbol'):
		print s

$global_postcode
'''
		# find start symbol
		start_symbol = ''
		for e in self.tag_rule_list:
			if e[0] == 'rule':
				start_symbol = e[1]
				break

		code = code.replace('$global_precode',\
		 self.generate_global_precode())
		code = code.replace('$global_postcode',\
		 self.generate_global_postcode())
		code = code.replace('$precodes',self.generate_precodes())
		code = code.replace('$postcodes',self.generate_postcodes())
		code = code.replace('$rules',self.generate_rules())
		code = code.replace('$gentree_file',gentree_file)
		code = code.replace('$start_symbol',start_symbol)
		return code

if __name__ == '__main__':
	# validate user inputs
	if len(sys.argv) != 2:
		print 'Usage: ./parser.py <grammar_file>'
		sys.exit(1)

	# parse text grammar
	f = open(sys.argv[1],'r')
	parser = Parser(f.read())
	f.close()
	parser.grammar()

	# find the name of the grammar
	grammar_name = 'h'
	match = re.match('(.*)\.gr$',sys.argv[1])
	if match:
		grammar_name = match.group(1)

	# generate code for the text grammar and write it to grammar_name.py
	code_generator = Code_generator(parser.tag_rule_list)
	f = open(grammar_name+'.py','w')
	f.write( code_generator.generate(grammar_name+'.xml') )
	f.close()
