source: icGREP/icgrep-devel/icgrep/re_nullable.cpp @ 4122

Last change on this file since 4122 was 4034, checked in by cameron, 5 years ago

Cleanups to clear compiler warnings.

File size: 8.2 KB
RevLine 
[3917]1#include "re_nullable.h"
2
3/*
4
5 A regular expression is nullable if it (a) matches the empty
6 string, and (b) applies everywhere.  Note that Start (^) and
7 End ($) match the empty string, but not everywhere).
8
9*/
10
11RE* RE_Nullable::removeNullablePrefix(RE* re)
12{
13    RE* retVal = 0;
14
15    if (Seq* re_seq = dynamic_cast<Seq*>(re))
16    {
17        std::list<RE*>* re_list = re_seq->GetREList();
18        std::list<RE*>* t1_list = new std::list<RE*>();
19        t1_list->assign(re_list->begin(), re_list->end());
[3935]20        Seq* new_seq = new Seq(removeNullableSeqPrefix(t1_list));
21        new_seq->setType(re_seq->getType());
[3917]22
[3935]23        return new_seq;
[3917]24    }
25    else if (Alt* re_alt = dynamic_cast<Alt*>(re))
26    {
27        Alt* new_alt = new Alt();
28        std::list<RE*>::iterator it;
29
30        for (it = re_alt->GetREList()->begin(); it != re_alt->GetREList()->end(); ++it)
31        {
32            new_alt->AddREListItem(removeNullablePrefix(*it));
33        }
34
35        return new_alt;
36    }
37    else if (Rep* re_rep = dynamic_cast<Rep*>(re))
38    {
39        if ((re_rep->getLB() == 0) || (isNullable(re_rep->getRE())))
40        {
41            return new Seq();
42        }
43        else if (hasNullablePrefix(re_rep->getRE()))
44        {
45            //std::cout << "removeNullablePrefix->Rep->hasNullablePrefix:" << std::endl;
46            std::list<RE*>* seq_lst = new std::list<RE*>();
47            seq_lst->push_back(new Rep(re_rep->getRE(), re_rep->getLB()-1, re_rep->getLB()-1));
48            seq_lst->push_back(removeNullablePrefix(re_rep->getRE()));
49
[3935]50            return RE_Simplifier::mkSeq(Seq::Normal, seq_lst);
[3917]51        }
52        else
53        {
54            return RE_Simplifier::mkRep(re_rep->getRE(), re_rep->getLB(), re_rep->getLB());
55        }
56    }
57    else
58    {
59        return re;
60    }
61}
62
63std::list<RE*>* RE_Nullable::removeNullableSeqPrefix(std::list<RE*>* re_list)
64{
65    if (re_list->size() == 0)
66    {
67        return re_list;
68    }
69    else if(isNullable(re_list->front()))
70    {
71        re_list->pop_front();
72
73        return removeNullableSeqPrefix(re_list);
74    }
75    else
76    {
77        RE* re = re_list->front();
78        re_list->pop_front();
79        re_list->push_front(removeNullablePrefix(re));
80        re_list->reverse();
81
82        return re_list;
83    }
84}
85
86RE* RE_Nullable::removeNullableSuffix(RE* re)
87{
88    if (Seq* re_seq = dynamic_cast<Seq*>(re))
89    {
90        std::list<RE*>* re_list = re_seq->GetREList();
91        std::list<RE*>* t1_list = new std::list<RE*>();
92        t1_list->assign(re_list->begin(), re_list->end());
[3935]93        Seq* new_seq = new Seq(removeNullableSeqSuffix(t1_list));
94        new_seq->setType(re_seq->getType());
95        return new_seq;
[3917]96    }
97    else if (Alt* re_alt = dynamic_cast<Alt*>(re))
98    {
99        Alt* new_alt = new Alt();
100        std::list<RE*>::iterator it;
101
102        for (it = re_alt->GetREList()->begin(); it != re_alt->GetREList()->end(); ++it)
103        {
104            new_alt->AddREListItem(removeNullableSuffix(*it));
105        }
106
107        return new_alt;
108    }
109    else if (Rep* re_rep = dynamic_cast<Rep*>(re))
110    {
111        if ((re_rep->getLB() == 0) || (isNullable(re_rep->getRE())))
112        {
113            //std::cout << "removeNullableSuffix->Rep->lb=0 or is nullable:" << std::endl;
114            return new Seq();
115        }
116        else if (hasNullableSuffix(re_rep->getRE()))
117        {
118            //std::cout << "removeNullableSuffix->Rep->hasNullableSuffix:" << std::endl;
119            std::list<RE*>* seq_lst = new std::list<RE*>();
120            seq_lst->push_back(removeNullableSuffix(re_rep->getRE()));
121            seq_lst->push_back(new Rep(re_rep->getRE(), re_rep->getLB()-1, re_rep->getLB()-1));
122
[3935]123            return RE_Simplifier::mkSeq(Seq::Normal, seq_lst);
[3917]124        }
125        else
126        {
127            return RE_Simplifier::mkRep(re_rep->getRE(), re_rep->getLB(), re_rep->getLB());
128        }
129    }
130    else
131    {
132        return re;
133    }
134}
135
136std::list<RE*>* RE_Nullable::removeNullableSeqSuffix(std::list<RE*>* re_list)
137{
138    if (re_list->size() == 0)
139    {
140        return re_list;
141    }
142
143    RE* seq_re = re_list->front();
144    re_list->pop_front();
145
146    if (isNullableSeq(re_list))
147    {
148
149        std::list<RE*>* t1_list = new std::list<RE*>();
150        t1_list->push_back(removeNullableSuffix(seq_re));
151
152        return t1_list;
153    }
154
155    std::list<RE*>* t2_list;
156    t2_list = removeNullableSeqSuffix(re_list);
157    t2_list->push_back(seq_re);
158
159    return t2_list;
160}
161
162bool RE_Nullable::isNullable(RE* re)
163{
[4034]164    if (Seq* re_seq = dynamic_cast<Seq*>(re))
[3917]165    {
166        return isNullableSeq(re_seq->GetREList());
167    }
168    else if (Alt* re_alt = dynamic_cast<Alt*>(re))
169    {
170        return isNullableAlt(re_alt->GetREList());
171    }
172    else if (Rep* re_rep = dynamic_cast<Rep*>(re))
173    {   
174        return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
175    }
[4034]176    else {
177        return false;
178    }
[3917]179}
180
181bool RE_Nullable::isNullableSeq(std::list<RE*>* re_list)
182{
183    std::list<RE*>::iterator it = re_list->begin();
184    return isNullableSeq_helper(re_list, it);
185}
186
187bool RE_Nullable::isNullableSeq_helper(std::list<RE*>* re_list, std::list<RE*>::iterator it)
188{
189    if (it != re_list->end())
190    {
191        return isNullable(*it) ? isNullableSeq_helper(re_list, ++it) : false;
192    }
193    else
194    {
195        return true;
196    }
197}
198
199bool RE_Nullable::isNullableAlt(std::list<RE*>* re_list)
200{
201    std::list<RE*>::iterator it = re_list->begin();
202    return isNullableAlt_helper(re_list, it);
203}
204
205bool RE_Nullable::isNullableAlt_helper(std::list<RE*>* re_list, std::list<RE*>::iterator it)
206{
207    if (it != re_list->end())
208    {
209        return isNullable(*it) ? true : isNullableAlt_helper(re_list, ++it);
210    }
211    else
212    {
213        return false;
214    }
215}
216
217bool RE_Nullable::hasNullablePrefix(RE* re)
218{
219    if (Seq* seq = dynamic_cast<Seq*>(re))
220    {
221        if (isNullable(seq->GetREList()->back()))
222        {
223            return true;
224        }
225        else
226        {
227            return hasNullablePrefix(seq->GetREList()->back());
228        }
229    }
230    else if (Alt* alt = dynamic_cast<Alt*>(re))
231    {
232        if (alt->GetREList()->size() == 0)
233        {
234            return false;
235        }
236        else
237        {
238            if (hasNullablePrefix(alt->GetREList()->back()))
239            {
240                return true;
241            }
242            else
243            {
244                std::list<RE*> alt_list;
245                std::list<RE*>::iterator it;
246                it = alt->GetREList()->end();
247                it--;
248                alt_list.insert(alt_list.end(), alt->GetREList()->begin(), it);
249                alt_list.reverse();
250
251                return hasNullablePrefix(new Alt(alt_list));
252            }
253        }
254    }
255    else if (Rep* rep = dynamic_cast<Rep*>(re))
256    {
257        return hasNullablePrefix(rep->getRE());
258    }
259    else
260    {
261        return false;
262    }
263}
264
265bool RE_Nullable::hasNullableSuffix(RE* re)
266{
267    if (Seq* seq = dynamic_cast<Seq*>(re))
268    {
269        if (seq->GetREList()->size() == 1)
270        {
271            if (isNullable(seq->GetREList()->back()))
272            {
273                return true;
274            }
275            else
276            {
277                return hasNullableSuffix(seq->GetREList()->front());
278            }
279        }
280        else
281        {
282            std::list<RE*> seq_list;
283            std::list<RE*>::iterator it;
284            it = seq->GetREList()->begin();
285            it++;
286            seq_list.insert(seq_list.end(), it, seq->GetREList()->end());
287            seq_list.reverse();
288
289            return hasNullableSuffix(new Seq(seq_list));
290        }
291    }
292    else if (Alt* alt = dynamic_cast<Alt*>(re))
293    {
294        if (alt->GetREList()->size() == 0)
295        {
296            return false;
297        }
298        else
299        {
300            if (hasNullableSuffix(alt->GetREList()->front()))
301            {
302                return true;
303            }
304            else
305            {
306                std::list<RE*> alt_list;
307                std::list<RE*>::iterator it;
308                it = alt->GetREList()->begin();
309                it++;
310                alt_list.insert(alt_list.begin(), it, alt->GetREList()->end());
311                alt_list.reverse();
312
313                return hasNullableSuffix(new Alt(alt_list));
314            }
315        }
316    }
317    else if (Rep* rep = dynamic_cast<Rep*>(re))
318    {
319        return hasNullableSuffix(rep->getRE());
320    }
321    else
322    {
323        return false;
324    }
325}
326
327
328
Note: See TracBrowser for help on using the repository browser.