source: icGREP/icgrep-devel/icgrep/re/re_nullable.cpp @ 5206

Last change on this file since 5206 was 5150, checked in by xuedongx, 3 years ago

bug fix

File size: 7.7 KB
Line 
1#include "re_nullable.h"
2#include <re/re_cc.h>
3#include <re/re_start.h>
4#include <re/re_end.h>
5#include <re/re_alt.h>
6#include <re/re_rep.h>
7#include <re/re_any.h>
8#include <re/re_diff.h>
9#include <re/re_intersect.h>
10#include <re/re_assertion.h>
11#include <re/re_name.h>
12
13/*
14
15 A regular expression is nullable if it (a) matches the empty
16 string, and (b) applies everywhere.  Note that Start (^) and
17 End ($) match the empty string, but not everywhere).
18
19*/
20
21namespace re {
22
23RE * RE_Nullable::removeNullablePrefix(RE * re) {
24    if (Seq * seq = dyn_cast<Seq>(re)) {
25        std::vector<RE*> list;
26        for (auto i = seq->begin(); i != seq->end(); ++i) {
27            if (!isNullable(*i)) {
28                list.push_back(removeNullablePrefix(*i));
29                std::copy(++i, seq->end(), std::back_inserter(list));
30                break;
31            }
32        }
33        re = makeSeq(list.begin(), list.end());
34    } else if (Alt * alt = dyn_cast<Alt>(re)) {
35        std::vector<RE*> list;
36        for (auto i = alt->begin(); i != alt->end(); ++i) {
37            list.push_back(removeNullablePrefix(*i));
38        }
39        re = makeAlt(list.begin(), list.end());
40    } else if (Rep * rep = dyn_cast<Rep>(re)) {
41        if ((rep->getLB() == 0) || (isNullable(rep->getRE()))) {
42            re = makeSeq();
43        }
44        else if (hasNullablePrefix(rep->getRE())) {
45            re = makeSeq({removeNullablePrefix(rep->getRE()), makeRep(rep->getRE(), rep->getLB() - 1, rep->getLB() - 1)});
46        }
47        else {
48            re = makeRep(rep->getRE(), rep->getLB(), rep->getLB());
49        }
50    } else if (Name * name = dyn_cast<Name>(re)) {
51        if (name->getDefinition()) {
52            name->setDefinition(removeNullablePrefix(name->getDefinition()));
53        }
54    }
55    return re;
56}
57
58RE * RE_Nullable::removeNullableSuffix(RE * re) {
59    if (Seq * seq = dyn_cast<Seq>(re)) {
60        std::vector<RE*> list;
61        for (auto i = seq->rbegin(); i != seq->rend(); ++i) {
62            if (!isNullable(*i)) {
63                std::copy(seq->begin(), (i + 1).base(), std::back_inserter(list));
64                list.push_back(removeNullableSuffix(*i));
65                break;
66            }
67        }
68        re = makeSeq(list.begin(), list.end());
69    } else if (Alt* alt = dyn_cast<Alt>(re)) {
70        std::vector<RE*> list;
71        for (auto i = alt->begin(); i != alt->end(); ++i) {
72            list.push_back(removeNullableSuffix(*i));
73        }
74        re = makeAlt(list.begin(), list.end());
75    } else if (Rep * rep = dyn_cast<Rep>(re)) {
76        if ((rep->getLB() == 0) || (isNullable(rep->getRE()))) {
77            re = makeSeq();
78        }
79        else if (hasNullableSuffix(rep->getRE())) {
80            re = makeSeq({makeRep(rep->getRE(), rep->getLB() - 1, rep->getLB() - 1), removeNullableSuffix(rep->getRE())});
81        }
82        else {
83            re = makeRep(rep->getRE(), rep->getLB(), rep->getLB());
84        }
85    } else if (Name * name = dyn_cast<Name>(re)) {
86        if (name->getDefinition()) {
87            name->setDefinition(removeNullableSuffix(name->getDefinition()));
88        }
89    }
90    return re;
91}
92
93// Deal with case: R1 (Assertion R2) R3
94// If R2 is nullable, then R1 R3.
95RE * RE_Nullable::removeNullableAssertion(RE * re) {
96    if (Assertion * a = dyn_cast<Assertion>(re)) {
97        if (isNullable(a->getAsserted())) {
98            std::vector<RE *> seq;
99            return makeSeq(seq.begin(), seq.end());
100        } else {
101            return re;
102        }
103    } else if (Seq * seq = dyn_cast<Seq>(re)) {
104        std::vector<RE*> list;
105        for (auto i = seq->begin(); i != seq->end(); ++i) {
106            list.push_back(removeNullableAssertion(*i));
107        }
108        re = makeSeq(list.begin(), list.end());
109    } else if (Alt * alt = dyn_cast<Alt>(re)) {
110        std::vector<RE*> list;
111        for (auto i = alt->begin(); i != alt->end(); ++i) {
112            list.push_back(removeNullableAssertion(*i));
113        }
114        re = makeAlt(list.begin(), list.end());
115    } 
116    return re;
117}
118
119// Deal with case: R1 (Assertion R2) R3
120// If R3 is nullable, then R1 R2.
121RE * RE_Nullable::removeNullableAfterAssertion(RE * re) {
122    if (isNullableAfterAssertion(re)) {
123        re = removeNullableAfterAssertion_helper(re);
124    }
125    return re;
126}
127
128bool RE_Nullable::isNullableAfterAssertion(const RE * re) {
129    bool nullable = false;
130    if (const Seq * seq = dyn_cast<const Seq>(re)) {
131        if (isNullable(re)) {
132            return nullable;
133        } else {
134            nullable = isa<Assertion>(seq->back()) ? true : isNullableAfterAssertion(seq->back());
135        }
136    } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
137        for (const RE * re : *alt) {
138            if (isNullableAfterAssertion(re)) {
139                nullable = true;
140                break;
141            }
142        }
143    }   
144    return nullable;
145}
146
147RE * RE_Nullable::removeNullableAfterAssertion_helper(RE * re) {
148    if (Assertion * a = dyn_cast<Assertion>(re)) {
149        if (a->getSense() == Assertion::Sense::Positive) {
150            return a->getAsserted();
151        } else {
152            return makeDiff(makeAny(), a->getAsserted());
153        }
154    } else if (Seq * seq = dyn_cast<Seq>(re)) {
155        std::vector<RE*> list;
156        auto i = seq->begin();
157        for (; i != seq->end() - 1; ++i) {
158            list.push_back(*i);
159        }
160        list.push_back(removeNullableAfterAssertion_helper(*i));
161        re = makeSeq(list.begin(), list.end());
162    } else if (Alt * alt = dyn_cast<Alt>(re)) {
163        std::vector<RE*> list;
164        for (auto i = alt->begin(); i != alt->end(); ++i) {
165            list.push_back(removeNullableAfterAssertion_helper(*i));
166        }
167        re = makeAlt(list.begin(), list.end());
168    } 
169    return re;
170}
171
172bool RE_Nullable::isNullable(const RE * re) {
173    if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
174        for (const RE * re : *re_seq) {
175            if (!isNullable(re)) {
176                return false;
177            }
178        }
179        return true;
180    } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
181        for (const RE * re : *re_alt) {
182            if (isNullable(re)) {
183                return true;
184            }
185        }
186    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
187        return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
188    } else if (const Diff * diff = dyn_cast<const Diff>(re)) {
189        return isNullable(diff->getLH()) && !isNullable(diff->getRH());
190    } else if (const Intersect * e = dyn_cast<const Intersect>(re)) {
191        return isNullable(e->getLH()) && isNullable(e->getRH());
192    } 
193    return false;
194}
195
196bool RE_Nullable::hasNullablePrefix(const RE * re) {
197    bool nullable = false;
198    if (const Seq * seq = dyn_cast<const Seq>(re)) {
199        nullable = isNullable(seq->front()) ? true : hasNullablePrefix(seq->front());
200    } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
201        for (const RE * re : *alt) {
202            if (hasNullablePrefix(re)) {
203                nullable = true;
204                break;
205            }
206        }
207    } else if (const Rep * rep = dyn_cast<const Rep>(re)) {
208        nullable = true;
209        if (rep->getLB() == rep->getUB()) {
210            nullable = hasNullablePrefix(rep->getRE());
211        }
212    }
213    return nullable;
214}
215
216bool RE_Nullable::hasNullableSuffix(const RE * re) {
217    bool nullable = false;
218    if (const Seq * seq = dyn_cast<const Seq>(re)) {
219        nullable = isNullable(seq->back()) ? true : hasNullableSuffix(seq->back());
220    } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
221        for (const RE * re : *alt) {
222            if (hasNullableSuffix(re)) {
223                nullable = true;
224                break;
225            }
226        }
227    } else if (const Rep * rep = dyn_cast<const Rep>(re)) {
228        nullable = true;
229        if (rep->getLB() == rep->getUB()) {
230            nullable = hasNullableSuffix(rep->getRE());
231        }
232    }
233    return nullable;
234}
235
236}
Note: See TracBrowser for help on using the repository browser.