source: icGREP/icgrep-devel/icgrep/re_parser.cpp @ 3914

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

Updates for icgrep-0.9: re simplifications, re names, replimit mods, debugged while loops

File size: 17.9 KB
Line 
1/*
2 *  Copyright (c) 2014 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6
7#include "re_parser.h"
8
9
10ParseResult* RE_Parser::parse_re(std::string input_string)
11{
12    parse_result_retVal re_result = parse_re_helper(input_string);
13
14    if (re_result.remaining.length() == 0)
15    {
16        return re_result.result;
17    }
18    else if (ParseSuccess* re_success = dynamic_cast<ParseSuccess*>(re_result.result))
19    {
20        ParseFailure* failure = new ParseFailure("Junk remaining!");
21
22        return failure;
23    }
24    else if (ParseFailure* re_failure = dynamic_cast<ParseFailure*>(re_result.result))
25    {
26        return re_failure;
27    }
28    else
29    {
30        return 0;
31    }
32}
33
34parse_result_retVal RE_Parser::parse_re_helper(std::string s)
35{
36    parse_result_retVal result_retVal;
37
38    parse_re_list_retVal af_result = parse_re_alt_form_list(s);
39
40    if (af_result.re_list.size() == 0)
41    {
42        result_retVal.result = new ParseFailure("No regular expression found!");
43        result_retVal.remaining = s;
44    }
45    else if (af_result.re_list.size() == 1)
46    {
47        result_retVal.result = new ParseSuccess(af_result.re_list.front());
48        result_retVal.remaining = af_result.remaining;
49    }
50    else
51    {
52        result_retVal.result = new ParseSuccess(new Alt(&af_result.re_list));
53        result_retVal.remaining = af_result.remaining;
54    }
55
56    return result_retVal;
57}
58
59parse_re_list_retVal RE_Parser::parse_re_alt_form_list(std::string s)
60{
61    parse_re_list_retVal re_list_retVal;
62    parse_result_retVal form_result = parse_re_form(s);
63
64    if (ParseSuccess* re_success = dynamic_cast<ParseSuccess*>(form_result.result))
65    {
66        if (form_result.remaining.operator [](0) == '|')
67        {           
68            parse_re_list_retVal t1_re_list_retVal =
69                    parse_re_alt_form_list(form_result.remaining.substr(1, form_result.remaining.length() - 1));
70            std::list<RE*>::iterator it;
71            it=t1_re_list_retVal.re_list.begin();
72            re_list_retVal.re_list.assign(it, t1_re_list_retVal.re_list.end());
73            re_list_retVal.remaining = t1_re_list_retVal.remaining;
74        }
75        else
76        {
77            re_list_retVal.remaining = form_result.remaining;
78        }
79        re_list_retVal.re_list.push_back(re_success->getRE());
80    }
81    else
82    {
83        re_list_retVal.re_list.clear();
84        re_list_retVal.remaining = s;
85    }
86
87    return re_list_retVal;
88}
89
90parse_result_retVal RE_Parser::parse_re_form(std::string s)
91{
92    parse_result_retVal form_retVal;
93    parse_re_list_retVal item_list_result = parse_re_item_list(s);
94
95    if (item_list_result.re_list.size() == 0)
96    {
97        form_retVal.result = new ParseFailure("No Regular Expression Found!");
98        form_retVal.remaining = s;
99    }
100    else if (item_list_result.re_list.size() == 1)
101    {
102        form_retVal.result = new ParseSuccess(item_list_result.re_list.front());
103        form_retVal.remaining = item_list_result.remaining;
104    }
105    else
106    {
107        form_retVal.result = new ParseSuccess(new Seq(&item_list_result.re_list));
108        form_retVal.remaining = item_list_result.remaining;
109    }
110
111    return form_retVal;
112}
113
114parse_re_list_retVal RE_Parser::parse_re_item_list(std::string s)
115{
116    parse_re_list_retVal item_list_retVal;
117    parse_result_retVal item_result = parse_re_item(s);
118
119    if (ParseSuccess* re_success = dynamic_cast<ParseSuccess*>(item_result.result))
120    {
121        parse_re_list_retVal t1_item_list_retVal = parse_re_item_list(item_result.remaining);
122
123        std::list<RE*>::iterator it;
124        it=t1_item_list_retVal.re_list.begin();
125        item_list_retVal.re_list.assign(it, t1_item_list_retVal.re_list.end());
126        item_list_retVal.re_list.push_back(re_success->getRE());
127        item_list_retVal.remaining = t1_item_list_retVal.remaining;
128    }
129    else
130    {
131        item_list_retVal.re_list.clear();
132        item_list_retVal.remaining = s;
133    }
134
135    return item_list_retVal;
136}
137
138parse_result_retVal RE_Parser::parse_re_item(std::string s)
139{
140    parse_result_retVal item_retVal;
141    parse_result_retVal unit_result = parse_re_unit(s);
142
143    if (ParseSuccess* re_success = dynamic_cast<ParseSuccess*>(unit_result.result))
144    {
145        item_retVal = extend_item(re_success->getRE(), unit_result.remaining);
146    }
147    else
148    {
149        item_retVal.result = new ParseFailure("Parse item failure!");
150        item_retVal.remaining = s;
151    }
152
153    return item_retVal;
154}
155
156parse_result_retVal RE_Parser::parse_re_unit(std::string s)
157{
158    parse_result_retVal unit_retVal;
159
160    if (s.length() == 0)
161    {
162        unit_retVal.result = new ParseFailure("Incomplete regular expression! (parse_re_unit)");
163        unit_retVal.remaining = "";
164    }
165    else if (s.operator[](0) == '(')
166    {
167        parse_result_retVal t1_unit_retVal = parse_re_helper(s.substr(1, s.length() - 1));
168        ParseSuccess* success = dynamic_cast<ParseSuccess*>(t1_unit_retVal.result);
169        if ((success != 0) && (t1_unit_retVal.remaining.operator[](0) == ')'))
170        {
171            unit_retVal.result = success;
172            unit_retVal.remaining = t1_unit_retVal.remaining.substr(1, t1_unit_retVal.remaining.length() - 1);
173        }
174        else
175        {
176            unit_retVal.result = new ParseFailure("Bad parenthesized RE!");
177            unit_retVal.remaining = s.substr(1, s.length() - 1);
178        }
179    }
180    else if (s.operator [](0) == '^')
181    {
182        unit_retVal.result = new ParseSuccess(new Start);
183        unit_retVal.remaining = s.substr(1, s.length() - 1);
184    }
185    else if (s.operator[](0) == '$')
186    {
187        unit_retVal.result = new ParseSuccess(new End);
188        unit_retVal.remaining = s.substr(1, s.length() - 1);
189    }
190    else
191    {
192        unit_retVal = parse_cc(s);
193    }
194
195    return unit_retVal;
196}
197
198parse_result_retVal RE_Parser::extend_item(RE *re, std::string s)
199{
200     parse_result_retVal extend_item_retVal;
201
202     if (s.operator [](0) == '*')
203     {
204         return extend_item(new Rep(re, 0, unboundedRep), s.substr(1, s.length() - 1));
205     }
206     else if (s.operator[](0) == '?')
207     {
208         return extend_item(new Rep(re, 0, 1), s.substr(1, s.length() - 1));
209     }
210     else if (s.operator[](0) == '+')
211     {
212         return extend_item(new Rep(re, 1, unboundedRep), s.substr(1, s.length() - 1));
213     }
214     else if (s.operator[](0) == '{')
215     {
216        parse_int_retVal int_retVal = parse_int(s.substr(1, s.length() - 1));
217
218        if ((int_retVal.i != -1) && (int_retVal.remaining.operator [](0) == '}'))
219        {
220            extend_item_retVal =
221                    extend_item(new Rep(re, int_retVal.i, int_retVal.i), int_retVal.remaining.substr(1, int_retVal.remaining.length() - 1));
222
223        }
224        else if ((int_retVal.i != -1) && ((int_retVal.remaining.operator [](0) == ',') && (int_retVal.remaining.operator [](1) == '}')))
225        {
226            extend_item_retVal =
227                    extend_item(new Rep(re, int_retVal.i, unboundedRep), int_retVal.remaining.substr(2, int_retVal.remaining.length() - 2));
228
229        }
230        else if ((int_retVal.i != -1) && (int_retVal.remaining.operator [](0) == ','))
231        {
232            parse_int_retVal t1_int_retVal = parse_int(int_retVal.remaining.substr(1, int_retVal.remaining.length() - 1));
233
234            if ((t1_int_retVal.i != -1) && (t1_int_retVal.remaining.operator [](0) == '}'))
235            {
236                extend_item_retVal =
237                        extend_item(new Rep(re, int_retVal.i, t1_int_retVal.i), t1_int_retVal.remaining.substr(1, t1_int_retVal.remaining.length() - 1));
238            }
239            else
240            {
241                extend_item_retVal.result = new ParseFailure("Bad upper bound!");
242                extend_item_retVal.remaining = int_retVal.remaining.substr(1, int_retVal.remaining.length() - 1);
243            }
244        }
245        else
246        {
247            extend_item_retVal.result = new ParseFailure("Bad lower bound!");
248            extend_item_retVal.remaining = s.substr(1, s.length() - 1);
249        }
250     }
251     else
252     {
253         extend_item_retVal.result = new ParseSuccess(re);
254         extend_item_retVal.remaining = s;
255     }
256
257     return extend_item_retVal;
258}
259
260parse_result_retVal RE_Parser::parse_cc(std::string s)
261{
262    parse_result_retVal cc_retVal;
263
264    if (s.operator [](0) == '\\')
265    {
266        if (s.operator [](1) == '?')
267        {
268            cc_retVal.result = new ParseSuccess(new CC('?'));
269        }
270        else if (s.operator [](1) == '+')
271        {
272            cc_retVal.result = new ParseSuccess(new CC('+'));
273        }
274        else if (s.operator [](1) == '*')
275        {
276            cc_retVal.result = new ParseSuccess(new CC('*'));
277        }
278        else if (s.operator [](1) == '(')
279        {
280            cc_retVal.result = new ParseSuccess(new CC('('));
281        }
282        else if (s.operator [](1) == ')')
283        {
284            cc_retVal.result = new ParseSuccess(new CC(')'));
285        }
286        else if (s.operator [](1) == '{')
287        {
288            cc_retVal.result = new ParseSuccess(new CC('{'));
289        }
290        else if (s.operator [](1) == '}')
291        {
292            cc_retVal.result = new ParseSuccess(new CC('}'));
293        }
294        else if (s.operator [](1) == '[')
295        {
296            cc_retVal.result = new ParseSuccess(new CC('['));
297        }
298        else if (s.operator [](1) == ']')
299        {
300            cc_retVal.result = new ParseSuccess(new CC(']'));
301        }
302        else if (s.operator [](1) == '|')
303        {
304            cc_retVal.result = new ParseSuccess(new CC('|'));
305        }
306        else if (s.operator [](1) == '.')
307        {
308            cc_retVal.result = new ParseSuccess(new CC('.'));
309        }
310        else if (s.operator [](1) == '\\')
311        {
312            cc_retVal.result = new ParseSuccess(new CC('\\'));
313        }
314        else if (s.operator [](1) == 'u')
315        {
316            parse_int_retVal hex_val = parse_hex(s.substr(2, s.length() - 2));
317
318            if (hex_val.i == -1)
319            {
320                cc_retVal.result = new ParseFailure("Bad Unicode hex notation!");
321                cc_retVal.remaining = hex_val.remaining;
322            }
323            else
324            {
325                cc_retVal.result = new ParseSuccess(new CC(hex_val.i));
326                cc_retVal.remaining = hex_val.remaining;
327            }
328
329            return cc_retVal;
330        }
331        else
332        {
333            cc_retVal.result = new ParseFailure("Illegal backslash escape!");
334            cc_retVal.remaining = s.substr(1, s.length() - 1);
335
336            return cc_retVal;
337        }
338
339        cc_retVal.remaining = s.substr(2, s.length() - 2);
340
341        return cc_retVal;
342    }
343
344    if (s.operator [](0) == '.')
345    {       
346        CC* cc = new CC();
347        cc->insert_range(0, 9);
348        cc->insert_range(11, 127);
349        cc_retVal.result = new ParseSuccess(cc);
350        cc_retVal.remaining = s.substr(1, s.length() - 1);
351
352        return cc_retVal;
353    }
354
355    if (s.operator [](0) == '[')
356    {
357        if (s.operator[](1) == '^')
358        {
359            cc_retVal = negate_cc_result(parse_cc_body(s.substr(2, s.length() - 2)));
360        }
361        else
362        {
363            cc_retVal = parse_cc_body(s.substr(1, s.length() - 1));
364        }
365
366        return cc_retVal;
367    }
368
369    std::string metacharacters = "?+*(){}[]|";
370    std::string c = s.substr(0,1);
371
372    if (metacharacters.find(c) == std::string::npos)
373    {
374        cc_retVal.result = new ParseSuccess(new CC(s.operator [](0)));
375        cc_retVal.remaining = s.substr(1, s.length() - 1);
376    }
377    else
378    {
379        cc_retVal.result = new ParseFailure("Metacharacter alone!");
380        cc_retVal.remaining = s;
381    }
382
383    return cc_retVal;
384}
385
386parse_result_retVal RE_Parser::parse_cc_body(std::string s)
387{
388    parse_result_retVal result_retVal;
389
390    if (s.length() == 0)
391    {
392        result_retVal.result = new ParseFailure("Unclosed character class!");
393        result_retVal.remaining = "";
394    }
395    else
396    {
397        CC* cc = new CC();
398        result_retVal = parse_cc_body1(s.operator [](0), s.substr(1, s.length() - 1), cc);
399    }
400
401    return result_retVal;
402}
403
404parse_result_retVal RE_Parser::parse_cc_body0(std::string s, CC* cc_sofar)
405{
406    parse_result_retVal cc_body0_retVal;
407
408    if (s.length() == 0)
409    {
410        delete cc_sofar;
411        cc_body0_retVal.result = new ParseFailure("Unclosed character class!");
412        cc_body0_retVal.remaining = "";
413    }
414    else if (s.operator [](0) == ']')
415    {
416        cc_body0_retVal.result = new ParseSuccess(cc_sofar);
417        cc_body0_retVal.remaining = s.substr(1, s.length() - 1);
418    }
419    else if ((s.operator [](0) == '-') && (s.operator [](1) == ']'))
420    {
421        cc_sofar->insert1('-');
422        cc_body0_retVal.result = new ParseSuccess(cc_sofar);
423        cc_body0_retVal.remaining = s.substr(2, s.length() - 2);
424    }
425    else if (s.operator [](0) == '-')
426    {
427        delete cc_sofar;
428        cc_body0_retVal.result = new ParseFailure("Bad range in character class!");
429        cc_body0_retVal.remaining = s.substr(1, s.length() - 1);
430    }
431    else
432    {
433        cc_body0_retVal = parse_cc_body1(s.operator [](0), s.substr(1, s.length() - 1), cc_sofar);
434    }
435
436    return cc_body0_retVal;
437}
438
439parse_result_retVal RE_Parser::parse_cc_body1(int chr, std::string s, CC* cc_sofar)
440{
441    parse_result_retVal cc_body1_retVal;
442
443    if (s.length() == 0)
444    {
445        delete cc_sofar;
446        cc_body1_retVal.result = new ParseFailure("Unclosed character class!");
447        cc_body1_retVal.remaining = "";
448    }
449    else if (s.operator [](0) == ']')
450    {
451        cc_sofar->insert1(chr);
452        cc_body1_retVal.result = new ParseSuccess(cc_sofar);
453        cc_body1_retVal.remaining = s.substr(1, s.length() - 1);
454    }
455    else if (s.length() == 1)
456    {
457        delete cc_sofar;
458        cc_body1_retVal.result = new ParseFailure("Unclosed character class!");
459        cc_body1_retVal.remaining = "";
460    }
461    else if ((s.operator [](0) == '-') && (s.operator [](1) == ']'))
462    {
463        cc_sofar->insert1(chr);
464        cc_sofar->insert1('-');
465        cc_body1_retVal = parse_cc_body0(s, cc_sofar);
466    }
467    else if ((s.operator [](0) == '-') && (s.operator [](1) == '\\') && (s.operator [](2) == 'u'))
468    {
469        parse_int_retVal int_retVal = parse_hex(s.substr(3, s.length() - 3));
470
471        if (int_retVal.i == -1)
472        {
473            cc_body1_retVal.result = new ParseFailure("Bad Unicode hex notation!");
474            cc_body1_retVal.remaining = "";
475        }
476        else
477        {
478            cc_sofar->insert_range(chr, int_retVal.i);
479            cc_body1_retVal = parse_cc_body0(int_retVal.remaining, cc_sofar);
480        }
481    }
482    else if ((s.operator [](0) == '-') && ( s.length() > 1))
483    {
484        cc_sofar->insert_range(chr, s.operator [](1));
485        cc_body1_retVal = parse_cc_body0(s.substr(2, s.length() - 2), cc_sofar);
486    }
487    else if ((s.operator [](0) == 'u') && ( s.length() > 1))
488    {
489        parse_int_retVal int_retVal = parse_hex(s.substr(1, s.length() - 1));
490
491        if (int_retVal.i == -1)
492        {
493            cc_body1_retVal.result = new ParseFailure("Bad Unicode hex notation!");
494            cc_body1_retVal.remaining = "";
495        }
496        else
497        {
498            cc_body1_retVal = parse_cc_body1(int_retVal.i, int_retVal.remaining, cc_sofar);
499        }
500    }
501    else
502    {
503        cc_sofar->insert1(chr);
504        cc_body1_retVal = parse_cc_body1(s.operator [](0), s.substr(1, s.length() - 1), cc_sofar);
505    }
506
507    return cc_body1_retVal;
508}
509
510parse_int_retVal RE_Parser::parse_hex(std::string s)
511{
512    parse_int_retVal int_retVal;
513
514    if (s.operator [](0) == '{')
515    {
516        int hexval_sofar = 0;
517        int_retVal = parse_hex_body(hexval_sofar, s.substr(1, s.length() - 1));
518
519    }
520    else
521    {
522        int_retVal.i = -1;
523        int_retVal.remaining = s;
524    }
525
526    return int_retVal;
527}
528
529parse_int_retVal RE_Parser::parse_hex_body(int i, std::string s)
530{
531    parse_int_retVal int_retVal;
532
533    if (s.length() == 0)
534    {
535        int_retVal.i = i;
536        int_retVal.remaining = "";
537    }
538    else if (s.operator [](0) == '}')
539    {
540        int_retVal.i = i;
541        int_retVal.remaining = s.substr(1, s.length() - 1);
542    }
543    else if ((s.operator [](0) >= '0') && (s.operator [](0) <= '9'))
544    {
545        int_retVal = parse_hex_body(parse_hex_body1(i, s.substr(0,1)), s.substr(1, s.length() - 1));
546    }
547    else if ((s.operator [](0) >= 'a') && (s.operator [](0) <= 'f'))
548    {
549        int_retVal = parse_hex_body(parse_hex_body1(i, s.substr(0,1)), s.substr(1, s.length() - 1));
550    }
551    else if ((s.operator [](0) >= 'A') && (s.operator [](0) <= 'F'))
552    {
553        int_retVal = parse_hex_body(parse_hex_body1(i, s.substr(0,1)), s.substr(1, s.length() - 1));
554    }
555    else
556    {
557        int_retVal.i = -1;
558        int_retVal.remaining = s;
559    }
560
561    return int_retVal;
562}
563
564int RE_Parser::parse_hex_body1(int i, std::string hex_str)
565{
566    int retVal = 0;
567    int newVal = 0;
568
569    retVal = i << 4;
570
571    std::stringstream ss(hex_str);
572    ss >> std::hex >> newVal;
573
574    retVal = retVal | newVal;
575
576    return retVal;
577}
578
579parse_int_retVal RE_Parser::parse_int(std::string s)
580{
581    parse_int_retVal int_retVal;
582
583    if (isdigit(s.operator [](0)))
584    {
585        int_retVal = parse_int1(s.operator [](0) - 48, s.substr(1, s.length() - 1));
586    }
587    else
588    {
589        int_retVal.i = -1;
590        int_retVal.remaining = s;
591    }
592
593    return int_retVal;
594}
595
596parse_int_retVal RE_Parser::parse_int1(int i, std::string s)
597{
598    parse_int_retVal int1_retVal;
599
600    if (s.length() == 0)
601    {
602        int1_retVal.i = i;
603        int1_retVal.remaining = "";
604    }
605    else if (isdigit(s.operator [](0)))
606    {
607        int1_retVal = parse_int1(i * 10 + (s.operator [](0) - 48), s.substr(1, s.length() - 1));
608    }
609    else
610    {
611        int1_retVal.i = i;
612        int1_retVal.remaining = s;
613    }
614
615    return int1_retVal;
616}
617
618parse_result_retVal RE_Parser::negate_cc_result(parse_result_retVal cc_result)
619{
620    if (ParseSuccess* success = dynamic_cast<ParseSuccess*>(cc_result.result))
621    {
622        if (CC* cc = dynamic_cast<CC*>(success->getRE()))
623        {
624            cc->negate_class();
625            //Remove any new-line.
626            cc->remove1(10);
627        }
628    }
629
630    return cc_result;
631}
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
Note: See TracBrowser for help on using the repository browser.