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

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

icGREP now accepts utf8 encoded characters in a regular expression.

File size: 19.5 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    int next_byte = (s.operator [](0) & 0xFF);
384    if ((next_byte >= 0xC0) && (next_byte <= 0xDF))
385    {       
386        cc_retVal = parse_utf8_bytes(1, s);
387    }
388    else if ((next_byte >= 0xE0) && (next_byte <= 0xEF))
389    {
390        cc_retVal = parse_utf8_bytes(2, s);
391    }
392    else if((next_byte >= 0xF0) && (next_byte <= 0xFF))
393    {
394        cc_retVal = parse_utf8_bytes(3, s);
395    }
396
397    return cc_retVal;
398}
399
400parse_result_retVal RE_Parser::parse_utf8_bytes(int suffix_count, std::string s)
401{
402    CC* cc = new CC((s.operator [](0) & 0xFF));
403    Seq* seq = new Seq();
404    seq->setType(Seq::Byte);
405    seq->AddREListItem(cc);
406
407    return parse_utf8_suffix_byte(suffix_count, s.substr(1, s.length() - 1), seq);
408}
409
410parse_result_retVal RE_Parser::parse_utf8_suffix_byte(int suffix_byte_num, std::string s, Seq *seq_sofar)
411{
412    parse_result_retVal result_RetVal;
413
414    if (suffix_byte_num == 0)
415    {
416        result_RetVal.result = new ParseSuccess(seq_sofar);
417        result_RetVal.remaining = s;
418    }
419    else if (s.length() == 0)
420    {
421        result_RetVal.result = new ParseFailure("Invalid UTF-8 encoding!");
422        result_RetVal.remaining = "";
423    }
424    else
425    {
426        if ((s.operator [](0) & 0xC0) == 0x80)
427        {
428            CC* cc = new CC((s.operator [](0) & 0xFF));
429            seq_sofar->AddREListItem(cc);
430            suffix_byte_num--;
431            result_RetVal = parse_utf8_suffix_byte(suffix_byte_num, s.substr(1, s.length() - 1), seq_sofar);
432        }
433        else
434        {
435            result_RetVal.result = new ParseFailure("Invalid UTF-8 encoding!");
436            result_RetVal.remaining = s;
437        }
438    }
439
440    return result_RetVal;
441}
442
443parse_result_retVal RE_Parser::parse_cc_body(std::string s)
444{
445    parse_result_retVal result_retVal;
446
447    if (s.length() == 0)
448    {
449        result_retVal.result = new ParseFailure("Unclosed character class!");
450        result_retVal.remaining = "";
451    }
452    else
453    {
454        CC* cc = new CC();
455        result_retVal = parse_cc_body1(s.operator [](0), s.substr(1, s.length() - 1), cc);
456    }
457
458    return result_retVal;
459}
460
461parse_result_retVal RE_Parser::parse_cc_body0(std::string s, CC* cc_sofar)
462{
463    parse_result_retVal cc_body0_retVal;
464
465    if (s.length() == 0)
466    {
467        delete cc_sofar;
468        cc_body0_retVal.result = new ParseFailure("Unclosed character class!");
469        cc_body0_retVal.remaining = "";
470    }
471    else if (s.operator [](0) == ']')
472    {
473        cc_body0_retVal.result = new ParseSuccess(cc_sofar);
474        cc_body0_retVal.remaining = s.substr(1, s.length() - 1);
475    }
476    else if ((s.operator [](0) == '-') && (s.operator [](1) == ']'))
477    {
478        cc_sofar->insert1('-');
479        cc_body0_retVal.result = new ParseSuccess(cc_sofar);
480        cc_body0_retVal.remaining = s.substr(2, s.length() - 2);
481    }
482    else if (s.operator [](0) == '-')
483    {
484        delete cc_sofar;
485        cc_body0_retVal.result = new ParseFailure("Bad range in character class!");
486        cc_body0_retVal.remaining = s.substr(1, s.length() - 1);
487    }
488    else
489    {
490        cc_body0_retVal = parse_cc_body1(s.operator [](0), s.substr(1, s.length() - 1), cc_sofar);
491    }
492
493    return cc_body0_retVal;
494}
495
496parse_result_retVal RE_Parser::parse_cc_body1(int chr, std::string s, CC* cc_sofar)
497{
498    parse_result_retVal cc_body1_retVal;
499
500    if (s.length() == 0)
501    {
502        delete cc_sofar;
503        cc_body1_retVal.result = new ParseFailure("Unclosed character class!");
504        cc_body1_retVal.remaining = "";
505    }
506    else if (s.operator [](0) == ']')
507    {
508        cc_sofar->insert1(chr);
509        cc_body1_retVal.result = new ParseSuccess(cc_sofar);
510        cc_body1_retVal.remaining = s.substr(1, s.length() - 1);
511    }
512    else if (s.length() == 1)
513    {
514        delete cc_sofar;
515        cc_body1_retVal.result = new ParseFailure("Unclosed character class!");
516        cc_body1_retVal.remaining = "";
517    }
518    else if ((s.operator [](0) == '-') && (s.operator [](1) == ']'))
519    {
520        cc_sofar->insert1(chr);
521        cc_sofar->insert1('-');
522        cc_body1_retVal = parse_cc_body0(s, cc_sofar);
523    }
524    else if ((s.operator [](0) == '-') && (s.operator [](1) == '\\') && (s.operator [](2) == 'u'))
525    {
526        parse_int_retVal int_retVal = parse_hex(s.substr(3, s.length() - 3));
527
528        if (int_retVal.i == -1)
529        {
530            cc_body1_retVal.result = new ParseFailure("Bad Unicode hex notation!");
531            cc_body1_retVal.remaining = "";
532        }
533        else
534        {
535            cc_sofar->insert_range(chr, int_retVal.i);
536            cc_body1_retVal = parse_cc_body0(int_retVal.remaining, cc_sofar);
537        }
538    }
539    else if ((s.operator [](0) == '-') && ( s.length() > 1))
540    {
541        cc_sofar->insert_range(chr, s.operator [](1));
542        cc_body1_retVal = parse_cc_body0(s.substr(2, s.length() - 2), cc_sofar);
543    }
544    else if ((s.operator [](0) == 'u') && ( s.length() > 1))
545    {
546        parse_int_retVal int_retVal = parse_hex(s.substr(1, s.length() - 1));
547
548        if (int_retVal.i == -1)
549        {
550            cc_body1_retVal.result = new ParseFailure("Bad Unicode hex notation!");
551            cc_body1_retVal.remaining = "";
552        }
553        else
554        {
555            cc_body1_retVal = parse_cc_body1(int_retVal.i, int_retVal.remaining, cc_sofar);
556        }
557    }
558    else
559    {
560        cc_sofar->insert1(chr);
561        cc_body1_retVal = parse_cc_body1(s.operator [](0), s.substr(1, s.length() - 1), cc_sofar);
562    }
563
564    return cc_body1_retVal;
565}
566
567parse_int_retVal RE_Parser::parse_hex(std::string s)
568{
569    parse_int_retVal int_retVal;
570
571    if (s.operator [](0) == '{')
572    {
573        int hexval_sofar = 0;
574        int_retVal = parse_hex_body(hexval_sofar, s.substr(1, s.length() - 1));
575
576    }
577    else
578    {
579        int_retVal.i = -1;
580        int_retVal.remaining = s;
581    }
582
583    return int_retVal;
584}
585
586parse_int_retVal RE_Parser::parse_hex_body(int i, std::string s)
587{
588    parse_int_retVal int_retVal;
589
590    if (s.length() == 0)
591    {
592        int_retVal.i = i;
593        int_retVal.remaining = "";
594    }
595    else if (s.operator [](0) == '}')
596    {
597        int_retVal.i = i;
598        int_retVal.remaining = s.substr(1, s.length() - 1);
599    }
600    else if ((s.operator [](0) >= '0') && (s.operator [](0) <= '9'))
601    {
602        int_retVal = parse_hex_body(parse_hex_body1(i, s.substr(0,1)), s.substr(1, s.length() - 1));
603    }
604    else if ((s.operator [](0) >= 'a') && (s.operator [](0) <= 'f'))
605    {
606        int_retVal = parse_hex_body(parse_hex_body1(i, s.substr(0,1)), s.substr(1, s.length() - 1));
607    }
608    else if ((s.operator [](0) >= 'A') && (s.operator [](0) <= 'F'))
609    {
610        int_retVal = parse_hex_body(parse_hex_body1(i, s.substr(0,1)), s.substr(1, s.length() - 1));
611    }
612    else
613    {
614        int_retVal.i = -1;
615        int_retVal.remaining = s;
616    }
617
618    return int_retVal;
619}
620
621int RE_Parser::parse_hex_body1(int i, std::string hex_str)
622{
623    int retVal = 0;
624    int newVal = 0;
625
626    retVal = i << 4;
627
628    std::stringstream ss(hex_str);
629    ss >> std::hex >> newVal;
630
631    retVal = retVal | newVal;
632
633    return retVal;
634}
635
636parse_int_retVal RE_Parser::parse_int(std::string s)
637{
638    parse_int_retVal int_retVal;
639
640    if (isdigit(s.operator [](0)))
641    {
642        int_retVal = parse_int1(s.operator [](0) - 48, s.substr(1, s.length() - 1));
643    }
644    else
645    {
646        int_retVal.i = -1;
647        int_retVal.remaining = s;
648    }
649
650    return int_retVal;
651}
652
653parse_int_retVal RE_Parser::parse_int1(int i, std::string s)
654{
655    parse_int_retVal int1_retVal;
656
657    if (s.length() == 0)
658    {
659        int1_retVal.i = i;
660        int1_retVal.remaining = "";
661    }
662    else if (isdigit(s.operator [](0)))
663    {
664        int1_retVal = parse_int1(i * 10 + (s.operator [](0) - 48), s.substr(1, s.length() - 1));
665    }
666    else
667    {
668        int1_retVal.i = i;
669        int1_retVal.remaining = s;
670    }
671
672    return int1_retVal;
673}
674
675parse_result_retVal RE_Parser::negate_cc_result(parse_result_retVal cc_result)
676{
677    if (ParseSuccess* success = dynamic_cast<ParseSuccess*>(cc_result.result))
678    {
679        if (CC* cc = dynamic_cast<CC*>(success->getRE()))
680        {
681            cc->negate_class();
682            //Remove any new-line.
683            cc->remove1(10);
684        }
685    }
686
687    return cc_result;
688}
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
Note: See TracBrowser for help on using the repository browser.