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

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

First attempt to intergrate 'generate_predefined_ucd_functions' into build process.

File size: 4.6 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_simplifier.h>
8#include <re/printer_re.h>
9#include <iostream>
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    }
32    else if (Alt * alt = dyn_cast<Alt>(re)) {
33        std::vector<RE*> list;
34        for (auto i = alt->begin(); i != alt->end(); ++i) {
35            list.push_back(removeNullablePrefix(*i));
36        }
37        re = makeAlt(list.begin(), list.end());
38    }
39    else if (Rep * rep = dyn_cast<Rep>(re)) {
40        if ((rep->getLB() == 0) || (isNullable(rep->getRE()))) {
41            re = makeSeq();
42        }
43        else if (hasNullablePrefix(rep->getRE())) {
44            re = makeSeq({removeNullablePrefix(rep->getRE()), makeRep(rep->getRE(), rep->getLB() - 1, rep->getLB() - 1)});
45        }
46        else {
47            re = makeRep(rep->getRE(), rep->getLB(), rep->getLB());
48        }
49    }
50    return re;
51}
52
53RE * RE_Nullable::removeNullableSuffix(RE * re) {
54    if (Seq * seq = dyn_cast<Seq>(re)) {
55        std::vector<RE*> list;
56        for (auto i = seq->rbegin(); i != seq->rend(); ++i) {
57            if (!isNullable(*i)) {
58                std::copy(seq->begin(), (i + 1).base(), std::back_inserter(list));
59                list.push_back(removeNullableSuffix(*i));
60                break;
61            }
62        }
63        re = makeSeq(list.begin(), list.end());
64    }
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    }
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    }
83    return re;
84}
85
86bool RE_Nullable::isNullable(const RE * re) {
87    if (const Seq * re_seq = dyn_cast<const Seq>(re)) {
88        for (const RE * re : *re_seq) {
89            if (!isNullable(re)) {
90                return false;
91            }
92        }
93        return true;
94    }
95    else if (const Alt * re_alt = dyn_cast<const Alt>(re)) {
96        for (const RE * re : *re_alt) {
97            if (isNullable(re)) {
98                return true;
99            }
100        }
101    }
102    else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
103        return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
104    }
105    return false;
106}
107
108bool RE_Nullable::hasNullablePrefix(const RE * re) {
109    bool nullable = false;
110    if (const Seq * seq = dyn_cast<const Seq>(re)) {
111        nullable = isNullable(seq->front()) ? true : hasNullablePrefix(seq->front());
112    }
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    }
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    }
135    else if (const Alt * alt = dyn_cast<const Alt>(re)) {
136        for (const RE * re : *alt) {
137            if (hasNullableSuffix(re)) {
138                nullable = true;
139                break;
140            }
141        }
142    }
143    else if (const Rep * rep = dyn_cast<const Rep>(re)) {
144        nullable = true;
145        if (rep->getLB() == rep->getUB()) {
146            nullable = hasNullableSuffix(rep->getRE());
147        }
148    }
149    return nullable;
150}
151
152}
Note: See TracBrowser for help on using the repository browser.