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

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

Avoid duplicating the repeated expression, if it can't be simplified

File size: 3.4 KB
Line 
1-- Module Nullable provides functions for optimizing a
2-- grep search expression to remove any "nullable" prefix.
3
4-- Robert D. Cameron, 2014
5
6module Nullable (isNullable, removeNullablePrefix, removeNullableSuffix) where
7       
8import CanonicalRE
9
10
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)
37
38--- removeNullablePrefix takes a regular expression and returns
39--- the version of it that has been transformed to remove any nullable
40--- prefix.  A prefix p is nullable if it can possibly match the empty
41--- string, i.e., minMatchLen(p) = 0.  For example, in the regexp
42--- [a-z]*-[0-9]+ the prefix [a-z]* is nullable.
43
44removeNullablePrefix :: RE -> RE
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   | hasNullablePrefix(r)  = mkSeq[removeNullablePrefix(r), mkRep(r, lb-1, lb-1)]
51   | otherwise             = mkRep(r, lb, lb)
52-- default: do nothing
53removeNullablePrefix r = r
54
55removeNullableSeqPrefix :: [RE] -> [RE]
56removeNullableSeqPrefix [] = []
57removeNullableSeqPrefix (a:more)
58  | isNullable(a)       = removeNullableSeqPrefix(more)
59  | otherwise           = removeNullablePrefix(a):more
60
61removeNullableSuffix :: RE -> RE
62removeNullableSuffix (Seq s) = Seq (removeNullableSeqSuffix(s))
63removeNullableSuffix (Alt as) = Alt (map removeNullableSuffix as)
64removeNullableSuffix (Rep(r, lb, ub))
65   | lb == 0               = Seq []
66   | isNullable(r)         = Seq []
67   | hasNullableSuffix(r)  = mkSeq[mkRep(r, lb-1, lb-1), removeNullableSuffix(r)]
68   | otherwise             = mkRep(r, lb, lb)
69-- default: do nothing
70removeNullableSuffix r = r
71
72removeNullableSeqSuffix :: [RE] -> [RE]
73removeNullableSeqSuffix [] = []
74removeNullableSeqSuffix (a:more)
75  | isNullableSeq(more)       = [removeNullableSuffix(a)]
76  | otherwise                 = a:removeNullableSeqSuffix(more)
77
78
79hasNullablePrefix :: RE -> Bool
80hasNullablePrefix (Seq (e:es))
81  | isNullable(e)   = True
82  | otherwise       = hasNullablePrefix(e)
83hasNullablePrefix (Alt []) = False
84hasNullablePrefix (Alt (a:as))
85  | hasNullablePrefix(a)   = True
86  | otherwise              = hasNullablePrefix (Alt as)
87hasNullablePrefix (Rep(r, lb, ub)) = hasNullablePrefix(r)
88hasNullablePrefix r = False
89
90hasNullableSuffix :: RE -> Bool
91hasNullableSuffix (Seq [e]) 
92  | isNullable(e)   = True
93  | otherwise       = hasNullableSuffix(e)
94hasNullableSuffix (Seq (e:es)) = hasNullableSuffix(Seq es)
95hasNullableSuffix (Alt []) = False
96hasNullableSuffix (Alt (a:as))
97  | hasNullableSuffix(a)   = True
98  | otherwise              = hasNullableSuffix (Alt as)
99hasNullableSuffix (Rep(r, lb, ub)) = hasNullableSuffix(r)
100hasNullableSuffix r = False
Note: See TracBrowser for help on using the repository browser.