source: icGREP/icgrep-devel/icgrep/re_simplifier.cpp @ 3917

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

New files for re simplification

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