-/*\r
- Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft\r
- Permission is hereby granted, free of charge, to any person obtaining a copy\r
- of this software and associated documentation files (the "Software"), to deal\r
- in the Software without restriction, including without limitation the rights\r
- to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
- copies of the Software, and to permit persons to whom the Software is\r
- furnished to do so, subject to the following conditions:\r
- \r
- The above copyright notice and this permission notice shall be included in\r
- all copies or substantial portions of the Software.\r
- \r
- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
- IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
- FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
- AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
- LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
- OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
- SOFTWARE.\r
-*/\r
-\r
-// Compile with \r
-// csc /r:C5.dll GNfaToDfa.cs\r
-\r
-// C5 examples: RegExp -> NFA -> DFA -> Graph\r
-// Java 2000-10-07, GC# 2001-10-23, C# 2.0 2003-09-03, C# 2.0+C5 2004-08-08\r
-\r
-// This file contains, in order:\r
-// * Helper class Set<T> defined in terms of C5 classes.\r
-// * A class Nfa for representing an NFA (a nondeterministic finite \r
-// automaton), and for converting it to a DFA (a deterministic \r
-// finite automaton). Most complexity is in this class.\r
-// * A class Dfa for representing a DFA, a deterministic finite \r
-// automaton, and for writing a dot input file representing the DFA.\r
-// * Classes for representing regular expressions, and for building an \r
-// NFA from a regular expression\r
-// * A test class that creates an NFA, a DFA, and a dot input file \r
-// for a number of small regular expressions. The DFAs are \r
-// not minimized.\r
-\r
-using System;\r
-using System.Text;\r
-using System.IO;\r
-using C5;\r
-using SCG = System.Collections.Generic;\r
-\r
-namespace GNfaToDfa\r
-{\r
-\r
- public class Set<T> : HashSet<T> {\r
- public Set(SCG.IEnumerable<T> enm) : base() {\r
- AddAll(enm);\r
- }\r
-\r
- public Set(params T[] elems) : this((SCG.IEnumerable<T>)elems) { }\r
-\r
- // Set union (+), difference (-), and intersection (*):\r
-\r
- public static Set<T> operator +(Set<T> s1, Set<T> s2) {\r
- if (s1 == null || s2 == null) \r
- throw new ArgumentNullException("Set+Set");\r
- else {\r
- Set<T> res = new Set<T>(s1);\r
- res.AddAll(s2);\r
- return res;\r
- }\r
- }\r
-\r
- public static Set<T> operator -(Set<T> s1, Set<T> s2) {\r
- if (s1 == null || s2 == null) \r
- throw new ArgumentNullException("Set-Set");\r
- else {\r
- Set<T> res = new Set<T>(s1);\r
- res.RemoveAll(s2);\r
- return res;\r
- }\r
- }\r
-\r
- public static Set<T> operator *(Set<T> s1, Set<T> s2) {\r
- if (s1 == null || s2 == null) \r
- throw new ArgumentNullException("Set*Set");\r
- else {\r
- Set<T> res = new Set<T>(s1);\r
- res.RetainAll(s2);\r
- return res;\r
- }\r
- }\r
-\r
- // Equality of sets; take care to avoid infinite loops\r
-\r
- public static bool operator ==(Set<T> s1, Set<T> s2) {\r
- return EqualityComparer<Set<T>>.Default.Equals(s1, s2);\r
- }\r
-\r
- public static bool operator !=(Set<T> s1, Set<T> s2) {\r
- return !(s1 == s2);\r
- }\r
-\r
- public override bool Equals(Object that) {\r
- return this == (that as Set<T>);\r
- }\r
-\r
- public override int GetHashCode() {\r
- return EqualityComparer<Set<T>>.Default.GetHashCode(this);\r
- }\r
-\r
- // Subset (<=) and superset (>=) relation:\r
-\r
- public static bool operator <=(Set<T> s1, Set<T> s2) {\r
- if (s1 == null || s2 == null) \r
- throw new ArgumentNullException("Set<=Set");\r
- else\r
- return s1.ContainsAll(s2);\r
- }\r
-\r
- public static bool operator >=(Set<T> s1, Set<T> s2) {\r
- if (s1 == null || s2 == null) \r
- throw new ArgumentNullException("Set>=Set");\r
- else\r
- return s2.ContainsAll(s1);\r
- }\r
- \r
- public override String ToString() {\r
- StringBuilder sb = new StringBuilder();\r
- sb.Append("{");\r
- bool first = true;\r
- foreach (T x in this) {\r
- if (!first)\r
- sb.Append(",");\r
- sb.Append(x);\r
- first = false;\r
- }\r
- sb.Append("}");\r
- return sb.ToString();\r
- }\r
- }\r
-\r
-// ----------------------------------------------------------------------\r
-\r
-// Regular expressions, NFAs, DFAs, and dot graphs\r
-// sestoft@dina.kvl.dk * \r
-// Java 2001-07-10 * C# 2001-10-22 * Gen C# 2001-10-23, 2003-09-03\r
-\r
-// In the Generic C# 2.0 version we \r
-// use Queue<int> and Queue<Set<int>> for worklists\r
-// use Set<int> for pre-DFA states\r
-// use ArrayList<Transition> for NFA transition relations\r
-// use HashDictionary<Set<int>, HashDictionary<String, Set<int>>>\r
-// and HashDictionary<int, HashDictionary<String, int>> for DFA transition relations\r
-\r
-/* Class Nfa and conversion from NFA to DFA ---------------------------\r
-\r
- A nondeterministic finite automaton (NFA) is represented as a\r
- dictionary mapping a state number (int) to an arraylist of\r
- Transitions, a Transition being a pair of a label lab (a string,\r
- null meaning epsilon) and a target state (an int).\r
-\r
- A DFA is created from an NFA in two steps:\r
-\r
- (1) Construct a DFA whose each of whose states is composite,\r
- namely a set of NFA states (Set of int). This is done by\r
- methods CompositeDfaTrans and EpsilonClose.\r
-\r
- (2) Replace composite states (Set of int) by simple states\r
- (int). This is done by methods Rename and MkRenamer.\r
-\r
- Method CompositeDfaTrans works as follows: \r
-\r
- Create the epsilon-closure S0 (a Set of ints) of the start state\r
- s0, and put it in a worklist (a Queue). Create an empty DFA\r
- transition relation, which is a dictionary mapping a composite\r
- state (an epsilon-closed set of ints) to a dictionary mapping a\r
- label (a non-null string) to a composite state.\r
-\r
- Repeatedly choose a composite state S from the worklist. If it is\r
- not already in the keyset of the DFA transition relation, compute\r
- for every non-epsilon label lab the set T of states reachable by\r
- that label from some state s in S. Compute the epsilon-closure\r
- Tclose of every such state T and put it on the worklist. Then add\r
- the transition S -lab-> Tclose to the DFA transition relation, for\r
- every lab.\r
-\r
- Method EpsilonClose works as follows: \r
-\r
- Given a set S of states. Put the states of S in a worklist.\r
- Repeatedly choose a state s from the worklist, and consider all\r
- epsilon-transitions s -eps-> s' from s. If s' is in S already,\r
- then do nothing; otherwise add s' to S and the worklist. When the\r
- worklist is empty, S is epsilon-closed; return S.\r
-\r
- Method MkRenamer works as follows: \r
-\r
- Given a dictionary mapping a set of int to something, create an\r
- injective dictionary mapping from set of int to int, by choosing a\r
- fresh int for every key in the given dictionary.\r
-\r
- Method Rename works as follows:\r
-\r
- Given a dictionary mapping a set of int to a dictionary mapping a\r
- string to set of int, use the result of MkRenamer to replace all\r
- sets of ints by ints.\r
-\r
-*/\r
-\r
- class Nfa {\r
- private readonly int startState;\r
- private readonly int exitState; // This is the unique accept state\r
- private readonly IDictionary<int, ArrayList<Transition>> trans;\r
-\r
- public Nfa(int startState, int exitState) {\r
- this.startState = startState; this.exitState = exitState;\r
- trans = new HashDictionary<int, ArrayList<Transition>>();\r
- if (!startState.Equals(exitState))\r
- trans.Add(exitState, new ArrayList<Transition>());\r
- }\r
-\r
- public int Start { get { return startState; } }\r
-\r
- public int Exit { get { return exitState; } }\r
-\r
- public IDictionary<int, ArrayList<Transition>> Trans {\r
- get { return trans; }\r
- }\r
-\r
- public void AddTrans(int s1, String lab, int s2) {\r
- ArrayList<Transition> s1Trans;\r
- if (trans.Contains(s1))\r
- s1Trans = trans[s1];\r
- else {\r
- s1Trans = new ArrayList<Transition>();\r
- trans.Add(s1, s1Trans);\r
- }\r
- s1Trans.Add(new Transition(lab, s2));\r
- }\r
-\r
- public void AddTrans(KeyValuePair<int, ArrayList<Transition>> tr) {\r
- // Assumption: if tr is in trans, it maps to an empty list (end state)\r
- trans.Remove(tr.Key);\r
- trans.Add(tr.Key, tr.Value);\r
- }\r
-\r
- public override String ToString() {\r
- return "NFA start=" + startState + " exit=" + exitState;\r
- }\r
-\r
- // Construct the transition relation of a composite-state DFA from\r
- // an NFA with start state s0 and transition relation trans (a\r
- // dictionary mapping int to arraylist of Transition). The start\r
- // state of the constructed DFA is the epsilon closure of s0, and\r
- // its transition relation is a dictionary mapping a composite state\r
- // (a set of ints) to a dictionary mapping a label (a string) to a\r
- // composite state (a set of ints).\r
-\r
- static IDictionary<Set<int>, IDictionary<String, Set<int>>>\r
- CompositeDfaTrans(int s0, IDictionary<int, ArrayList<Transition>> trans) {\r
- Set<int> S0 = EpsilonClose(new Set<int>(s0), trans);\r
- IQueue<Set<int>> worklist = new CircularQueue<Set<int>>();\r
- worklist.Enqueue(S0);\r
- // The transition relation of the DFA\r
- IDictionary<Set<int>, IDictionary<String, Set<int>>> res =\r
- new HashDictionary<Set<int>, IDictionary<String, Set<int>>>();\r
- while (!worklist.IsEmpty) {\r
- Set<int> S = worklist.Dequeue();\r
- if (!res.Contains(S)) {\r
- // The S -lab-> T transition relation being constructed for a given S\r
- IDictionary<String, Set<int>> STrans =\r
- new HashDictionary<String, Set<int>>();\r
- // For all s in S, consider all transitions s -lab-> t\r
- foreach (int s in S) {\r
- // For all non-epsilon transitions s -lab-> t, add t to T\r
- foreach (Transition tr in trans[s]) {\r
- if (tr.lab != null) { // Non-epsilon transition\r
- Set<int> toState;\r
- if (STrans.Contains(tr.lab)) // Already a transition on lab\r
- toState = STrans[tr.lab];\r
- else { // No transitions on lab yet\r
- toState = new Set<int>();\r
- STrans.Add(tr.lab, toState);\r
- }\r
- toState.Add(tr.target);\r
- }\r
- }\r
- }\r
- // Epsilon-close all T such that S -lab-> T, and put on worklist\r
- IDictionary<String, Set<int>> STransClosed =\r
- new HashDictionary<String, Set<int>>();\r
- foreach (KeyValuePair<String, Set<int>> entry in STrans) {\r
- Set<int> Tclose = EpsilonClose(entry.Value, trans);\r
- STransClosed.Add(entry.Key, Tclose);\r
- worklist.Enqueue(Tclose);\r
- }\r
- res.Add(S, STransClosed);\r
- }\r
- }\r
- return res;\r
- }\r
-\r
- // Compute epsilon-closure of state set S in transition relation trans. \r
-\r
- static Set<int>\r
- EpsilonClose(Set<int> S, IDictionary<int, ArrayList<Transition>> trans) {\r
- // The worklist initially contains all S members\r
- IQueue<int> worklist = new CircularQueue<int>();\r
- S.Apply(worklist.Enqueue);\r
- Set<int> res = new Set<int>(S);\r
- while (!worklist.IsEmpty) {\r
- int s = worklist.Dequeue();\r
- foreach (Transition tr in trans[s]) {\r
- if (tr.lab == null && !res.Contains(tr.target)) {\r
- res.Add(tr.target);\r
- worklist.Enqueue(tr.target);\r
- }\r
- }\r
- }\r
- return res;\r
- }\r
-\r
- // Compute a renamer, which is a dictionary mapping set of int to int\r
-\r
- static IDictionary<Set<int>, int> MkRenamer(ICollectionValue<Set<int>> states)\r
- {\r
- IDictionary<Set<int>, int> renamer = new HashDictionary<Set<int>, int>();\r
- int count = 0;\r
- foreach (Set<int> k in states)\r
- renamer.Add(k, count++);\r
- return renamer;\r
- }\r
-\r
- // Using a renamer (a dictionary mapping set of int to int), replace\r
- // composite (set of int) states with simple (int) states in the\r
- // transition relation trans, which is a dictionary mapping set of\r
- // int to a dictionary mapping from string to set of int. The\r
- // result is a dictionary mapping from int to a dictionary mapping\r
- // from string to int.\r
-\r
- static IDictionary<int, IDictionary<String, int>>\r
- Rename(IDictionary<Set<int>, int> renamer,\r
- IDictionary<Set<int>, IDictionary<String, Set<int>>> trans)\r
- {\r
- IDictionary<int, IDictionary<String, int>> newtrans =\r
- new HashDictionary<int, IDictionary<String, int>>();\r
- foreach (KeyValuePair<Set<int>, IDictionary<String, Set<int>>> entry\r
- in trans) {\r
- Set<int> k = entry.Key;\r
- IDictionary<String, int> newktrans = new HashDictionary<String, int>();\r
- foreach (KeyValuePair<String, Set<int>> tr in entry.Value)\r
- newktrans.Add(tr.Key, renamer[tr.Value]);\r
- newtrans.Add(renamer[k], newktrans);\r
- }\r
- return newtrans;\r
- }\r
-\r
- static Set<int> AcceptStates(ICollectionValue<Set<int>> states,\r
- IDictionary<Set<int>, int> renamer,\r
- int exit)\r
- {\r
- Set<int> acceptStates = new Set<int>();\r
- foreach (Set<int> state in states)\r
- if (state.Contains(exit))\r
- acceptStates.Add(renamer[state]);\r
- return acceptStates;\r
- }\r
-\r
- public Dfa ToDfa() {\r
- IDictionary<Set<int>, IDictionary<String, Set<int>>>\r
- cDfaTrans = CompositeDfaTrans(startState, trans);\r
- Set<int> cDfaStart = EpsilonClose(new Set<int>(startState), trans);\r
- ICollectionValue<Set<int>> cDfaStates = cDfaTrans.Keys;\r
- IDictionary<Set<int>, int> renamer = MkRenamer(cDfaStates);\r
- IDictionary<int, IDictionary<String, int>> simpleDfaTrans =\r
- Rename(renamer, cDfaTrans);\r
- int simpleDfaStart = renamer[cDfaStart];\r
- Set<int> simpleDfaAccept = AcceptStates(cDfaStates, renamer, exitState);\r
- return new Dfa(simpleDfaStart, simpleDfaAccept, simpleDfaTrans);\r
- }\r
-\r
- // Nested class for creating distinctly named states when constructing NFAs\r
-\r
- public class NameSource {\r
- private static int nextName = 0;\r
-\r
- public int next() {\r
- return nextName++;\r
- }\r
- }\r
-\r
- // Write an input file for the dot program. You can find dot at\r
- // http://www.research.att.com/sw/tools/graphviz/\r
-\r
- public void WriteDot(String filename) {\r
- TextWriter wr =\r
- new StreamWriter(new FileStream(filename, FileMode.Create,\r
- FileAccess.Write));\r
- wr.WriteLine("// Format this file as a Postscript file with ");\r
- wr.WriteLine("// dot " + filename + " -Tps -o out.ps\n");\r
- wr.WriteLine("digraph nfa {");\r
- wr.WriteLine("size=\"11,8.25\";");\r
- wr.WriteLine("rotate=90;");\r
- wr.WriteLine("rankdir=LR;");\r
- wr.WriteLine("start [style=invis];"); // Invisible start node\r
- wr.WriteLine("start -> d" + startState); // Edge into start state\r
-\r
- // The accept state has a double circle\r
- wr.WriteLine("d" + exitState + " [peripheries=2];");\r
-\r
- // The transitions \r
- foreach (KeyValuePair<int, ArrayList<Transition>> entry in trans) {\r
- int s1 = entry.Key;\r
- foreach (Transition s1Trans in entry.Value) {\r
- String lab = s1Trans.lab ?? "eps";\r
- int s2 = s1Trans.target;\r
- wr.WriteLine("d" + s1 + " -> d" + s2 + " [label=\"" + lab + "\"];");\r
- }\r
- }\r
- wr.WriteLine("}");\r
- wr.Close();\r
- }\r
- }\r
-\r
-// Class Transition, a transition from one state to another ----------\r
-\r
- public class Transition {\r
- public readonly String lab;\r
- public readonly int target;\r
-\r
- public Transition(String lab, int target) {\r
- this.lab = lab; this.target = target;\r
- }\r
-\r
- public override String ToString() {\r
- return "-" + lab + "-> " + target;\r
- }\r
- }\r
-\r
-// Class Dfa, deterministic finite automata --------------------------\r
-\r
-/*\r
- A deterministic finite automaton (DFA) is represented as a\r
- dictionary mapping state number (int) to a dictionary mapping label\r
- (a non-null string) to a target state (an int).\r
-*/\r
-\r
- class Dfa {\r
- private readonly int startState;\r
- private readonly Set<int> acceptStates;\r
- private readonly IDictionary<int, IDictionary<String, int>> trans;\r
-\r
- public Dfa(int startState, Set<int> acceptStates,\r
- IDictionary<int, IDictionary<String, int>> trans)\r
- {\r
- this.startState = startState;\r
- this.acceptStates = acceptStates;\r
- this.trans = trans;\r
- }\r
-\r
- public int Start { get { return startState; } }\r
-\r
- public Set<int> Accept { get { return acceptStates; } }\r
-\r
- public IDictionary<int, IDictionary<String, int>> Trans {\r
- get { return trans; }\r
- }\r
-\r
- public override String ToString() {\r
- return "DFA start=" + startState + "\naccept=" + acceptStates;\r
- }\r
-\r
- // Write an input file for the dot program. You can find dot at\r
- // http://www.research.att.com/sw/tools/graphviz/\r
-\r
- public void WriteDot(String filename) {\r
- TextWriter wr =\r
- new StreamWriter(new FileStream(filename, FileMode.Create,\r
- FileAccess.Write));\r
- wr.WriteLine("// Format this file as a Postscript file with ");\r
- wr.WriteLine("// dot " + filename + " -Tps -o out.ps\n");\r
- wr.WriteLine("digraph dfa {");\r
- wr.WriteLine("size=\"11,8.25\";");\r
- wr.WriteLine("rotate=90;");\r
- wr.WriteLine("rankdir=LR;");\r
- wr.WriteLine("start [style=invis];"); // Invisible start node\r
- wr.WriteLine("start -> d" + startState); // Edge into start state\r
-\r
- // Accept states are double circles\r
- foreach (int state in trans.Keys)\r
- if (acceptStates.Contains(state))\r
- wr.WriteLine("d" + state + " [peripheries=2];");\r
-\r
- // The transitions \r
- foreach (KeyValuePair<int, IDictionary<String, int>> entry in trans) {\r
- int s1 = entry.Key;\r
- foreach (KeyValuePair<String, int> s1Trans in entry.Value) {\r
- String lab = s1Trans.Key;\r
- int s2 = s1Trans.Value;\r
- wr.WriteLine("d" + s1 + " -> d" + s2 + " [label=\"" + lab + "\"];");\r
- }\r
- }\r
- wr.WriteLine("}");\r
- wr.Close();\r
- }\r
- }\r
-\r
-// Regular expressions ----------------------------------------------\r
-//\r
-// Abstract syntax of regular expressions\r
-// r ::= A | r1 r2 | (r1|r2) | r*\r
-//\r
-\r
- abstract class Regex {\r
- abstract public Nfa MkNfa(Nfa.NameSource names);\r
- }\r
-\r
- class Eps : Regex {\r
- // The resulting nfa0 has form s0s -eps-> s0e\r
-\r
- public override Nfa MkNfa(Nfa.NameSource names) {\r
- int s0s = names.next();\r
- int s0e = names.next();\r
- Nfa nfa0 = new Nfa(s0s, s0e);\r
- nfa0.AddTrans(s0s, null, s0e);\r
- return nfa0;\r
- }\r
- }\r
-\r
- class Sym : Regex {\r
- String sym;\r
-\r
- public Sym(String sym) {\r
- this.sym = sym;\r
- }\r
-\r
- // The resulting nfa0 has form s0s -sym-> s0e\r
-\r
- public override Nfa MkNfa(Nfa.NameSource names) {\r
- int s0s = names.next();\r
- int s0e = names.next();\r
- Nfa nfa0 = new Nfa(s0s, s0e);\r
- nfa0.AddTrans(s0s, sym, s0e);\r
- return nfa0;\r
- }\r
- }\r
-\r
- class Seq : Regex {\r
- Regex r1, r2;\r
-\r
- public Seq(Regex r1, Regex r2) {\r
- this.r1 = r1; this.r2 = r2;\r
- }\r
-\r
- // If nfa1 has form s1s ----> s1e \r
- // and nfa2 has form s2s ----> s2e \r
- // then nfa0 has form s1s ----> s1e -eps-> s2s ----> s2e\r
-\r
- public override Nfa MkNfa(Nfa.NameSource names) {\r
- Nfa nfa1 = r1.MkNfa(names);\r
- Nfa nfa2 = r2.MkNfa(names);\r
- Nfa nfa0 = new Nfa(nfa1.Start, nfa2.Exit);\r
- foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa1.Trans)\r
- nfa0.AddTrans(entry);\r
- foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa2.Trans)\r
- nfa0.AddTrans(entry);\r
- nfa0.AddTrans(nfa1.Exit, null, nfa2.Start);\r
- return nfa0;\r
- }\r
- }\r
-\r
- class Alt : Regex {\r
- Regex r1, r2;\r
-\r
- public Alt(Regex r1, Regex r2) {\r
- this.r1 = r1; this.r2 = r2;\r
- }\r
-\r
- // If nfa1 has form s1s ----> s1e \r
- // and nfa2 has form s2s ----> s2e \r
- // then nfa0 has form s0s -eps-> s1s ----> s1e -eps-> s0e\r
- // s0s -eps-> s2s ----> s2e -eps-> s0e\r
-\r
- public override Nfa MkNfa(Nfa.NameSource names) {\r
- Nfa nfa1 = r1.MkNfa(names);\r
- Nfa nfa2 = r2.MkNfa(names);\r
- int s0s = names.next();\r
- int s0e = names.next();\r
- Nfa nfa0 = new Nfa(s0s, s0e);\r
- foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa1.Trans)\r
- nfa0.AddTrans(entry);\r
- foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa2.Trans)\r
- nfa0.AddTrans(entry);\r
- nfa0.AddTrans(s0s, null, nfa1.Start);\r
- nfa0.AddTrans(s0s, null, nfa2.Start);\r
- nfa0.AddTrans(nfa1.Exit, null, s0e);\r
- nfa0.AddTrans(nfa2.Exit, null, s0e);\r
- return nfa0;\r
- }\r
- }\r
-\r
- class Star : Regex {\r
- Regex r;\r
-\r
- public Star(Regex r) {\r
- this.r = r;\r
- }\r
-\r
- // If nfa1 has form s1s ----> s1e \r
- // then nfa0 has form s0s ----> s0s\r
- // s0s -eps-> s1s\r
- // s1e -eps-> s0s\r
-\r
- public override Nfa MkNfa(Nfa.NameSource names) {\r
- Nfa nfa1 = r.MkNfa(names);\r
- int s0s = names.next();\r
- Nfa nfa0 = new Nfa(s0s, s0s);\r
- foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa1.Trans)\r
- nfa0.AddTrans(entry);\r
- nfa0.AddTrans(s0s, null, nfa1.Start);\r
- nfa0.AddTrans(nfa1.Exit, null, s0s);\r
- return nfa0;\r
- }\r
- }\r
-\r
-// Trying the RE->NFA->DFA translation on three regular expressions\r
-\r
- class TestNFA {\r
- public static void Main(String[] args) {\r
- Regex a = new Sym("A");\r
- Regex b = new Sym("B");\r
- Regex c = new Sym("C");\r
- Regex abStar = new Star(new Alt(a, b));\r
- Regex bb = new Seq(b, b);\r
- Regex r = new Seq(abStar, new Seq(a, b));\r
- // The regular expression (a|b)*ab\r
- BuildAndShow("ex1", r);\r
- // The regular expression ((a|b)*ab)*\r
- BuildAndShow("ex2", new Star(r));\r
- // The regular expression ((a|b)*ab)((a|b)*ab)\r
- BuildAndShow("ex3", new Seq(r, r));\r
- // The regular expression (a|b)*abb, from ASU 1986 p 136\r
- BuildAndShow("ex4", new Seq(abStar, new Seq(a, bb)));\r
- // SML reals: sign?((digit+(\.digit+)?))([eE]sign?digit+)?\r
- Regex d = new Sym("digit");\r
- Regex dPlus = new Seq(d, new Star(d));\r
- Regex s = new Sym("sign");\r
- Regex sOpt = new Alt(s, new Eps());\r
- Regex dot = new Sym(".");\r
- Regex dotDigOpt = new Alt(new Eps(), new Seq(dot, dPlus));\r
- Regex mant = new Seq(sOpt, new Seq(dPlus, dotDigOpt));\r
- Regex e = new Sym("e");\r
- Regex exp = new Alt(new Eps(), new Seq(e, new Seq(sOpt, dPlus)));\r
- Regex smlReal = new Seq(mant, exp);\r
- BuildAndShow("ex5", smlReal);\r
- }\r
-\r
- public static void BuildAndShow(String fileprefix, Regex r) {\r
- Nfa nfa = r.MkNfa(new Nfa.NameSource());\r
- Console.WriteLine(nfa);\r
- Console.WriteLine("Writing NFA graph to file");\r
- nfa.WriteDot(fileprefix + "nfa.dot");\r
- Console.WriteLine("---");\r
- Dfa dfa = nfa.ToDfa();\r
- Console.WriteLine(dfa);\r
- Console.WriteLine("Writing DFA graph to file");\r
- dfa.WriteDot(fileprefix + "dfa.dot");\r
- Console.WriteLine();\r
- }\r
- }\r
-}\r
+/*
+ Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
+ Permission is hereby granted, free of charge, to any person obtaining a copy
+ of this software and associated documentation files (the "Software"), to deal
+ in the Software without restriction, including without limitation the rights
+ to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ copies of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+
+ The above copyright notice and this permission notice shall be included in
+ all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ SOFTWARE.
+*/
+
+// Compile with
+// csc /r:C5.dll GNfaToDfa.cs
+
+// C5 examples: RegExp -> NFA -> DFA -> Graph
+// Java 2000-10-07, GC# 2001-10-23, C# 2.0 2003-09-03, C# 2.0+C5 2004-08-08
+
+// This file contains, in order:
+// * Helper class Set<T> defined in terms of C5 classes.
+// * A class Nfa for representing an NFA (a nondeterministic finite
+// automaton), and for converting it to a DFA (a deterministic
+// finite automaton). Most complexity is in this class.
+// * A class Dfa for representing a DFA, a deterministic finite
+// automaton, and for writing a dot input file representing the DFA.
+// * Classes for representing regular expressions, and for building an
+// NFA from a regular expression
+// * A test class that creates an NFA, a DFA, and a dot input file
+// for a number of small regular expressions. The DFAs are
+// not minimized.
+
+using System;
+using System.Text;
+using System.IO;
+using C5;
+using SCG = System.Collections.Generic;
+
+namespace GNfaToDfa
+{
+
+ public class Set<T> : HashSet<T> {
+ public Set(SCG.IEnumerable<T> enm) : base() {
+ AddAll(enm);
+ }
+
+ public Set(params T[] elems) : this((SCG.IEnumerable<T>)elems) { }
+
+ // Set union (+), difference (-), and intersection (*):
+
+ public static Set<T> operator +(Set<T> s1, Set<T> s2) {
+ if (s1 == null || s2 == null)
+ throw new ArgumentNullException("Set+Set");
+ else {
+ Set<T> res = new Set<T>(s1);
+ res.AddAll(s2);
+ return res;
+ }
+ }
+
+ public static Set<T> operator -(Set<T> s1, Set<T> s2) {
+ if (s1 == null || s2 == null)
+ throw new ArgumentNullException("Set-Set");
+ else {
+ Set<T> res = new Set<T>(s1);
+ res.RemoveAll(s2);
+ return res;
+ }
+ }
+
+ public static Set<T> operator *(Set<T> s1, Set<T> s2) {
+ if (s1 == null || s2 == null)
+ throw new ArgumentNullException("Set*Set");
+ else {
+ Set<T> res = new Set<T>(s1);
+ res.RetainAll(s2);
+ return res;
+ }
+ }
+
+ // Equality of sets; take care to avoid infinite loops
+
+ public static bool operator ==(Set<T> s1, Set<T> s2) {
+ return EqualityComparer<Set<T>>.Default.Equals(s1, s2);
+ }
+
+ public static bool operator !=(Set<T> s1, Set<T> s2) {
+ return !(s1 == s2);
+ }
+
+ public override bool Equals(Object that) {
+ return this == (that as Set<T>);
+ }
+
+ public override int GetHashCode() {
+ return EqualityComparer<Set<T>>.Default.GetHashCode(this);
+ }
+
+ // Subset (<=) and superset (>=) relation:
+
+ public static bool operator <=(Set<T> s1, Set<T> s2) {
+ if (s1 == null || s2 == null)
+ throw new ArgumentNullException("Set<=Set");
+ else
+ return s1.ContainsAll(s2);
+ }
+
+ public static bool operator >=(Set<T> s1, Set<T> s2) {
+ if (s1 == null || s2 == null)
+ throw new ArgumentNullException("Set>=Set");
+ else
+ return s2.ContainsAll(s1);
+ }
+
+ public override String ToString() {
+ StringBuilder sb = new StringBuilder();
+ sb.Append("{");
+ bool first = true;
+ foreach (T x in this) {
+ if (!first)
+ sb.Append(",");
+ sb.Append(x);
+ first = false;
+ }
+ sb.Append("}");
+ return sb.ToString();
+ }
+ }
+
+// ----------------------------------------------------------------------
+
+// Regular expressions, NFAs, DFAs, and dot graphs
+// sestoft@dina.kvl.dk *
+// Java 2001-07-10 * C# 2001-10-22 * Gen C# 2001-10-23, 2003-09-03
+
+// In the Generic C# 2.0 version we
+// use Queue<int> and Queue<Set<int>> for worklists
+// use Set<int> for pre-DFA states
+// use ArrayList<Transition> for NFA transition relations
+// use HashDictionary<Set<int>, HashDictionary<String, Set<int>>>
+// and HashDictionary<int, HashDictionary<String, int>> for DFA transition relations
+
+/* Class Nfa and conversion from NFA to DFA ---------------------------
+
+ A nondeterministic finite automaton (NFA) is represented as a
+ dictionary mapping a state number (int) to an arraylist of
+ Transitions, a Transition being a pair of a label lab (a string,
+ null meaning epsilon) and a target state (an int).
+
+ A DFA is created from an NFA in two steps:
+
+ (1) Construct a DFA whose each of whose states is composite,
+ namely a set of NFA states (Set of int). This is done by
+ methods CompositeDfaTrans and EpsilonClose.
+
+ (2) Replace composite states (Set of int) by simple states
+ (int). This is done by methods Rename and MkRenamer.
+
+ Method CompositeDfaTrans works as follows:
+
+ Create the epsilon-closure S0 (a Set of ints) of the start state
+ s0, and put it in a worklist (a Queue). Create an empty DFA
+ transition relation, which is a dictionary mapping a composite
+ state (an epsilon-closed set of ints) to a dictionary mapping a
+ label (a non-null string) to a composite state.
+
+ Repeatedly choose a composite state S from the worklist. If it is
+ not already in the keyset of the DFA transition relation, compute
+ for every non-epsilon label lab the set T of states reachable by
+ that label from some state s in S. Compute the epsilon-closure
+ Tclose of every such state T and put it on the worklist. Then add
+ the transition S -lab-> Tclose to the DFA transition relation, for
+ every lab.
+
+ Method EpsilonClose works as follows:
+
+ Given a set S of states. Put the states of S in a worklist.
+ Repeatedly choose a state s from the worklist, and consider all
+ epsilon-transitions s -eps-> s' from s. If s' is in S already,
+ then do nothing; otherwise add s' to S and the worklist. When the
+ worklist is empty, S is epsilon-closed; return S.
+
+ Method MkRenamer works as follows:
+
+ Given a dictionary mapping a set of int to something, create an
+ injective dictionary mapping from set of int to int, by choosing a
+ fresh int for every key in the given dictionary.
+
+ Method Rename works as follows:
+
+ Given a dictionary mapping a set of int to a dictionary mapping a
+ string to set of int, use the result of MkRenamer to replace all
+ sets of ints by ints.
+
+*/
+
+ class Nfa {
+ private readonly int startState;
+ private readonly int exitState; // This is the unique accept state
+ private readonly IDictionary<int, ArrayList<Transition>> trans;
+
+ public Nfa(int startState, int exitState) {
+ this.startState = startState; this.exitState = exitState;
+ trans = new HashDictionary<int, ArrayList<Transition>>();
+ if (!startState.Equals(exitState))
+ trans.Add(exitState, new ArrayList<Transition>());
+ }
+
+ public int Start { get { return startState; } }
+
+ public int Exit { get { return exitState; } }
+
+ public IDictionary<int, ArrayList<Transition>> Trans {
+ get { return trans; }
+ }
+
+ public void AddTrans(int s1, String lab, int s2) {
+ ArrayList<Transition> s1Trans;
+ if (trans.Contains(s1))
+ s1Trans = trans[s1];
+ else {
+ s1Trans = new ArrayList<Transition>();
+ trans.Add(s1, s1Trans);
+ }
+ s1Trans.Add(new Transition(lab, s2));
+ }
+
+ public void AddTrans(KeyValuePair<int, ArrayList<Transition>> tr) {
+ // Assumption: if tr is in trans, it maps to an empty list (end state)
+ trans.Remove(tr.Key);
+ trans.Add(tr.Key, tr.Value);
+ }
+
+ public override String ToString() {
+ return "NFA start=" + startState + " exit=" + exitState;
+ }
+
+ // Construct the transition relation of a composite-state DFA from
+ // an NFA with start state s0 and transition relation trans (a
+ // dictionary mapping int to arraylist of Transition). The start
+ // state of the constructed DFA is the epsilon closure of s0, and
+ // its transition relation is a dictionary mapping a composite state
+ // (a set of ints) to a dictionary mapping a label (a string) to a
+ // composite state (a set of ints).
+
+ static IDictionary<Set<int>, IDictionary<String, Set<int>>>
+ CompositeDfaTrans(int s0, IDictionary<int, ArrayList<Transition>> trans) {
+ Set<int> S0 = EpsilonClose(new Set<int>(s0), trans);
+ IQueue<Set<int>> worklist = new CircularQueue<Set<int>>();
+ worklist.Enqueue(S0);
+ // The transition relation of the DFA
+ IDictionary<Set<int>, IDictionary<String, Set<int>>> res =
+ new HashDictionary<Set<int>, IDictionary<String, Set<int>>>();
+ while (!worklist.IsEmpty) {
+ Set<int> S = worklist.Dequeue();
+ if (!res.Contains(S)) {
+ // The S -lab-> T transition relation being constructed for a given S
+ IDictionary<String, Set<int>> STrans =
+ new HashDictionary<String, Set<int>>();
+ // For all s in S, consider all transitions s -lab-> t
+ foreach (int s in S) {
+ // For all non-epsilon transitions s -lab-> t, add t to T
+ foreach (Transition tr in trans[s]) {
+ if (tr.lab != null) { // Non-epsilon transition
+ Set<int> toState;
+ if (STrans.Contains(tr.lab)) // Already a transition on lab
+ toState = STrans[tr.lab];
+ else { // No transitions on lab yet
+ toState = new Set<int>();
+ STrans.Add(tr.lab, toState);
+ }
+ toState.Add(tr.target);
+ }
+ }
+ }
+ // Epsilon-close all T such that S -lab-> T, and put on worklist
+ IDictionary<String, Set<int>> STransClosed =
+ new HashDictionary<String, Set<int>>();
+ foreach (KeyValuePair<String, Set<int>> entry in STrans) {
+ Set<int> Tclose = EpsilonClose(entry.Value, trans);
+ STransClosed.Add(entry.Key, Tclose);
+ worklist.Enqueue(Tclose);
+ }
+ res.Add(S, STransClosed);
+ }
+ }
+ return res;
+ }
+
+ // Compute epsilon-closure of state set S in transition relation trans.
+
+ static Set<int>
+ EpsilonClose(Set<int> S, IDictionary<int, ArrayList<Transition>> trans) {
+ // The worklist initially contains all S members
+ IQueue<int> worklist = new CircularQueue<int>();
+ S.Apply(worklist.Enqueue);
+ Set<int> res = new Set<int>(S);
+ while (!worklist.IsEmpty) {
+ int s = worklist.Dequeue();
+ foreach (Transition tr in trans[s]) {
+ if (tr.lab == null && !res.Contains(tr.target)) {
+ res.Add(tr.target);
+ worklist.Enqueue(tr.target);
+ }
+ }
+ }
+ return res;
+ }
+
+ // Compute a renamer, which is a dictionary mapping set of int to int
+
+ static IDictionary<Set<int>, int> MkRenamer(ICollectionValue<Set<int>> states)
+ {
+ IDictionary<Set<int>, int> renamer = new HashDictionary<Set<int>, int>();
+ int count = 0;
+ foreach (Set<int> k in states)
+ renamer.Add(k, count++);
+ return renamer;
+ }
+
+ // Using a renamer (a dictionary mapping set of int to int), replace
+ // composite (set of int) states with simple (int) states in the
+ // transition relation trans, which is a dictionary mapping set of
+ // int to a dictionary mapping from string to set of int. The
+ // result is a dictionary mapping from int to a dictionary mapping
+ // from string to int.
+
+ static IDictionary<int, IDictionary<String, int>>
+ Rename(IDictionary<Set<int>, int> renamer,
+ IDictionary<Set<int>, IDictionary<String, Set<int>>> trans)
+ {
+ IDictionary<int, IDictionary<String, int>> newtrans =
+ new HashDictionary<int, IDictionary<String, int>>();
+ foreach (KeyValuePair<Set<int>, IDictionary<String, Set<int>>> entry
+ in trans) {
+ Set<int> k = entry.Key;
+ IDictionary<String, int> newktrans = new HashDictionary<String, int>();
+ foreach (KeyValuePair<String, Set<int>> tr in entry.Value)
+ newktrans.Add(tr.Key, renamer[tr.Value]);
+ newtrans.Add(renamer[k], newktrans);
+ }
+ return newtrans;
+ }
+
+ static Set<int> AcceptStates(ICollectionValue<Set<int>> states,
+ IDictionary<Set<int>, int> renamer,
+ int exit)
+ {
+ Set<int> acceptStates = new Set<int>();
+ foreach (Set<int> state in states)
+ if (state.Contains(exit))
+ acceptStates.Add(renamer[state]);
+ return acceptStates;
+ }
+
+ public Dfa ToDfa() {
+ IDictionary<Set<int>, IDictionary<String, Set<int>>>
+ cDfaTrans = CompositeDfaTrans(startState, trans);
+ Set<int> cDfaStart = EpsilonClose(new Set<int>(startState), trans);
+ ICollectionValue<Set<int>> cDfaStates = cDfaTrans.Keys;
+ IDictionary<Set<int>, int> renamer = MkRenamer(cDfaStates);
+ IDictionary<int, IDictionary<String, int>> simpleDfaTrans =
+ Rename(renamer, cDfaTrans);
+ int simpleDfaStart = renamer[cDfaStart];
+ Set<int> simpleDfaAccept = AcceptStates(cDfaStates, renamer, exitState);
+ return new Dfa(simpleDfaStart, simpleDfaAccept, simpleDfaTrans);
+ }
+
+ // Nested class for creating distinctly named states when constructing NFAs
+
+ public class NameSource {
+ private static int nextName = 0;
+
+ public int next() {
+ return nextName++;
+ }
+ }
+
+ // Write an input file for the dot program. You can find dot at
+ // http://www.research.att.com/sw/tools/graphviz/
+
+ public void WriteDot(String filename) {
+ TextWriter wr =
+ new StreamWriter(new FileStream(filename, FileMode.Create,
+ FileAccess.Write));
+ wr.WriteLine("// Format this file as a Postscript file with ");
+ wr.WriteLine("// dot " + filename + " -Tps -o out.ps\n");
+ wr.WriteLine("digraph nfa {");
+ wr.WriteLine("size=\"11,8.25\";");
+ wr.WriteLine("rotate=90;");
+ wr.WriteLine("rankdir=LR;");
+ wr.WriteLine("start [style=invis];"); // Invisible start node
+ wr.WriteLine("start -> d" + startState); // Edge into start state
+
+ // The accept state has a double circle
+ wr.WriteLine("d" + exitState + " [peripheries=2];");
+
+ // The transitions
+ foreach (KeyValuePair<int, ArrayList<Transition>> entry in trans) {
+ int s1 = entry.Key;
+ foreach (Transition s1Trans in entry.Value) {
+ String lab = s1Trans.lab ?? "eps";
+ int s2 = s1Trans.target;
+ wr.WriteLine("d" + s1 + " -> d" + s2 + " [label=\"" + lab + "\"];");
+ }
+ }
+ wr.WriteLine("}");
+ wr.Close();
+ }
+ }
+
+// Class Transition, a transition from one state to another ----------
+
+ public class Transition {
+ public readonly String lab;
+ public readonly int target;
+
+ public Transition(String lab, int target) {
+ this.lab = lab; this.target = target;
+ }
+
+ public override String ToString() {
+ return "-" + lab + "-> " + target;
+ }
+ }
+
+// Class Dfa, deterministic finite automata --------------------------
+
+/*
+ A deterministic finite automaton (DFA) is represented as a
+ dictionary mapping state number (int) to a dictionary mapping label
+ (a non-null string) to a target state (an int).
+*/
+
+ class Dfa {
+ private readonly int startState;
+ private readonly Set<int> acceptStates;
+ private readonly IDictionary<int, IDictionary<String, int>> trans;
+
+ public Dfa(int startState, Set<int> acceptStates,
+ IDictionary<int, IDictionary<String, int>> trans)
+ {
+ this.startState = startState;
+ this.acceptStates = acceptStates;
+ this.trans = trans;
+ }
+
+ public int Start { get { return startState; } }
+
+ public Set<int> Accept { get { return acceptStates; } }
+
+ public IDictionary<int, IDictionary<String, int>> Trans {
+ get { return trans; }
+ }
+
+ public override String ToString() {
+ return "DFA start=" + startState + "\naccept=" + acceptStates;
+ }
+
+ // Write an input file for the dot program. You can find dot at
+ // http://www.research.att.com/sw/tools/graphviz/
+
+ public void WriteDot(String filename) {
+ TextWriter wr =
+ new StreamWriter(new FileStream(filename, FileMode.Create,
+ FileAccess.Write));
+ wr.WriteLine("// Format this file as a Postscript file with ");
+ wr.WriteLine("// dot " + filename + " -Tps -o out.ps\n");
+ wr.WriteLine("digraph dfa {");
+ wr.WriteLine("size=\"11,8.25\";");
+ wr.WriteLine("rotate=90;");
+ wr.WriteLine("rankdir=LR;");
+ wr.WriteLine("start [style=invis];"); // Invisible start node
+ wr.WriteLine("start -> d" + startState); // Edge into start state
+
+ // Accept states are double circles
+ foreach (int state in trans.Keys)
+ if (acceptStates.Contains(state))
+ wr.WriteLine("d" + state + " [peripheries=2];");
+
+ // The transitions
+ foreach (KeyValuePair<int, IDictionary<String, int>> entry in trans) {
+ int s1 = entry.Key;
+ foreach (KeyValuePair<String, int> s1Trans in entry.Value) {
+ String lab = s1Trans.Key;
+ int s2 = s1Trans.Value;
+ wr.WriteLine("d" + s1 + " -> d" + s2 + " [label=\"" + lab + "\"];");
+ }
+ }
+ wr.WriteLine("}");
+ wr.Close();
+ }
+ }
+
+// Regular expressions ----------------------------------------------
+//
+// Abstract syntax of regular expressions
+// r ::= A | r1 r2 | (r1|r2) | r*
+//
+
+ abstract class Regex {
+ abstract public Nfa MkNfa(Nfa.NameSource names);
+ }
+
+ class Eps : Regex {
+ // The resulting nfa0 has form s0s -eps-> s0e
+
+ public override Nfa MkNfa(Nfa.NameSource names) {
+ int s0s = names.next();
+ int s0e = names.next();
+ Nfa nfa0 = new Nfa(s0s, s0e);
+ nfa0.AddTrans(s0s, null, s0e);
+ return nfa0;
+ }
+ }
+
+ class Sym : Regex {
+ String sym;
+
+ public Sym(String sym) {
+ this.sym = sym;
+ }
+
+ // The resulting nfa0 has form s0s -sym-> s0e
+
+ public override Nfa MkNfa(Nfa.NameSource names) {
+ int s0s = names.next();
+ int s0e = names.next();
+ Nfa nfa0 = new Nfa(s0s, s0e);
+ nfa0.AddTrans(s0s, sym, s0e);
+ return nfa0;
+ }
+ }
+
+ class Seq : Regex {
+ Regex r1, r2;
+
+ public Seq(Regex r1, Regex r2) {
+ this.r1 = r1; this.r2 = r2;
+ }
+
+ // If nfa1 has form s1s ----> s1e
+ // and nfa2 has form s2s ----> s2e
+ // then nfa0 has form s1s ----> s1e -eps-> s2s ----> s2e
+
+ public override Nfa MkNfa(Nfa.NameSource names) {
+ Nfa nfa1 = r1.MkNfa(names);
+ Nfa nfa2 = r2.MkNfa(names);
+ Nfa nfa0 = new Nfa(nfa1.Start, nfa2.Exit);
+ foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa1.Trans)
+ nfa0.AddTrans(entry);
+ foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa2.Trans)
+ nfa0.AddTrans(entry);
+ nfa0.AddTrans(nfa1.Exit, null, nfa2.Start);
+ return nfa0;
+ }
+ }
+
+ class Alt : Regex {
+ Regex r1, r2;
+
+ public Alt(Regex r1, Regex r2) {
+ this.r1 = r1; this.r2 = r2;
+ }
+
+ // If nfa1 has form s1s ----> s1e
+ // and nfa2 has form s2s ----> s2e
+ // then nfa0 has form s0s -eps-> s1s ----> s1e -eps-> s0e
+ // s0s -eps-> s2s ----> s2e -eps-> s0e
+
+ public override Nfa MkNfa(Nfa.NameSource names) {
+ Nfa nfa1 = r1.MkNfa(names);
+ Nfa nfa2 = r2.MkNfa(names);
+ int s0s = names.next();
+ int s0e = names.next();
+ Nfa nfa0 = new Nfa(s0s, s0e);
+ foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa1.Trans)
+ nfa0.AddTrans(entry);
+ foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa2.Trans)
+ nfa0.AddTrans(entry);
+ nfa0.AddTrans(s0s, null, nfa1.Start);
+ nfa0.AddTrans(s0s, null, nfa2.Start);
+ nfa0.AddTrans(nfa1.Exit, null, s0e);
+ nfa0.AddTrans(nfa2.Exit, null, s0e);
+ return nfa0;
+ }
+ }
+
+ class Star : Regex {
+ Regex r;
+
+ public Star(Regex r) {
+ this.r = r;
+ }
+
+ // If nfa1 has form s1s ----> s1e
+ // then nfa0 has form s0s ----> s0s
+ // s0s -eps-> s1s
+ // s1e -eps-> s0s
+
+ public override Nfa MkNfa(Nfa.NameSource names) {
+ Nfa nfa1 = r.MkNfa(names);
+ int s0s = names.next();
+ Nfa nfa0 = new Nfa(s0s, s0s);
+ foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa1.Trans)
+ nfa0.AddTrans(entry);
+ nfa0.AddTrans(s0s, null, nfa1.Start);
+ nfa0.AddTrans(nfa1.Exit, null, s0s);
+ return nfa0;
+ }
+ }
+
+// Trying the RE->NFA->DFA translation on three regular expressions
+
+ class TestNFA {
+ public static void Main(String[] args) {
+ Regex a = new Sym("A");
+ Regex b = new Sym("B");
+ Regex c = new Sym("C");
+ Regex abStar = new Star(new Alt(a, b));
+ Regex bb = new Seq(b, b);
+ Regex r = new Seq(abStar, new Seq(a, b));
+ // The regular expression (a|b)*ab
+ BuildAndShow("ex1", r);
+ // The regular expression ((a|b)*ab)*
+ BuildAndShow("ex2", new Star(r));
+ // The regular expression ((a|b)*ab)((a|b)*ab)
+ BuildAndShow("ex3", new Seq(r, r));
+ // The regular expression (a|b)*abb, from ASU 1986 p 136
+ BuildAndShow("ex4", new Seq(abStar, new Seq(a, bb)));
+ // SML reals: sign?((digit+(\.digit+)?))([eE]sign?digit+)?
+ Regex d = new Sym("digit");
+ Regex dPlus = new Seq(d, new Star(d));
+ Regex s = new Sym("sign");
+ Regex sOpt = new Alt(s, new Eps());
+ Regex dot = new Sym(".");
+ Regex dotDigOpt = new Alt(new Eps(), new Seq(dot, dPlus));
+ Regex mant = new Seq(sOpt, new Seq(dPlus, dotDigOpt));
+ Regex e = new Sym("e");
+ Regex exp = new Alt(new Eps(), new Seq(e, new Seq(sOpt, dPlus)));
+ Regex smlReal = new Seq(mant, exp);
+ BuildAndShow("ex5", smlReal);
+ }
+
+ public static void BuildAndShow(String fileprefix, Regex r) {
+ Nfa nfa = r.MkNfa(new Nfa.NameSource());
+ Console.WriteLine(nfa);
+ Console.WriteLine("Writing NFA graph to file");
+ nfa.WriteDot(fileprefix + "nfa.dot");
+ Console.WriteLine("---");
+ Dfa dfa = nfa.ToDfa();
+ Console.WriteLine(dfa);
+ Console.WriteLine("Writing DFA graph to file");
+ dfa.WriteDot(fileprefix + "dfa.dot");
+ Console.WriteLine();
+ }
+ }
+}
projects / mono.git / blobdiff