source: proto/RE/Haskell/Nullable.hs @ 3856

Last change on this file since 3856 was 3856, checked in by cameron, 5 years ago

Simplify to use -1 as upperbound

File size: 1.6 KB
Line 
1-- Module Nullable provides functions for optimizing a
2-- grep search expression to remove any "nullable" prefix.
3
4-- Robert D. Cameron, 2013
5
6module NullAble (minMatchLen, removeNullablePrefix) where
7       
8import CanonicalRE
9
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.
13
14minMatchLen :: RE -> Int
15minMatchLen (CC s) = 1
16minMatchLen Start = 1
17minMatchLen End = 1
18minMatchLen (Seq []) = 0
19minMatchLen (Seq (r:rs)) = minMatchLen r + (minMatchLen (Seq rs))
20minMatchLen (Alt [r]) = minMatchLen r
21minMatchLen (Alt (r:rs)) = min (minMatchLen r) (minMatchLen (Alt rs))
22minMatchLen (Rep (r, i, j)) = i * (minMatchLen r)
23
24--- removeNullablePrefix takes a regular expression and returns
25--- the version of it that has been transformed to remove any nullable
26--- prefix.  A prefix p is nullable if it can possibly match the empty
27--- string, i.e., minMatchLen(p) = 0.  For example, in the regexp
28--- [a-z]*-[0-9]+ the prefix [a-z]* is nullable.
29
30removeNullablePrefix :: RE -> RE
31removeNullablePrefix (CC s) = (CC s)
32removeNullablePrefix Start = Start
33removeNullablePrefix End = End
34removeNullablePrefix (Seq []) = Seq []
35removeNullablePrefix (Seq (r:rs))
36   | minMatchLen(r) == 0  = removeNullablePrefix(Seq rs)
37   | otherwise            = Seq ((removeNullablePrefix r):rs)
38removeNullablePrefix (Alt rs) = Alt (map removeNullablePrefix rs)
39removeNullablePrefix (Rep (r, 0, ub)) = Seq []
40removeNullablePrefix (Rep (r, lb, ub))
41   | minMatchLen(r) == 0  = Seq []
42   | otherwise            = Seq [removeNullablePrefix(r), Rep (r, lb-1, lb-1)]
43
44
Note: See TracBrowser for help on using the repository browser.