Changeset 4309 for icGREP


Ignore:
Timestamp:
Nov 22, 2014, 3:01:59 PM (5 years ago)
Author:
cameron
Message:

New character class parser, supporting intersection, set difference, posix set expressions

Location:
icGREP/icgrep-devel/icgrep/re
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/re/re_parser.cpp

    r4307 r4309  
    1717#include <algorithm>
    1818
     19
     20// It would probably be best to enforce that {}, [], () must always
     21// be balanced.   But legacy syntax allows } and ] to occur as literals
     22// in certain contexts (no opening { or [, or immediately after [ or [^ ).
     23// Perhaps this define should become a parameter.
     24#define LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED true
     25#define LEGACY_UNESCAPED_HYPHEN_ALLOWED true
     26
     27
    1928namespace re {
    2029
     
    8291            case '(':
    8392                ++_cursor;
    84                 re = parse_alt(true);
    85                 break;
     93                return parse_alt(true);
    8694            case '^':
    8795                ++_cursor;
    88                 re = makeStart();
    89                 break;
     96                return makeStart();
    9097            case '$':
    9198                ++_cursor;
    92                 re = makeEnd();
    93                 break;
     99                return makeEnd();
    94100            case '|': case ')':
    95                 break;
     101                return nullptr;  // This is ugly.
    96102            case '*': case '+': case '?': case '{':
    97103                throw NothingToRepeat();
    98104            case ']': case '}':
    99                 throw ParseFailure("Illegal metacharacter usage!");
     105                                if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
     106                                        return parse_literal();
     107                                }
     108                                else throw ParseFailure("Use  \\] or \\} for literal ] or }.");
    100109            case '[':
    101                 re = parse_charset();
    102                 break;
     110                *_cursor++;
     111                return parse_charset();
    103112            case '.': // the 'any' metacharacter
    104                 re = parse_any_character();
    105                 break;
    106             case '\\':  // escape processing
     113                return parse_any_character();
     114                        case '\\':  // escape processing
    107115                ++_cursor;
    108                 re = parse_escaped();
    109                 break;
     116                return parse_escaped();
    110117            default:
    111                 re = parse_literal();
    112                 break;
     118                return parse_literal();
    113119        }
    114120    }
     
    198204}
    199205
     206unsigned RE_Parser::parse_int() {
     207    unsigned value = 0;
     208    for (; _cursor != _end; ++_cursor) {
     209        if (!isdigit(*_cursor)) {
     210            break;
     211        }
     212        value *= 10;
     213        value += static_cast<int>(*_cursor) - 48;
     214    }
     215    return value;
     216}
     217
    200218inline RE * RE_Parser::parse_literal() {
    201219    return makeCC(parse_utf8_codepoint());
     
    233251}
    234252
    235 inline RE * RE_Parser::parse_escaped_set() {
     253RE * RE_Parser::parse_escaped_set() {
     254        bool complemented = false;
     255        RE * s;
    236256    switch (*_cursor) {
     257                case 'd':
     258                        ++_cursor;
     259                        return makeDigitSet();
     260                case 'D':
     261                        ++_cursor;
     262                        return makeComplement(makeDigitSet());
     263                case 's':
     264                        ++_cursor;
     265                        return makeWhitespaceSet();
     266                case 'S':
     267                        ++_cursor;
     268                        return makeComplement(makeWhitespaceSet());
     269                case 'w':
     270                        ++_cursor;
     271                        return makeWordSet();
     272                case 'W':
     273                        ++_cursor;
     274                        return makeComplement(makeWordSet());
    237275        case 'P':
    238             return makeDiff(makeAny(), parse_unicode_category());
     276            complemented = true;
    239277        case 'p':
    240             return parse_unicode_category();
    241         case 'd':
    242             ++_cursor;
    243             return makeDigitSet();
    244         case 'D':
    245             ++_cursor;
    246             return makeComplement(makeDigitSet());
    247         case 's':
    248             ++_cursor;
    249             return makeWhitespaceSet();
    250         case 'S':
    251             ++_cursor;
    252             return makeComplement(makeWhitespaceSet());
    253         case 'w':
    254             ++_cursor;
    255             return makeWordSet();
    256         case 'W':
    257             ++_cursor;
    258             return makeComplement(makeWordSet());
    259         default:
    260             throw ParseFailure("Internal error");
     278                        ++_cursor;
     279                        if (_cursor == _end || *_cursor != '{') throw ParseFailure("Malformed property expression");
     280                        ++_cursor;
     281                        s = parse_property_expression();
     282                        if (_cursor == _end || *_cursor != '}') throw ParseFailure("Malformed property expression");
     283                        ++_cursor;
     284                        if (complemented) return makeComplement(s);
     285                        else return s;
     286                default:
     287                        throw ParseFailure("Internal error");
    261288    }
    262289}
     
    304331}
    305332
    306 Name * RE_Parser::parse_unicode_category() {
    307     if (++_cursor != _end && *_cursor == '{') {
    308         const cursor_t start = _cursor + 1;
    309         for (;;) {
    310             if (++_cursor == _end) {
    311                 throw UnclosedUnicodeCharacterClass();
    312             }
    313             if (*_cursor == '}') {
    314                 break;
    315             }
    316             ++_cursor;
    317         }
    318         return makeName(std::string(start, _cursor++), Name::Type::UnicodeCategory);
    319     }
    320     throw ParseFailure("Incorrect Unicode character class format!");
    321 }
    322 
     333Name * RE_Parser::parse_property_expression() {
     334    const cursor_t start = _cursor;
     335        while (_cursor != _end && *_cursor != '}' and *_cursor != ':') {
     336                _cursor++;
     337        }
     338        return makeName(std::string(start, _cursor), Name::Type::UnicodeCategory);
     339}
     340       
     341CharsetOperatorKind RE_Parser::getCharsetOperator() {
     342    throw_incomplete_expression_error_if_end_of_stream();
     343        switch (*_cursor) {
     344                case '&':
     345                        ++_cursor;
     346                        if (_cursor != _end && *_cursor == '&') {
     347                                ++_cursor;
     348                                return intersectOp;
     349                        }
     350                        else if (_cursor != _end && *_cursor == '[') {
     351                                // Short-hand for intersectOp when a set follows
     352                                return intersectOp;
     353                        }
     354                        else return ampChar;
     355                case '-':
     356                        ++_cursor;
     357                        if (_cursor != _end && *_cursor == '-') {
     358                                ++_cursor;
     359                                return setDiffOp;
     360                        }
     361                        else if (_cursor != _end && *_cursor == '[') {
     362                                return setDiffOp;
     363                        }
     364                        else if (_cursor != _end && *_cursor == ']') {
     365                                return hyphenChar;
     366                        }
     367                        else return rangeHyphen;
     368                case '[':
     369                        ++_cursor;
     370                        if (_cursor != _end && *_cursor == ':') {
     371                                ++_cursor;
     372                                return posixPropertyOpener;
     373                        }
     374                        else return setOpener;
     375                case ']':
     376                        ++_cursor;
     377                        return setCloser;
     378                case '\\':
     379                        ++_cursor;
     380                        return backSlash;
     381                default:
     382                        return emptyOperator;
     383        }
     384}                       
     385       
     386// Precondition: cursor is immediately after opening '[' character
    323387RE * RE_Parser::parse_charset() {
     388        // Sets are accumulated using two variables:
     389        // subexprs accumulates set expressions such as \p{Lu}, [\w && \p{Greek}]
     390        // cc accumulates the literal and calculated codepoints and ranges
     391        std::vector<RE *> subexprs;
    324392    CC * cc = makeCC();
     393        // When the last item deal with is a single literal charcacter or calculated codepoint,
     394        // a following hyphen can indicate a range.   When the last item is a set subexpression,
     395        // a following hyphen can indicate set subtraction.
     396        enum {NoItem, CodepointItem, RangeItem, SetItem, BrackettedSetItem} lastItemKind = NoItem;
     397        unsigned lastCodepointItem;
     398       
     399        bool havePendingOperation = false;
     400        CharsetOperatorKind pendingOperationKind;
     401        RE * pendingOperand;
     402       
     403    // If the first character after the [ is a ^ (caret) then the matching character class is complemented.
    325404    bool negated = false;
    326     cursor_t start = ++_cursor;
     405    if (_cursor != _end && *_cursor == '^') {
     406      negated = true;
     407      ++_cursor;
     408    }
     409    throw_incomplete_expression_error_if_end_of_stream();
     410        // Legacy rule: an unescaped ] may appear as a literal set character
     411        // if and only if it appears immediately after the opening [ or [^
     412    if ( *_cursor == ']' && LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
     413                cc->insert(']');
     414                lastItemKind = CodepointItem;
     415                lastCodepointItem = static_cast<unsigned> (']');
     416                ++_cursor;
     417    }
     418    else if ( *_cursor == '-' && LEGACY_UNESCAPED_HYPHEN_ALLOWED) {
     419                ++_cursor;
     420                cc->insert('-');
     421                lastItemKind = CodepointItem;
     422                lastCodepointItem = static_cast<unsigned> ('-');
     423                if (*_cursor == '-') throw ParseFailure("Set operator has no left operand.");
     424    }
    327425    while (_cursor != _end) {
    328         bool literal = true;
    329         switch (*_cursor) {
    330             case '^':
    331                 // If the first character after the [ is a ^ (caret) then the matching character class is complemented.
    332                 if ((start == _cursor) && !negated) {
    333                     negated = true;
    334                     start = ++_cursor; // move the start ahead in case the next character is a ] or -
    335                     literal = false;                   
    336                 }
    337                 break;
    338             case ']':
    339                 // To include a ], put it immediately after the opening [ or [^; if it occurs later it will
    340                 // close the bracket expression.
    341                 if (start == _cursor) {
    342                     cc->insert(']');
    343                     ++_cursor;
    344                     literal = false;
    345                     break;
    346                 }
    347                 ++_cursor;
    348                 if (negated) {
    349                     return makeDiff(makeAny(), cc);
    350                 }
    351                 return cc;
    352             // The hyphen (-) is not treated as a range separator if it appears first or last, or as the
    353             // endpoint of a range.
    354             case '-':
    355                 if (true) {
    356                     literal = false;
    357                     const cursor_t next = _cursor + 1;
    358                     if (next == _end) {
    359                         throw UnclosedCharacterClass();
    360                     }
    361                     if ((start == _cursor) ? (*next != '-') : (*next == ']')) {
    362                         _cursor = next;
    363                         cc->insert('-');
    364                         break;
    365                     }
    366                 }
    367                 throw ParseFailure("Invalid Lower Range Bound!");
    368             // case ':':
    369         }
    370         if (literal) {
    371             unsigned low;
    372             if (parse_charset_literal(low)) {
    373                 // the previous literal allows for a - to create a range; test for it
    374                 if (_cursor == _end) {
    375                     break; // out of loop to failure handling
    376                 }
    377                 if (*_cursor == '-') { // in range unless the next character is a ']'
    378                     if (++_cursor == _end) {
    379                         break; // out of loop to failure handling
    380                     }
    381                     if (*_cursor != ']') {
    382                         unsigned high;
    383                         if (!parse_charset_literal(high)) {
    384                             throw ParseFailure("Invalid Upper Range Bound!");
    385                         }
    386                         cc->insert_range(low, high);
    387                     }
    388                     else {
    389                         cc->insert(low);
    390                         cc->insert('-');
    391                     }
    392                     continue;
    393                 }
    394             }
    395             cc->insert(low);
    396         }
    397     }
    398     throw UnclosedCharacterClass();
    399 }
    400 
    401 inline bool RE_Parser::parse_charset_literal(unsigned & literal) {
    402     if (_cursor == _end) {
    403         return false;
    404     }
    405     if (*_cursor == '\\') {
    406                 _cursor++;
    407                 literal = parse_escaped_codepoint();
    408                 return true;
     426                CharsetOperatorKind op = getCharsetOperator();
     427                switch (op) {
     428                        case intersectOp: case setDiffOp: {
     429                                if (lastItemKind == NoItem) throw ParseFailure("Set operator has no left operand.");
     430                                if (cc->begin() != cc->end()) subexprs.push_back(cc);
     431                                RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
     432                                subexprs.clear();
     433                                cc = makeCC();
     434                                if (havePendingOperation) {
     435                                        if (pendingOperationKind == intersectOp) {
     436                                                pendingOperand = makeIntersect(pendingOperand, newOperand);
     437                                        }
     438                                        else {
     439                                                pendingOperand = makeDiff(pendingOperand, newOperand);
     440                                        }
     441                                }
     442                                else {
     443                                        pendingOperand = newOperand;
     444                                }
     445                                havePendingOperation = true;
     446                                pendingOperationKind = op;
     447                                lastItemKind = NoItem;
     448                        }
     449                        break;
     450                        case setCloser: {
     451                                if (lastItemKind == NoItem) throw ParseFailure("Set operator has no right operand.");
     452                                if (cc->begin() != cc->end()) subexprs.push_back(cc);
     453                                RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
     454                                if (havePendingOperation) {
     455                                        if (pendingOperationKind == intersectOp) {
     456                                                newOperand = makeIntersect(pendingOperand, newOperand);
     457                                        }
     458                                        else {
     459                                                newOperand = makeDiff(pendingOperand, newOperand);
     460                                        }
     461                                }
     462                                if (negated) return makeComplement(newOperand);
     463                                else return newOperand;
     464                        }
     465                        case setOpener: case posixPropertyOpener: {
     466                                if (lastItemKind != NoItem) {
     467                                        if (cc->begin() != cc->end()) subexprs.push_back(cc);
     468                                        RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
     469                                        subexprs.clear();
     470                                        cc = makeCC();
     471                                        if (havePendingOperation) {
     472                                                if (pendingOperationKind == intersectOp) {
     473                                                        pendingOperand = makeIntersect(pendingOperand, newOperand);
     474                                                }
     475                                                else {
     476                                                        pendingOperand = makeDiff(pendingOperand, newOperand);
     477                                                }
     478                                        }
     479                                        else {
     480                                                pendingOperand = newOperand;
     481                                        }
     482                                        subexprs.push_back(pendingOperand);
     483                                        havePendingOperation = false;
     484                                }
     485                                if (op == setOpener) {
     486                                        subexprs.push_back(parse_charset());
     487                                        lastItemKind = SetItem;
     488                                }
     489                                else if (op == posixPropertyOpener) {
     490                                        bool negated = false;
     491                                        if (*_cursor == '^') {
     492                                                negated = true;
     493                                                _cursor++;
     494                                        }
     495                                        RE * posixSet = parse_property_expression();
     496                                        if (negated) posixSet = makeComplement(posixSet);
     497                                        subexprs.push_back(posixSet);
     498                                        lastItemKind = BrackettedSetItem;
     499                                        if (_cursor == _end || *_cursor++ != ':' || _cursor == _end || *_cursor++ != ']')
     500                                                throw ParseFailure("Posix set expression improperly terminated.");
     501                                }
     502                        }
     503                        break;
     504                        case rangeHyphen:
     505                                if (lastItemKind != CodepointItem) throw ParseFailure("Range operator - has illegal left operand.");
     506                                cc->insert_range(lastCodepointItem, parse_codepoint());
     507                                lastItemKind = RangeItem;
     508                                break;
     509                        case hyphenChar:
     510                                cc->insert('-'); 
     511                                lastItemKind = CodepointItem;
     512                                lastCodepointItem = static_cast<unsigned> ('-');
     513                                break;
     514                        case ampChar:
     515                                cc->insert('&');
     516                                lastItemKind = CodepointItem;
     517                                lastCodepointItem = static_cast<unsigned> ('&');
     518                                break;
     519                        case backSlash:
     520                                throw_incomplete_expression_error_if_end_of_stream();
     521                                if (isSetEscapeChar(*_cursor)) {
     522                                        subexprs.push_back(parse_escaped_set());
     523                                        lastItemKind = SetItem;
     524                                }
     525                                else {
     526                                        lastCodepointItem = parse_escaped_codepoint();
     527                                        cc->insert(lastCodepointItem);
     528                                        lastItemKind = CodepointItem;
     529                                }
     530                                break;
     531                        case emptyOperator:
     532                                lastCodepointItem = parse_utf8_codepoint();
     533                                cc->insert(lastCodepointItem);
     534                                lastItemKind = CodepointItem;
     535                                break;
     536                }
     537        }
     538        throw ParseFailure("Set expression not properly terminated.");
     539}
     540
     541
     542unsigned RE_Parser::parse_codepoint() {
     543    if (_cursor != _end && *_cursor == '\\') {
     544        _cursor++;
     545        return parse_escaped_codepoint();
    409546    }
    410547    else {
    411         literal = parse_utf8_codepoint();
    412         return true;
    413     }
    414     return false;
    415 }
    416 
    417 unsigned RE_Parser::parse_int() {
    418     unsigned value = 0;
    419     for (; _cursor != _end; ++_cursor) {
    420         if (!isdigit(*_cursor)) {
    421             break;
    422         }
    423         value *= 10;
    424         value += static_cast<int>(*_cursor) - 48;
    425     }
    426     return value;
    427 }
    428 
     548        return parse_utf8_codepoint();
     549    }
     550}
    429551
    430552// A backslash escape was found, and various special cases (back reference,
     
    505627                        ++_cursor;
    506628                        return parse_hex_codepoint(8,8);  // ICU compatibility
     629                case 'N':
     630                        ++_cursor;
     631                        throw ParseFailure("\\N{...} character name syntax not yet supported.");
     632
    507633                default:
     634                        // Escaped letters should be reserved for special functions.
    508635                        if (((*_cursor >= 'A') && (*_cursor <= 'Z')) || ((*_cursor >= 'a') && (*_cursor <= 'z')))
    509636                                throw ParseFailure("Undefined or unsupported escape sequence");
  • icGREP/icgrep-devel/icgrep/re/re_parser.h

    r4307 r4309  
    1717
    1818namespace re {
     19       
     20enum CharsetOperatorKind
     21        {intersectOp, setDiffOp, ampChar, hyphenChar, rangeHyphen, posixPropertyOpener, setOpener, setCloser, backSlash, emptyOperator};
     22
    1923
    2024class RE_Parser
     
    5054    unsigned parse_utf8_codepoint();
    5155
    52     Name * parse_unicode_category();
     56    Name * parse_property_expression();
     57       
     58        CharsetOperatorKind getCharsetOperator();
    5359
    5460    RE * parse_charset();
    5561
    56     bool parse_charset_literal(unsigned & literal);
     62    unsigned parse_codepoint();
    5763
    5864    unsigned parse_escaped_codepoint();
Note: See TracChangeset for help on using the changeset viewer.