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

#############################################
## Trabalho de Linguagens Formais - MATA50 ##
## Professora Lais Salvador - 2009.1       ##
## Kessia Pinheiro - kessia@dcc.ufba.br    ##
## Parte 01 - Análise sintática de regex   ##
## Para executar: python main.py           ##
## Na execucao sao mostradas as instrucoes ##
#############################################

import sys

class ParserOp:
	def __init__(self):
		"""
		Definition of symbols accepted
		"""
		self.alpha 	= ['a','b','c','d','e',
					   'f','g','h','i','j',
					   'k','l','m','n','o',
					   'p','q','r','s','t',
					   'u','v','w','x','y','z']
		self.num	= ['0','1','2','3','4',
					   '5','6','7','8','9']
		self.symbol = ['(',')', #delimiter
					   '|', #choice between alternatives
					   '*', #zero or more
					   '?', #zero or one
					   '+'] #one or more
		self.alphanum = self.alpha + self.num

	def verifysymbol(self, alpha=[], regex=[]):
		stack = 0
		for pos, char in enumerate(regex):
			if char in alpha and char in self.alphanum:
				continue
				#print char, " pertence ", alpha
			elif char in self.symbol:
				#Parsing parenthesis
				#Need check if each parenthesis are closed
				#print char, " eh um simbolo"
				if char == '(' and regex[pos+1] != ')':
					stack += 1
				elif char == ')':
					if stack >= 0:
						stack -= 1
				#Parsing asterisc or plus
				#Each multipicator are permited only after a char or a right closed expression
				elif char == '*' or char == '+' or char == '?':
					symbols_permited = [')', '(']
					if regex[pos-1] in self.alphanum or regex[pos-1] in symbols_permited[0]:
						continue
					elif regex[pos-1] in self.alphanum and regex[pos+1] in symbols_permited[1]:
						continue
					else:
						#print char, " nao permitido"
						return False
				#Parsing pipe
				#Pipe are permited if predecessor are a closed parenthesis, char or multiplicator
				#and predecessor are a parenthesis or char
				elif char == '|':
					parenthesis = [')', '(']
					symbols_permited = ['*', '+', '?']
					if regex[pos-1] in self.alphanum and regex[pos+1] in self.alphanum:
						continue
					elif regex[pos-1] in parenthesis[0] and regex[pos+1] in parenthesis[1]:
						continue
					elif regex[pos-1] in self.alphanum and regex[pos+1] in parenthesis[1]:
						continue
					elif regex[pos-1] in parenthesis[0] and regex[pos+1] in self.alphanum:
						continue
					elif regex[pos-1] in symbols_permited and regex[pos+1] in self.alphanum:
						continue
					elif regex[pos-1] in symbols_permited and regex[pos+1] in parenthesis[1]:
						continue
					else:
						#print char, " nao permitido"
						return False
			else:
				#print char, " nao pertence ", alpha
				return False
		if stack == 0:
			#print "parsing correto"
			return True
		else:
			#print "parsing errado"
			return False

class ProcessIn:
	def __init__ (self):
		self.inputlist = []

	def readInput(self, input=[]):
		try:
			input = input.readline().split()[0]
			for char in input:
				self.inputlist.append(char)
			return True
		except:
			return False

	def getInput(self):
		return self.inputlist

	def isEmpty(self):
		return (self.inputlist == [])

class Input:
	def __init__(self):
		"""
		Definition of symbols accepted
		"""
		self.alpha 	= ['a','b','c','d','e',
					   'f','g','h','i','j',
					   'k','l','m','n','o',
					   'p','q','r','s','t',
					   'u','v','w','x','y','z']
		self.num	= ['0','1','2','3','4',
					   '5','6','7','8','9']
		self.symbol = ['(',')', #delimiter
					   '|', #choice between alternatives
					   '*', #zero or more
					   '?', #zero or one
					   '+'] #one or more
		self.alphanum = self.alpha + self.num

	def receiveIn(self):
		self.alfabeto = ProcessIn()
		self.regex = ProcessIn()
		print "insira o alfabeto: "
		if self.alfabeto.readInput(sys.stdin):
			for char in self.alfabeto.getInput():
				if char in self.alphanum:
					continue
				else:
					print "alfabeto com simbolos nao permitidos"
					return True
			#print "alfabeto: ", self.alfabeto.getInput()
			print "insira a expressao regular: "
			if self.regex.readInput(sys.stdin):
				for char in self.regex.getInput():
					if char in self.alphanum or char in self.symbol:
						continue
					else:
						print "regex com simbolos nao permitidos"
						return True
			#print "regex: ", self.regex.getInput()
			return True
		else:
			print "alfabeto em branco"
			print "Saindo..."
			return False


if __name__ == "__main__":
	empty = '$' #cadeia vazia
	input = Input()
	print "----------------------------------"
	print "Trabalho de Linguages Formais e Automatos"
	print "Professora Lais Salvador - MATA50 - Semestre 2009.1"
	print "Aluna: Kessia Pinheiro - Matricula: 200522206"
	print "----------------------------------"
	print
	print "Instrucoes:"
	print
	print "O alfabeto deve ser uma string seguida e somente aceita caracteres de a-z e numeros"
	print "A expressao regular segue os seguintes operadores:"
	print "| - escolha entre duas alternativas"
	print "* - repeticao de zero ou mais vezes"
	print "? - repeticao de zero ou uma vez"
	print "+ - repeticao de uma ou mais vezes"
	print
	print "Exemplo de entrada correta:"
	print "alfabeto: abcdefghi"
	print "expressao regular: a*|b*ab*|c*ab*ab*|d*ab*eb*ab*a(g|b)*"
	print
	print "Para entrada a partir de arquivo use: python main.py < entrada.txt"
	print "O programa pede entradas ate que o alfabeto seja em branco"
	print "----------------------------------"
	print
	while input.receiveIn():
		process = ParserOp()
		if not input.alfabeto.isEmpty() and not input.regex.isEmpty():
			if process.verifysymbol(input.alfabeto.getInput(), input.regex.getInput()):
				print "------------------------------------------"
				print "alfabeto:", "{", ",".join(map(str, input.alfabeto.getInput())), "}"
				print "expressao regular:", "".join(input.regex.getInput())
				print '- expressao regular sintaticamente correta.'
				print "------------------------------------------"
			else:
				print "----------------------------"
				print '- expressao regular incorreta'
				print "----------------------------"