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

Last change on this file since 4197 was 4197, checked in by nmedfort, 5 years ago

More refactoring of the RE system; moved the original re/RE_Compiler to compiler.cpp and the PBIX_Compiler to the re/RE_Compiler.

File size: 5.1 KB
Line 
1#include "re_nullable.h"
2#include "re_cc.h"
3#include "re_start.h"
4#include "re_end.h"
5#include "re_alt.h"
6#include "re_rep.h"
7#include "re_simplifier.h"
8
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
15*/
16
17namespace re {
18
19RE * RE_Nullable::removeNullablePrefix(RE * re) {
20    if (Seq * seq = dyn_cast<Seq>(re)) {
21        re = removeNullablePrefix(seq);
22    }
23    else if (Alt * alt = dyn_cast<Alt>(re)) {
24        for (auto i = alt->begin(); i != alt->end(); ++i) {
25            *i = removeNullablePrefix(*i);
26        }
27        re = alt;
28    }
29    else if (Rep * rep = dyn_cast<Rep>(re)) {
30        if ((rep->getLB() == 0) || (isNullable(rep->getRE()))) {
31            re = makeSeq();
32        }
33        else if (hasNullablePrefix(rep->getRE())) {
34            Seq * seq = makeSeq();
35            seq->push_back(removeNullablePrefix(rep->getRE()->clone()));
36            seq->push_back(makeRep(rep->getRE(), rep->getLB() - 1, rep->getLB() - 1));
37            rep->setRE(nullptr);
38            delete rep;
39            re = RE_Simplifier::simplify(seq);
40        }
41        else {
42            re = RE_Simplifier::simplify(rep);
43        }
44    }
45    return re;
46}
47
48inline Seq * RE_Nullable::removeNullablePrefix(Seq * seq) {
49    if (!seq->empty()) {
50        std::vector<RE *> list;
51        auto i = seq->begin();
52        // find the first non-nullable prefix
53        while (i != seq->end() && isNullable(*i)) {
54            delete *i;
55            ++i;
56        }
57        if (i != seq->end()) {
58            // push the first non-nullable seq item to the front of the new_seq
59            list.push_back(removeNullablePrefix(*i));
60            std::copy(++i, seq->end(), std::back_inserter(list));
61        }
62        seq->swap(list);
63    }
64    return seq;
65}
66
67RE * RE_Nullable::removeNullableSuffix(RE * re) {
68    if (Seq * seq = dyn_cast<Seq>(re)) {
69        re = removeNullableSuffix(seq);
70    }
71    else if (Alt* alt = dyn_cast<Alt>(re)) {
72        for (auto i = alt->begin(); i != alt->end(); ++i) {
73            *i = removeNullableSuffix(*i);
74        }
75    }
76    else if (Rep * rep = dyn_cast<Rep>(re)) {
77        if ((rep->getLB() == 0) || (isNullable(rep->getRE()))) {
78            delete rep;
79            re = makeSeq();
80        }
81        else if (hasNullableSuffix(rep->getRE())) {
82            Seq * seq = makeSeq();
83            seq->push_back(RE_Simplifier::simplify(makeRep(rep->getRE()->clone(), rep->getLB() - 1, rep->getLB() - 1)));
84            seq->push_back(removeNullableSuffix(rep->getRE()));
85            rep->setRE(nullptr);
86            delete rep;
87            re = RE_Simplifier::simplify(seq);
88        }
89        else {
90            re = RE_Simplifier::simplify(rep);
91        }
92    }
93    return re;
94}
95
96inline Seq * RE_Nullable::removeNullableSuffix(Seq * seq) {
97    if (!seq->empty()) {
98        std::vector<RE *> list;
99        auto i = seq->end();
100        // find the last non-nullable suffix
101        while (i != seq->begin() && isNullable(*--i)) {
102            delete *i;
103        }
104        if (i != seq->begin()) {
105            std::copy(seq->begin(), i, std::back_inserter(list));
106            list.push_back(removeNullableSuffix(*i));
107        }
108        seq->swap(list);
109    }
110    return seq;
111}
112
113bool RE_Nullable::isNullable(const RE * re) {
114    if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
115        return isNullable(re_seq);
116    }
117    else if (const Alt* re_alt = dyn_cast<const Alt>(re)) {
118        return isNullable(re_alt);
119    }
120    else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
121        return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
122    }
123    return false;
124}
125
126inline bool RE_Nullable::isNullable(const Vector * vec) {
127    for (const RE * re : *vec) {
128        if (!isNullable(re)) {
129            return false;
130        }
131    }
132    return true;
133}
134
135bool RE_Nullable::hasNullablePrefix(const RE * re) {
136    bool nullable = false;
137    if (const Seq * seq = dyn_cast<const Seq>(re)) {
138        nullable = isNullable(seq->front()) ? true : hasNullablePrefix(seq->front());
139    }
140    else if (const Alt * alt = dyn_cast<const Alt>(re)) {
141        if (!alt->empty()) {
142            nullable = true;
143            for (const RE * re : *alt) {
144                if (!hasNullablePrefix(re)) {
145                    nullable = false;
146                    break;
147                }
148            }
149        }
150    }
151    else if (const Rep * rep = dyn_cast<const Rep>(re)) {
152        nullable = hasNullablePrefix(rep->getRE());
153    }
154    return nullable;
155}
156
157bool RE_Nullable::hasNullableSuffix(const RE * re) {
158    bool nullable = false;
159    if (const Seq * seq = dyn_cast<const Seq>(re)) {
160        nullable = isNullable(seq->back()) ? true : hasNullableSuffix(seq->back());
161    }
162    else if (const Alt * alt = dyn_cast<const Alt>(re)) {
163        if (!alt->empty()) {
164            nullable = true;
165            for (const RE * re : *alt) {
166                if (!hasNullableSuffix(re)) {
167                    nullable = false;
168                    break;
169                }
170            }
171        }
172    }
173    else if (const Rep * rep = dyn_cast<const Rep>(re)) {
174        nullable = hasNullableSuffix(rep->getRE());
175    }
176    return nullable;
177}
178
179}
Note: See TracBrowser for help on using the repository browser.