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

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

Set Intersection back-end support

File size: 12.4 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 ']': case '{': case '}':
97                throw ParseFailure("Illegal metacharacter usage!");
98            case '[':
99                re = parse_charset();
100                break;
101            case '.': // the 'any' metacharacter
102                re = parse_any_character();
103                break;
104            default:
105                re = parse_literal();
106                break;
107        }
108    }
109    return re;
110}
111
112Any * RE_Parser::parse_any_character() {
113    ++_cursor;
114    return makeAny();
115}
116
117RE * RE_Parser::extend_item(RE * re) {
118    if (_cursor == _end) {
119        return re;
120    }
121    switch (*_cursor) {
122        case '*':
123            ++_cursor; // skip past the '*'
124            re = makeRep(re, 0, Rep::UNBOUNDED_REP);
125            break;
126        case '?':
127            ++_cursor; // skip past the '?'
128            re = makeRep(re, 0, 1);
129            break;
130        case '+':
131            ++_cursor; // skip past the '+'
132            re = makeRep(re, 1, Rep::UNBOUNDED_REP);
133            break;
134        case '{':
135            re = parse_range_bound(re);
136            break;
137        default:
138            return re;
139    }
140    // this only occurs if we encountered one of the non-default cases above.
141    return extend_item(re);
142}
143
144inline RE * RE_Parser::parse_range_bound(RE * re) {
145    ++_cursor;
146    throw_incomplete_expression_error_if_end_of_stream();
147    RE * rep = nullptr;
148    unsigned lower_bound;
149    if (*_cursor == ',') {
150        ++_cursor;
151        lower_bound = 0;
152    }
153    else {
154        lower_bound = parse_int();
155    }
156    throw_incomplete_expression_error_if_end_of_stream();
157    if (*_cursor == '}') {
158        rep = makeRep(re, lower_bound, lower_bound);
159    }
160    else if (*_cursor != ',') {
161        throw BadLowerBound();
162    }
163    else { // [^,}]
164        ++_cursor;
165        throw_incomplete_expression_error_if_end_of_stream();
166        if (*_cursor == '}') {
167            rep = makeRep(re, lower_bound, Rep::UNBOUNDED_REP);
168        }
169        else {
170            const unsigned upper_bound = parse_int();
171            if (*_cursor != '}') {
172                throw BadUpperBound();
173            }
174            rep = makeRep(re, lower_bound, upper_bound);
175        }
176    }
177    ++_cursor;
178    return rep;
179}
180
181inline RE * RE_Parser::parse_literal() {
182    // handle the escaped metacharacter (assuming it is one)
183    if (*_cursor == '\\') {
184        return parse_escaped_metacharacter();
185    }
186    else {
187        return makeCC(parse_utf8_codepoint());
188    }
189}
190
191inline RE * RE_Parser::parse_escaped_metacharacter() {
192    ++_cursor;
193    throw_incomplete_expression_error_if_end_of_stream();
194    switch (*_cursor) {
195        case '(': case ')': case '*': case '+':
196        case '.': case '?': case '[': case '\\':
197        case ']': case '{': case '|': case '}':
198            return makeCC(*_cursor++);
199        case 'u':
200            return makeCC(parse_hex());
201        case 'P':
202            return makeDiff(makeAny(), parse_unicode_category());
203        case 'p':
204            return parse_unicode_category();
205    }
206    throw ParseFailure("Illegal backslash escape!");
207}
208
209unsigned RE_Parser::parse_utf8_codepoint() {
210    unsigned c = static_cast<unsigned>(*_cursor++);
211    if (c > 0x80) { // if non-ascii
212        if (c < 0xC2) {
213            throw InvalidUTF8Encoding();
214        }
215        else { // [0xC2, 0xFF]
216            unsigned bytes = 0;
217            if (c < 0xE0) { // [0xC2, 0xDF]
218                c &= 0x1F;
219                bytes = 1;
220            }
221            else if (c < 0xF0) { // [0xE0, 0xEF]
222                c &= 0x0F;
223                bytes = 2;
224            }
225            else { // [0xF0, 0xFF]
226                c &= 0x0F;
227                bytes = 3;
228            }
229            while (--bytes) {
230                if (++_cursor == _end || (*_cursor & 0xC0) != 0x80) {
231                    throw InvalidUTF8Encoding();
232                }
233                c = (c << 6) | static_cast<unsigned>(*_cursor & 0x3F);
234                // It is an error if a 3-byte sequence is used to encode a codepoint < 0x800
235                // or a 4-byte sequence is used to encode a codepoint < 0x10000.
236                // if (((bytes == 1) && (c < 0x20)) || ((bytes == 2) && (c < 0x10))) {
237                if ((c << (bytes - 1)) < 0x20) {
238                    throw InvalidUTF8Encoding();
239                }
240            }
241        }
242    }
243    // It is an error if a 4-byte sequence is used to encode a codepoint
244    // above the Unicode maximum.   
245    if (c > CC::UNICODE_MAX) {
246        throw InvalidUTF8Encoding();
247    }
248    return c;
249}
250
251Name * RE_Parser::parse_unicode_category() {
252    if (++_cursor != _end && *_cursor == '{') {
253        const cursor_t start = _cursor + 1;
254        for (;;) {
255            if (++_cursor == _end) {
256                throw UnclosedUnicodeCharacterClass();
257            }
258            if (*_cursor == '}') {
259                break;
260            }
261            ++_cursor;
262        }
263        return makeName(std::string(start, _cursor++), Name::Type::UnicodeCategory);
264    }
265    throw ParseFailure("Incorrect Unicode character class format!");
266}
267
268RE * RE_Parser::parse_charset() {
269    CC * cc = makeCC();
270    bool negated = false;
271    cursor_t start = ++_cursor;
272    while (_cursor != _end) {
273        bool literal = true;
274        switch (*_cursor) {
275            case '^':
276                // If the first character after the [ is a ^ (caret) then the matching character class is complemented.
277                if ((start == _cursor) && !negated) {
278                    negated = true;
279                    start = ++_cursor; // move the start ahead in case the next character is a ] or -
280                    literal = false;                   
281                }
282                break;
283            case ']':
284                // To include a ], put it immediately after the opening [ or [^; if it occurs later it will
285                // close the bracket expression.
286                if (start == _cursor) {
287                    cc->insert(']');
288                    ++_cursor;
289                    literal = false;
290                    break;
291                }
292                ++_cursor;
293                if (negated) {
294                    return makeDiff(makeAny(), cc);
295                }
296                return cc;
297            // The hyphen (-) is not treated as a range separator if it appears first or last, or as the
298            // endpoint of a range.
299            case '-':
300                if (true) {
301                    literal = false;
302                    const cursor_t next = _cursor + 1;
303                    if (next == _end) {
304                        throw UnclosedCharacterClass();
305                    }
306                    if ((start == _cursor) ? (*next != '-') : (*next == ']')) {
307                        _cursor = next;
308                        cc->insert('-');
309                        break;
310                    }
311                }
312                throw ParseFailure("Invalid Lower Range Bound!");
313            // case ':':
314        }
315        if (literal) {
316            unsigned low;
317            if (parse_charset_literal(low)) {
318                // the previous literal allows for a - to create a range; test for it
319                if (_cursor == _end) {
320                    break; // out of loop to failure handling
321                }
322                if (*_cursor == '-') { // in range unless the next character is a ']'
323                    if (++_cursor == _end) {
324                        break; // out of loop to failure handling
325                    }
326                    if (*_cursor != ']') {
327                        unsigned high;
328                        if (!parse_charset_literal(high)) {
329                            throw ParseFailure("Invalid Upper Range Bound!");
330                        }
331                        cc->insert_range(low, high);
332                    }
333                    else {
334                        cc->insert(low);
335                        cc->insert('-');
336                    }
337                    continue;
338                }
339            }
340            cc->insert(low);
341        }
342    }
343    throw UnclosedCharacterClass();
344}
345
346inline bool RE_Parser::parse_charset_literal(unsigned & literal) {
347    if (_cursor == _end) {
348        return false;
349    }
350    if (*_cursor == '\\') {
351        if (++_cursor == _end) {
352            throw ParseFailure("Unknown charset escape!");
353        }
354        switch (*_cursor) {
355            case '(': case ')': case '*': case '+':
356            case '.': case '?': case '[': case '\\':
357            case ']': case '{': case '|': case '}':
358            case '-':
359                if (_allow_escapes_within_charset) {
360                    literal = *_cursor++;
361                    return true;
362                }
363                break;
364            case 'u':
365                literal = parse_hex();
366                return true;
367            // probably need to pass in the CC to handle \w, \s, etc...
368        }
369        throw ParseFailure("Unknown charset escape!");
370    }
371    else {
372        literal = parse_utf8_codepoint();
373        return true;
374    }
375    return false;
376}
377
378unsigned RE_Parser::parse_int() {
379    unsigned value = 0;
380    for (; _cursor != _end; ++_cursor) {
381        if (!isdigit(*_cursor)) {
382            break;
383        }
384        value *= 10;
385        value += static_cast<int>(*_cursor) - 48;
386    }
387    return value;
388}
389
390unsigned RE_Parser::parse_hex() {
391    if (++_cursor != _end && *_cursor == '{') {
392        unsigned value = 0;
393        for (++_cursor; _cursor != _end; ++_cursor) {
394            const char t = *_cursor;
395            if (t == '}') {
396                ++_cursor;
397                return value;
398            }
399            value *= 16;
400            if (t >= '0' && t <= '9') {
401                value |= (t - '0');
402            }
403            else if ((t | 32) >= 'a' && (t | 32) <= 'f') {
404                value |= ((t | 32) - 'a') + 10;
405            }
406            else {
407                break;
408            }
409        }
410    }
411    throw ParseFailure("Bad Unicode hex notation!");
412}
413
414inline void RE_Parser::throw_incomplete_expression_error_if_end_of_stream() const {
415    if (_cursor == _end) throw IncompleteRegularExpression();
416}
417
418}
Note: See TracBrowser for help on using the repository browser.