# Source code for fio

# -*- coding: utf-8 -*-
"""**In/Out.**

.. *Authors:* Rogério Reis & Nelma Moreira

.. *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
import lark

:param fileName: name of the file
:type fileName: str
:rtype: DFA|FA|STF|SST"""
if type(o) == list:
return o[0]
else:
return o

"""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')