source: icGREP/icgrep-devel/icgrep/re_simplifier.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: 6.7 KB
Line 
1#include "re_simplifier.h"
2
3
4RE* RE_Simplifier::simplify(RE* re)
5{
6    RE* retVal = 0;
7
8    if (Alt* re_alt = dynamic_cast<Alt*>(re))
9    {
10        std::list<RE*> re_list;
11        std::list<RE*>::reverse_iterator rit = re_alt->GetREList()->rbegin();
12
13        for (rit = re_alt->GetREList()->rbegin(); rit != re_alt->GetREList()->rend(); ++rit)
14        {
15            re_list.push_back(simplify(*rit));
16        }
17
18        retVal = mkAlt(&re_list);
19    }
20    else if (Seq* re_seq = dynamic_cast<Seq*>(re))
21    {
22        std::list<RE*> re_list;
23        std::list<RE*>::iterator it;
24
25        for (it = re_seq->GetREList()->begin(); it != re_seq->GetREList()->end(); ++it)
26        {
27            re_list.push_front(simplify(*it));
28        }
29
30        retVal = mkSeq(re_seq->getType(), &re_list);
31    }
32    else if (CC* re_cc = dynamic_cast<CC*>(re))
33    {
34        retVal = re_cc;
35    }
36    else if (Name* re_name = dynamic_cast<Name*>(re))
37    {
38        retVal = new Name(re_name->getName());
39    }
40    else if (Rep* re_rep = dynamic_cast<Rep*>(re))
41    {
42        retVal = mkRep(simplify(re_rep->getRE()), re_rep->getLB(), re_rep->getUB());
43    }
44    else if (Start* re_start = dynamic_cast<Start*>(re))
45    {
46        retVal = new Start();
47    }
48    else if (End* re_end = dynamic_cast<End*>(re))
49    {
50        retVal = new End();
51    }
52
53    return retVal;
54}
55
56RE* RE_Simplifier::mkSeq(Seq::Type type, std::list<RE*>* re_list)
57{
58    /*
59      mkSeq - make a sequence, but flatten.  Result might not be a Seq. If
60      there is only one component for a sequence, simply return that.
61    */
62
63    //We don't want to modify the AST that we are walking so we'll make a copy.
64    std::list<RE*>* t1_list = new std::list<RE*>();
65    //Linear in initial and final sizes.
66    t1_list->assign(re_list->begin(), re_list->end());
67    if (t1_list->size() > 0)
68    {
69        std::list<RE*>* t2_list = mkSeqList(t1_list);
70        if (t2_list->size() > 1)
71        {
72            Seq* new_seq = new Seq(t2_list);
73            new_seq->setType(type);
74            return new_seq;
75        }
76        else
77        {
78            return t2_list->back();
79        }
80    }
81    else
82    {
83        return 0;
84    }
85}
86
87std::list<RE*>* RE_Simplifier::mkSeqList(std::list<RE*>* re_list)
88{
89    std::list<RE*>* ret_list = new std::list<RE*>();
90    return mkSeqList_helper(ret_list, re_list);
91}
92
93std::list<RE*>* RE_Simplifier::mkSeqList_helper(std::list<RE*>* ret_list, std::list<RE*>* re_list)
94{
95    /*
96      Build a list for Seq, flattening subsequences.
97    */
98
99    if (re_list->size() == 0)
100    {
101        return ret_list;
102    }
103    else if (Seq* seq = dynamic_cast<Seq*>(re_list->back()))
104    {
105        re_list->pop_back();
106        seq->GetREList()->reverse();
107        re_list->insert(re_list->end(), seq->GetREList()->begin(), seq->GetREList()->end());
108
109        return mkSeqList_helper(ret_list, re_list);
110    }
111    else
112    {
113        ret_list->push_front(re_list->back());
114        re_list->pop_back();
115        return mkSeqList_helper(ret_list, re_list);
116    }
117}
118
119RE* RE_Simplifier::mkAlt(std::list<RE*>* re_list)
120{
121    /*
122      mkAlt - make a list of alternatives, but flatten, and combine character
123      classes.  If there is only one alternative, simply return that.
124    */
125
126    std::list<RE*>* t1_list = new std::list<RE*>();
127    t1_list->assign(re_list->begin(), re_list->end());
128    if (t1_list->size() > 0)
129    {
130        std::list<RE*>* t2_list = mkAltList(t1_list);
131        if (t2_list->size() > 1)
132        {
133            return new Alt(t2_list);
134        }
135        else
136        {
137            return t2_list->back();
138        }
139    }
140    else
141    {
142        return 0;
143    }
144}
145
146std::list<RE*>* RE_Simplifier::mkAltList(std::list<RE*>* re_list)
147{
148    std::list<RE*>* ret_list = new std::list<RE*>();
149    return mkAltList_helper(ret_list, re_list);
150}
151
152std::list<RE*>* RE_Simplifier::mkAltList_helper(std::list<RE*>* ret_list, std::list<RE*>* re_list)
153{
154    /*
155      Build a list for Alt, flattening alternative subgroups, and combining character classes.  We
156      move character classes towards the end of the list to ensure that all combinations are found.
157    */
158
159    if (re_list->size() == 0)
160    {
161        return ret_list;
162    }
163    else if (Alt* alt = dynamic_cast<Alt*>(re_list->back()))
164    {
165        re_list->pop_back();
166        re_list->insert(re_list->end(), alt->GetREList()->begin(), alt->GetREList()->end());
167        return mkAltList_helper(ret_list, re_list);
168    }
169    else if (re_list->size() >= 2)
170    {
171        std::list<RE*>::iterator it;
172        it = re_list->end();
173        it--;
174        if (CC* cc1 = dynamic_cast<CC*>(*it))
175        {
176            it--;
177            if(CC* cc2 = dynamic_cast<CC*>(*it))
178            {
179                CC* cc = new CC(cc1, cc2);
180                re_list->pop_back();
181                re_list->pop_back();
182                re_list->push_back(cc);
183                return mkAltList_helper(ret_list, re_list);
184            }
185            else
186            {
187                std::list<RE*>::iterator item1 = re_list->end();
188                --item1;
189                std::list<RE*>::iterator item2 = item1;
190                --item2;
191                std::swap(*item1, *item2);
192                return mkAltList_helper(ret_list, re_list);
193            }
194        }
195        ret_list->push_front(re_list->back());
196        re_list->pop_back();
197        return mkAltList_helper(ret_list, re_list);
198    }
199    else
200    {
201        ret_list->push_front(re_list->back());
202        re_list->pop_back();
203        return mkAltList_helper(ret_list, re_list);
204    }
205}
206
207int RE_Simplifier::ubCombine(int h1, int h2)
208{
209    if ((h1 == unboundedRep) || (h2 == unboundedRep))
210    {
211        return unboundedRep;
212    }
213    else
214    {
215        return h1 * h2;
216    }
217}
218
219RE* RE_Simplifier::mkRep(RE* re, int lb2, int ub2)
220{
221    if (Rep* rep = dynamic_cast<Rep*>(re))
222    {
223        if (((rep->getUB() == unboundedRep) && (lb2 > 0)) ||
224                ((rep->getUB() == unboundedRep) && (rep->getLB() <= 1)))
225        {
226            return new Rep(rep->getRE(), rep->getLB() * lb2, unboundedRep);
227        }
228        else if ((rep->getUB() == unboundedRep) && (lb2 == 0))
229        {
230            return new Rep(rep, 0, 1);
231        }
232        else if ((rep->getUB() * lb2) >= (rep->getLB() * (lb2 + 1) - 1))
233        {
234            return new Rep(rep->getRE(), rep->getLB() * lb2, ubCombine(rep->getUB(), ub2));
235        }
236        else
237        {
238            return new Rep(rep, lb2, ub2);
239        }
240    }
241    else
242    {
243        if (Seq* seq = dynamic_cast<Seq*>(re))
244        {
245            if(seq->GetREList()->size() == 0)
246            {
247                return seq;
248            }
249        }
250
251        if ((lb2 == 0) && (ub2 == 0))
252        {
253            return new Seq();
254        }
255        else if ((lb2 == 1) && (ub2 == 1))
256        {
257            return re;
258        }
259        else
260        {
261            return new Rep(re, lb2, ub2);
262        }
263    }
264}
Note: See TracBrowser for help on using the repository browser.