mcs/class/Mono.C5/UserGuideExamples/GNfaToDfa.cs

   1 /*\r
   2  Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft\r
   3  Permission is hereby granted, free of charge, to any person obtaining a copy\r
   4  of this software and associated documentation files (the "Software"), to deal\r
   5  in the Software without restriction, including without limitation the rights\r
   6  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
   7  copies of the Software, and to permit persons to whom the Software is\r
   8  furnished to do so, subject to the following conditions:\r
   9  \r
  10  The above copyright notice and this permission notice shall be included in\r
  11  all copies or substantial portions of the Software.\r
  12  \r
  13  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
  14  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
  15  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
  16  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
  17  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
  18  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
  19  SOFTWARE.\r
  20 */\r
  21 \r
  22 // Compile with \r
  23 //    csc /r:C5.dll GNfaToDfa.cs\r
  24 \r
  25 // C5 examples: RegExp -> NFA -> DFA -> Graph\r
  26 // Java 2000-10-07, GC# 2001-10-23, C# 2.0 2003-09-03, C# 2.0+C5 2004-08-08\r
  27 \r
  28 // This file contains, in order:\r
  29 //   * Helper class Set<T> defined in terms of C5 classes.\r
  30 //   * A class Nfa for representing an NFA (a nondeterministic finite \r
  31 //     automaton), and for converting it to a DFA (a deterministic \r
  32 //     finite automaton).  Most complexity is in this class.\r
  33 //   * A class Dfa for representing a DFA, a deterministic finite \r
  34 //     automaton, and for writing a dot input file representing the DFA.\r
  35 //   * Classes for representing regular expressions, and for building an \r
  36 //     NFA from a regular expression\r
  37 //   * A test class that creates an NFA, a DFA, and a dot input file \r
  38 //     for a number of small regular expressions.  The DFAs are \r
  39 //     not minimized.\r
  40 \r
  41 using System;\r
  42 using System.Text;\r
  43 using System.IO;\r
  44 using C5;\r
  45 using SCG = System.Collections.Generic;\r
  46 \r
  47 namespace GNfaToDfa\r
  48 {\r
  49 \r
  50   public class Set<T> : HashSet<T> {\r
  51     public Set(SCG.IEnumerable<T> enm) : base() {\r
  52       AddAll(enm);\r
  53     }\r
  54 \r
  55     public Set(params T[] elems) : this((SCG.IEnumerable<T>)elems) { }\r
  56 \r
  57     // Set union (+), difference (-), and intersection (*):\r
  58 \r
  59     public static Set<T> operator +(Set<T> s1, Set<T> s2) {\r
  60       if (s1 == null || s2 == null) \r
  61         throw new ArgumentNullException("Set+Set");\r
  62       else {\r
  63         Set<T> res = new Set<T>(s1);\r
  64         res.AddAll(s2);\r
  65         return res;\r
  66       }\r
  67     }\r
  68 \r
  69     public static Set<T> operator -(Set<T> s1, Set<T> s2) {\r
  70       if (s1 == null || s2 == null) \r
  71         throw new ArgumentNullException("Set-Set");\r
  72       else {\r
  73         Set<T> res = new Set<T>(s1);\r
  74         res.RemoveAll(s2);\r
  75         return res;\r
  76       }\r
  77     }\r
  78 \r
  79     public static Set<T> operator *(Set<T> s1, Set<T> s2) {\r
  80       if (s1 == null || s2 == null) \r
  81         throw new ArgumentNullException("Set*Set");\r
  82       else {\r
  83         Set<T> res = new Set<T>(s1);\r
  84         res.RetainAll(s2);\r
  85         return res;\r
  86       }\r
  87     }\r
  88 \r
  89     // Equality of sets; take care to avoid infinite loops\r
  90 \r
  91     public static bool operator ==(Set<T> s1, Set<T> s2) {\r
  92       return EqualityComparer<Set<T>>.Default.Equals(s1, s2);\r
  93     }\r
  94 \r
  95     public static bool operator !=(Set<T> s1, Set<T> s2) {\r
  96       return !(s1 == s2);\r
  97     }\r
  98 \r
  99     public override bool Equals(Object that) {\r
 100       return this == (that as Set<T>);\r
 101     }\r
 102 \r
 103     public override int GetHashCode() {\r
 104       return EqualityComparer<Set<T>>.Default.GetHashCode(this);\r
 105     }\r
 106 \r
 107     // Subset (<=) and superset (>=) relation:\r
 108 \r
 109     public static bool operator <=(Set<T> s1, Set<T> s2) {\r
 110       if (s1 == null || s2 == null) \r
 111         throw new ArgumentNullException("Set<=Set");\r
 112       else\r
 113         return s1.ContainsAll(s2);\r
 114     }\r
 115 \r
 116     public static bool operator >=(Set<T> s1, Set<T> s2) {\r
 117       if (s1 == null || s2 == null) \r
 118         throw new ArgumentNullException("Set>=Set");\r
 119       else\r
 120         return s2.ContainsAll(s1);\r
 121     }\r
 122     \r
 123     public override String ToString() {\r
 124       StringBuilder sb = new StringBuilder();\r
 125       sb.Append("{");\r
 126       bool first = true;\r
 127       foreach (T x in this) {\r
 128         if (!first)\r
 129           sb.Append(",");\r
 130         sb.Append(x);\r
 131         first = false;\r
 132       }\r
 133       sb.Append("}");\r
 134       return sb.ToString();\r
 135     }\r
 136   }\r
 137 \r
 138 // ----------------------------------------------------------------------\r
 139 \r
 140 // Regular expressions, NFAs, DFAs, and dot graphs\r
 141 // sestoft@dina.kvl.dk * \r
 142 // Java 2001-07-10 * C# 2001-10-22 * Gen C# 2001-10-23, 2003-09-03\r
 143 \r
 144 // In the Generic C# 2.0 version we \r
 145 //  use Queue<int> and Queue<Set<int>> for worklists\r
 146 //  use Set<int> for pre-DFA states\r
 147 //  use ArrayList<Transition> for NFA transition relations\r
 148 //  use HashDictionary<Set<int>, HashDictionary<String, Set<int>>>\r
 149 //  and HashDictionary<int, HashDictionary<String, int>> for DFA transition relations\r
 150 \r
 151 /* Class Nfa and conversion from NFA to DFA ---------------------------\r
 152 \r
 153   A nondeterministic finite automaton (NFA) is represented as a\r
 154   dictionary mapping a state number (int) to an arraylist of\r
 155   Transitions, a Transition being a pair of a label lab (a string,\r
 156   null meaning epsilon) and a target state (an int).\r
 157 \r
 158   A DFA is created from an NFA in two steps:\r
 159 \r
 160     (1) Construct a DFA whose each of whose states is composite,\r
 161         namely a set of NFA states (Set of int).  This is done by\r
 162         methods CompositeDfaTrans and EpsilonClose.\r
 163 \r
 164     (2) Replace composite states (Set of int) by simple states\r
 165         (int).  This is done by methods Rename and MkRenamer.\r
 166 \r
 167   Method CompositeDfaTrans works as follows: \r
 168 \r
 169     Create the epsilon-closure S0 (a Set of ints) of the start state\r
 170     s0, and put it in a worklist (a Queue).  Create an empty DFA\r
 171     transition relation, which is a dictionary mapping a composite\r
 172     state (an epsilon-closed set of ints) to a dictionary mapping a\r
 173     label (a non-null string) to a composite state.\r
 174 \r
 175     Repeatedly choose a composite state S from the worklist.  If it is\r
 176     not already in the keyset of the DFA transition relation, compute\r
 177     for every non-epsilon label lab the set T of states reachable by\r
 178     that label from some state s in S.  Compute the epsilon-closure\r
 179     Tclose of every such state T and put it on the worklist.  Then add\r
 180     the transition S -lab-> Tclose to the DFA transition relation, for\r
 181     every lab.\r
 182 \r
 183   Method EpsilonClose works as follows: \r
 184 \r
 185     Given a set S of states.  Put the states of S in a worklist.\r
 186     Repeatedly choose a state s from the worklist, and consider all\r
 187     epsilon-transitions s -eps-> s' from s.  If s' is in S already,\r
 188     then do nothing; otherwise add s' to S and the worklist.  When the\r
 189     worklist is empty, S is epsilon-closed; return S.\r
 190 \r
 191   Method MkRenamer works as follows: \r
 192 \r
 193     Given a dictionary mapping a set of int to something, create an\r
 194     injective dictionary mapping from set of int to int, by choosing a\r
 195     fresh int for every key in the given dictionary.\r
 196 \r
 197   Method Rename works as follows:\r
 198 \r
 199     Given a dictionary mapping a set of int to a dictionary mapping a\r
 200     string to set of int, use the result of MkRenamer to replace all\r
 201     sets of ints by ints.\r
 202 \r
 203 */\r
 204 \r
 205   class Nfa {\r
 206     private readonly int startState;\r
 207     private readonly int exitState;    // This is the unique accept state\r
 208     private readonly IDictionary<int, ArrayList<Transition>> trans;\r
 209 \r
 210     public Nfa(int startState, int exitState) {\r
 211       this.startState = startState; this.exitState = exitState;\r
 212       trans = new HashDictionary<int, ArrayList<Transition>>();\r
 213       if (!startState.Equals(exitState))\r
 214         trans.Add(exitState, new ArrayList<Transition>());\r
 215     }\r
 216 \r
 217     public int Start { get { return startState; } }\r
 218 \r
 219     public int Exit { get { return exitState; } }\r
 220 \r
 221     public IDictionary<int, ArrayList<Transition>> Trans {\r
 222       get { return trans; }\r
 223     }\r
 224 \r
 225     public void AddTrans(int s1, String lab, int s2) {\r
 226       ArrayList<Transition> s1Trans;\r
 227       if (trans.Contains(s1))\r
 228         s1Trans = trans[s1];\r
 229       else {\r
 230         s1Trans = new ArrayList<Transition>();\r
 231         trans.Add(s1, s1Trans);\r
 232       }\r
 233       s1Trans.Add(new Transition(lab, s2));\r
 234     }\r
 235 \r
 236     public void AddTrans(KeyValuePair<int, ArrayList<Transition>> tr) {\r
 237       // Assumption: if tr is in trans, it maps to an empty list (end state)\r
 238       trans.Remove(tr.Key);\r
 239       trans.Add(tr.Key, tr.Value);\r
 240     }\r
 241 \r
 242     public override String ToString() {\r
 243       return "NFA start=" + startState + " exit=" + exitState;\r
 244     }\r
 245 \r
 246     // Construct the transition relation of a composite-state DFA from\r
 247     // an NFA with start state s0 and transition relation trans (a\r
 248     // dictionary mapping int to arraylist of Transition).  The start\r
 249     // state of the constructed DFA is the epsilon closure of s0, and\r
 250     // its transition relation is a dictionary mapping a composite state\r
 251     // (a set of ints) to a dictionary mapping a label (a string) to a\r
 252     // composite state (a set of ints).\r
 253 \r
 254     static IDictionary<Set<int>, IDictionary<String, Set<int>>>\r
 255       CompositeDfaTrans(int s0, IDictionary<int, ArrayList<Transition>> trans) {\r
 256       Set<int> S0 = EpsilonClose(new Set<int>(s0), trans);\r
 257       IQueue<Set<int>> worklist = new CircularQueue<Set<int>>();\r
 258       worklist.Enqueue(S0);\r
 259       // The transition relation of the DFA\r
 260       IDictionary<Set<int>, IDictionary<String, Set<int>>> res =\r
 261         new HashDictionary<Set<int>, IDictionary<String, Set<int>>>();\r
 262       while (!worklist.IsEmpty) {\r
 263         Set<int> S = worklist.Dequeue();\r
 264         if (!res.Contains(S)) {\r
 265           // The S -lab-> T transition relation being constructed for a given S\r
 266           IDictionary<String, Set<int>> STrans =\r
 267             new HashDictionary<String, Set<int>>();\r
 268           // For all s in S, consider all transitions s -lab-> t\r
 269           foreach (int s in S) {\r
 270             // For all non-epsilon transitions s -lab-> t, add t to T\r
 271             foreach (Transition tr in trans[s]) {\r
 272               if (tr.lab != null) {        // Non-epsilon transition\r
 273                 Set<int> toState;\r
 274                 if (STrans.Contains(tr.lab))   // Already a transition on lab\r
 275                   toState = STrans[tr.lab];\r
 276                 else {                         // No transitions on lab yet\r
 277                   toState = new Set<int>();\r
 278                   STrans.Add(tr.lab, toState);\r
 279                 }\r
 280                 toState.Add(tr.target);\r
 281               }\r
 282             }\r
 283           }\r
 284           // Epsilon-close all T such that S -lab-> T, and put on worklist\r
 285           IDictionary<String, Set<int>> STransClosed =\r
 286             new HashDictionary<String, Set<int>>();\r
 287           foreach (KeyValuePair<String, Set<int>> entry in STrans) {\r
 288             Set<int> Tclose = EpsilonClose(entry.Value, trans);\r
 289             STransClosed.Add(entry.Key, Tclose);\r
 290             worklist.Enqueue(Tclose);\r
 291           }\r
 292           res.Add(S, STransClosed);\r
 293         }\r
 294       }\r
 295       return res;\r
 296     }\r
 297 \r
 298     // Compute epsilon-closure of state set S in transition relation trans.  \r
 299 \r
 300     static Set<int>\r
 301       EpsilonClose(Set<int> S, IDictionary<int, ArrayList<Transition>> trans) {\r
 302       // The worklist initially contains all S members\r
 303       IQueue<int> worklist = new CircularQueue<int>();\r
 304       S.Apply(worklist.Enqueue);\r
 305       Set<int> res = new Set<int>(S);\r
 306       while (!worklist.IsEmpty) {\r
 307         int s = worklist.Dequeue();\r
 308         foreach (Transition tr in trans[s]) {\r
 309           if (tr.lab == null && !res.Contains(tr.target)) {\r
 310             res.Add(tr.target);\r
 311             worklist.Enqueue(tr.target);\r
 312           }\r
 313         }\r
 314       }\r
 315       return res;\r
 316     }\r
 317 \r
 318     // Compute a renamer, which is a dictionary mapping set of int to int\r
 319 \r
 320     static IDictionary<Set<int>, int> MkRenamer(ICollectionValue<Set<int>> states)\r
 321     {\r
 322       IDictionary<Set<int>, int> renamer = new HashDictionary<Set<int>, int>();\r
 323       int count = 0;\r
 324       foreach (Set<int> k in states)\r
 325         renamer.Add(k, count++);\r
 326       return renamer;\r
 327     }\r
 328 \r
 329     // Using a renamer (a dictionary mapping set of int to int), replace\r
 330     // composite (set of int) states with simple (int) states in the\r
 331     // transition relation trans, which is a dictionary mapping set of\r
 332     // int to a dictionary mapping from string to set of int.  The\r
 333     // result is a dictionary mapping from int to a dictionary mapping\r
 334     // from string to int.\r
 335 \r
 336     static IDictionary<int, IDictionary<String, int>>\r
 337       Rename(IDictionary<Set<int>, int> renamer,\r
 338              IDictionary<Set<int>, IDictionary<String, Set<int>>> trans)\r
 339     {\r
 340       IDictionary<int, IDictionary<String, int>> newtrans =\r
 341         new HashDictionary<int, IDictionary<String, int>>();\r
 342       foreach (KeyValuePair<Set<int>, IDictionary<String, Set<int>>> entry\r
 343          in trans) {\r
 344         Set<int> k = entry.Key;\r
 345         IDictionary<String, int> newktrans = new HashDictionary<String, int>();\r
 346         foreach (KeyValuePair<String, Set<int>> tr in entry.Value)\r
 347           newktrans.Add(tr.Key, renamer[tr.Value]);\r
 348         newtrans.Add(renamer[k], newktrans);\r
 349       }\r
 350       return newtrans;\r
 351     }\r
 352 \r
 353     static Set<int> AcceptStates(ICollectionValue<Set<int>> states,\r
 354                IDictionary<Set<int>, int> renamer,\r
 355                int exit)\r
 356     {\r
 357       Set<int> acceptStates = new Set<int>();\r
 358       foreach (Set<int> state in states)\r
 359         if (state.Contains(exit))\r
 360           acceptStates.Add(renamer[state]);\r
 361       return acceptStates;\r
 362     }\r
 363 \r
 364     public Dfa ToDfa() {\r
 365       IDictionary<Set<int>, IDictionary<String, Set<int>>>\r
 366         cDfaTrans = CompositeDfaTrans(startState, trans);\r
 367       Set<int> cDfaStart = EpsilonClose(new Set<int>(startState), trans);\r
 368       ICollectionValue<Set<int>> cDfaStates = cDfaTrans.Keys;\r
 369       IDictionary<Set<int>, int> renamer = MkRenamer(cDfaStates);\r
 370       IDictionary<int, IDictionary<String, int>> simpleDfaTrans =\r
 371         Rename(renamer, cDfaTrans);\r
 372       int simpleDfaStart = renamer[cDfaStart];\r
 373       Set<int> simpleDfaAccept = AcceptStates(cDfaStates, renamer, exitState);\r
 374       return new Dfa(simpleDfaStart, simpleDfaAccept, simpleDfaTrans);\r
 375     }\r
 376 \r
 377     // Nested class for creating distinctly named states when constructing NFAs\r
 378 \r
 379     public class NameSource {\r
 380       private static int nextName = 0;\r
 381 \r
 382       public int next() {\r
 383         return nextName++;\r
 384       }\r
 385     }\r
 386 \r
 387     // Write an input file for the dot program.  You can find dot at\r
 388     // http://www.research.att.com/sw/tools/graphviz/\r
 389 \r
 390     public void WriteDot(String filename) {\r
 391       TextWriter wr =\r
 392         new StreamWriter(new FileStream(filename, FileMode.Create,\r
 393                                         FileAccess.Write));\r
 394       wr.WriteLine("// Format this file as a Postscript file with ");\r
 395       wr.WriteLine("//    dot " + filename + " -Tps -o out.ps\n");\r
 396       wr.WriteLine("digraph nfa {");\r
 397       wr.WriteLine("size=\"11,8.25\";");\r
 398       wr.WriteLine("rotate=90;");\r
 399       wr.WriteLine("rankdir=LR;");\r
 400       wr.WriteLine("start [style=invis];");    // Invisible start node\r
 401       wr.WriteLine("start -> d" + startState); // Edge into start state\r
 402 \r
 403       // The accept state has a double circle\r
 404       wr.WriteLine("d" + exitState + " [peripheries=2];");\r
 405 \r
 406       // The transitions \r
 407       foreach (KeyValuePair<int, ArrayList<Transition>> entry in trans) {\r
 408         int s1 = entry.Key;\r
 409         foreach (Transition s1Trans in entry.Value) {\r
 410           String lab = s1Trans.lab ?? "eps";\r
 411           int s2 = s1Trans.target;\r
 412           wr.WriteLine("d" + s1 + " -> d" + s2 + " [label=\"" + lab + "\"];");\r
 413         }\r
 414       }\r
 415       wr.WriteLine("}");\r
 416       wr.Close();\r
 417     }\r
 418   }\r
 419 \r
 420 // Class Transition, a transition from one state to another ----------\r
 421 \r
 422   public class Transition {\r
 423     public readonly String lab;\r
 424     public readonly int target;\r
 425 \r
 426     public Transition(String lab, int target) {\r
 427       this.lab = lab; this.target = target;\r
 428     }\r
 429 \r
 430     public override String ToString() {\r
 431       return "-" + lab + "-> " + target;\r
 432     }\r
 433   }\r
 434 \r
 435 // Class Dfa, deterministic finite automata --------------------------\r
 436 \r
 437 /*\r
 438    A deterministic finite automaton (DFA) is represented as a\r
 439    dictionary mapping state number (int) to a dictionary mapping label\r
 440    (a non-null string) to a target state (an int).\r
 441 */\r
 442 \r
 443   class Dfa {\r
 444     private readonly int startState;\r
 445     private readonly Set<int> acceptStates;\r
 446     private readonly IDictionary<int, IDictionary<String, int>> trans;\r
 447 \r
 448     public Dfa(int startState, Set<int> acceptStates,\r
 449                IDictionary<int, IDictionary<String, int>> trans)\r
 450     {\r
 451       this.startState = startState;\r
 452       this.acceptStates = acceptStates;\r
 453       this.trans = trans;\r
 454     }\r
 455 \r
 456     public int Start { get { return startState; } }\r
 457 \r
 458     public Set<int> Accept { get { return acceptStates; } }\r
 459 \r
 460     public IDictionary<int, IDictionary<String, int>> Trans {\r
 461       get { return trans; }\r
 462     }\r
 463 \r
 464     public override String ToString() {\r
 465       return "DFA start=" + startState + "\naccept=" + acceptStates;\r
 466     }\r
 467 \r
 468     // Write an input file for the dot program.  You can find dot at\r
 469     // http://www.research.att.com/sw/tools/graphviz/\r
 470 \r
 471     public void WriteDot(String filename) {\r
 472       TextWriter wr =\r
 473         new StreamWriter(new FileStream(filename, FileMode.Create,\r
 474                                         FileAccess.Write));\r
 475       wr.WriteLine("// Format this file as a Postscript file with ");\r
 476       wr.WriteLine("//    dot " + filename + " -Tps -o out.ps\n");\r
 477       wr.WriteLine("digraph dfa {");\r
 478       wr.WriteLine("size=\"11,8.25\";");\r
 479       wr.WriteLine("rotate=90;");\r
 480       wr.WriteLine("rankdir=LR;");\r
 481       wr.WriteLine("start [style=invis];");    // Invisible start node\r
 482       wr.WriteLine("start -> d" + startState); // Edge into start state\r
 483 \r
 484       // Accept states are double circles\r
 485       foreach (int state in trans.Keys)\r
 486         if (acceptStates.Contains(state))\r
 487           wr.WriteLine("d" + state + " [peripheries=2];");\r
 488 \r
 489       // The transitions \r
 490       foreach (KeyValuePair<int, IDictionary<String, int>> entry in trans) {\r
 491         int s1 = entry.Key;\r
 492         foreach (KeyValuePair<String, int> s1Trans in entry.Value) {\r
 493           String lab = s1Trans.Key;\r
 494           int s2 = s1Trans.Value;\r
 495           wr.WriteLine("d" + s1 + " -> d" + s2 + " [label=\"" + lab + "\"];");\r
 496         }\r
 497       }\r
 498       wr.WriteLine("}");\r
 499       wr.Close();\r
 500     }\r
 501   }\r
 502 \r
 503 // Regular expressions ----------------------------------------------\r
 504 //\r
 505 // Abstract syntax of regular expressions\r
 506 //    r ::= A | r1 r2 | (r1|r2) | r*\r
 507 //\r
 508 \r
 509   abstract class Regex {\r
 510     abstract public Nfa MkNfa(Nfa.NameSource names);\r
 511   }\r
 512 \r
 513   class Eps : Regex {\r
 514     // The resulting nfa0 has form s0s -eps-> s0e\r
 515 \r
 516     public override Nfa MkNfa(Nfa.NameSource names) {\r
 517       int s0s = names.next();\r
 518       int s0e = names.next();\r
 519       Nfa nfa0 = new Nfa(s0s, s0e);\r
 520       nfa0.AddTrans(s0s, null, s0e);\r
 521       return nfa0;\r
 522     }\r
 523   }\r
 524 \r
 525   class Sym : Regex {\r
 526     String sym;\r
 527 \r
 528     public Sym(String sym) {\r
 529       this.sym = sym;\r
 530     }\r
 531 \r
 532     // The resulting nfa0 has form s0s -sym-> s0e\r
 533 \r
 534     public override Nfa MkNfa(Nfa.NameSource names) {\r
 535       int s0s = names.next();\r
 536       int s0e = names.next();\r
 537       Nfa nfa0 = new Nfa(s0s, s0e);\r
 538       nfa0.AddTrans(s0s, sym, s0e);\r
 539       return nfa0;\r
 540     }\r
 541   }\r
 542 \r
 543   class Seq : Regex {\r
 544     Regex r1, r2;\r
 545 \r
 546     public Seq(Regex r1, Regex r2) {\r
 547       this.r1 = r1; this.r2 = r2;\r
 548     }\r
 549 \r
 550     // If   nfa1 has form s1s ----> s1e \r
 551     // and  nfa2 has form s2s ----> s2e \r
 552     // then nfa0 has form s1s ----> s1e -eps-> s2s ----> s2e\r
 553 \r
 554     public override Nfa MkNfa(Nfa.NameSource names) {\r
 555       Nfa nfa1 = r1.MkNfa(names);\r
 556       Nfa nfa2 = r2.MkNfa(names);\r
 557       Nfa nfa0 = new Nfa(nfa1.Start, nfa2.Exit);\r
 558       foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa1.Trans)\r
 559         nfa0.AddTrans(entry);\r
 560       foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa2.Trans)\r
 561         nfa0.AddTrans(entry);\r
 562       nfa0.AddTrans(nfa1.Exit, null, nfa2.Start);\r
 563       return nfa0;\r
 564     }\r
 565   }\r
 566 \r
 567   class Alt : Regex {\r
 568     Regex r1, r2;\r
 569 \r
 570     public Alt(Regex r1, Regex r2) {\r
 571       this.r1 = r1; this.r2 = r2;\r
 572     }\r
 573 \r
 574     // If   nfa1 has form s1s ----> s1e \r
 575     // and  nfa2 has form s2s ----> s2e \r
 576     // then nfa0 has form s0s -eps-> s1s ----> s1e -eps-> s0e\r
 577     //                    s0s -eps-> s2s ----> s2e -eps-> s0e\r
 578 \r
 579     public override Nfa MkNfa(Nfa.NameSource names) {\r
 580       Nfa nfa1 = r1.MkNfa(names);\r
 581       Nfa nfa2 = r2.MkNfa(names);\r
 582       int s0s = names.next();\r
 583       int s0e = names.next();\r
 584       Nfa nfa0 = new Nfa(s0s, s0e);\r
 585       foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa1.Trans)\r
 586         nfa0.AddTrans(entry);\r
 587       foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa2.Trans)\r
 588         nfa0.AddTrans(entry);\r
 589       nfa0.AddTrans(s0s, null, nfa1.Start);\r
 590       nfa0.AddTrans(s0s, null, nfa2.Start);\r
 591       nfa0.AddTrans(nfa1.Exit, null, s0e);\r
 592       nfa0.AddTrans(nfa2.Exit, null, s0e);\r
 593       return nfa0;\r
 594     }\r
 595   }\r
 596 \r
 597   class Star : Regex {\r
 598     Regex r;\r
 599 \r
 600     public Star(Regex r) {\r
 601       this.r = r;\r
 602     }\r
 603 \r
 604     // If   nfa1 has form s1s ----> s1e \r
 605     // then nfa0 has form s0s ----> s0s\r
 606     //                    s0s -eps-> s1s\r
 607     //                    s1e -eps-> s0s\r
 608 \r
 609     public override Nfa MkNfa(Nfa.NameSource names) {\r
 610       Nfa nfa1 = r.MkNfa(names);\r
 611       int s0s = names.next();\r
 612       Nfa nfa0 = new Nfa(s0s, s0s);\r
 613       foreach (KeyValuePair<int, ArrayList<Transition>> entry in nfa1.Trans)\r
 614         nfa0.AddTrans(entry);\r
 615       nfa0.AddTrans(s0s, null, nfa1.Start);\r
 616       nfa0.AddTrans(nfa1.Exit, null, s0s);\r
 617       return nfa0;\r
 618     }\r
 619   }\r
 620 \r
 621 // Trying the RE->NFA->DFA translation on three regular expressions\r
 622 \r
 623   class TestNFA {\r
 624     public static void Main(String[] args) {\r
 625       Regex a = new Sym("A");\r
 626       Regex b = new Sym("B");\r
 627       Regex c = new Sym("C");\r
 628       Regex abStar = new Star(new Alt(a, b));\r
 629       Regex bb = new Seq(b, b);\r
 630       Regex r = new Seq(abStar, new Seq(a, b));\r
 631       // The regular expression (a|b)*ab\r
 632       BuildAndShow("ex1", r);\r
 633       // The regular expression ((a|b)*ab)*\r
 634       BuildAndShow("ex2", new Star(r));\r
 635       // The regular expression ((a|b)*ab)((a|b)*ab)\r
 636       BuildAndShow("ex3", new Seq(r, r));\r
 637       // The regular expression (a|b)*abb, from ASU 1986 p 136\r
 638       BuildAndShow("ex4", new Seq(abStar, new Seq(a, bb)));\r
 639       // SML reals: sign?((digit+(\.digit+)?))([eE]sign?digit+)?\r
 640       Regex d = new Sym("digit");\r
 641       Regex dPlus = new Seq(d, new Star(d));\r
 642       Regex s = new Sym("sign");\r
 643       Regex sOpt = new Alt(s, new Eps());\r
 644       Regex dot = new Sym(".");\r
 645       Regex dotDigOpt = new Alt(new Eps(), new Seq(dot, dPlus));\r
 646       Regex mant = new Seq(sOpt, new Seq(dPlus, dotDigOpt));\r
 647       Regex e = new Sym("e");\r
 648       Regex exp = new Alt(new Eps(), new Seq(e, new Seq(sOpt, dPlus)));\r
 649       Regex smlReal = new Seq(mant, exp);\r
 650       BuildAndShow("ex5", smlReal);\r
 651     }\r
 652 \r
 653     public static void BuildAndShow(String fileprefix, Regex r) {\r
 654       Nfa nfa = r.MkNfa(new Nfa.NameSource());\r
 655       Console.WriteLine(nfa);\r
 656       Console.WriteLine("Writing NFA graph to file");\r
 657       nfa.WriteDot(fileprefix + "nfa.dot");\r
 658       Console.WriteLine("---");\r
 659       Dfa dfa = nfa.ToDfa();\r
 660       Console.WriteLine(dfa);\r
 661       Console.WriteLine("Writing DFA graph to file");\r
 662       dfa.WriteDot(fileprefix + "dfa.dot");\r
 663       Console.WriteLine();\r
 664     }\r
 665   }\r
 666 }\r