#!/usr/bin/python
#samostalni projekt iz automata , broj 47 created by Melita Mihaljevic
#implementiraj na racunalu program koji za zadanu konekstno neovisnu gramatiku gradi odgovarajuci PA (L(m)= L(G)) prema
#algoritmu danom na predavanjima (u knjizi)

import sys
import string
import pygtk

#########################TESTIRANE KLASE#########################

class zavrsni_znakovi :
        lista= []
        lista_zavrsnih=[]
	Y=[]
	novi_nezavrsni=[]
	pomocni=[]
        def __init__(self):
                """zavrsni znakovi"""

        def dodaj_string(self,niz):
                self.niz= niz
                for znak in self.niz:
                        if znak.islower() and znak not in self.lista_zavrsnih:
                                self.lista_zavrsnih.append(znak)
                        else:
                                pass

                return self.lista_zavrsnih

        def dodaj_sign (self, znak):
                self.lista = self.lista_zavrsnih
                if znak.islower():
                        self.lista.append(znak)
                else:
                        pass
                return self.lista

        def check_sign (self, znak):
                x= False
                if znak in self.lista_zavrsnih:
                        x= True
                else:
                        pass
                return x
	
        def check_zavrsne(self, niz):
                x= False
                for znak in niz:
                        if znak in self.lista_zavrsnih :
                                x= True
                        elif znak == '$':
                                x= True
                                break
                        else:
                                x= False
                                break
                return x
	def ispisi (self):
		return self.lista_zavrsnih

class nezavrsni_znakovi:
        lista= []
        lista_nezavrsnih= []
        def __init__(self):
                """nezavrsni znakovi"""

        def dodaj_string (self, niz):
                self.niz= niz
                for znak in self.niz:
                        if znak.isupper():
				if znak not in self.lista_nezavrsnih:
                                	self.lista_nezavrsnih.append(znak)
                        else:
                                pass
                return self.lista_nezavrsnih

        def dodaj_sign (self,znak):
                self.lista= self.lista_nezavrsnih
                if znak.isupper() and znak not in self.lista:
                        self.lista.append(znak)
                else:
                        pass
                return self.lista

        def check_sign(self,znak):
                x= False
                if znak in self.lista_nezavrsnih:
                        x= True
                else:
                        pass
                return x
	def ispisi(self):
		return self.lista_nezavrsnih

class produkcije(nezavrsni_znakovi):
	produkcije= {}
        def __init__(self):
                """klasa koja definira operacije nad produkcijema"""

        def dodaj_produkciju (self,nezavrsni,desna_strana_produkcije):
		nezavrsan= nezavrsni_znakovi()
   		if nezavrsni not in self.produkcije.keys():
	           	self.produkcije[nezavrsni]=[]
        	else:
			pass
	        self.produkcije[nezavrsni].append(desna_strana_produkcije)
		nezavrsan.dodaj_sign(nezavrsni)
			
		return self.produkcije
		
        def obrisi_produkciju (self, nezavrsni):
                del self.produkcije[nezavrsni]
		return self.produkcije

        def obrisi_desnu_stranu (self, nezavrsni, desna_strana):
		if nezavrsni in self.produkcije.keys():
			if desna_strana in self.produkcije[nezavrsni]:
                		self.produkcije[nezavrsni].remove(desna_strana)
		return self.produkcije

        def ispisi(self):
                return self.produkcije

class izraz (produkcije, nezavrsni_znakovi, zavrsni_znakovi):
        def __init__(self):
                """radi s ucitanim izrazima i pretvara ih u produkcije"""

        def dodaj_u_produkciju (self,string):
		nZnakovi= nezavrsni_znakovi()
		zZnakovi = zavrsni_znakovi()
		instance= produkcije()
                self.nezavrsni= string[0]
                self.desnaStrana= string[3:] # ovo jos provjeriti od kud ide
                nZnakovi.dodaj_sign(self.nezavrsni)
                instance.dodaj_produkciju(self.nezavrsni,self.desnaStrana)
		zZnakovi.dodaj_string(self.desnaStrana)
		return self.produkcije


class zivi_znakovi (nezavrsni_znakovi,zavrsni_znakovi,produkcije) :

      	lista_zivih = []

        def __init__(self):
                """zivi znakovi"""

        def dodaj_ziv(self, znak):
                if znak not in self.lista_zivih:
                        self.lista_zivih.append(znak)
                else:
                        pass
		return self.lista_zivih
        def is_ziv(self,znak):
                x= False
                if znak in self.lista_zivih:
                        x= True
                else:
                        pass
                return x;

        def provjeri_listu(self):
                return self.lista_zivih

	def izbaci_mrtve_znakove(self):
		zavrsni = zavrsni_znakovi()
		instance = zivi_znakovi()
		prod = produkcije()
		nezavrsni = nezavrsni_znakovi()
		self.nova_lista_zivih =[]
		self.nova_lista_zivih=instance.provjeri_listu()
		self.stara_lista_zivih = []
		self.lista_samozavrsni= []
		for nezavrsni_znak in self.produkcije.keys():
			print nezavrsni_znak
			for self.desna_strana in self.produkcije[nezavrsni_znak]:
					print self.desna_strana
					for znak in self.desna_strana:
						print znak
						x= zavrsni.check_sign(znak)
						print x
						if not zavrsni.check_sign(znak):
							x=0
						else:
							x =1
			if x ==1:
				if nezavrsni not in self.lista_samozavrsni:
					self.lista_samozavrsni.append(nezavrsni_znak)

		print self.lista_samozavrsni
		self.temp1=[]
		self.temp1= zavrsni.ispisi()
		self.lista_samozavrsni= self.lista_samozavrsni + self.temp1
		print self.lista_samozavrsni
		while self.lista_samozavrsni <> self.nova_lista_zivih:
			self.nova_lista_zivih = self.lista_samozavrsni
			for nezavrsni_znak in self.produkcije.keys():
				for self.desna_strana in self.produkcije[nezavrsni_znak]:
					for znak in self.desna_strana:
					
					
						
						if x != 'greska':
							if nezavrsni_znak not in self.lista_samozavrsni:
								self.lista_samozavrsni.append(nezavrsni_znak)
								print self.lista_samozavrsni

		

		for nezavrsni_znak in self.produkcije.keys():
			if nezavrsni_znak not in self.lista_samozavrsni:
				prod.obrisi_produkciju(nezavrsni_znak)
		
		for nezavrsni_znak in self.produkcije.keys():
			for self.desna_strana in self.produkcije[nezavrsni_znak]:
				for znak in self.desna_strana:
					if znak not in self.lista_samozavrsni:
						prod.obrisi_desnu_stranu(nezavrsni_znak,self.desna_strana)
		return self.produkcije
				 
class dohvatljivi_znakovi( produkcije, nezavrsni_znakovi, zavrsni_znakovi):

        lista_dohvatljivih = []

        def __init__(self):
                """ dohvatljivi znakovi"""

        def dodaj_dohvatljivi(self, znak):
                if znak not in self.lista_dohvatljivih:
                        self.lista_dohvatljivih.append(znak)
                else:
                        pass
		return self.lista_dohvatljivih

        def is_dohvatljiv (self, znak):
                self.x= True
                if znak not in self.lista_dohvatljivih:
                        self.x = False
                else:
                        pass
                return self.x
        
	def provjeri_listu(self):
                return self.lista_dohvatljivih

	def izbaci_nedohvatljive_znakove(self):
		instance= dohvatljivi_znakovi()
		prod = produkcije()
		zav= zavrsni_znakovi()
		nezav = nezavrsni_znakovi()
		self.lista_samoS=[]
		self.lista_temp=[]
		self.lista_samoS.append('S')
		for self.desna_strana in self.produkcije['S']:
			for znak in self.desna_strana:
				if znak not in self.lista_samoS:
					self.lista_samoS.append(znak)
		print self.lista_samoS
		
		while self.lista_samoS <> self.lista_temp:
			self.lista_temp= self.lista_samoS
			for znak in self.lista_samoS:
				if nezav.check_sign(znak):
					for self.desna_strana in self.produkcije[znak]:
						for temp2 in self.desna_strana:
							if temp2 not in self.lista_samoS:
								self.lista_samoS.append(temp2)
		
		print self.lista_samoS
		
		for nezav in self.produkcije.keys():
			if nezav not in self.lista_samoS:
				prod.obrisi_produkciju(nezav)
		
		return self.produkcije
							 	
class epsilon_produkcije(produkcije):
        def __init__(self):
                """epslon produkcije"""

        def is_epsilon (self, nezavrsni):
                self.x= False
                if '$' in self.produkcije[nezavrsni]:
                        self.x= True
                else:
                        pass
                return self.x
	def rijesi_epsilon(self, znak):
                instance = produkcije()
                self.brojac = 0
                self.indeks= []
                self.polje= []
                for nezavrsni in self.produkcije.keys():
                        for self.desna_strana in self.produkcije[nezavrsni]:
                                for i in range (len(self.desna_strana)):
                                        if znak == self.desna_strana[i]:
                                                self.indeks = str(i)
                                                self.polje.append(self.indeks)
                                                for x in self.polje:
                                                        self.temp1= self.desna_strana[:int(x)]
                                                        self.temp2= self.desna_strana[int(x)+1:]
                                                        self.niz = self.temp1+ self.temp2
                                                        if self.niz not in self.produkcije[nezavrsni]:
                                                                instance.dodaj_produkciju(nezavrsni, self.niz)
                                                del self.polje[:]
		return self.produkcije

	def izbaci_epsilon(self):
		eps= epsilon_produkcije()
		instance = produkcije()
	        for znak in self.produkcije.keys():
        	        	if eps.is_epsilon(znak):
                       			 eps.rijesi_epsilon(znak)
                else:
                        pass
		for nezavrsni in self.produkcije.keys():
                	if eps.is_epsilon(nezavrsni):
                                instance.obrisi_desnu_stranu(nezavrsni,'$')

		return self.produkcije
	
class jedinicne_produkcije(nezavrsni_znakovi,produkcije):
        def __init__(self):
                """jedinicne produkcije"""

        def is_jedinicna(self,nezavrsni):
                x= False
                if nezavrsniZnak in self.produkcije[nezavrsni] and length(self.produkcije[nezavrsni]) ==1:
                        x= True
                else:
                        pass
                return x

	def izbaci_jedinicne(self):
		nezavrsni= nezavrsni_znakovi()
		instance = produkcije()
        	for nezavrsni_znak in self.produkcije.keys():
                	for self.desna_strana in self.produkcije[nezavrsni_znak]:
                        	if (len(self.desna_strana))==1:
					self.x = self.desna_strana[0]
					if nezavrsni.check_sign(self.x):	
						self.temp = self.produkcije[self.desna_strana]
						for self.niz in self.temp:
                                        		instance.dodaj_produkciju(nezavrsni_znak, self.niz)
						instance.obrisi_desnu_stranu(nezavrsni_znak, self.desna_strana)	
                        	else:
                                	pass
		return self.produkcije

############################################G R E I B A C H #################################################################

class greibachov_oblik(zavrsni_znakovi, nezavrsni_znakovi,produkcije):
	nezav= nezavrsni_znakovi()
	prod= produkcije()
	zav= zavrsni_znakovi()	
	prod_greibach= {}
	prod_za_PA={}
	X=[]
	def __init__(self):
		"""greibachov oblik produkcija"""
	def krajnje_lijevi(self):
		for nezavrsni in self.produkcije.keys():
			for self.desna_strana in self.produkcije[nezavrsni]:
				temp = self.desna_strana[0]
				self.desna_strana= self.desna_strana[1:]
				if self.nezav.check_sign(temp):
					for nezavrsni_znak in self.produkcije.keys():
						if temp == nezavrsni_znak:
							for ds in self.produkcije[nezavrsni_znak]:
								nova  = ds + self.desna_strana
								self.prod.dodaj_produkciju(nezavrsni, nova)
	
		for nezavrsni in self.produkcije.keys():
			for self.desna_strana in self.produkcije[nezavrsni]:
				temp = self.desna_strana[0]
				if self.nezav.check_sign(temp):
					self.prod.obrisi_desnu_stranu(nezavrsni, self.desna_strana)
		return self.produkcije 					
							 
	def u_greibacha(self):
		for nezavrsni in self.produkcije.keys():
			for self.desna_strana in self.produkcije[nezavrsni]:
				temp = self.desna_strana[1:]
				for znak in temp:
					if self.zav.check_sign(znak) and znak not in self.X:
						self.X.append(znak)
		
		self.temp=''
		for nezavrsni in self.produkcije.keys():
			for self.desna_strana in self.produkcije[nezavrsni]:
				temp1= self.desna_strana[0]
				temp2 = self.desna_strana[1:]
				if temp2== '':
					self.temp =''
				else:
					for m in temp2:
						print m
						if self.zav.check_sign(m):
							X= 'X'+ str(self.X.index(m))
						else:
							X=m
							print X
						self.temp= self.temp +X
						print self.temp
				temp4= temp1+self.temp
				if nezavrsni not in self.prod_greibach.keys():
					self.prod_greibach[nezavrsni]=[]
				self.prod_greibach[nezavrsni].append(temp4)
				if nezavrsni not in self.prod_za_PA.keys():
					self.prod_za_PA[nezavrsni]=[]
				self.prod_za_PA[nezavrsni].append(self.desna_strana)
				
				self.temp=''
					
		for znak in self.X:
			temp = 'X' + str(self.X.index(znak))
			self.prod_greibach[temp]=[]
			self.prod_greibach[temp].append(znak)	
		for znak in self.X:
			self.prod_za_PA[znak]=[]
			self.prod_za_PA[znak].append(znak)
		print self.prod_za_PA
		return self.prod_greibach

# skup ulaznih znakova je skup zavrsnih znakova
#skup znakova stoga = skup nezavrsnih znakova, 
#pocetno na stogu je 'S',poceno i jedino stanje je q, pa prihvaca praznim stogom			

	
class skup_ulaznih(greibachov_oblik, zavrsni_znakovi):
	zav= zavrsni_znakovi()
	lista_ulaznih=[]
	gr= greibachov_oblik()
	def __init__(self):
		"""skup ulaznih znakova PA"""
	
	def listu_ulaznih(self):
		for nezavrsni in self.gr.prod_za_PA.keys():
			for self.desna_strana in self.gr.prod_za_PA[nezavrsni]:
				for znak in self.desna_strana:
					if self.zav.check_sign(znak) and znak not in self.lista_ulaznih:
						self.lista_ulaznih.append(znak)
		return self.lista_ulaznih
	def check_znak(self, znak):
		x= False
		if znak in self.lista_ulaznih:
			x= True
		else:
			pass
		return x
	def ispisi(self):
		return self.lista_ulaznih
class stog(greibachov_oblik):
	stogs=['S']
	gr=greibachov_oblik()

	def __init__(self):
		"""opisuje stog kao dio definicije PA"""	
	
	def listu_stog(self):
		self.lista_stog=[]
		for nezavrsni in self.gr.prod_za_PA.keys():
			if nezavrsni not in self.lista_stog:
				self.lista_stog.append(nezavrsni)
		
	def ispisi(self):
		return self.lista_stog
	
	def ispisi_stog(self):
		return self.stog

	def skini(self):
		self.stog.pop()
	
class radniStog(stog,greibachov_oblik):
	radni_stog=[]
	ispis=[]
	radni_stog.append('S')
	ispis.append('S')
	lista_stog=[]
	def __init__(self):
		"""radni stog kojeg ne vidi korisnik"""

	def listu_stoga(self):
		self.lista_radniStog=[]
                for nezavrsni in self.prod_za_PA.keys():
			if nezavrsni not in self.lista_stog:
                        	self.lista_stog.append(nezavrsni)
			
	def check_znak(self,znak):
	       	x= False
               	if znak in self.lista_stog:
               		x= True
                else:
                       	pass
               	return x

	def dodaj_naStog(self,niz):
                instance = radniStog()
		self.pomocni= []
    	 	for znak in niz:
     	                if instance.check_znak(znak):
	               		self.pomocni.append(znak)
                       	else:
              	                print'znak nije u skupu ulaznih znakova'
       	                        break
                self.pomocni.reverse()
		for znak in self.pomocni:
                     	self.radni_stog.append(znak)
               	del self.pomocni[:]			
		for znak in self.radni_stog:
			if znak in self.X:
				temp = 'X' + str (self.X.index(znak) +1)
			else:
				temp= znak
			self.ispis.append(temp)
			return self.ispis	
		
	def ispisi_radni(self):
		return self.radni_stog	

	def skini(self):
              	self.radni_stog.pop()
		self.ispis.pop()
		return self.radni_stog

       	def akcija_stog(self, akcija):
             	instance= radniStog()
               	self.radni_stog= instance.skini()
               	if akcija  == '$':
                   	pass
              	else:
              		self.radni_stog= instance.dodaj_naStog(akcija)

   	def trenutno_stog(self):
           	trenutno = self.radni_stog.pop()
		self.radni_stog.append(trenutno)
            	return trenutno
			
		

	
class prijelazi_PA(greibachov_oblik):
	prijelaz_PA={}
				
	def __init__(self):
		"""prijelazi potisnog automata-radni"""
	
	def generiraj_prijelaze(self):
		for nezavrsni in self.prod_za_PA.keys():
			for niz in self.prod_za_PA[nezavrsni]:
				self.znak= niz[0]
				self.akcija_stog = niz[1:]
				if self.akcija_stog=='':
					self.akcija_stog = '$'
				self.trenutnoStog= nezavrsni
				if (self.znak,self.trenutnoStog) not in self.prijelaz_PA.keys():
					self.prijelaz_PA[self.znak, self.trenutnoStog]=[]
				self.prijelaz_PA[self.znak, self.trenutnoStog].append(self.akcija_stog)

		return self.prijelaz_PA

	def funkcija_prijelaza(self):
		print' FUNKCIJA PRIJELAZA PA'
		for nezavrsni in self.prod_greibach.keys():
                      	for niz in self.prod_greibach[nezavrsni]:
                            	self.znak= niz[0]
                               	self.akcija_stog = niz[1:]
                             	if self.akcija_stog=='':
                                     	self.akcija_stog = '$'
                              	self.trenutnoStog= nezavrsni
				print '&(q,',self.znak,',',self.trenutnoStog,')= ', self.akcija_stog

class simulacija_PA(skup_ulaznih,radniStog,prijelazi_PA):
	ulazni= skup_ulaznih()
	radni = radniStog()
	provjeri_stog=[]
	rzn=[]
	rzs=[]
	rza=[]
		
	def __init__(self):
		"""DPA i NPA"""

	def DPA_simulacija(self,niz):
		instance=simulacija_PA()
		self.lista=[]
		self.rezervna_akcija=[]
		self.novi_niz= niz
		m=[]
		self.novaakcija=''
		for znak in self.novi_niz:
			print znak
			self.trenutno_stog=self.radni.trenutno_stog()
			self.niz= self.trenutno_stog[0]
			print self.niz
			m= self.ulazni.ispisi()
			print m
			print self.radni_stog
			print len(self.radni_stog)
			if self.ulazni.check_znak(znak):
				if (znak, self.niz) in self.prijelaz_PA.keys():
					print 'ulazi'
					if self.novaakcija =='':
						self.lista = self.prijelaz_PA[znak,self.niz]
						if (len(self.lista))>1:
							self.novaakcija = self.lista[0]
							self.rezervna_akcija = self.lista[1:]
							self.rezervni_niz = self.novi_niz
							self.rezervni_stog = self.radni_stog	
						else:
							self.novaakcija= self.lista[0]
						self.rzn.append(self.rezervni_niz)
						self.rzs.append(self.rezervni_stog)
						self.rza.append(self.rezervna_akcija)
					self.radni.akcija_stog(self.novaakcija)
					self.novaakcija=''
				else:
					print'PRIJELAZ NIJE DOZVOLJEN'
					break

				self.provjeri_stog=self.radni_stog
				del self.radni_stog[:]
				self.radni_stog.append('S')
		print 'provjeravam stog',self.provjeri_stog			
		if self.provjeri_stog == []:
			print 'NIZ SE PRIHVACA'
			return
		else:
			print'DPA SE NE PRIHVACA'
			x = instance.NPA_simulacija()
	
	def NPA_simulacija(self):
		instance= simulacija_PA()
		if len(self.rzn)==0:
			print 'NIZ SE NE PRIHVACA'
			return
		else:
			self.niz = self.rzn.pop()
			self.radni_stog = self.rzs.pop()
			self.novaakcija = self.rza.pop()
				
		instance.DPA_simulacija(self.niz)					
							
			

p= produkcije()
iz = izraz()
gr= greibachov_oblik()

zivi = zivi_znakovi()
prod  = {}
av= zavrsni_znakovi()

x= ['S->abcA','S->a','S->mnoBA','A->melita','A->mB','B->CD','C->mnD','D->nmo']
for niz in x:
	prod = iz.dodaj_u_produkciju(niz)  

prod = zivi.izbaci_mrtve_znakove()
print prod
m= av.ispisi()
print m
dih = dohvatljivi_znakovi()
prod=dih.izbaci_nedohvatljive_znakove()
print prod
prod = gr.krajnje_lijevi()
print prod
prod= gr.u_greibacha()
print prod
prijelaz= prijelazi_PA()
prij={}
prij= prijelaz.generiraj_prijelaze()
print'PRIJELAZ', prij
prijelaz.funkcija_prijelaza()
sim= simulacija_PA()
niz1= 'abc'
niz2= 'a'
ulazni= skup_ulaznih()
stog= radniStog()
ulazni.listu_ulaznih()
stog.listu_stoga()
temp1= sim.DPA_simulacija(niz1)
temp2= sim.DPA_simulacija(niz2)
print 'niz a', temp2
print 'niz ancde',temp1