Ignore:
Timestamp:
Jun 21, 2014, 6:24:39 PM (5 years ago)
Author:
cameron
Message:

removeNullablePrefix, removeNullableSuffix optimizations

File:
1 edited

Legend:

Unmodified
Added
Removed
  • proto/RE/Haskell/Nullable.hs

    r3856 r3888  
    22-- grep search expression to remove any "nullable" prefix.
    33
    4 -- Robert D. Cameron, 2013
     4-- Robert D. Cameron, 2014
    55
    6 module NullAble (minMatchLen, removeNullablePrefix) where
     6module Nullable (isNullable, removeNullablePrefix, removeNullableSuffix) where
    77       
    88import CanonicalRE
    99
    10 -- Write a minimal match length function that determines the minimum length
    11 -- string that can be matched by an RE, considering that Start and End match
    12 -- single \n character.
    1310
    14 minMatchLen :: RE -> Int
    15 minMatchLen (CC s) = 1
    16 minMatchLen Start = 1
    17 minMatchLen End = 1
    18 minMatchLen (Seq []) = 0
    19 minMatchLen (Seq (r:rs)) = minMatchLen r + (minMatchLen (Seq rs))
    20 minMatchLen (Alt [r]) = minMatchLen r
    21 minMatchLen (Alt (r:rs)) = min (minMatchLen r) (minMatchLen (Alt rs))
    22 minMatchLen (Rep (r, i, j)) = i * (minMatchLen r)
     11-- A regular expression is nullable if it (a) matches the empty
     12-- string, and (b) applies everywhere.  Note that Start (^) and
     13-- End ($) match the empty string, but not everywhere).
     14
     15isNullable :: RE -> Bool
     16isNullableSeq :: [RE] -> Bool
     17isNullableAlt :: [RE] -> Bool
     18
     19isNullable (CC s) = False
     20isNullable Start = False
     21isNullable End = False
     22isNullable (Seq x) = isNullableSeq x
     23isNullable (Alt x) = isNullableAlt x
     24isNullable (Rep (r, i, j))
     25  | i == 0     = True
     26  | otherwise  = isNullable(r)
     27
     28isNullableSeq []       = True
     29isNullableSeq (a:more)
     30  | isNullable(a)      = isNullableSeq(more)
     31  | otherwise          = False
     32
     33isNullableAlt []       = False
     34isNullableAlt (a:more)
     35  | isNullable(a)      = True
     36  | otherwise          = isNullableAlt(more)
    2337
    2438--- removeNullablePrefix takes a regular expression and returns
     
    2943
    3044removeNullablePrefix :: RE -> RE
    31 removeNullablePrefix (CC s) = (CC s)
    32 removeNullablePrefix Start = Start
    33 removeNullablePrefix End = End
    34 removeNullablePrefix (Seq []) = Seq []
    35 removeNullablePrefix (Seq (r:rs))
    36    | minMatchLen(r) == 0  = removeNullablePrefix(Seq rs)
    37    | otherwise            = Seq ((removeNullablePrefix r):rs)
    38 removeNullablePrefix (Alt rs) = Alt (map removeNullablePrefix rs)
    39 removeNullablePrefix (Rep (r, 0, ub)) = Seq []
    40 removeNullablePrefix (Rep (r, lb, ub))
    41    | minMatchLen(r) == 0  = Seq []
    42    | otherwise            = Seq [removeNullablePrefix(r), Rep (r, lb-1, lb-1)]
     45removeNullablePrefix (Seq s) = Seq (removeNullableSeqPrefix(s))
     46removeNullablePrefix (Alt as) = Alt (map removeNullablePrefix as)
     47removeNullablePrefix (Rep(r, lb, ub))
     48   | lb == 0        = Seq []
     49   | isNullable(r)  = Seq []
     50   | otherwise      = Seq [removeNullablePrefix(r), Rep(r, lb-1, lb-1)]
     51-- default: do nothing
     52removeNullablePrefix r = r
    4353
     54removeNullableSeqPrefix :: [RE] -> [RE]
     55removeNullableSeqPrefix [] = []
     56removeNullableSeqPrefix (a:more)
     57  | isNullable(a)       = removeNullableSeqPrefix(more)
     58  | otherwise           = removeNullablePrefix(a):more
    4459
     60removeNullableSuffix :: RE -> RE
     61removeNullableSuffix (Seq s) = Seq (removeNullableSeqSuffix(s))
     62removeNullableSuffix (Alt as) = Alt (map removeNullableSuffix as)
     63removeNullableSuffix (Rep(r, lb, ub))
     64   | lb == 0        = Seq []
     65   | isNullable(r)  = Seq []
     66   | otherwise      = Seq [Rep(r, lb-1, lb-1), removeNullableSuffix(r)]
     67-- default: do nothing
     68removeNullableSuffix r = r
     69
     70removeNullableSeqSuffix :: [RE] -> [RE]
     71removeNullableSeqSuffix [] = []
     72removeNullableSeqSuffix (a:more)
     73  | isNullableSeq(more)       = [removeNullableSuffix(a)]
     74  | otherwise                 = a:removeNullableSeqSuffix(more)
Note: See TracChangeset for help on using the changeset viewer.