# -*- coding: utf-8 -*-
"""**In/Out.**
FAdo IO.
.. *Authors:* Rogério Reis & Nelma Moreira
.. *This is part of FAdo project* http://fado.dcc.fc.up.pt.
.. *Copyright:* 2014 Rogério Reis & Nelma Moreira {rvr,nam}@dcc.fc.up.pt
.. This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as published
by the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
675 Mass Ave, Cambridge, MA 02139, USA."""
import cStringIO
import common
from fa import DFA, NFA, statePP
from transducers import SFT, GFT, Transducer
from sst import PSPVanila, PSPEqual, PSPDiff, SSOneOf, SSAnyOf, SSNoneOf, SSEpsilon, SST, SSFA
from fl import ADFA
import lark
def readOneFromFile(fileName):
""" Read the first of the FAdo objects from File
:param fileName: name of the file
:type fileName: str
:rtype: DFA|FA|STF|SST"""
o = readFromFile(fileName)
if type(o) == list:
return o[0]
else:
return o
[docs]def readFromFile(FileName):
"""Reads list of finite automata definition from a file.
:param str FileName: file name
:rtype: list
The format of these files must be the as simple as possible:
.. hlist::
:columns: 1
* ``#`` begins a comment
* ``@DFA`` or ``@NFA`` begin a new automata (and determines its type) and must be followed by the list of the
final states separated by blanks
* fields are separated by a blank and transitions by a CR: ``state`` ``symbol`` ``new state``
* in case of a NFA declaration, the "symbol" @epsilon is interpreted as a epsilon-transition
* the source state of the first transition is the initial state
* in the case of a NFA, its declaration ``@NFA`` can, after the declaration of the final states,
have a ``*`` followed by the list of initial states
* both, NFA and DFA, may have a declaration of alphabet starting with a ``$`` followed by the symbols of the
alphabet
* a line with a sigle name, decrares a state
.. productionlist:: Fado Format
FAdo: FA | FA CR FAdo
FA: DFA | NFA | Transducer
DFA: "@DFA" LsStates Alphabet CR dTrans
NFA: "@NFA" LsStates Initials Alphabet CR nTrans
Transducer: "@Transducer" LsStates Initials Alphabet Output CR tTrans
Initials: "*" LsStates | \epsilon
Alphabet: "$" LsSymbols | \epsilon
Output: "$" LsSymbols | \epsilon
nSymbol: symbol | "@epsilon"
LsStates: stateid | stateid , LsStates
LsSymbols: symbol | symbol , LsSymbols
dTrans: stateid symbol stateid |
:| stateid symbol stateid CR dTrans
nTrans: stateid nSymbol stateid |
:| stateid nSymbol stateid CR nTrans
tTrans: stateid nSymbol nSymbol stateid |
:| stateid nSymbol nSymbol stateid CR nTrans
.. note::
If an error occur, either syntactic or because of a violation of the declared automata type,
an exception is raised
.. versionchanged:: 0.9.6
.. versionchanged:: 1.0"""
s = open(FileName, "r").read()
tree = FAdoGrammar.parse(s)
return BuildFadoObject().transform(tree)
def readOneFromString(s):
"""Reads one finite automata definition from a file.
.. seealso::
readFromFile for description of format
:param str s: the string
:rtype: DFA|NFA|SFT"""
tree = FAdoGrammar.parse(s)
return BuildFadoObject().transform(tree)
def alphabetPP(sigma):
ssig = "[ \"{0:>s}\"".format(str(sigma.pop()))
for sym in sigma:
ssig += ", \"{0:>s}\"".format(str(sym))
ssig += " ]"
return ssig
def toJson(aut):
"""
Json for a FA
:param aut:
:return:
"""
io = cStringIO.StringIO()
if isinstance(aut, DFA):
jtype = "DFA"
elif isinstance(aut, NFA):
jtype = "NFA"
elif isinstance(aut, Transducer):
jtype = "Transducer"
elif isinstance(aut, ADFA):
jtype = "ADFA"
io.write("{ \"automaton\": {\n\t\"title\": \"\", \n\t\"version\": \"\",\n")
# noinspection PyUnboundLocalVariable
io.write("\t\"type\": \"{0:>s}\",\n".format(jtype))
io.write("\t\"states\": [\n")
sn = 0
for s in xrange(len(aut.States)):
if sn == 0:
io.write("{ \n")
else:
io.write(",\n{ \n")
io.write("\t\t\"name\": \"{0:>s}\",\n".format(str(s)))
io.write("\t\t\"label\": \"{0:>s}\",\n".format(statePP(aut.States[s])))
io.write("\t\t\"output\": \"\",\n")
if aut.initialP(s):
io.write("\t\t\"initial\": true,\n")
else:
io.write("\t\t\"initial\":false,\n")
if aut.finalP(s):
io.write("\t\t\"final\": true\n")
else:
io.write("\t\t\"final\": false\n")
io.write("}")
sn += 1
io.write("], \n")
io.write("\t\"trans\": [\n")
trn = 0
for s in xrange(len(aut.States)):
if s in aut.delta:
for a in aut.delta[s].keys():
if isinstance(aut.delta[s][a], set):
for s1 in aut.delta[s][a]:
if trn == 0:
io.write("{ \n")
else:
io.write(",\n{ \n")
io.write("\t\t\"name\": \"{0:>s}\,\n".format(str(trn)))
io.write("\t\t\"orig_name\": \"{0:>s}\,\n".format(statePP(aut.States[s])))
io.write("\t\t\"dest_name\": \"{0:>s}\",\n".format(statePP(aut.States[s1])))
io.write("\t\t\"label\": \"{0:>s}\",\n".format(str(a))),
io.write("\t\t\"weight\": \"\"\n")
io.write("}")
trn += 1
else:
if trn == 0:
io.write("{ \n")
else:
io.write(",\n{ \n")
# io.write(", \n{ \n")
io.write("\t\t\"name\": \"{0:>s}\",\n".format(str(trn)))
io.write("\t\t\"orig_name\": \"{0:>s}\",\n".format(statePP(aut.States[s])))
io.write("\t\t\"dest_name\": \"{0:>s}\",\n".format(statePP(aut.States[aut.delta[s][a]])))
io.write("\t\t\"label\": \"{0:>s}\",\n".format(str(a))),
io.write("\t\t\"weight\": \"\"\n")
io.write("}")
trn += 1
io.write("],\n")
io.write("\t\"alphabet\": {0:>s} \n".format(alphabetPP(aut.Sigma)))
io.write(" } ")
return io.getvalue()
def saveToJson(FileName, aut, mode="w"):
""" Saves a finite automata definition to a file using the JSON format
"""
try:
f = open(FileName, mode)
except IOError:
raise common.DFAerror()
f.write(toJson(aut))
f.close()
def saveToString(fa):
""" Saves a finite automaton definition to a string
:param fa: automaton
:return: the string containing the automaton definition
:rtype: str
..versionadded:: 1.2.1"""
def _save_SFTransducer(tr, io):
io.write("@Transducer ")
for s in tr.Final:
io.write("{0:>s} ".format(statePP(tr.States[s])))
io.write("* ")
for s in tr.Initial:
io.write("{0:>s} ".format(statePP(fa.States[s])))
io.write("\n")
for sin in tr.delta:
for syin in tr.delta[sin]:
for (syout, sout) in tr.delta[sin][syin]:
io.write("{0:>s} {1:>s} {2:>s} {3:>s}\n".format(statePP(tr.States[sin]), str(syin), str(syout),
statePP(tr.States[sout])))
io.write("\n")
def _saveFA(aut, io):
if isinstance(aut, DFA):
io.write("@DFA ")
NFAp = False
elif isinstance(aut, NFA):
io.write("@NFA ")
NFAp = True
else:
raise common.DFAerror()
if not NFAp and aut.Initial != 0:
foo = {0: aut.Initial, aut.Initial: 0}
aut.reorder(foo)
for sf in aut.Final:
io.write("{0:>s} ".format(statePP(aut.States[sf])))
if NFAp:
io.write(" * ")
for sf in aut.Initial:
io.write("{0:>s} ".format(statePP(aut.States[sf])))
io.write("\n")
for s in xrange(len(aut.States)):
if s in aut.delta:
for a in aut.delta[s].keys():
if isinstance(aut.delta[s][a], set):
for s1 in aut.delta[s][a]:
io.write("{0:>s} {1:>s} {2:>}\n".format(statePP(aut.States[s]),
str(a), statePP(aut.States[s1])))
else:
io.write("{0:>s} {1:>s} {2:>s}\n".format(statePP(aut.States[s]), str(a),
statePP(aut.States[aut.delta[s][a]])))
else:
io.write("{0:>s} \n".format(statePP(aut.States[s])))
out = cStringIO.StringIO()
if isinstance(fa, Transducer):
_save_SFTransducer(fa, out)
return out.getvalue()
else:
_saveFA(fa, out)
return out.getvalue()
[docs]def saveToFile(FileName, fa, mode="a"):
""" Saves a list finite automata definition to a file using the input format
.. versionchanged:: 0.9.5
.. versionchanged:: 0.9.6
.. versionchanged:: 0.9.7 New format with quotes and alphabet
:param str FileName: file name
:param fa: the FA
:type fa: list of FA
:param str mode: writing mode"""
# TODO: write the complete information into file according with the new format
try:
f = open(FileName, mode)
except IOError:
raise common.DFAerror()
if type(fa) == list:
for d in fa:
f.write(saveToString(d))
else:
f.write(saveToString(fa))
f.close()
def _exportToTeX(FileName, fa):
""" Saves a finite automatom definition to a latex tabular. Saves a finite automata definition to a file using
the input format
.. versionchanged:: 0.9.4
:param str FileName: file name
:param FA fa: the FA
:raises DFAerror: if a file error occurs"""
try:
f = open(FileName, "w")
except IOError:
raise common.DFAerror()
# initial is the first one
if fa.Initial:
foo = {0: fa.Initial, fa.Initial: 0}
fa.reorder(foo)
f.write("$$\\begin{array}{r|")
for i in xrange(len(fa.Sigma)):
f.write("|c")
f.write("}\n")
for c in fa.Sigma:
f.write("&{0:>s}".format(str(c)))
f.write(" \\\\\hline\n")
for s in xrange(len(fa.States)):
if s in fa.delta:
if fa.Initial == s:
f.write("\\rightarrow")
if s in fa.Final:
f.write("\\star")
f.write("{0:>s}".format(str(s)))
for a in fa.delta[s].keys():
if isinstance(fa.delta[s][a], set):
f.write("&\{")
for s1 in fa.delta[s][a]:
f.write("{0:>s} ".format(str(s1)))
f.write("\}")
else:
s1 = fa.delta[s][a]
f.write("&{0:>s}".format(str(s1)))
f.write("\\\\\n")
f.write("\end{array}$$")
f.close()
def show(obj):
""" General, context sensitive, display method
:param obj: the object to show
.. versionaded:: 1.2.1 """
pass
class BuildFadoObject(lark.Transformer):
""" Semantics of the FAdo grammars' objects """
def object(self, s):
return s
def dfa(self, s):
f = DFA()
if "AlphabetI" in s:
for x in self.AlphabetI:
f.addSigma(x)
initial = True
for t in self.Transitions:
if t is None:
continue
if len(t) == 3:
i0 = f.stateIndex(t[0], True)
i1 = f.stateIndex(t[2], True)
if t[1] not in f.Sigma:
f.addSigma(t[1])
f.addTransition(i0,t[1],i1)
if initial:
f.setInitial(i0)
initial = False
if "Finals" in s:
for x in self.Finals:
f.addFinal (f.stateIndex(x,True))
if "declaredStates" in s:
for x in self.DFADStates:
f.addSigma(x)
return f
def nfa(self, s):
f = NFA()
if "Alphabet" in s:
for x in self.AlphabetI:
f.addSigma(x)
if "Initials" in s:
initial = False
for x in self.Initials:
i = f.stateIndex(x, True)
f.addInitial(i)
else:
initial = True
for t in self.Transitions:
if t is None:
continue
if len(t) == 3:
i0 = f.stateIndex(t[0], True)
i1 = f.stateIndex(t[2], True)
if t[1] not in f.Sigma and t[1] != common.Epsilon:
f.addSigma(t[1])
f.addTransition(i0,t[1],i1)
if initial:
f.addInitial(i0)
initial = False
if "Finals" in s:
for x in self.Finals:
f.addFinal (f.stateIndex(x, True))
return f
def transducer(self, s):
tt = []
gft = False
for t in self.Transitions:
if t is None:
continue
tt.append(t)
if len(t[1]) > 1 and t[1] != common.Epsilon and not gft:
gft = True
if len(t[2]) > 1 and t[2] != common.Epsilon and not gft:
gft = True
if gft is True:
f = GFT()
else:
f = SFT()
if "AlphabetI" in s:
for x in self.AlphabetI:
f.addSigma(x)
if "AlphabetO" in s:
for x in self.AlphabetO:
f.addOutput(x)
if "Initials" in s:
initial = False
for x in self.Initials:
i = f.stateIndex(x, True)
f.addInitial(i)
else:
initial = True
for t in tt:
i0 = f.stateIndex(t[0], True)
i1 = f.stateIndex(t[3], True)
f.addTransition(i0, t[1], t[2], i1)
if initial:
f.addInitial(i0)
initial = False
if "Finals" in s:
for x in self.Finals:
try:
i = f.stateIndex(x)
except common.DFAstateUnknown:
i = f.addState(x)
f.addFinal(i)
return f
def sstransducer(self, s):
if "AlphabetI" in s:
a = {x for x in self.AlphabetI}
else:
a = set()
f = SST(a)
if "Initials" in s:
initial = False
for x in self.Initials:
i = f.stateIndex(x, True)
f.addInitial(i)
initial = True
for t in self.Transitions:
if t is None:
continue
if len(t) == 3:
try:
i0 = f.stateIndex(t[0])
except common.DFAstateUnknown:
i0 = f.addState(t[0])
try:
i1 = f.stateIndex(t[2])
except common.DFAstateUnknown:
i1 = f.addState(t[2])
if not t[1].isAInvariant() and "AlphabetI" not in s:
raise common.SSMissAlphabet()
f.addTransition(i0, t[1], i1)
if initial:
f.addInitial(i0)
initial = False
if "Finals" in s:
for x in self.Finals:
try:
i = f.stateIndex(x)
except common.DFAstateUnknown:
i = f.addState(x)
f.addFinal(i)
return f
def ssfa(self, s):
if "AlphabetI" in s:
a = {x for x in self.AlphabetI}
else:
a = set()
f = SSFA(a)
if "Initials" in s:
initial = False
for x in self.Initials:
i = f.stateIndex(x, True)
f.addInitial(i)
initial = True
for t in self.Transitions:
if t is None:
continue
if len(t) == 3:
try:
i0 = f.stateIndex(t[0])
except common.DFAstateUnknown:
i0 = f.addState(t[0])
try:
i1 = f.stateIndex(t[2])
except common.DFAstateUnknown:
i1 = f.addState(t[2])
if not t[1].isAInvariant() and "AlphabetI" not in s:
raise common.SSMissAlphabet()
f.addTransition(i0, t[1], i1)
if initial:
f.addInitial(i0)
initial = False
if "Finals" in s:
for x in self.Finals:
try:
i = f.stateIndex(x)
except common.DFAstateUnknown:
i = f.addState(x)
f.addFinal(i)
return f
def finals(self, s):
self.Finals = list(s)
return "Finals"
def initials(self, s):
self.Initials = list(s)
return "Initials"
def alphabeti(self, s):
self.AlphabetI = s[0]
return "AlphabetI"
def alphabeto(self, s):
self.AlphabetO = s[0]
return "AlphabetO"
def alphabet(self, s):
return s
def name(self, (s,)):
return s[:]
def transitions(self, s):
self.Transitions = [x for x in s if x is not None]
return "Transitions"
def ttransitions(self, s):
self.Transitions = [x for x in s if x is not None]
return "Transitions"
def ssttransitions(self, s):
self.Transitions = [x for x in s if x is not None]
return "Transitions"
def ssatransitions(self, s):
self.Transitions = [x for x in s if x is not None]
return "Transitions"
def transition(self,(s1,s2,s3)):
return (s1,s2,s3)
def ttransition(self, (s1, s2, s3 , s4)):
return (s1, s2, s3, s4)
def ssttransition(self, (s1, s2, s3)):
return (s1, s2, s3)
def ssatransition(self, (s1, s2, s3)):
return (s1, s2, s3)
def symbol(self,s):
return s[0]
def number(self,s):
return int(s[0])
def statedecl(self,s):
if not hasattr(self,'DFADStates'):
self.DFADStates = []
self.DFADStates.append(s)
return "DeclaredStates"
def sallspec(self, s):
return SSAnyOf()
def sonespec(self, s):
return SSOneOf(sorted(list({x for x in s[0]})))
def snotspec(self, s):
return SSNoneOf(sorted(list({x for x in s[0]})))
def vpspec(self, (s1, s2)):
return PSPVanila(s1, s2)
def eqpspec(self, s1):
return PSPEqual(s1[0])
def neqpspec(self, (s1, s2)):
return PSPDiff(s1, s2)
def sepsilon(self, s):
return SSEpsilon()
def names(self, s):
return s
def epsilon(self, s):
return common.Epsilon
def spec(self, s):
return s[0]
eol = lambda self, _: None
dollar = lambda self, _: None
FAdoGrammar = lark.Lark(r"""
?object: [(dfa | nfa | transducer | sstransducer | emptyline | ssfa)+]
peg: "@PEG" vars eol pegbody
tdpl: "@TDPL" vars eol tdplbody
dfa: "@DFA" finals [alphabeti?] eol transitions
nfa: "@NFA" finals [(star initials)?] [alphabeti?] eol transitions
transducer: "@Transducer" finals [(star initials)?] [(alphabeti (alphabeto)?)?] eol ttransitions
sstransducer: "@SST" finals [(star initials)?] alphabeti eol ssttransitions
ssfa: "@SSFA" finals [(star initials)?] [alphabeti?] eol ssatransitions
?alphabet: [var (var)* ]
?var: name
name: /[a-zA-Z0-9]+/
number: /[0-9]+/
finals: [(var)+]
alphabeti: "$" alphabet
alphabeto: "$" alphabet
transitions: [(strule eol)+]
?strule: statedecl | transition
transition: var symbol var
ttransitions: [(tstrule eol)+]
?tstrule: statedecl | ttransition
ttransition: var symbol symbol var
ssttransitions: [(sststrule eol)+]
?sststrule: statedecl | ssttransition
?ssttransition: var pspec var
spec: sepsilon | nspec
?nspec: sallspec | sonespec | snotspec
sallspec: "@a"
sonespec: "@o" names
snotspec: "@n" names
?pspec: vpspec | eqpspec | neqpspec
vpspec: spec spec
eqpspec: nspec "@="
sepsilon: "@epsilon"
neqpspec: nspec nspec "!"
ssatransitions: [(ssatransition eol)+]
?ssatransition: var spec var
?vars: names
?names: [var ( var)* ]
pegbody: [(pegrule eol)+]
pegrule: var "<-" expr
?expr: "(" expr ")" | var | not | concat | kstar | cond | test
not: "!" expr
concat: expr expr
kstar: expr star
cond: expr SLASH expr
!test: AMPERSAND expr
tdplbody: [(tdplrule eol)+]
tdplrule: var "<-" var var "|" var
statedecl: var
emptyline: /\n/
symbol: var | epsilon
epsilon: "@epsilon"
initials: [var (var)* ]
star: "*"
dollar: /\$/
AMPERSAND: /&/
SLASH: /\//
eol: /[\n\r]+/
%ignore /[ \t\f\"]+/
%ignore /#[^\n]*\n/
%ignore /#[^\r\n]*/
""", start='object')