source: icGREP/icgrep-0.8/icgrep/re_parser.cpp @ 3972

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

icgrep-0.8 distribution

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