Transducers.py

"""
* Transducers
0 epsilon
? any
.#. beginning or end of string
%x, "x" character x
"\n", "\t"
(A) optionality
[] empty string
?* universal
A - B complement
A .x. B cross product
A .o. B composition

** new operators
$A = [?* A ?*] # containment
A => B _ C     # context restriction
  = [ ~[ [~[?* B] A ?*] | [?* A  ~[C ?*]] ]]
A -> B   [ [ ~$[A - []] [A .x. B]]*  ~$[A - []]]	# replacement
"""

from  FSA import *
from types import TupleType

class TransducerLabel:
	def __init__(self, upper, lower):
		self.upper = upper
		self.lower = lower
	
	def complement(self):
		if self.upper and self.lower:
			return [TransducerLabel(labelComplement(self.upper, None), ANY), TransducerLabel(ANY, labelComplement(self.lower, None))]
		elif self.upper:
			return TransducerLabel(labelComplement(self.upper), self.lower)
		else:
			return TransducerLabel(self.upper, labelComplement(self.lower))
	
	def __repr__(self):
		return (self.upper and str(self.upper) or '0') + ':' + (self.lower and str(self.lower) or '0')

def compose(a, b):
	states0, alpha0, transitions0, start0, finals0 = a.tuple()
	states1, alpha1, transitions1, start1, finals1 = b.tuple()
	states, index = [(start0, start1)], 0
	transitions = []
	while index < len(states):
		state, index = states[index], index + 1
		upperSource, lowerSource = state
		for _, upperTarget, upperLabel in a.transitionsFrom(upperSource):
			if labelLower(upperLabel) is None:
				target = (upperTarget, lowerSource)
				if target not in states:
					states.append(target)
				transitions.append((state, target, upperLabel))
			else:
				for _, lowerTarget, lowerLabel in b.transitionsFrom(lowerSource):
					if labelLower(upperLabel) == labelUpper(lowerLabel):
						target = (upperTarget, lowerTarget)
						if target not in states:
							states.append(target)
						transitions.append((state, target, makeLabel(labelUpper(upperLabel), labelLower(lowerLabel))))
	for _, lowerTarget, lowerLabel in b.transitionsFrom(lowerSource):
		if labelUpper(lowerLabel) is None:
			target = (upperSource, lowerTarget)
			if target not in states:
				states.append(target)
			transitions.append((state, target, lowerLabel))
	finals = filter(lambda (s0, s1), f0=finals0, f1=finals1: s0 in f0 and s1 in f1, states)
	return a.create(states, None, transitions, states[0], finals).sorted()

def labelUpper(label):
	return getattr(label, 'upper', label)
	if type(label) is TupleType:
		return label[0]
	else:
		return label

def labelLower(label):
	return getattr(label, 'lower', label)
	if type(label) is TupleType:
		return label[1]
	else:
		return label

def makeLabel(upper, lower):
	if upper == lower:
		return upper
	return TransducerLabel(upper, lower)
	if upper == lower:
		return upper
	else:
		return (upper, lower)

"""
from FSA import *
print compose(compileRE('ab'), compileRE('ab')).trimmed()
print compose(compileRE('ab'), compileRE('a')).trimmed()
"""

from REUtils import SymbolRECompiler

class TransducerCompiler(SymbolRECompiler):
	def readCH(self):
		c = self.readChar()
		if c == '0':
			return None
		elif c == '?':
			return ANY
		elif c == '%':
			return self.readChar()
		elif c == '"':
			c = self.readChar()
			if c == '\\':
				c = self.readChar()
				c = {'r': '\r', 'n': '\n', 't': '\t'}.get(c, c)
			if self.readChar() != '"':
				raise '\'"\' expected'
		else:
			return c
	
	def _readNextToken(self):
		c = self.readCH()
		if self.peekChar() == ':':
			return makeLabel(c, self.readCH())
		else:
			return c

def compileTransducer(str):
	return TransducerCompiler(str).toFSA()

"""
print compileTransducer('ab:cd')
print compileTransducer('ab:0d')
"""