# Changeset 3595

Ignore:
Timestamp:
Dec 24, 2013, 7:21:38 AM (6 years ago)
Message:

Various corrections and cleanups

File:
1 edited

Unmodified
Removed
• ## proto/RE/doc/CanonicalRE.hs

 r3594 import Data.Char data RepLimit = UpperBound Int | Unbounded deriving Show data RepLimit = UpperBound Int | UnBounded deriving Show upper_bound_dec :: RepLimit -> RepLimit upper_bound_dec (UpperBound j) = UpperBound (j - 1) upper_bound_dec Unbounded = Unbounded upper_bound_dec UnBounded = UnBounded data RE = CC String | Seq [RE] | Alt [RE] | Rep RE Int RepLimit | Start | End  -- lookbehind/lookahead assertions for newline -- Rep r i j represents bounded repetition, with lower bound i and -- Rep r i j represents UpperBound repetition, with lower bound i and -- upper bound j.   We use the convention that any negative value of -- j represents unbounded repetition. -- j represents UnBounded repetition. canonicalize :: Proto.RE -> RE canonicalize (Proto.Alt rs) = Alt (map canonicalize rs) canonicalize (Proto.Opt r) = Rep (canonicalize r) 0 (UpperBound 1) canonicalize (Proto.Kstar r) = Rep (canonicalize r) 0 Unbounded canonicalize (Proto.Kplus r) = Rep (canonicalize r) 1 Unbounded canonicalize (Proto.OrMore i r) = Rep (canonicalize r) i Unbounded canonicalize (Proto.Kstar r) = Rep (canonicalize r) 0 UnBounded canonicalize (Proto.Kplus r) = Rep (canonicalize r) 1 UnBounded canonicalize (Proto.OrMore i r) = Rep (canonicalize r) i UnBounded canonicalize (Proto.Bounded i j r) = Rep (canonicalize r) i (UpperBound j) -- is the next one in sequence. mre2pablo_helper(CC(c), m) = re2pablo_helper(CC(c), m) = (m + 1, [SetMarker (m + 1, Advance(And(Marker(m), CharClass(c))))]) re2pablo_helper(Seq (r1:rs), m) = (m2, s1 ++ s2) where (m1, s1) = mre2pablo_helper(r1, m) (m2, s2) = mre2pablo_helper(Seq rs, m1) (m1, s1) = re2pablo_helper(r1, m) (m2, s2) = re2pablo_helper(Seq rs, m1) -- Alt[r] has a single alternative r to match, just match -- does. re2pablo_helper(Alt (r1:rs), m) = (m2 + 1, s1 ++ s2 ++ [SetMarker (m2 + 1, Or(Marker m1, Marker m2))]) re2pablo_helper(Alt (r1:rs), m) = (m2 + 1, save ++ s1 ++ s2 ++ final) where (m1, s1) = mre2pablo_helper(r1, m) (m2, s2) = mre2pablo_helper(Alt rs, m1) (m1, s1) = re2pablo_helper(r1, m) (m2, s2) = re2pablo_helper(Alt rs, m1+1) save = [SetMarker(m1 + 1, Marker(m))] final = [SetMarker(m2 + 1, Or(Marker(m1), Marker(m2)))] re2pablo_helper(Rep (CC c) 0 Unbounded, m) = re2pablo_helper(Rep (CC c) 0 UnBounded, m) = (m + 1, [SetMarker(m + 1, MatchStar(Marker(m), CharClass(c)))]) re2pablo_helper(Rep r 0 ub, m) | ub < 0 = (m1, [SetMarker(m + 1, Marker m), While (Marker (m+1), s1 ++ [SetMarker(m + 1, And(Marker m1 ,Not(Marker (m+1))))] )]) | otherwise = (m + 1, s1 ++ s2 ++ [SetMarker (m + 1, Or(Marker m1, Marker m2))]) re2pablo_helper(Rep r 0 UnBounded, m) = (m1+1, save ++ [While (Marker(m+1), s1 ++ loopfinal)]) where (m1, s1) = mre2pablo_helper(r, m+1) (m2, s2) = mre2pablo_helper(Rep r 0 (upper_bound_dec ub), m1) (m1, s1) = re2pablo_helper(r, m+1) save = [SetMarker(m+1, Marker(m)), SetMarker(m1+1, Marker(m))] loopfinal = [SetMarker(m+1, And(Marker(m1), Not(Marker(m1+1)))), SetMarker(m1+1, Or(Marker(m1+1), Marker(m1)))] re2pablo_helper(Rep r 0 (UpperBound 0), m) = (m, []) re2pablo_helper(Rep r lb ub, m) =  (m2, s1 ++ s2) re2pablo_helper(Rep r 0 (UpperBound ub), m) = (m2 + 1, s1 ++ s2 ++ [SetMarker (m2 + 1, Or(Marker m1, Marker m2))]) where (m1, s1) = mre2pablo_helper(r, m) (m2, s2) = mre2pablo_helper(Rep r (lb - 1) (upper_bound_dec ub), m1) (m1, s1) = re2pablo_helper(r, m) (m2, s2) = re2pablo_helper(Rep r 0 (UpperBound(ub-1)), m1) re2pablo_helper(Rep r lb (UpperBound ub), m) =  (m2, s1 ++ s2) where (m1, s1) = re2pablo_helper(r, m) (m2, s2) = re2pablo_helper(Rep r (lb-1) (UpperBound(ub-1)), m1)
Note: See TracChangeset for help on using the changeset viewer.