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

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

Some refactoring of the RE CC class and CC Compiler; Moved RE into re subdirectory.

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