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

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

Parsing escaped set vs. escaped codepoints

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