source: icGREP/icgrep-devel/icgrep/re/re_parser.cpp @ 4309

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

New character class parser, supporting intersection, set difference, posix set expressions

File size: 19.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/re_parser.h>
8#include <re/re_name.h>
9#include <re/re_alt.h>
10#include <re/re_end.h>
11#include <re/re_rep.h>
12#include <re/re_seq.h>
13#include <re/re_start.h>
14#include <re/re_diff.h>
15#include <re/re_intersect.h>
16#include <re/parsefailure.h>
17#include <algorithm>
18
19
20// It would probably be best to enforce that {}, [], () must always
21// be balanced.   But legacy syntax allows } and ] to occur as literals
22// in certain contexts (no opening { or [, or immediately after [ or [^ ).
23// Perhaps this define should become a parameter.
24#define LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED true
25#define LEGACY_UNESCAPED_HYPHEN_ALLOWED true
26
27
28namespace re {
29
30RE * RE_Parser::parse(const std::string & regular_expression) {
31    RE_Parser parser(regular_expression);
32    RE * re = parser.parse_alt(false);
33    if (re == nullptr) {
34        throw ParseFailure("An unexpected parsing error occurred!");
35    }
36    return re;
37}
38
39inline RE_Parser::RE_Parser(const std::string & regular_expression)
40: _cursor(regular_expression.begin())
41, _end(regular_expression.end())
42{
43
44}
45
46RE * RE_Parser::parse_alt(const bool subexpression) {
47    std::vector<RE *> alt;
48    for (;;) {
49        alt.push_back(parse_seq());
50        if (_cursor == _end || *_cursor != '|') {
51            break;
52        }
53        ++_cursor; // advance past the alternation character '|'
54    }
55    if (alt.empty())
56    {
57        throw NoRegularExpressionFound();
58    }
59    else if (subexpression) {
60        if (_cursor == _end || *_cursor != ')') {
61            throw ParseFailure("Parenthesization error!");
62        }
63        ++_cursor;
64    }
65    else if (_cursor != _end) { // !subexpression
66        throw ParseFailure("Cannot fully parse statement!");
67    }
68    return makeAlt(alt.begin(), alt.end());
69}
70
71inline RE * RE_Parser::parse_seq() {
72    std::vector<RE *> seq;
73    for (;;) {
74        RE * re = parse_next_token();
75        if (re == nullptr) {
76            break;
77        }
78        seq.push_back(extend_item(re));
79    }
80    if (seq.empty())
81    {
82        throw NoRegularExpressionFound();
83    }
84    return makeSeq(seq.begin(), seq.end());
85}
86
87RE * RE_Parser::parse_next_token() {
88    RE * re = nullptr;
89    if (_cursor != _end) {
90        switch (*_cursor) {
91            case '(':
92                ++_cursor;
93                return parse_alt(true);
94            case '^':
95                ++_cursor;
96                return makeStart();
97            case '$':
98                ++_cursor;
99                return makeEnd();
100            case '|': case ')':
101                return nullptr;  // This is ugly.
102            case '*': case '+': case '?': case '{':
103                throw NothingToRepeat();
104            case ']': case '}':
105                                if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
106                                        return parse_literal();
107                                }
108                                else throw ParseFailure("Use  \\] or \\} for literal ] or }.");
109            case '[':
110                *_cursor++;
111                return parse_charset();
112            case '.': // the 'any' metacharacter
113                return parse_any_character();
114                        case '\\'// escape processing
115                ++_cursor;
116                return parse_escaped();
117            default:
118                return parse_literal();
119        }
120    }
121    return re;
122}
123
124Any * RE_Parser::parse_any_character() {
125    ++_cursor;
126    return makeAny();
127}
128
129RE * RE_Parser::extend_item(RE * re) {
130    int lower_bound, upper_bound;
131    if (_cursor == _end) {
132        return re;
133    }
134    switch (*_cursor) {
135        case '*':
136            lower_bound = 0;
137            upper_bound = Rep::UNBOUNDED_REP;
138            break;
139        case '?':
140            lower_bound = 0;
141            upper_bound = 1;
142            break;
143        case '+':
144            lower_bound = 1;
145            upper_bound = Rep::UNBOUNDED_REP;
146            break;
147        case '{':
148            parse_range_bound(lower_bound, upper_bound);
149            break;
150        default:
151            return re;
152    }
153    ++_cursor;
154    if (*_cursor == '?') {
155        // Non-greedy qualifier
156        ++_cursor;
157        //return makeNonGreedyRep(re, lower_bound, upper_bound);
158        // Greedy vs. non-greedy makes no difference for icgrep.
159        return makeRep(re, lower_bound, upper_bound);
160    }
161    else if (*_cursor == '+') {
162        // Possessive qualifier
163        ++_cursor;
164        //return makePossessiveRep(re, lower_bound, upper_bound);
165        throw ParseFailure("Possessive repetition is not supported in icgrep 1.0");
166    }
167    else {
168        // Normal repetition operator.
169        return makeRep(re, lower_bound, upper_bound);
170    }
171}
172
173inline void RE_Parser::parse_range_bound(int & lower_bound, int & upper_bound) {
174    ++_cursor;
175    throw_incomplete_expression_error_if_end_of_stream();
176    RE * rep = nullptr;
177    if (*_cursor == ',') {
178        ++_cursor;
179        lower_bound = 0;
180    }
181    else {
182        lower_bound = parse_int();
183    }
184    throw_incomplete_expression_error_if_end_of_stream();
185    if (*_cursor == '}') {
186        upper_bound = lower_bound;
187    }
188    else if (*_cursor != ',') {
189        throw BadLowerBound();
190    }
191    else { // [^,}]
192        ++_cursor;
193        throw_incomplete_expression_error_if_end_of_stream();
194        if (*_cursor == '}') {
195            upper_bound = Rep::UNBOUNDED_REP;
196        }
197        else {
198            upper_bound = parse_int();
199            if (*_cursor != '}') {
200                throw BadUpperBound();
201            }
202        }
203    }
204}
205
206unsigned RE_Parser::parse_int() {
207    unsigned value = 0;
208    for (; _cursor != _end; ++_cursor) {
209        if (!isdigit(*_cursor)) {
210            break;
211        }
212        value *= 10;
213        value += static_cast<int>(*_cursor) - 48;
214    }
215    return value;
216}
217
218inline RE * RE_Parser::parse_literal() {
219    return makeCC(parse_utf8_codepoint());
220}
221
222#define bit40(x) (1ULL << ((x) - 0x40))
223const uint64_t setEscapeCharacters = bit40('p') | bit40('d') | bit40('w') | bit40('s') | bit40('P') | bit40('D') | bit40('W') | bit40('S');
224
225inline bool isSetEscapeChar(char c) {
226    return c >= 0x40 && c <= 0x7F && ((setEscapeCharacters >> (c - 0x40)) & 1) == 1;
227}
228
229inline RE * RE_Parser::parse_escaped() {
230    throw_incomplete_expression_error_if_end_of_stream();
231    if (isSetEscapeChar(*_cursor)) 
232      return parse_escaped_set();
233    else 
234      return makeCC(parse_escaped_codepoint());
235}
236
237RE * makeDigitSet() {
238  return makeName("Nd", Name::Type::UnicodeCategory);
239}
240
241RE * makeWhitespaceSet() {
242  throw ParseFailure("\\s not implemented.");
243}
244
245RE * makeWordSet() {
246  throw ParseFailure("\\w not implemented.");
247}
248
249RE * makeComplement(RE * s) {
250  return makeDiff(makeAny(), s);
251}
252
253RE * RE_Parser::parse_escaped_set() {
254        bool complemented = false;
255        RE * s;
256    switch (*_cursor) {
257                case 'd':
258                        ++_cursor;
259                        return makeDigitSet();
260                case 'D':
261                        ++_cursor;
262                        return makeComplement(makeDigitSet());
263                case 's':
264                        ++_cursor;
265                        return makeWhitespaceSet();
266                case 'S':
267                        ++_cursor;
268                        return makeComplement(makeWhitespaceSet());
269                case 'w':
270                        ++_cursor;
271                        return makeWordSet();
272                case 'W':
273                        ++_cursor;
274                        return makeComplement(makeWordSet());
275        case 'P':
276            complemented = true;
277        case 'p':
278                        ++_cursor;
279                        if (_cursor == _end || *_cursor != '{') throw ParseFailure("Malformed property expression");
280                        ++_cursor;
281                        s = parse_property_expression();
282                        if (_cursor == _end || *_cursor != '}') throw ParseFailure("Malformed property expression");
283                        ++_cursor;
284                        if (complemented) return makeComplement(s);
285                        else return s;
286                default:
287                        throw ParseFailure("Internal error");
288    }
289}
290
291unsigned RE_Parser::parse_utf8_codepoint() {
292    unsigned c = static_cast<unsigned>(*_cursor++);
293    if (c > 0x80) { // if non-ascii
294        if (c < 0xC2) {
295            throw InvalidUTF8Encoding();
296        }
297        else { // [0xC2, 0xFF]
298            unsigned bytes = 0;
299            if (c < 0xE0) { // [0xC2, 0xDF]
300                c &= 0x1F;
301                bytes = 1;
302            }
303            else if (c < 0xF0) { // [0xE0, 0xEF]
304                c &= 0x0F;
305                bytes = 2;
306            }
307            else { // [0xF0, 0xFF]
308                c &= 0x0F;
309                bytes = 3;
310            }
311            while (--bytes) {
312                if (++_cursor == _end || (*_cursor & 0xC0) != 0x80) {
313                    throw InvalidUTF8Encoding();
314                }
315                c = (c << 6) | static_cast<unsigned>(*_cursor & 0x3F);
316                // It is an error if a 3-byte sequence is used to encode a codepoint < 0x800
317                // or a 4-byte sequence is used to encode a codepoint < 0x10000.
318                // if (((bytes == 1) && (c < 0x20)) || ((bytes == 2) && (c < 0x10))) {
319                if ((c << (bytes - 1)) < 0x20) {
320                    throw InvalidUTF8Encoding();
321                }
322            }
323        }
324    }
325    // It is an error if a 4-byte sequence is used to encode a codepoint
326    // above the Unicode maximum.   
327    if (c > CC::UNICODE_MAX) {
328        throw InvalidUTF8Encoding();
329    }
330    return c;
331}
332
333Name * RE_Parser::parse_property_expression() {
334    const cursor_t start = _cursor;
335        while (_cursor != _end && *_cursor != '}' and *_cursor != ':') {
336                _cursor++;
337        }
338        return makeName(std::string(start, _cursor), Name::Type::UnicodeCategory);
339}
340       
341CharsetOperatorKind RE_Parser::getCharsetOperator() {
342    throw_incomplete_expression_error_if_end_of_stream();
343        switch (*_cursor) {
344                case '&':
345                        ++_cursor;
346                        if (_cursor != _end && *_cursor == '&') {
347                                ++_cursor;
348                                return intersectOp;
349                        }
350                        else if (_cursor != _end && *_cursor == '[') {
351                                // Short-hand for intersectOp when a set follows
352                                return intersectOp;
353                        }
354                        else return ampChar;
355                case '-':
356                        ++_cursor;
357                        if (_cursor != _end && *_cursor == '-') {
358                                ++_cursor;
359                                return setDiffOp;
360                        }
361                        else if (_cursor != _end && *_cursor == '[') {
362                                return setDiffOp;
363                        }
364                        else if (_cursor != _end && *_cursor == ']') {
365                                return hyphenChar;
366                        }
367                        else return rangeHyphen;
368                case '[':
369                        ++_cursor;
370                        if (_cursor != _end && *_cursor == ':') {
371                                ++_cursor;
372                                return posixPropertyOpener;
373                        }
374                        else return setOpener;
375                case ']':
376                        ++_cursor;
377                        return setCloser;
378                case '\\':
379                        ++_cursor;
380                        return backSlash;
381                default:
382                        return emptyOperator;
383        }
384}                       
385       
386// Precondition: cursor is immediately after opening '[' character
387RE * RE_Parser::parse_charset() {
388        // Sets are accumulated using two variables:
389        // subexprs accumulates set expressions such as \p{Lu}, [\w && \p{Greek}]
390        // cc accumulates the literal and calculated codepoints and ranges
391        std::vector<RE *> subexprs;
392    CC * cc = makeCC();
393        // When the last item deal with is a single literal charcacter or calculated codepoint,
394        // a following hyphen can indicate a range.   When the last item is a set subexpression,
395        // a following hyphen can indicate set subtraction.
396        enum {NoItem, CodepointItem, RangeItem, SetItem, BrackettedSetItem} lastItemKind = NoItem;
397        unsigned lastCodepointItem;
398       
399        bool havePendingOperation = false;
400        CharsetOperatorKind pendingOperationKind;
401        RE * pendingOperand;
402       
403    // If the first character after the [ is a ^ (caret) then the matching character class is complemented.
404    bool negated = false;
405    if (_cursor != _end && *_cursor == '^') {
406      negated = true;
407      ++_cursor;
408    }
409    throw_incomplete_expression_error_if_end_of_stream();
410        // Legacy rule: an unescaped ] may appear as a literal set character
411        // if and only if it appears immediately after the opening [ or [^
412    if ( *_cursor == ']' && LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
413                cc->insert(']');
414                lastItemKind = CodepointItem;
415                lastCodepointItem = static_cast<unsigned> (']');
416                ++_cursor;
417    }
418    else if ( *_cursor == '-' && LEGACY_UNESCAPED_HYPHEN_ALLOWED) {
419                ++_cursor;
420                cc->insert('-');
421                lastItemKind = CodepointItem;
422                lastCodepointItem = static_cast<unsigned> ('-');
423                if (*_cursor == '-') throw ParseFailure("Set operator has no left operand.");
424    }
425    while (_cursor != _end) {
426                CharsetOperatorKind op = getCharsetOperator();
427                switch (op) {
428                        case intersectOp: case setDiffOp: {
429                                if (lastItemKind == NoItem) throw ParseFailure("Set operator has no left operand.");
430                                if (cc->begin() != cc->end()) subexprs.push_back(cc);
431                                RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
432                                subexprs.clear();
433                                cc = makeCC();
434                                if (havePendingOperation) {
435                                        if (pendingOperationKind == intersectOp) {
436                                                pendingOperand = makeIntersect(pendingOperand, newOperand);
437                                        }
438                                        else {
439                                                pendingOperand = makeDiff(pendingOperand, newOperand);
440                                        }
441                                }
442                                else {
443                                        pendingOperand = newOperand;
444                                }
445                                havePendingOperation = true;
446                                pendingOperationKind = op;
447                                lastItemKind = NoItem;
448                        }
449                        break;
450                        case setCloser: {
451                                if (lastItemKind == NoItem) throw ParseFailure("Set operator has no right operand.");
452                                if (cc->begin() != cc->end()) subexprs.push_back(cc);
453                                RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
454                                if (havePendingOperation) {
455                                        if (pendingOperationKind == intersectOp) {
456                                                newOperand = makeIntersect(pendingOperand, newOperand);
457                                        }
458                                        else {
459                                                newOperand = makeDiff(pendingOperand, newOperand);
460                                        }
461                                }
462                                if (negated) return makeComplement(newOperand); 
463                                else return newOperand;
464                        }
465                        case setOpener: case posixPropertyOpener: {
466                                if (lastItemKind != NoItem) {
467                                        if (cc->begin() != cc->end()) subexprs.push_back(cc);
468                                        RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
469                                        subexprs.clear();
470                                        cc = makeCC();
471                                        if (havePendingOperation) {
472                                                if (pendingOperationKind == intersectOp) {
473                                                        pendingOperand = makeIntersect(pendingOperand, newOperand);
474                                                }
475                                                else {
476                                                        pendingOperand = makeDiff(pendingOperand, newOperand);
477                                                }
478                                        }
479                                        else {
480                                                pendingOperand = newOperand;
481                                        }
482                                        subexprs.push_back(pendingOperand);
483                                        havePendingOperation = false;
484                                }
485                                if (op == setOpener) {
486                                        subexprs.push_back(parse_charset());
487                                        lastItemKind = SetItem;
488                                }
489                                else if (op == posixPropertyOpener) {
490                                        bool negated = false;
491                                        if (*_cursor == '^') {
492                                                negated = true;
493                                                _cursor++;
494                                        }
495                                        RE * posixSet = parse_property_expression();
496                                        if (negated) posixSet = makeComplement(posixSet);
497                                        subexprs.push_back(posixSet);
498                                        lastItemKind = BrackettedSetItem;
499                                        if (_cursor == _end || *_cursor++ != ':' || _cursor == _end || *_cursor++ != ']')
500                                                throw ParseFailure("Posix set expression improperly terminated.");
501                                }
502                        }
503                        break;
504                        case rangeHyphen:
505                                if (lastItemKind != CodepointItem) throw ParseFailure("Range operator - has illegal left operand.");
506                                cc->insert_range(lastCodepointItem, parse_codepoint());
507                                lastItemKind = RangeItem;
508                                break;
509                        case hyphenChar:
510                                cc->insert('-'); 
511                                lastItemKind = CodepointItem;
512                                lastCodepointItem = static_cast<unsigned> ('-');
513                                break;
514                        case ampChar:
515                                cc->insert('&'); 
516                                lastItemKind = CodepointItem;
517                                lastCodepointItem = static_cast<unsigned> ('&');
518                                break;
519                        case backSlash:
520                                throw_incomplete_expression_error_if_end_of_stream();
521                                if (isSetEscapeChar(*_cursor)) {
522                                        subexprs.push_back(parse_escaped_set());
523                                        lastItemKind = SetItem;
524                                }
525                                else {
526                                        lastCodepointItem = parse_escaped_codepoint();
527                                        cc->insert(lastCodepointItem);
528                                        lastItemKind = CodepointItem;
529                                }
530                                break;
531                        case emptyOperator:
532                                lastCodepointItem = parse_utf8_codepoint();
533                                cc->insert(lastCodepointItem);
534                                lastItemKind = CodepointItem;
535                                break;
536                }
537        }
538        throw ParseFailure("Set expression not properly terminated.");
539}
540
541
542unsigned RE_Parser::parse_codepoint() {
543    if (_cursor != _end && *_cursor == '\\') {
544        _cursor++;
545        return parse_escaped_codepoint();
546    }
547    else {
548        return parse_utf8_codepoint();
549    }
550}
551
552// A backslash escape was found, and various special cases (back reference,
553// quoting with \Q, \E, sets (\p, \P, \d, \D, \w, \W, \s, \S), grapheme
554// cluster \X have been ruled out.
555// It may be one of several possibilities or an error sequence.
556// 1. Special control codes (\a, \b, \e, \f, \n, \r, \t, \v)
557// 2. General control codes c[@-_a-z?]
558// 3. Restricted octal notation 0 - 0777
559// 4. General octal notation o\{[0-7]+\}
560// 5. General hex notation x\{[0-9A-Fa-f]+\}
561// 6. An error for any unrecognized alphabetic escape
562// 7. An escaped ASCII symbol, standing for itself
563
564unsigned RE_Parser::parse_escaped_codepoint() {
565        unsigned cp_value;
566        throw_incomplete_expression_error_if_end_of_stream();
567        switch (*_cursor) {
568                case 'a': ++_cursor; return 0x07; // BEL
569                case 'b': ++_cursor; return 0x08; // BS
570                case 'e': ++_cursor; return 0x1B; // ESC
571                case 'f': ++_cursor; return 0x0C; // FF
572                case 'n': ++_cursor; return 0x0A; // LF
573                case 'r': ++_cursor; return 0x0D; // CR
574                case 't': ++_cursor; return 0x09; // HT
575                case 'v': ++_cursor; return 0x0B; // VT
576                case 'c': // Control-escape based on next char
577                        ++_cursor;
578                        throw_incomplete_expression_error_if_end_of_stream();
579                        // \c@, \cA, ... \c_, or \ca, ..., \cz
580                        if (((*_cursor >= '@') && (*_cursor <= '_')) || ((*_cursor >= 'a') && (*_cursor <= 'z'))) {
581                                cp_value = static_cast<unsigned>(*_cursor & 0x1F);
582                                _cursor++;
583                                return cp_value;
584                        }
585                        else if (*_cursor++ == '?') return 0x7F;  // \c? ==> DEL
586                        else throw("Illegal \\c escape sequence");
587                case '0': // Octal escape:  0 - 0377
588                        ++_cursor;
589                        return parse_octal_codepoint(0,3);
590                case 'o':
591                        ++_cursor;
592                        throw_incomplete_expression_error_if_end_of_stream();
593                        if (*_cursor == '{') {
594                                ++_cursor;
595                                cp_value = parse_octal_codepoint(1, 7);
596                                if (_cursor == _end || *_cursor++ != '}') throw ParseFailure("Malformed octal escape sequence");
597                                return cp_value;
598                        }
599                        else {
600                                throw ParseFailure("Malformed octal escape sequence");
601                        }
602                case 'x':
603                        ++_cursor;
604                        throw_incomplete_expression_error_if_end_of_stream();
605                        if (*_cursor == '{') {
606                          ++_cursor;
607                          cp_value = parse_hex_codepoint(1, 6);
608                          if (_cursor == _end || *_cursor++ != '}') throw ParseFailure("Malformed hex escape sequence");
609                          return cp_value;
610                        }
611                        else {
612                                return parse_hex_codepoint(1,2);  // ICU compatibility
613                        }
614                case 'u':
615                        ++_cursor;
616                        throw_incomplete_expression_error_if_end_of_stream();
617                        if (*_cursor == '{') {
618                                ++_cursor;
619                                cp_value = parse_hex_codepoint(1, 6);
620                                if (_cursor == _end || *_cursor++ != '}') throw ParseFailure("Malformed hex escape sequence");
621                                return cp_value;
622                        }
623                        else {
624                                return parse_hex_codepoint(4,4);  // ICU compatibility
625                        }
626                case 'U':
627                        ++_cursor;
628                        return parse_hex_codepoint(8,8);  // ICU compatibility
629                case 'N':
630                        ++_cursor;
631                        throw ParseFailure("\\N{...} character name syntax not yet supported.");
632
633                default:
634                        // Escaped letters should be reserved for special functions.
635                        if (((*_cursor >= 'A') && (*_cursor <= 'Z')) || ((*_cursor >= 'a') && (*_cursor <= 'z')))
636                                throw ParseFailure("Undefined or unsupported escape sequence");
637                        else if ((*_cursor < 0x20) || (*_cursor >= 0x7F))
638                                throw ParseFailure("Illegal escape sequence");
639                        else return static_cast<unsigned>(*_cursor++);
640        }
641}
642
643
644unsigned RE_Parser::parse_octal_codepoint(int mindigits, int maxdigits) {
645        unsigned value = 0;
646        int count = 0;
647        while (_cursor != _end && count < maxdigits) {
648                const char t = *_cursor;
649                if (t < '0' || t > '7') {
650                        break;
651                }
652                value = value * 8 | (t - '0');
653                ++_cursor;
654                ++count;
655        }
656        if (count < mindigits) throw ParseFailure("Octal sequence has too few digits");
657        if (value > CC::UNICODE_MAX) throw ParseFailure("Octal value too large");
658        return value;
659}
660
661unsigned RE_Parser::parse_hex_codepoint(int mindigits, int maxdigits) {
662        unsigned value = 0;
663        int count = 0;
664        while (_cursor != _end && isxdigit(*_cursor) && count < maxdigits) {
665                const char t = *_cursor;
666                if (isdigit(t)) {
667                        value = (value * 16) | (t - '0');
668                }
669                else { 
670                        value = (value * 16) | ((t | 32) - 'a') + 10;
671                }
672                ++_cursor;
673                ++count;
674        }
675        if (count < mindigits) throw ParseFailure("Hexadecimal sequence has too few digits");
676        if (value > CC::UNICODE_MAX) throw ParseFailure("Hexadecimal value too large");
677        return value;
678}
679
680
681inline void RE_Parser::throw_incomplete_expression_error_if_end_of_stream() const {
682    if (_cursor == _end) throw IncompleteRegularExpression();
683}
684
685}
Note: See TracBrowser for help on using the repository browser.