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

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

Support for ICU, Perl backslash escape codepoint sequences; non-codepoint escapes to follow

File size: 14.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_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    if (_cursor == _end) {
121        return re;
122    }
123    switch (*_cursor) {
124        case '*':
125            ++_cursor; // skip past the '*'
126            re = makeRep(re, 0, Rep::UNBOUNDED_REP);
127            break;
128        case '?':
129            ++_cursor; // skip past the '?'
130            re = makeRep(re, 0, 1);
131            break;
132        case '+':
133            ++_cursor; // skip past the '+'
134            re = makeRep(re, 1, Rep::UNBOUNDED_REP);
135            break;
136        case '{':
137            re = parse_range_bound(re);
138            break;
139        default:
140            return re;
141    }
142    // this only occurs if we encountered one of the non-default cases above.
143    return extend_item(re);
144}
145
146inline RE * RE_Parser::parse_range_bound(RE * re) {
147    ++_cursor;
148    throw_incomplete_expression_error_if_end_of_stream();
149    RE * rep = nullptr;
150    unsigned lower_bound;
151    if (*_cursor == ',') {
152        ++_cursor;
153        lower_bound = 0;
154    }
155    else {
156        lower_bound = parse_int();
157    }
158    throw_incomplete_expression_error_if_end_of_stream();
159    if (*_cursor == '}') {
160        rep = makeRep(re, lower_bound, lower_bound);
161    }
162    else if (*_cursor != ',') {
163        throw BadLowerBound();
164    }
165    else { // [^,}]
166        ++_cursor;
167        throw_incomplete_expression_error_if_end_of_stream();
168        if (*_cursor == '}') {
169            rep = makeRep(re, lower_bound, Rep::UNBOUNDED_REP);
170        }
171        else {
172            const unsigned upper_bound = parse_int();
173            if (*_cursor != '}') {
174                throw BadUpperBound();
175            }
176            rep = makeRep(re, lower_bound, upper_bound);
177        }
178    }
179    ++_cursor;
180    return rep;
181}
182
183inline RE * RE_Parser::parse_literal() {
184    // handle the escaped metacharacter (assuming it is one)
185    if (*_cursor == '\\') {
186        return parse_escaped_metacharacter();
187    }
188    else {
189        return makeCC(parse_utf8_codepoint());
190    }
191}
192
193inline RE * RE_Parser::parse_escaped_metacharacter() {
194    ++_cursor;
195    throw_incomplete_expression_error_if_end_of_stream();
196    switch (*_cursor) {
197        case 'P':
198            return makeDiff(makeAny(), parse_unicode_category());
199        case 'p':
200            return parse_unicode_category();
201                default:
202                        return makeCC(parse_escaped_codepoint());
203    }
204    throw ParseFailure("Illegal backslash escape!");
205}
206
207unsigned RE_Parser::parse_utf8_codepoint() {
208    unsigned c = static_cast<unsigned>(*_cursor++);
209    if (c > 0x80) { // if non-ascii
210        if (c < 0xC2) {
211            throw InvalidUTF8Encoding();
212        }
213        else { // [0xC2, 0xFF]
214            unsigned bytes = 0;
215            if (c < 0xE0) { // [0xC2, 0xDF]
216                c &= 0x1F;
217                bytes = 1;
218            }
219            else if (c < 0xF0) { // [0xE0, 0xEF]
220                c &= 0x0F;
221                bytes = 2;
222            }
223            else { // [0xF0, 0xFF]
224                c &= 0x0F;
225                bytes = 3;
226            }
227            while (--bytes) {
228                if (++_cursor == _end || (*_cursor & 0xC0) != 0x80) {
229                    throw InvalidUTF8Encoding();
230                }
231                c = (c << 6) | static_cast<unsigned>(*_cursor & 0x3F);
232                // It is an error if a 3-byte sequence is used to encode a codepoint < 0x800
233                // or a 4-byte sequence is used to encode a codepoint < 0x10000.
234                // if (((bytes == 1) && (c < 0x20)) || ((bytes == 2) && (c < 0x10))) {
235                if ((c << (bytes - 1)) < 0x20) {
236                    throw InvalidUTF8Encoding();
237                }
238            }
239        }
240    }
241    // It is an error if a 4-byte sequence is used to encode a codepoint
242    // above the Unicode maximum.   
243    if (c > CC::UNICODE_MAX) {
244        throw InvalidUTF8Encoding();
245    }
246    return c;
247}
248
249Name * RE_Parser::parse_unicode_category() {
250    if (++_cursor != _end && *_cursor == '{') {
251        const cursor_t start = _cursor + 1;
252        for (;;) {
253            if (++_cursor == _end) {
254                throw UnclosedUnicodeCharacterClass();
255            }
256            if (*_cursor == '}') {
257                break;
258            }
259            ++_cursor;
260        }
261        return makeName(std::string(start, _cursor++), Name::Type::UnicodeCategory);
262    }
263    throw ParseFailure("Incorrect Unicode character class format!");
264}
265
266RE * RE_Parser::parse_charset() {
267    CC * cc = makeCC();
268    bool negated = false;
269    cursor_t start = ++_cursor;
270    while (_cursor != _end) {
271        bool literal = true;
272        switch (*_cursor) {
273            case '^':
274                // If the first character after the [ is a ^ (caret) then the matching character class is complemented.
275                if ((start == _cursor) && !negated) {
276                    negated = true;
277                    start = ++_cursor; // move the start ahead in case the next character is a ] or -
278                    literal = false;                   
279                }
280                break;
281            case ']':
282                // To include a ], put it immediately after the opening [ or [^; if it occurs later it will
283                // close the bracket expression.
284                if (start == _cursor) {
285                    cc->insert(']');
286                    ++_cursor;
287                    literal = false;
288                    break;
289                }
290                ++_cursor;
291                if (negated) {
292                    return makeDiff(makeAny(), cc);
293                }
294                return cc;
295            // The hyphen (-) is not treated as a range separator if it appears first or last, or as the
296            // endpoint of a range.
297            case '-':
298                if (true) {
299                    literal = false;
300                    const cursor_t next = _cursor + 1;
301                    if (next == _end) {
302                        throw UnclosedCharacterClass();
303                    }
304                    if ((start == _cursor) ? (*next != '-') : (*next == ']')) {
305                        _cursor = next;
306                        cc->insert('-');
307                        break;
308                    }
309                }
310                throw ParseFailure("Invalid Lower Range Bound!");
311            // case ':':
312        }
313        if (literal) {
314            unsigned low;
315            if (parse_charset_literal(low)) {
316                // the previous literal allows for a - to create a range; test for it
317                if (_cursor == _end) {
318                    break; // out of loop to failure handling
319                }
320                if (*_cursor == '-') { // in range unless the next character is a ']'
321                    if (++_cursor == _end) {
322                        break; // out of loop to failure handling
323                    }
324                    if (*_cursor != ']') {
325                        unsigned high;
326                        if (!parse_charset_literal(high)) {
327                            throw ParseFailure("Invalid Upper Range Bound!");
328                        }
329                        cc->insert_range(low, high);
330                    }
331                    else {
332                        cc->insert(low);
333                        cc->insert('-');
334                    }
335                    continue;
336                }
337            }
338            cc->insert(low);
339        }
340    }
341    throw UnclosedCharacterClass();
342}
343
344inline bool RE_Parser::parse_charset_literal(unsigned & literal) {
345    if (_cursor == _end) {
346        return false;
347    }
348    if (*_cursor == '\\') {
349                _cursor++;
350                literal = parse_escaped_codepoint();
351                return true;
352    }
353    else {
354        literal = parse_utf8_codepoint();
355        return true;
356    }
357    return false;
358}
359
360unsigned RE_Parser::parse_int() {
361    unsigned value = 0;
362    for (; _cursor != _end; ++_cursor) {
363        if (!isdigit(*_cursor)) {
364            break;
365        }
366        value *= 10;
367        value += static_cast<int>(*_cursor) - 48;
368    }
369    return value;
370}
371
372
373// A backslash escape was found, and various special cases (back reference,
374// quoting with \Q, \E, sets (\p, \P, \d, \D, \w, \W, \s, \S), grapheme
375// cluster \X have been ruled out.
376// It may be one of several possibilities or an error sequence.
377// 1. Special control codes (\a, \b, \e, \f, \n, \r, \t, \v)
378// 2. General control codes c[@-_a-z?]
379// 3. Restricted octal notation 0 - 0777
380// 4. General octal notation o\{[0-7]+\}
381// 5. General hex notation x\{[0-9A-Fa-f]+\}
382// 6. An error for any unrecognized alphabetic escape
383// 7. An escaped ASCII symbol, standing for itself
384
385unsigned RE_Parser::parse_escaped_codepoint() {
386        unsigned cp_value;
387        throw_incomplete_expression_error_if_end_of_stream();
388        switch (*_cursor) {
389                case 'a': ++_cursor; return 0x07; // BEL
390                case 'b': ++_cursor; return 0x08; // BS
391                case 'e': ++_cursor; return 0x1B; // ESC
392                case 'f': ++_cursor; return 0x0C; // FF
393                case 'n': ++_cursor; return 0x0A; // LF
394                case 'r': ++_cursor; return 0x0D; // CR
395                case 't': ++_cursor; return 0x09; // HT
396                case 'v': ++_cursor; return 0x0B; // VT
397                case 'c': // Control-escape based on next char
398                        ++_cursor;
399                        throw_incomplete_expression_error_if_end_of_stream();
400                        // \c@, \cA, ... \c_, or \ca, ..., \cz
401                        if (((*_cursor >= '@') && (*_cursor <= '_')) || ((*_cursor >= 'a') && (*_cursor <= 'z'))) {
402                                cp_value = static_cast<unsigned>(*_cursor & 0x1F);
403                                _cursor++;
404                                return cp_value;
405                        }
406                        else if (*_cursor++ == '?') return 0x7F;  // \c? ==> DEL
407                        else throw("Illegal \\c escape sequence");
408                case '0': // Octal escape:  0 - 0377
409                        ++_cursor;
410                        return parse_octal_codepoint(0,3);
411                case 'o':
412                        ++_cursor;
413                        throw_incomplete_expression_error_if_end_of_stream();
414                        if (*_cursor == '{') {
415                                ++_cursor;
416                                cp_value = parse_octal_codepoint(1, 7);
417                                if (_cursor == _end || *_cursor++ != '}') throw ParseFailure("Malformed octal escape sequence");
418                                return cp_value;
419                        }
420                        else {
421                                throw ParseFailure("Malformed octal escape sequence");
422                        }
423                case 'x':
424                        ++_cursor;
425                        throw_incomplete_expression_error_if_end_of_stream();
426                        if (*_cursor == '{') {
427                          ++_cursor;
428                          cp_value = parse_hex_codepoint(1, 6);
429                          if (_cursor == _end || *_cursor++ != '}') throw ParseFailure("Malformed hex escape sequence");
430                          return cp_value;
431                        }
432                        else {
433                                return parse_hex_codepoint(1,2);  // ICU compatibility
434                        }
435                case 'u':
436                        ++_cursor;
437                        throw_incomplete_expression_error_if_end_of_stream();
438                        if (*_cursor == '{') {
439                                ++_cursor;
440                                cp_value = parse_hex_codepoint(1, 6);
441                                if (_cursor == _end || *_cursor++ != '}') throw ParseFailure("Malformed hex escape sequence");
442                                return cp_value;
443                        }
444                        else {
445                                return parse_hex_codepoint(4,4);  // ICU compatibility
446                        }
447                case 'U':
448                        ++_cursor;
449                        return parse_hex_codepoint(8,8);  // ICU compatibility
450                default:
451                        if (((*_cursor >= 'A') && (*_cursor <= 'Z')) || ((*_cursor >= 'a') && (*_cursor <= 'z')))
452                                throw ParseFailure("Undefined or unsupported escape sequence");
453                        else return static_cast<unsigned>(*_cursor++);
454        }
455}
456
457
458unsigned RE_Parser::parse_octal_codepoint(int mindigits, int maxdigits) {
459        unsigned value = 0;
460        int count = 0;
461        while (_cursor != _end && count < maxdigits) {
462                const char t = *_cursor;
463                if (t < '0' || t > '7') {
464                        break;
465                }
466                value = value * 8 | (t - '0');
467                ++_cursor;
468                ++count;
469        }
470        if (count < mindigits) throw ParseFailure("Octal sequence has too few digits");
471        if (value > CC::UNICODE_MAX) throw ParseFailure("Octal value too large");
472        return value;
473}
474
475unsigned RE_Parser::parse_hex_codepoint(int mindigits, int maxdigits) {
476        unsigned value = 0;
477        int count = 0;
478        while (_cursor != _end && isxdigit(*_cursor) && count < maxdigits) {
479                const char t = *_cursor;
480                if (isdigit(t)) {
481                        value = (value * 16) | (t - '0');
482                }
483                else { 
484                        value = (value * 16) | ((t | 32) - 'a') + 10;
485                }
486                ++_cursor;
487                ++count;
488        }
489        if (count < mindigits) throw ParseFailure("Hexadecimal sequence has too few digits");
490        if (value > CC::UNICODE_MAX) throw ParseFailure("Hexadecimal value too large");
491        return value;
492}
493
494
495inline void RE_Parser::throw_incomplete_expression_error_if_end_of_stream() const {
496    if (_cursor == _end) throw IncompleteRegularExpression();
497}
498
499}
Note: See TracBrowser for help on using the repository browser.