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

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

Modify repetition parsing for non-greedy and possessive qualifiers

File size: 15.3 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_alt.h>
9#include <re/re_end.h>
10#include <re/re_rep.h>
11#include <re/re_seq.h>
12#include <re/re_start.h>
13#include <re/re_diff.h>
14#include <re/re_intersect.h>
15#include <re/parsefailure.h>
16#include <algorithm>
17
18namespace re {
19
20RE * RE_Parser::parse(const std::string & regular_expression, const bool allow_escapes_within_charset) {
21    RE_Parser parser(regular_expression, allow_escapes_within_charset);
22    RE * re = parser.parse_alt(false);
23    if (re == nullptr) {
24        throw ParseFailure("An unexpected parsing error occurred!");
25    }
26    return re;
27}
28
29inline RE_Parser::RE_Parser(const std::string & regular_expression, const bool allow_escapes_within_charset)
30: _cursor(regular_expression.begin())
31, _end(regular_expression.end())
32, _allow_escapes_within_charset(allow_escapes_within_charset)
33{
34
35}
36
37RE * RE_Parser::parse_alt(const bool subexpression) {
38    std::vector<RE *> alt;
39    for (;;) {
40        alt.push_back(parse_seq());
41        if (_cursor == _end || *_cursor != '|') {
42            break;
43        }
44        ++_cursor; // advance past the alternation character '|'
45    }
46    if (alt.empty())
47    {
48        throw NoRegularExpressionFound();
49    }
50    else if (subexpression) {
51        if (_cursor == _end || *_cursor != ')') {
52            throw ParseFailure("Parenthesization error!");
53        }
54        ++_cursor;
55    }
56    else if (_cursor != _end) { // !subexpression
57        throw ParseFailure("Cannot fully parse statement!");
58    }
59    return makeAlt(alt.begin(), alt.end());
60}
61
62inline RE * RE_Parser::parse_seq() {
63    std::vector<RE *> seq;
64    for (;;) {
65        RE * re = parse_next_token();
66        if (re == nullptr) {
67            break;
68        }
69        seq.push_back(extend_item(re));
70    }
71    if (seq.empty())
72    {
73        throw NoRegularExpressionFound();
74    }
75    return makeSeq(seq.begin(), seq.end());
76}
77
78RE * RE_Parser::parse_next_token() {
79    RE * re = nullptr;
80    if (_cursor != _end) {
81        switch (*_cursor) {
82            case '(':
83                ++_cursor;
84                re = parse_alt(true);
85                break;
86            case '^':
87                ++_cursor;
88                re = makeStart();
89                break;
90            case '$':
91                ++_cursor;
92                re = makeEnd();
93                break;
94            case '|': case ')':
95                break;
96            case '*': case '+': case '?': case '{':
97                throw NothingToRepeat();
98            case ']': case '}':
99                throw ParseFailure("Illegal metacharacter usage!");
100            case '[':
101                re = parse_charset();
102                break;
103            case '.': // the 'any' metacharacter
104                re = parse_any_character();
105                break;
106            default:
107                re = parse_literal();
108                break;
109        }
110    }
111    return re;
112}
113
114Any * RE_Parser::parse_any_character() {
115    ++_cursor;
116    return makeAny();
117}
118
119RE * RE_Parser::extend_item(RE * re) {
120    int lower_bound, upper_bound;
121    if (_cursor == _end) {
122        return re;
123    }
124    switch (*_cursor) {
125        case '*':
126            lower_bound = 0;
127            upper_bound = Rep::UNBOUNDED_REP;
128            break;
129        case '?':
130            lower_bound = 0;
131            upper_bound = 1;
132            break;
133        case '+':
134            lower_bound = 1;
135            upper_bound = Rep::UNBOUNDED_REP;
136            break;
137        case '{':
138            parse_range_bound(lower_bound, upper_bound);
139            break;
140        default:
141            return re;
142    }
143    ++_cursor;
144    if (*_cursor == '?') {
145        // Non-greedy qualifier
146        ++_cursor;
147        //return makeNonGreedyRep(re, lower_bound, upper_bound);
148        // Greedy vs. non-greedy makes no difference for icgrep.
149        return makeRep(re, lower_bound, upper_bound);
150    }
151    else if (*_cursor == '+') {
152        // Possessive qualifier
153        ++_cursor;
154        //return makePossessiveRep(re, lower_bound, upper_bound);
155        throw ParseFailure("Possessive repetition is not supported in icgrep 1.0");
156    }
157    else {
158        // Normal repetition operator.
159        return makeRep(re, lower_bound, upper_bound);
160    }
161}
162
163inline void RE_Parser::parse_range_bound(int & lower_bound, int & upper_bound) {
164    ++_cursor;
165    throw_incomplete_expression_error_if_end_of_stream();
166    RE * rep = nullptr;
167    if (*_cursor == ',') {
168        ++_cursor;
169        lower_bound = 0;
170    }
171    else {
172        lower_bound = parse_int();
173    }
174    throw_incomplete_expression_error_if_end_of_stream();
175    if (*_cursor == '}') {
176        upper_bound = lower_bound;
177    }
178    else if (*_cursor != ',') {
179        throw BadLowerBound();
180    }
181    else { // [^,}]
182        ++_cursor;
183        throw_incomplete_expression_error_if_end_of_stream();
184        if (*_cursor == '}') {
185            upper_bound = Rep::UNBOUNDED_REP;
186        }
187        else {
188            upper_bound = parse_int();
189            if (*_cursor != '}') {
190                throw BadUpperBound();
191            }
192        }
193    }
194}
195
196inline RE * RE_Parser::parse_literal() {
197    // handle the escaped metacharacter (assuming it is one)
198    if (*_cursor == '\\') {
199        return parse_escaped_metacharacter();
200    }
201    else {
202        return makeCC(parse_utf8_codepoint());
203    }
204}
205
206inline RE * RE_Parser::parse_escaped_metacharacter() {
207    ++_cursor;
208    throw_incomplete_expression_error_if_end_of_stream();
209    switch (*_cursor) {
210        case 'P':
211            return makeDiff(makeAny(), parse_unicode_category());
212        case 'p':
213            return parse_unicode_category();
214                default:
215                        return makeCC(parse_escaped_codepoint());
216    }
217    throw ParseFailure("Illegal backslash escape!");
218}
219
220unsigned RE_Parser::parse_utf8_codepoint() {
221    unsigned c = static_cast<unsigned>(*_cursor++);
222    if (c > 0x80) { // if non-ascii
223        if (c < 0xC2) {
224            throw InvalidUTF8Encoding();
225        }
226        else { // [0xC2, 0xFF]
227            unsigned bytes = 0;
228            if (c < 0xE0) { // [0xC2, 0xDF]
229                c &= 0x1F;
230                bytes = 1;
231            }
232            else if (c < 0xF0) { // [0xE0, 0xEF]
233                c &= 0x0F;
234                bytes = 2;
235            }
236            else { // [0xF0, 0xFF]
237                c &= 0x0F;
238                bytes = 3;
239            }
240            while (--bytes) {
241                if (++_cursor == _end || (*_cursor & 0xC0) != 0x80) {
242                    throw InvalidUTF8Encoding();
243                }
244                c = (c << 6) | static_cast<unsigned>(*_cursor & 0x3F);
245                // It is an error if a 3-byte sequence is used to encode a codepoint < 0x800
246                // or a 4-byte sequence is used to encode a codepoint < 0x10000.
247                // if (((bytes == 1) && (c < 0x20)) || ((bytes == 2) && (c < 0x10))) {
248                if ((c << (bytes - 1)) < 0x20) {
249                    throw InvalidUTF8Encoding();
250                }
251            }
252        }
253    }
254    // It is an error if a 4-byte sequence is used to encode a codepoint
255    // above the Unicode maximum.   
256    if (c > CC::UNICODE_MAX) {
257        throw InvalidUTF8Encoding();
258    }
259    return c;
260}
261
262Name * RE_Parser::parse_unicode_category() {
263    if (++_cursor != _end && *_cursor == '{') {
264        const cursor_t start = _cursor + 1;
265        for (;;) {
266            if (++_cursor == _end) {
267                throw UnclosedUnicodeCharacterClass();
268            }
269            if (*_cursor == '}') {
270                break;
271            }
272            ++_cursor;
273        }
274        return makeName(std::string(start, _cursor++), Name::Type::UnicodeCategory);
275    }
276    throw ParseFailure("Incorrect Unicode character class format!");
277}
278
279RE * RE_Parser::parse_charset() {
280    CC * cc = makeCC();
281    bool negated = false;
282    cursor_t start = ++_cursor;
283    while (_cursor != _end) {
284        bool literal = true;
285        switch (*_cursor) {
286            case '^':
287                // If the first character after the [ is a ^ (caret) then the matching character class is complemented.
288                if ((start == _cursor) && !negated) {
289                    negated = true;
290                    start = ++_cursor; // move the start ahead in case the next character is a ] or -
291                    literal = false;                   
292                }
293                break;
294            case ']':
295                // To include a ], put it immediately after the opening [ or [^; if it occurs later it will
296                // close the bracket expression.
297                if (start == _cursor) {
298                    cc->insert(']');
299                    ++_cursor;
300                    literal = false;
301                    break;
302                }
303                ++_cursor;
304                if (negated) {
305                    return makeDiff(makeAny(), cc);
306                }
307                return cc;
308            // The hyphen (-) is not treated as a range separator if it appears first or last, or as the
309            // endpoint of a range.
310            case '-':
311                if (true) {
312                    literal = false;
313                    const cursor_t next = _cursor + 1;
314                    if (next == _end) {
315                        throw UnclosedCharacterClass();
316                    }
317                    if ((start == _cursor) ? (*next != '-') : (*next == ']')) {
318                        _cursor = next;
319                        cc->insert('-');
320                        break;
321                    }
322                }
323                throw ParseFailure("Invalid Lower Range Bound!");
324            // case ':':
325        }
326        if (literal) {
327            unsigned low;
328            if (parse_charset_literal(low)) {
329                // the previous literal allows for a - to create a range; test for it
330                if (_cursor == _end) {
331                    break; // out of loop to failure handling
332                }
333                if (*_cursor == '-') { // in range unless the next character is a ']'
334                    if (++_cursor == _end) {
335                        break; // out of loop to failure handling
336                    }
337                    if (*_cursor != ']') {
338                        unsigned high;
339                        if (!parse_charset_literal(high)) {
340                            throw ParseFailure("Invalid Upper Range Bound!");
341                        }
342                        cc->insert_range(low, high);
343                    }
344                    else {
345                        cc->insert(low);
346                        cc->insert('-');
347                    }
348                    continue;
349                }
350            }
351            cc->insert(low);
352        }
353    }
354    throw UnclosedCharacterClass();
355}
356
357inline bool RE_Parser::parse_charset_literal(unsigned & literal) {
358    if (_cursor == _end) {
359        return false;
360    }
361    if (*_cursor == '\\') {
362                _cursor++;
363                literal = parse_escaped_codepoint();
364                return true;
365    }
366    else {
367        literal = parse_utf8_codepoint();
368        return true;
369    }
370    return false;
371}
372
373unsigned RE_Parser::parse_int() {
374    unsigned value = 0;
375    for (; _cursor != _end; ++_cursor) {
376        if (!isdigit(*_cursor)) {
377            break;
378        }
379        value *= 10;
380        value += static_cast<int>(*_cursor) - 48;
381    }
382    return value;
383}
384
385
386// A backslash escape was found, and various special cases (back reference,
387// quoting with \Q, \E, sets (\p, \P, \d, \D, \w, \W, \s, \S), grapheme
388// cluster \X have been ruled out.
389// It may be one of several possibilities or an error sequence.
390// 1. Special control codes (\a, \b, \e, \f, \n, \r, \t, \v)
391// 2. General control codes c[@-_a-z?]
392// 3. Restricted octal notation 0 - 0777
393// 4. General octal notation o\{[0-7]+\}
394// 5. General hex notation x\{[0-9A-Fa-f]+\}
395// 6. An error for any unrecognized alphabetic escape
396// 7. An escaped ASCII symbol, standing for itself
397
398unsigned RE_Parser::parse_escaped_codepoint() {
399        unsigned cp_value;
400        throw_incomplete_expression_error_if_end_of_stream();
401        switch (*_cursor) {
402                case 'a': ++_cursor; return 0x07; // BEL
403                case 'b': ++_cursor; return 0x08; // BS
404                case 'e': ++_cursor; return 0x1B; // ESC
405                case 'f': ++_cursor; return 0x0C; // FF
406                case 'n': ++_cursor; return 0x0A; // LF
407                case 'r': ++_cursor; return 0x0D; // CR
408                case 't': ++_cursor; return 0x09; // HT
409                case 'v': ++_cursor; return 0x0B; // VT
410                case 'c': // Control-escape based on next char
411                        ++_cursor;
412                        throw_incomplete_expression_error_if_end_of_stream();
413                        // \c@, \cA, ... \c_, or \ca, ..., \cz
414                        if (((*_cursor >= '@') && (*_cursor <= '_')) || ((*_cursor >= 'a') && (*_cursor <= 'z'))) {
415                                cp_value = static_cast<unsigned>(*_cursor & 0x1F);
416                                _cursor++;
417                                return cp_value;
418                        }
419                        else if (*_cursor++ == '?') return 0x7F;  // \c? ==> DEL
420                        else throw("Illegal \\c escape sequence");
421                case '0': // Octal escape:  0 - 0377
422                        ++_cursor;
423                        return parse_octal_codepoint(0,3);
424                case 'o':
425                        ++_cursor;
426                        throw_incomplete_expression_error_if_end_of_stream();
427                        if (*_cursor == '{') {
428                                ++_cursor;
429                                cp_value = parse_octal_codepoint(1, 7);
430                                if (_cursor == _end || *_cursor++ != '}') throw ParseFailure("Malformed octal escape sequence");
431                                return cp_value;
432                        }
433                        else {
434                                throw ParseFailure("Malformed octal escape sequence");
435                        }
436                case 'x':
437                        ++_cursor;
438                        throw_incomplete_expression_error_if_end_of_stream();
439                        if (*_cursor == '{') {
440                          ++_cursor;
441                          cp_value = parse_hex_codepoint(1, 6);
442                          if (_cursor == _end || *_cursor++ != '}') throw ParseFailure("Malformed hex escape sequence");
443                          return cp_value;
444                        }
445                        else {
446                                return parse_hex_codepoint(1,2);  // ICU compatibility
447                        }
448                case 'u':
449                        ++_cursor;
450                        throw_incomplete_expression_error_if_end_of_stream();
451                        if (*_cursor == '{') {
452                                ++_cursor;
453                                cp_value = parse_hex_codepoint(1, 6);
454                                if (_cursor == _end || *_cursor++ != '}') throw ParseFailure("Malformed hex escape sequence");
455                                return cp_value;
456                        }
457                        else {
458                                return parse_hex_codepoint(4,4);  // ICU compatibility
459                        }
460                case 'U':
461                        ++_cursor;
462                        return parse_hex_codepoint(8,8);  // ICU compatibility
463                default:
464                        if (((*_cursor >= 'A') && (*_cursor <= 'Z')) || ((*_cursor >= 'a') && (*_cursor <= 'z')))
465                                throw ParseFailure("Undefined or unsupported escape sequence");
466                        else return static_cast<unsigned>(*_cursor++);
467        }
468}
469
470
471unsigned RE_Parser::parse_octal_codepoint(int mindigits, int maxdigits) {
472        unsigned value = 0;
473        int count = 0;
474        while (_cursor != _end && count < maxdigits) {
475                const char t = *_cursor;
476                if (t < '0' || t > '7') {
477                        break;
478                }
479                value = value * 8 | (t - '0');
480                ++_cursor;
481                ++count;
482        }
483        if (count < mindigits) throw ParseFailure("Octal sequence has too few digits");
484        if (value > CC::UNICODE_MAX) throw ParseFailure("Octal value too large");
485        return value;
486}
487
488unsigned RE_Parser::parse_hex_codepoint(int mindigits, int maxdigits) {
489        unsigned value = 0;
490        int count = 0;
491        while (_cursor != _end && isxdigit(*_cursor) && count < maxdigits) {
492                const char t = *_cursor;
493                if (isdigit(t)) {
494                        value = (value * 16) | (t - '0');
495                }
496                else { 
497                        value = (value * 16) | ((t | 32) - 'a') + 10;
498                }
499                ++_cursor;
500                ++count;
501        }
502        if (count < mindigits) throw ParseFailure("Hexadecimal sequence has too few digits");
503        if (value > CC::UNICODE_MAX) throw ParseFailure("Hexadecimal value too large");
504        return value;
505}
506
507
508inline void RE_Parser::throw_incomplete_expression_error_if_end_of_stream() const {
509    if (_cursor == _end) throw IncompleteRegularExpression();
510}
511
512}
Note: See TracBrowser for help on using the repository browser.