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

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

delete GCB as a separate type.

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