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

Last change on this file since 4242 was 4242, checked in by nmedfort, 5 years ago

Minor changes in preperation for adding multiplexing.

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_parser.h"
8#include "re_alt.h"
9#include "re_end.h"
10#include "re_rep.h"
11#include "re_seq.h"
12#include "re_start.h"
13#include "parsefailure.h"
14#include <algorithm>
15
16namespace re {
17
18RE * RE_Parser::parse(const std::string & regular_expression, const bool allow_escapes_within_charset) {
19    RE_Parser parser(regular_expression, allow_escapes_within_charset);
20    RE * re = parser.parse_alt(false);
21    if (re == nullptr) {
22        throw ParseFailure("An unexpected parsing error occurred!");
23    }
24    return re;
25}
26
27inline RE_Parser::RE_Parser(const std::string & regular_expression, const bool allow_escapes_within_charset)
28: _cursor(regular_expression.begin())
29, _end(regular_expression.end())
30, _allow_escapes_within_charset(allow_escapes_within_charset)
31{
32
33}
34
35RE * RE_Parser::parse_alt(const bool subexpression) {
36    std::vector<RE *> alt;
37    for (;;) {
38        alt.push_back(parse_seq());
39        if (_cursor == _end || *_cursor != '|') {
40            break;
41        }
42        ++_cursor; // advance past the alternation character '|'
43    }
44    if (alt.empty())
45    {
46        throw NoRegularExpressionFound();
47    }
48    else if (subexpression) {
49        if (_cursor == _end || *_cursor != ')') {
50            throw ParseFailure("Parenthesization error!");
51        }
52        ++_cursor;
53    }
54    else if (_cursor != _end) { // !subexpression
55        throw ParseFailure("Cannot fully parse statement!");
56    }
57    return makeAlt(alt.begin(), alt.end());
58}
59
60inline RE * RE_Parser::parse_seq() {
61    std::vector<RE *> seq;
62    for (;;) {
63        RE * re = parse_next_token();
64        if (re == nullptr) {
65            break;
66        }
67        seq.push_back(extend_item(re));
68    }
69    if (seq.empty())
70    {
71        throw NoRegularExpressionFound();
72    }
73    return makeSeq(Seq::Type::Normal, seq.begin(), seq.end());
74}
75
76RE * RE_Parser::parse_next_token() {
77    RE * re = nullptr;
78    if (_cursor != _end) {
79        switch (*_cursor) {
80            case '(':
81                ++_cursor;
82                re = parse_alt(true);
83                break;
84            case '^':
85                ++_cursor;
86                re = makeStart();
87                break;
88            case '$':
89                ++_cursor;
90                re = makeEnd();
91                break;
92            case '|': case ')':
93                break;
94            case '*': case '+': case '?': case ']': case '{': case '}':
95                throw ParseFailure("Illegal metacharacter usage!");
96            case '[':
97                re = parse_charset();
98                break;
99            case '.': // the 'any' metacharacter
100                re = parse_any_character();
101                break;
102            default:
103                re = parse_literal();
104                break;
105        }
106    }
107    return re;
108}
109
110CC * RE_Parser::parse_any_character() {
111    CC * cc = makeCC();
112    cc->insert_range(0, 9);
113    cc->insert_range(11, CC::UNICODE_MAX);
114    ++_cursor;
115    return cc;
116}
117
118RE * RE_Parser::extend_item(RE * re) {
119    if (_cursor == _end) {
120        return re;
121    }
122    switch (*_cursor) {
123        case '*':
124            ++_cursor; // skip past the '*'
125            re = makeRep(re, 0, Rep::UNBOUNDED_REP);
126            break;
127        case '?':
128            ++_cursor; // skip past the '?'
129            re = makeRep(re, 0, 1);
130            break;
131        case '+':
132            ++_cursor; // skip past the '+'
133            re = makeRep(re, 1, Rep::UNBOUNDED_REP);
134            break;
135        case '{':
136            re = parse_range_bound(re);
137            break;
138        default:
139            return re;
140    }
141    // this only occurs if we encountered one of the non-default cases above.
142    return extend_item(re);
143}
144
145inline RE * RE_Parser::parse_range_bound(RE * re) {
146    ++_cursor;
147    throw_incomplete_expression_error_if_end_of_stream();
148    RE * rep = nullptr;
149    unsigned lower_bound;
150    if (*_cursor == ',') {
151        ++_cursor;
152        lower_bound = 0;
153    }
154    else {
155        lower_bound = parse_int();
156    }
157    throw_incomplete_expression_error_if_end_of_stream();
158    if (*_cursor == '}') {
159        rep = makeRep(re, lower_bound, lower_bound);
160    }
161    else if (*_cursor != ',') {
162        throw BadLowerBound();
163    }
164    else { // [^,}]
165        ++_cursor;
166        throw_incomplete_expression_error_if_end_of_stream();
167        if (*_cursor == '}') {
168            rep = makeRep(re, lower_bound, Rep::UNBOUNDED_REP);
169        }
170        else {
171            const unsigned upper_bound = parse_int();
172            if (*_cursor != '}') {
173                throw BadUpperBound();
174            }
175            rep = makeRep(re, lower_bound, upper_bound);
176        }
177    }
178    ++_cursor;
179    return rep;
180}
181
182inline RE * RE_Parser::parse_literal() {
183    // handle the escaped metacharacter (assuming it is one)
184    if (*_cursor == '\\') {
185        return parse_escaped_metacharacter();
186    }
187    else {
188        return makeCC(parse_utf8_codepoint());
189    }
190}
191
192inline RE * RE_Parser::parse_escaped_metacharacter() {
193    ++_cursor;
194    throw_incomplete_expression_error_if_end_of_stream();
195    bool negated = false;
196    switch (*_cursor) {
197        case '(': case ')': case '*': case '+':
198        case '.': case '?': case '[': case '\\':
199        case ']': case '{': case '|': case '}':
200            return makeCC(*_cursor++);
201        case 'u':
202            return makeCC(parse_hex());
203        case 'P':
204            negated = true;
205        case 'p':
206            return parse_unicode_category(negated);
207    }
208    throw ParseFailure("Illegal backslash escape!");
209}
210
211unsigned RE_Parser::parse_utf8_codepoint() {
212    unsigned c = static_cast<unsigned>(*_cursor++);
213    if (c > 0x80) { // if non-ascii
214        if (c < 0xC2) {
215            throw InvalidUTF8Encoding();
216        }
217        else { // [0xC2, 0xFF]
218            unsigned bytes = 0;
219            if (c < 0xE0) { // [0xC2, 0xDF]
220                c &= 0x1F;
221                bytes = 1;
222            }
223            else if (c < 0xF0) { // [0xE0, 0xEF]
224                c &= 0x0F;
225                bytes = 2;
226            }
227            else { // [0xF0, 0xFF]
228                c &= 0x0F;
229                bytes = 3;
230            }
231            while (--bytes) {
232                if (++_cursor == _end || (*_cursor & 0xC0) != 0x80) {
233                    throw InvalidUTF8Encoding();
234                }
235                c = (c << 6) | static_cast<unsigned>(*_cursor & 0x3F);
236                // It is an error if a 3-byte sequence is used to encode a codepoint < 0x800
237                // or a 4-byte sequence is used to encode a codepoint < 0x10000.
238                // if (((bytes == 1) && (c < 0x20)) || ((bytes == 2) && (c < 0x10))) {
239                if ((c << (bytes - 1)) < 0x20) {
240                    throw InvalidUTF8Encoding();
241                }
242            }
243        }
244    }
245    // It is an error if a 4-byte sequence is used to encode a codepoint
246    // above the Unicode maximum.   
247    if (c > CC::UNICODE_MAX) {
248        throw InvalidUTF8Encoding();
249    }
250    return c;
251}
252
253inline Name * RE_Parser::parse_unicode_category(const bool negated) {
254    if (++_cursor != _end && *_cursor == '{') {
255        const cursor_t start = _cursor + 1;
256        for (;;) {
257            if (++_cursor == _end) {
258                throw UnclosedUnicodeCharacterClass();
259            }
260            if (*_cursor == '}') {
261                break;
262            }
263            ++_cursor;
264        }
265        return makeName(std::string(start, _cursor++), negated, Name::Type::UnicodeCategory);
266    }
267    throw ParseFailure("Incorrect Unicode character class format!");
268}
269
270RE * RE_Parser::parse_charset() {
271    std::unique_ptr<CC> cc(makeCC());
272    bool negated = false;
273    cursor_t start = ++_cursor;
274    while (_cursor != _end) {
275        bool literal = true;
276        switch (*_cursor) {
277            case '^':
278                // If the first character after the [ is a ^ (caret) then the matching character class is complemented.
279                if ((start == _cursor) && !negated) {
280                    negated = true;
281                    start = ++_cursor; // move the start ahead in case the next character is a ] or -
282                    literal = false;                   
283                }
284                break;
285            case ']':
286                // To include a ], put it immediately after the opening [ or [^; if it occurs later it will
287                // close the bracket expression.
288                if (start == _cursor) {
289                    cc->insert(']');
290                    ++_cursor;
291                    literal = false;
292                    break;
293                }
294                if (negated) {
295                    negate_cc(cc);
296                }
297                ++_cursor;
298                return cc.release();
299            // The hyphen (-) is not treated as a range separator if it appears first or last, or as the
300            // endpoint of a range.
301            case '-':
302                if (true) {
303                    literal = false;
304                    const cursor_t next = _cursor + 1;
305                    if (next == _end) {
306                        throw UnclosedCharacterClass();
307                    }
308                    if ((start == _cursor) ? (*next != '-') : (*next == ']')) {
309                        _cursor = next;
310                        cc->insert('-');
311                        break;
312                    }
313                }
314                throw ParseFailure("Invalid Lower Range Bound!");
315            // case ':':
316        }
317        if (literal) {
318            unsigned low;
319            if (parse_charset_literal(low)) {
320                // the previous literal allows for a - to create a range; test for it
321                if (_cursor == _end) {
322                    break; // out of loop to failure handling
323                }
324                if (*_cursor == '-') { // in range unless the next character is a ']'
325                    if (++_cursor == _end) {
326                        break; // out of loop to failure handling
327                    }
328                    if (*_cursor != ']') {
329                        unsigned high;
330                        if (!parse_charset_literal(high)) {
331                            throw ParseFailure("Invalid Upper Range Bound!");
332                        }
333                        cc->insert_range(low, high);
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        if (++_cursor == _end) {
350            throw ParseFailure("Unknown charset escape!");
351        }
352        switch (*_cursor) {
353            case '(': case ')': case '*': case '+':
354            case '.': case '?': case '[': case '\\':
355            case ']': case '{': case '|': case '}':
356            case '-':
357                if (_allow_escapes_within_charset) {
358                    literal = *_cursor++;
359                    return true;
360                }
361                break;
362            case 'u':
363                literal = parse_hex();
364                return true;
365            // probably need to pass in the CC to handle \w, \s, etc...
366        }
367        throw ParseFailure("Unknown charset escape!");
368    }
369    else {
370        literal = parse_utf8_codepoint();
371        return true;
372    }
373    return false;
374}
375
376unsigned RE_Parser::parse_int() {
377    unsigned value = 0;
378    for (; _cursor != _end; ++_cursor) {
379        if (!isdigit(*_cursor)) {
380            break;
381        }
382        value *= 10;
383        value += static_cast<int>(*_cursor) - 48;
384    }
385    return value;
386}
387
388unsigned RE_Parser::parse_hex() {
389    if (++_cursor != _end && *_cursor == '{') {
390        unsigned value = 0;
391        for (++_cursor; _cursor != _end; ++_cursor) {
392            const char t = *_cursor;
393            if (t == '}') {
394                ++_cursor;
395                return value;
396            }
397            value *= 16;
398            if (t >= '0' && t <= '9') {
399                value |= (t - '0');
400            }
401            else if ((t | 32) >= 'a' && (t | 32) <= 'f') {
402                value |= ((t | 32) - 'a') + 10;
403            }
404            else {
405                break;
406            }
407        }
408    }
409    throw ParseFailure("Bad Unicode hex notation!");
410}
411
412inline void RE_Parser::negate_cc(std::unique_ptr<CC> & cc) {
413    cc->negate();
414    cc->remove(10);
415}
416
417inline void RE_Parser::throw_incomplete_expression_error_if_end_of_stream() const {
418    if (_cursor == _end) throw IncompleteRegularExpression();
419}
420
421}
Note: See TracBrowser for help on using the repository browser.