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

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

The parser is now able to parse unicode categories.

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