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

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

bug fix

File size: 7.8 KB
RevLine 
[3917]1#include "re_nullable.h"
[4684]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>
[5147]7#include <re/re_any.h>
8#include <re/re_diff.h>
9#include <re/re_intersect.h>
10#include <re/re_assertion.h>
[4829]11#include <re/re_name.h>
12
[3917]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
[4194]21namespace re {
22
[4187]23RE * RE_Nullable::removeNullablePrefix(RE * re) {
[4194]24    if (Seq * seq = dyn_cast<Seq>(re)) {
[4203]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        }
[4249]33        re = makeSeq(list.begin(), list.end());
[4829]34    } else if (Alt * alt = dyn_cast<Alt>(re)) {
[4203]35        std::vector<RE*> list;
[4194]36        for (auto i = alt->begin(); i != alt->end(); ++i) {
[4203]37            list.push_back(removeNullablePrefix(*i));
[3917]38        }
[4203]39        re = makeAlt(list.begin(), list.end());
[4829]40    } else if (Rep * rep = dyn_cast<Rep>(re)) {
[4194]41        if ((rep->getLB() == 0) || (isNullable(rep->getRE()))) {
42            re = makeSeq();
[3917]43        }
[4194]44        else if (hasNullablePrefix(rep->getRE())) {
[4203]45            re = makeSeq({removeNullablePrefix(rep->getRE()), makeRep(rep->getRE(), rep->getLB() - 1, rep->getLB() - 1)});
[3917]46        }
[4182]47        else {
[4203]48            re = makeRep(rep->getRE(), rep->getLB(), rep->getLB());
[3917]49        }
[4829]50    } else if (Name * name = dyn_cast<Name>(re)) {
51        if (name->getDefinition()) {
52            name->setDefinition(removeNullablePrefix(name->getDefinition()));
53        }
[3917]54    }
[4182]55    return re;
[3917]56}
57
[4182]58RE * RE_Nullable::removeNullableSuffix(RE * re) {
[4194]59    if (Seq * seq = dyn_cast<Seq>(re)) {
[4203]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        }
[4249]68        re = makeSeq(list.begin(), list.end());
[4829]69    } else if (Alt* alt = dyn_cast<Alt>(re)) {
[4203]70        std::vector<RE*> list;
[4194]71        for (auto i = alt->begin(); i != alt->end(); ++i) {
[4203]72            list.push_back(removeNullableSuffix(*i));
[3917]73        }
[4203]74        re = makeAlt(list.begin(), list.end());
[4829]75    } else if (Rep * rep = dyn_cast<Rep>(re)) {
[4194]76        if ((rep->getLB() == 0) || (isNullable(rep->getRE()))) {
77            re = makeSeq();
[3917]78        }
[4194]79        else if (hasNullableSuffix(rep->getRE())) {
[4203]80            re = makeSeq({makeRep(rep->getRE(), rep->getLB() - 1, rep->getLB() - 1), removeNullableSuffix(rep->getRE())});
[3917]81        }
[4182]82        else {
[4203]83            re = makeRep(rep->getRE(), rep->getLB(), rep->getLB());
[3917]84        }
[4829]85    } else if (Name * name = dyn_cast<Name>(re)) {
86        if (name->getDefinition()) {
87            name->setDefinition(removeNullableSuffix(name->getDefinition()));
88        }
[3917]89    }
[4182]90    return re;
[3917]91}
92
[5147]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) {
[5149]106            if (!isNullable(*i)) {
107                list.push_back(removeNullableAssertion(*i));
108            }
[5147]109        }
110        re = makeSeq(list.begin(), list.end());
111    } else if (Alt * alt = dyn_cast<Alt>(re)) {
112        std::vector<RE*> list;
113        for (auto i = alt->begin(); i != alt->end(); ++i) {
114            list.push_back(removeNullableAssertion(*i));
115        }
116        re = makeAlt(list.begin(), list.end());
117    } 
118    return re;
119}
120
121// Deal with case: R1 (Assertion R2) R3
122// If R3 is nullable, then R1 R2.
123RE * RE_Nullable::removeNullableAfterAssertion(RE * re) {
124    if (isNullableAfterAssertion(re)) {
125        re = removeNullableAfterAssertion_helper(re);
126    }
127    return re;
128}
129
130bool RE_Nullable::isNullableAfterAssertion(const RE * re) {
131    bool nullable = false;
132    if (const Seq * seq = dyn_cast<const Seq>(re)) {
[5149]133        if (isNullable(re)) {
134            return nullable;
135        } else {
136            nullable = isa<Assertion>(seq->back()) ? true : isNullableAfterAssertion(seq->back());
137        }
[5147]138    } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
139        for (const RE * re : *alt) {
140            if (isNullableAfterAssertion(re)) {
141                nullable = true;
142                break;
143            }
144        }
145    }   
146    return nullable;
147}
148
149RE * RE_Nullable::removeNullableAfterAssertion_helper(RE * re) {
150    if (Assertion * a = dyn_cast<Assertion>(re)) {
151        if (a->getSense() == Assertion::Sense::Positive) {
152            return a->getAsserted();
153        } else {
154            return makeDiff(makeAny(), a->getAsserted());
155        }
156    } else if (Seq * seq = dyn_cast<Seq>(re)) {
157        std::vector<RE*> list;
158        auto i = seq->begin();
159        for (; i != seq->end() - 1; ++i) {
160            list.push_back(*i);
161        }
162        list.push_back(removeNullableAfterAssertion_helper(*i));
163        re = makeSeq(list.begin(), list.end());
164    } else if (Alt * alt = dyn_cast<Alt>(re)) {
165        std::vector<RE*> list;
166        for (auto i = alt->begin(); i != alt->end(); ++i) {
167            list.push_back(removeNullableAfterAssertion_helper(*i));
168        }
169        re = makeAlt(list.begin(), list.end());
170    } 
171    return re;
172}
173
[4182]174bool RE_Nullable::isNullable(const RE * re) {
[4194]175    if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
[4203]176        for (const RE * re : *re_seq) {
177            if (!isNullable(re)) {
178                return false;
179            }
180        }
181        return true;
[4829]182    } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
[4203]183        for (const RE * re : *re_alt) {
184            if (isNullable(re)) {
185                return true;
186            }
187        }
[4829]188    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
[3917]189        return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
[5147]190    } else if (const Diff * diff = dyn_cast<const Diff>(re)) {
191        return isNullable(diff->getLH()) && !isNullable(diff->getRH());
192    } else if (const Intersect * e = dyn_cast<const Intersect>(re)) {
193        return isNullable(e->getLH()) && isNullable(e->getRH());
194    } 
[4182]195    return false;
[3917]196}
197
[4182]198bool RE_Nullable::hasNullablePrefix(const RE * re) {
199    bool nullable = false;
[4194]200    if (const Seq * seq = dyn_cast<const Seq>(re)) {
[4182]201        nullable = isNullable(seq->front()) ? true : hasNullablePrefix(seq->front());
[4829]202    } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
[4203]203        for (const RE * re : *alt) {
204            if (hasNullablePrefix(re)) {
205                nullable = true;
206                break;
[3917]207            }
208        }
[4829]209    } else if (const Rep * rep = dyn_cast<const Rep>(re)) {
[4203]210        nullable = true;
211        if (rep->getLB() == rep->getUB()) {
212            nullable = hasNullablePrefix(rep->getRE());
213        }
[3917]214    }
[4182]215    return nullable;
[3917]216}
217
[4182]218bool RE_Nullable::hasNullableSuffix(const RE * re) {
219    bool nullable = false;
[4194]220    if (const Seq * seq = dyn_cast<const Seq>(re)) {
[4187]221        nullable = isNullable(seq->back()) ? true : hasNullableSuffix(seq->back());
[4829]222    } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
[4203]223        for (const RE * re : *alt) {
224            if (hasNullableSuffix(re)) {
225                nullable = true;
226                break;
[3917]227            }
228        }
[4829]229    } else if (const Rep * rep = dyn_cast<const Rep>(re)) {
[4203]230        nullable = true;
231        if (rep->getLB() == rep->getUB()) {
232            nullable = hasNullableSuffix(rep->getRE());
233        }
[3917]234    }
[4182]235    return nullable;
[3917]236}
237
[4194]238}
Note: See TracBrowser for help on using the repository browser.