source: icGREP/icgrep-devel/icgrep/re_parser.cpp @ 4182

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

RE Parser modification to use ParseFailure? exceptions; removed the list reversal within Alt and Seq constructors and adjusted the functions that relied on it occurring.

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