Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/src/smlnj-lib/RegExp/BackEnd/dfa-engine.sml
ViewVC logotype

Annotation of /sml/trunk/src/smlnj-lib/RegExp/BackEnd/dfa-engine.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 104 - (view) (download)

1 : monnier 104 (* dfa-engine.sml
2 :     *
3 :     * COPYRIGHT (c) 1998 Bell Labs, Lucent Technologies.
4 :     *
5 :     * Implements a matcher engine based on deterministic finite
6 :     * automata.
7 :     *)
8 :    
9 :     structure DfaEngine : REGEXP_ENGINE =
10 :     struct
11 :    
12 :     structure D = Dfa
13 :     structure M = MatchTree
14 :    
15 :     type regexp = D.dfa
16 :    
17 :     fun compile r = D.build r
18 :     handle _ => raise RegExpSyntax.CannotCompile
19 :    
20 :     (* scan looks at a stream and attempts to match the dfa.
21 :     * it returns NONE if it fails
22 :     * it returns SOME (pattern#,Match,rest of stream) upon success
23 :     *)
24 :     fun scan (regexp,getc,p,stream) =
25 :     let val move = D.move regexp
26 :     val accepting = D.accepting regexp
27 :     val canStart = D.canStart regexp
28 :     fun loop (state,p,inits,lastP,lastS,lastN) =
29 :     (case (getc (inits))
30 :     of NONE => (lastP,lastS,lastN)
31 :     | SOME (c,s') =>
32 :     (case move (state,c)
33 :     of NONE => (lastP,lastS,lastN)
34 :     | SOME (new) =>
35 :     case (accepting new)
36 :     of SOME n => loop (new,p+1,s',p+1,s',n)
37 :     | NONE => loop (new,p+1,s',lastP,lastS,lastN)))
38 :     in
39 :     case (getc (stream))
40 :     of NONE => (case (accepting 0)
41 :     of SOME n => SOME (n,M.Match (SOME {pos=stream,len=0},[]),stream)
42 :     | NONE => NONE)
43 :     | SOME (c,s') =>
44 :     if (canStart c)
45 :     then let val (last,cs,n) = loop (0,p,stream,~1,stream,0)
46 :     in
47 :     if (last<0)
48 :     then NONE
49 :     else SOME (n,M.Match (SOME {pos=stream,
50 :     len=last-p},
51 :     []),cs)
52 :     end
53 :     else NONE
54 :     end
55 :    
56 :     fun prefix regexp getc stream = case (scan (regexp,getc,0,stream))
57 :     of NONE => NONE
58 :     | SOME (n,m,cs) => SOME (m,cs)
59 :    
60 :     fun find regexp getc stream =
61 :     let fun loop (p,s) = (case (scan (regexp,getc,p,s))
62 :     of NONE => (case (getc (s))
63 :     of SOME (_,s') => loop (p+1,s')
64 :     | NONE => NONE)
65 :     | SOME (n,m,cs) => SOME (m,cs))
66 :     in
67 :     loop (0,stream)
68 :     end
69 :    
70 :     fun match [] = (fn getc => fn stream => NONE)
71 :     | match l =
72 :     let val dfa = D.buildPattern (map #1 l)
73 :     val a = Array.fromList (map (fn (a,b) => b) l)
74 :     in
75 :     fn getc => fn stream => case (scan (dfa,getc,0,stream))
76 :     of NONE => NONE
77 :     | SOME (n,m,cs) => SOME ((Array.sub (a,n)) m,cs)
78 :     end
79 :    
80 :     end

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0