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

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

Implemented slab allocator based on the original Parabix StringPool?; intergrated it with RE and Pablo AST nodes.

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