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

Last change on this file since 3994 was 3965, checked in by daled, 5 years ago

The Unicode category 'Nd' is in place and it is working.

File size: 8.5 KB
Line 
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());
20        Seq* new_seq = new Seq(removeNullableSeqPrefix(t1_list));
21        new_seq->setType(re_seq->getType());
22
23        return new_seq;
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
50            return RE_Simplifier::mkSeq(Seq::Normal, seq_lst);
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());
93        Seq* new_seq = new Seq(removeNullableSeqSuffix(t1_list));
94        new_seq->setType(re_seq->getType());
95        return new_seq;
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
123            return RE_Simplifier::mkSeq(Seq::Normal, seq_lst);
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{
164    if (CC* re_cc = dynamic_cast<CC*>(re))
165    {
166        return false;
167    }
168    else if (Name* re_name = dynamic_cast<Name*>(re))
169    {
170        return false;
171    }
172    else if (Start* re_start = dynamic_cast<Start*>(re))
173    {
174        return false;
175    }
176    else if (End* re_end = dynamic_cast<End*>(re))
177    {
178        return false;
179    }
180    else if (Seq* re_seq = dynamic_cast<Seq*>(re))
181    {
182        return isNullableSeq(re_seq->GetREList());
183    }
184    else if (Alt* re_alt = dynamic_cast<Alt*>(re))
185    {
186        return isNullableAlt(re_alt->GetREList());
187    }
188    else if (Rep* re_rep = dynamic_cast<Rep*>(re))
189    {   
190        return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
191    }
192}
193
194bool RE_Nullable::isNullableSeq(std::list<RE*>* re_list)
195{
196    std::list<RE*>::iterator it = re_list->begin();
197    return isNullableSeq_helper(re_list, it);
198}
199
200bool RE_Nullable::isNullableSeq_helper(std::list<RE*>* re_list, std::list<RE*>::iterator it)
201{
202    if (it != re_list->end())
203    {
204        return isNullable(*it) ? isNullableSeq_helper(re_list, ++it) : false;
205    }
206    else
207    {
208        return true;
209    }
210}
211
212bool RE_Nullable::isNullableAlt(std::list<RE*>* re_list)
213{
214    std::list<RE*>::iterator it = re_list->begin();
215    return isNullableAlt_helper(re_list, it);
216}
217
218bool RE_Nullable::isNullableAlt_helper(std::list<RE*>* re_list, std::list<RE*>::iterator it)
219{
220    if (it != re_list->end())
221    {
222        return isNullable(*it) ? true : isNullableAlt_helper(re_list, ++it);
223    }
224    else
225    {
226        return false;
227    }
228}
229
230bool RE_Nullable::hasNullablePrefix(RE* re)
231{
232    if (Seq* seq = dynamic_cast<Seq*>(re))
233    {
234        if (isNullable(seq->GetREList()->back()))
235        {
236            return true;
237        }
238        else
239        {
240            return hasNullablePrefix(seq->GetREList()->back());
241        }
242    }
243    else if (Alt* alt = dynamic_cast<Alt*>(re))
244    {
245        if (alt->GetREList()->size() == 0)
246        {
247            return false;
248        }
249        else
250        {
251            if (hasNullablePrefix(alt->GetREList()->back()))
252            {
253                return true;
254            }
255            else
256            {
257                std::list<RE*> alt_list;
258                std::list<RE*>::iterator it;
259                it = alt->GetREList()->end();
260                it--;
261                alt_list.insert(alt_list.end(), alt->GetREList()->begin(), it);
262                alt_list.reverse();
263
264                return hasNullablePrefix(new Alt(alt_list));
265            }
266        }
267    }
268    else if (Rep* rep = dynamic_cast<Rep*>(re))
269    {
270        return hasNullablePrefix(rep->getRE());
271    }
272    else
273    {
274        return false;
275    }
276}
277
278bool RE_Nullable::hasNullableSuffix(RE* re)
279{
280    if (Seq* seq = dynamic_cast<Seq*>(re))
281    {
282        if (seq->GetREList()->size() == 1)
283        {
284            if (isNullable(seq->GetREList()->back()))
285            {
286                return true;
287            }
288            else
289            {
290                return hasNullableSuffix(seq->GetREList()->front());
291            }
292        }
293        else
294        {
295            std::list<RE*> seq_list;
296            std::list<RE*>::iterator it;
297            it = seq->GetREList()->begin();
298            it++;
299            seq_list.insert(seq_list.end(), it, seq->GetREList()->end());
300            seq_list.reverse();
301
302            return hasNullableSuffix(new Seq(seq_list));
303        }
304    }
305    else if (Alt* alt = dynamic_cast<Alt*>(re))
306    {
307        if (alt->GetREList()->size() == 0)
308        {
309            return false;
310        }
311        else
312        {
313            if (hasNullableSuffix(alt->GetREList()->front()))
314            {
315                return true;
316            }
317            else
318            {
319                std::list<RE*> alt_list;
320                std::list<RE*>::iterator it;
321                it = alt->GetREList()->begin();
322                it++;
323                alt_list.insert(alt_list.begin(), it, alt->GetREList()->end());
324                alt_list.reverse();
325
326                return hasNullableSuffix(new Alt(alt_list));
327            }
328        }
329    }
330    else if (Rep* rep = dynamic_cast<Rep*>(re))
331    {
332        return hasNullableSuffix(rep->getRE());
333    }
334    else
335    {
336        return false;
337    }
338}
339
340
341
Note: See TracBrowser for help on using the repository browser.