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

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

Modified RE module to use a LLVM-like dyn_cast system; added 'make' functions to hide RE constructors.

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