icfp-2015/fsm.sml at master · cbv/icfp-2015 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
(* Flying Spaghetti Monsters *)
structure FSM =
struct

  (*

     datatype syntax
       = Group of syntax
       | Alt of syntax list
       | Concat of syntax list
       | Interval of (syntax * int * int option)
       | Option of syntax       (* == Interval(re, 0, SOME 1) *)
       | Star of syntax (* == Interval(re, 0, NONE) *)
       | Plus of syntax (* == Interval(re, 1, NONE) *)
       | MatchSet of CharSet.set
       | NonmatchSet of CharSet.set
       | Char of char
       | Begin
       | End
       *)

  structure RS = RegExpSyntax
  fun stringtosyntax s =
    RS.Concat (map RS.Char (explode s))


  val syntax =
    RS.Concat[RS.Star (RS.MatchSet (RS.allChars)),
              (RS.Alt [stringtosyntax "monster",
                       stringtosyntax "spaghetti"])]

  val dfa = Dfa.build syntax

end