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

Last change on this file since 4983 was 4841, checked in by nmedfort, 4 years ago

Update for grapheme cluster mode and boundaries.

File size: 4.9 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_grapheme_boundary.hpp>
8#include <re/re_name.h>
9
10/*
11
12 A regular expression is nullable if it (a) matches the empty
13 string, and (b) applies everywhere.  Note that Start (^) and
14 End ($) match the empty string, but not everywhere).
15
16*/
17
18namespace re {
19
20RE * RE_Nullable::removeNullablePrefix(RE * re) {
21    if (Seq * seq = dyn_cast<Seq>(re)) {
22        std::vector<RE*> list;
23        for (auto i = seq->begin(); i != seq->end(); ++i) {
24            if (!isNullable(*i)) {
25                list.push_back(removeNullablePrefix(*i));
26                std::copy(++i, seq->end(), std::back_inserter(list));
27                break;
28            }
29        }
30        re = makeSeq(list.begin(), list.end());
31    } else if (Alt * alt = dyn_cast<Alt>(re)) {
32        std::vector<RE*> list;
33        for (auto i = alt->begin(); i != alt->end(); ++i) {
34            list.push_back(removeNullablePrefix(*i));
35        }
36        re = makeAlt(list.begin(), list.end());
37    } else if (Rep * rep = dyn_cast<Rep>(re)) {
38        if ((rep->getLB() == 0) || (isNullable(rep->getRE()))) {
39            re = makeSeq();
40        }
41        else if (hasNullablePrefix(rep->getRE())) {
42            re = makeSeq({removeNullablePrefix(rep->getRE()), makeRep(rep->getRE(), rep->getLB() - 1, rep->getLB() - 1)});
43        }
44        else {
45            re = makeRep(rep->getRE(), rep->getLB(), rep->getLB());
46        }
47    } else if (Name * name = dyn_cast<Name>(re)) {
48        if (name->getDefinition()) {
49            name->setDefinition(removeNullablePrefix(name->getDefinition()));
50        }
51    }
52    return re;
53}
54
55RE * RE_Nullable::removeNullableSuffix(RE * re) {
56    if (Seq * seq = dyn_cast<Seq>(re)) {
57        std::vector<RE*> list;
58        for (auto i = seq->rbegin(); i != seq->rend(); ++i) {
59            if (!isNullable(*i)) {
60                std::copy(seq->begin(), (i + 1).base(), std::back_inserter(list));
61                list.push_back(removeNullableSuffix(*i));
62                break;
63            }
64        }
65        re = makeSeq(list.begin(), list.end());
66    } else if (Alt* alt = dyn_cast<Alt>(re)) {
67        std::vector<RE*> list;
68        for (auto i = alt->begin(); i != alt->end(); ++i) {
69            list.push_back(removeNullableSuffix(*i));
70        }
71        re = makeAlt(list.begin(), list.end());
72    } else if (Rep * rep = dyn_cast<Rep>(re)) {
73        if ((rep->getLB() == 0) || (isNullable(rep->getRE()))) {
74            re = makeSeq();
75        }
76        else if (hasNullableSuffix(rep->getRE())) {
77            re = makeSeq({makeRep(rep->getRE(), rep->getLB() - 1, rep->getLB() - 1), removeNullableSuffix(rep->getRE())});
78        }
79        else {
80            re = makeRep(rep->getRE(), rep->getLB(), rep->getLB());
81        }
82    } else if (Name * name = dyn_cast<Name>(re)) {
83        if (name->getDefinition()) {
84            name->setDefinition(removeNullableSuffix(name->getDefinition()));
85        }
86    }
87    return re;
88}
89
90bool RE_Nullable::isNullable(const RE * re) {
91    if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
92        for (const RE * re : *re_seq) {
93            if (!isNullable(re)) {
94                return false;
95            }
96        }
97        return true;
98    } else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
99        for (const RE * re : *re_alt) {
100            if (isNullable(re)) {
101                return true;
102            }
103        }
104    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
105        return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
106    }
107    return false;
108}
109
110bool RE_Nullable::hasNullablePrefix(const RE * re) {
111    bool nullable = false;
112    if (const Seq * seq = dyn_cast<const Seq>(re)) {
113        nullable = isNullable(seq->front()) ? true : hasNullablePrefix(seq->front());
114    } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
115        for (const RE * re : *alt) {
116            if (hasNullablePrefix(re)) {
117                nullable = true;
118                break;
119            }
120        }
121    } else if (const Rep * rep = dyn_cast<const Rep>(re)) {
122        nullable = true;
123        if (rep->getLB() == rep->getUB()) {
124            nullable = hasNullablePrefix(rep->getRE());
125        }
126    }
127    return nullable;
128}
129
130bool RE_Nullable::hasNullableSuffix(const RE * re) {
131    bool nullable = false;
132    if (const Seq * seq = dyn_cast<const Seq>(re)) {
133        nullable = isNullable(seq->back()) ? true : hasNullableSuffix(seq->back());
134    } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
135        for (const RE * re : *alt) {
136            if (hasNullableSuffix(re)) {
137                nullable = true;
138                break;
139            }
140        }
141    } else if (const Rep * rep = dyn_cast<const Rep>(re)) {
142        nullable = true;
143        if (rep->getLB() == rep->getUB()) {
144            nullable = hasNullableSuffix(rep->getRE());
145        }
146    }
147    return nullable;
148}
149
150}
Note: See TracBrowser for help on using the repository browser.