Ignore:
Timestamp:
Dec 18, 2017, 1:56:51 PM (16 months ago)
Author:
cameron
Message:

RE parser restructuring; parsing symbolic ranges, collation and equivalence exprs

File:
1 edited

Legend:

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

    r5737 r5787  
    66
    77#include <re/re_parser_bre.h>
    8 #include <re/re_parser_helper.h>
    98#include <re/re_alt.h>
    109#include <re/re_any.h>
     
    1615
    1716
    18 namespace re{
     17namespace re {
    1918
    20     // \d and \D Removed
    21     const uint64_t setEscapeCharacters = bit3C('b') | bit3C('p') | bit3C('q') | bit3C('w') | bit3C('s') | bit3C('<') | bit3C('>') |
    22                                          bit3C('B') | bit3C('P') | bit3C('Q') | bit3C('W') | bit3C('S') | bit3C('N') | bit3C('X');
    2319
    24     bool RE_Parser_BRE::isSetEscapeChar(char c) {
    25         return c >= 0x3C && c <= 0x7B && ((setEscapeCharacters >> (c - 0x3C)) & 1) == 1;
     20RE * RE_Parser_BRE::parse_alt() {
     21    std::vector<RE *> alt;
     22    do {
     23        alt.push_back(parse_seq());
    2624    }
     25    while (accept("\\|"));
     26    return makeAlt(alt.begin(), alt.end());
     27}
    2728
    28     inline bool RE_Parser_BRE::isUnsupportChartsetOperator(char c) {
    29         switch (c) {
    30             case '\\':
    31                 return true;
    32             default:
    33                 return false;
     29RE * RE_Parser_BRE::parse_seq() {
     30    std::vector<RE *> seq;
     31    if (!mCursor.more() || at("\\|") || ((mGroupsOpen > 0) && at("\\)"))) return makeSeq();
     32    for (;;) {
     33        RE * re = parse_next_item();
     34        if (re == nullptr) {
     35            break;
    3436        }
     37        re = extend_item(re);
     38        seq.push_back(re);
    3539    }
     40    return makeSeq(seq.begin(), seq.end());
     41}
    3642
    37     RE * RE_Parser_BRE::parse_alt() {
    38         std::vector<RE *> alt;
    39         for (;;) {
    40             alt.push_back(parse_seq());
    4143
    42             if (!isEscapedCharAhead('|')) {
    43                 break;
    44             }
    45             ++mCursor; // advance past the alternation character '\'
    46             ++mCursor; // advance past the alternation character '|'
    47         }
    48         if (alt.empty()) {
    49             ParseFailure("No regular expression found!");
    50         }
    51         return makeAlt(alt.begin(), alt.end());
    52     }
     44RE * RE_Parser_BRE::parse_next_item() {
     45    if (mCursor.noMore() || at('*') || at("\\?") || at("\\{") || at("\\|")) return nullptr;
     46    else if ((mGroupsOpen > 0) && at("\\)")) return nullptr;
     47    else if (accept('^')) return makeStart();
     48    else if (accept('$')) return makeEnd();
     49    else if (accept('.')) return makeAny();
     50    else if (accept("\\(")) return parse_group();
     51    else if (accept('[')) return parse_bracket_expr();
     52    else if (accept('\\')) return parse_escaped();
     53    else return createCC(parse_literal_codepoint());
     54}
    5355
    54     RE * RE_Parser_BRE::parse_next_item() {
    55         RE * re = nullptr;
    56         if (mCursor.more()) {
    57             switch (*mCursor) {
    58                 case '^':
    59                     ++mCursor;
    60                     return makeStart();
    61                 case '$':
    62                     ++mCursor;
    63                     return makeEnd();
    64                 case '*':
    65                     ParseFailure("Need something to repeat before *, \\+, \\? or \\{.");
    66                 case ']':
    67                     if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
    68                         return createCC(parse_utf8_codepoint());
    69                     }
    70                     ParseFailure("Use  \\] for literal ].");
    71                 case '[':
    72                     mCursor++;
    73                     re = parse_charset();
    74                     if ((fModeFlagSet & ModeFlagType::GRAPHEME_CLUSTER_MODE) != 0) {
    75                         re = makeSeq({re, makeZeroWidth("GCB")});
    76                     }
    77                     return re;
    78                 case '.': // the 'any' metacharacter
    79                     mCursor++;
    80                     return makeAny();
    81                 case '\\':  // escape processing
    82                     return parse_escaped();
    83                 default:
    84                     re = createCC(parse_utf8_codepoint());
    85                     if ((fModeFlagSet & ModeFlagType::GRAPHEME_CLUSTER_MODE) != 0) {
    86                         fGraphemeBoundaryPending = true;
    87                     }
    88                     return re;
    89             }
    90         }
    91         return nullptr;
    92     }
     56// A parenthesized group.  Input precondition: the opening ( has been consumed
     57RE * RE_Parser_BRE::parse_group() {
     58    // Capturing paren group.
     59    mGroupsOpen++;
     60    RE * captured = parse_alt();
     61    mCaptureGroupCount++;
     62    std::string captureName = "\\" + std::to_string(mCaptureGroupCount);
     63    Name * const capture  = mMemoizer.memoize(makeCapture(captureName, captured));
     64    auto key = std::make_pair("", captureName);
     65    mNameMap.insert(std::make_pair(std::move(key), capture));
     66    if (!accept("\\)")) ParseFailure("Closing parenthesis required.");
     67    mGroupsOpen--;
     68    return capture;
     69}
    9370
    94     inline RE * RE_Parser_BRE::parse_escaped() {
    95         if (mCursor.remaining() < 2) {
    96             ParseFailure("Redundant \\ in the end");
    97         }
    98         auto nextCursor = mCursor.pos() + 1;
    99         switch (*nextCursor) {
    100             case '(':
    101                 ++mCursor;
    102                 ++mCursor;
    103                 return parse_group();
    104             case '|': case ')':
    105                 return nullptr;
    106             case '}':
    107                 if (fNested) {
    108                     return nullptr;  //  a recursive invocation for a regexp in \N{...}
    109                 } else if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
    110                     ++mCursor;
    111                     return createCC(parse_utf8_codepoint());
    112                 }
    113                 ParseFailure("Use \\} for literal }.");
    114             case '+': case '?': case '{':
    115                 ParseFailure("Need something to repeat before *, \\+, \\? or \\{.");
    116         }
    117 
    118         ++mCursor;
    119         if (isSetEscapeChar(*mCursor)) {
    120             return parseEscapedSet();
    121         }
    122         else if (isdigit(*mCursor)) {
    123             mCursor++;
    124             std::string backref = std::string(mCursor.pos()-2, mCursor.pos());
    125             auto key = std::make_pair("", backref);
    126             auto f = mNameMap.find(key);
    127             if (f != mNameMap.end()) {
    128                 return makeReference(backref, f->second);
    129             }
    130             else {
    131                 ParseFailure("Back reference " + backref + " without prior capture group.");
    132             }
    133         }
    134         else {
    135             return createCC(parse_escaped_codepoint());
    136         }
    137     }
    138 
    139     RE * RE_Parser_BRE::extend_item(RE * re) {
    140         if (LLVM_LIKELY(mCursor.more())) {
    141             if (*mCursor == '*') {
    142                 return RE_Parser::extend_item(re);
    143             } else if (*mCursor == '\\') {
    144                 if (mCursor.remaining() < 2) {
    145                     ParseFailure("Redundant \\ in the end");
    146                 }
    147                 if (isCharAhead('?') || isCharAhead('+')) {
    148                     ++mCursor;
    149                     return RE_Parser::extend_item(re);
    150                 } else if (isCharAhead('{')) {
    151                     ++mCursor;
    152                     auto ret = RE_Parser::extend_item(re);
    153                     ++mCursor;  //Skip '}'
    154                     return ret;
    155                 }
    156             }
    157         }
     71// Extend a RE item with one or more quantifiers
     72RE * RE_Parser_BRE::extend_item(RE * re) {
     73    int lb, ub;
     74    if (accept('*')) {lb = 0; ub = Rep::UNBOUNDED_REP;}
     75    else if (accept("\\?")) {lb = 0; ub = 1;}
     76    else if (accept("\\+")) {lb = 1; ub = Rep::UNBOUNDED_REP;}
     77    else if (accept("\\{")) std::tie(lb, ub) = parse_range_bound();
     78    else {
     79        // No quantifier found.
    15880        return re;
    15981    }
     82    re = makeRep(re, lb, ub);
     83    // The quantified expression may be extended with a further quantifier, e,g., [a-z]\{6,7\}\{2,3\}
     84    return extend_item(re);
     85}
    16086
    161     // Parse some kind of parenthesized group.  Input precondition: mCursor
    162     // after the (
    163     RE * RE_Parser_BRE::parse_group() {
    164         RE * group_expr = nullptr;
    165         // Capturing paren group.
    166         RE * captured = parse_alt();
    167         mCaptureGroupCount++;
    168         std::string captureName = "\\" + std::to_string(mCaptureGroupCount);
    169         Name * const capture  = mMemoizer.memoize(makeCapture(captureName, captured));
    170         auto key = std::make_pair("", captureName);
    171         mNameMap.insert(std::make_pair(std::move(key), capture));
    172         group_expr = capture;
     87std::pair<int, int> RE_Parser_BRE::parse_range_bound() {
     88    int lb, ub;
     89    if (accept(',')) {
     90        lb = 0;
     91        ub = parse_int();
     92    } else {
     93        lb = parse_int();
     94        if (accept("\\}")) return std::make_pair(lb, lb);
     95        if (!accept(',')) ParseFailure("Expecting , or }");
     96        if (accept("\\}")) return std::make_pair(lb, Rep::UNBOUNDED_REP);
     97        ub = parse_int();
     98        if (ub < lb) ParseFailure("Upper bound less than lower bound");
     99    }
     100    if (accept("\\}")) return std::make_pair(lb, ub);
     101    else ParseFailure("Expecting \\}");
     102}
    173103
    174         if (!isEscapedCharAhead(')')) {
    175             ParseFailure("Closing parenthesis required.");
    176         }
    177         ++mCursor;
    178         ++mCursor;
    179         return group_expr;
    180     }
     104}
    181105
    182     inline bool RE_Parser_BRE::isEscapedCharAhead(char c) {
    183         if (*mCursor != '\\') {
    184             return false;
    185         }
    186         if (mCursor.remaining() < 2) {
    187             ParseFailure("Redundant \\ in the end");
    188         }
    189         return isCharAhead(c);
    190     }
    191 
    192     inline std::pair<int, int> RE_Parser_BRE::parse_range_bound() {
    193         int lower_bound = 0, upper_bound = 0;
    194         if (*++mCursor != ',') {
    195             lower_bound = parse_int();
    196         }
    197 
    198         if (isEscapedCharAhead('}')) {
    199             upper_bound = lower_bound;
    200         } else if (*mCursor != ',') {
    201             ParseFailure("Bad lower bound!");
    202         } else if (++mCursor, isEscapedCharAhead('}')) {
    203             upper_bound = Rep::UNBOUNDED_REP;
    204         } else {
    205             upper_bound = parse_int();
    206             if (!isEscapedCharAhead('}')) {
    207                 ParseFailure("Bad upper bound!");
    208             }
    209         }
    210         return std::make_pair(lower_bound, upper_bound);
    211     }
    212 
    213     // A backslash escape was found, and various special cases (back reference,
    214     // quoting with \Q, \E, sets (\p, \P, \d, \D, \w, \W, \s, \S, \b, \B), grapheme
    215     // cluster \X have been ruled out.
    216     // It may be one of several possibilities or an error sequence.
    217     // 1. Special control codes (\a, \e, \f, \n, \r, \t, \v)
    218     // 2. General control codes c[@-_a-z?]
    219     // 3. Restricted octal notation 0 - 0777
    220     // 4. General octal notation o\{[0-7]+\}
    221     // 5. General hex notation x\{[0-9A-Fa-f]+\}
    222     // 6. An error for any unrecognized alphabetic escape
    223     // 7. An escaped ASCII symbol, standing for itself
    224 
    225     codepoint_t RE_Parser_BRE::parse_escaped_codepoint() {
    226         codepoint_t cp_value;
    227         switch (*mCursor) {
    228             case 'o':
    229                 ++mCursor;
    230                 if (isEscapedCharAhead('{')) {
    231                     ++mCursor;
    232                     ++mCursor;
    233                     cp_value = parse_octal_codepoint(1, 7);
    234                     if (!isEscapedCharAhead('}')) ParseFailure("Malformed octal escape sequence");
    235                     ++mCursor;
    236                     ++mCursor;
    237                     return cp_value;
    238                 }
    239                 else {
    240                     ParseFailure("Malformed octal escape sequence");
    241                 }
    242             case 'x':
    243                 ++mCursor;
    244                 if (isEscapedCharAhead('{')) {
    245                     ++mCursor;
    246                     ++mCursor;
    247                     cp_value = parse_hex_codepoint(1, 6);
    248                     if (!isEscapedCharAhead('}')) ParseFailure("Malformed hex escape sequence");
    249                     ++mCursor;
    250                     ++mCursor;
    251                     return cp_value;
    252                 }
    253                 else {
    254                     return parse_hex_codepoint(1,2);  // ICU compatibility
    255                 }
    256             case 'u':
    257                 ++mCursor;
    258                 if (isEscapedCharAhead('{')) {
    259                     ++mCursor;
    260                     ++mCursor;
    261                     cp_value = parse_hex_codepoint(1, 6);
    262                     if (!isEscapedCharAhead('}')) ParseFailure("Malformed hex escape sequence");
    263                     ++mCursor;
    264                     ++mCursor;
    265                     return cp_value;
    266                 }
    267                 else {
    268                     return parse_hex_codepoint(4,4);  // ICU compatibility
    269                 }
    270             default:
    271                 return RE_Parser::parse_escaped_codepoint();
    272         }
    273     }
    274 
    275     RE * RE_Parser_BRE::parsePropertyExpression() {
    276         const auto start = mCursor.pos();
    277         while (mCursor.more()) {
    278             bool done = false;
    279             if (isEscapedCharAhead('}')) {
    280                 done = true;
    281             } else {
    282                 switch (*mCursor) {
    283                     case ':': case '=':
    284                         done = true;
    285                 }
    286             }
    287             if (done) {
    288                 break;
    289             }
    290             ++mCursor;
    291         }
    292         return createName(canonicalize(start, mCursor.pos()));
    293     }
    294 
    295     RE * RE_Parser_BRE::parseEscapedSet() {
    296         bool complemented = false;
    297         RE * re = nullptr;
    298         switch (*mCursor) {
    299             case 'b':
    300                 ++mCursor;
    301                 if (!isEscapedCharAhead('{')) {
    302                     return complemented ? makeWordNonBoundary() : makeWordBoundary();
    303                 } else {
    304                     ++mCursor;
    305                     switch (*++mCursor) {
    306                         case 'g':
    307                             re = complemented ? makeZeroWidth("NonGCB") : makeZeroWidth("GCB");
    308                             break;
    309                         case 'w': ParseFailure("\\b{w} not yet supported.");
    310                         case 'l': ParseFailure("\\b{l} not yet supported.");
    311                         case 's': ParseFailure("\\b{s} not yet supported.");
    312                         default: ParseFailure("Unrecognized boundary assertion");
    313                     }
    314                     ++mCursor;
    315                     if (!isEscapedCharAhead('}')) {
    316                         ParseFailure("Malformed boundary assertion");
    317                     }
    318                     ++mCursor;
    319                     ++mCursor;
    320                     return re;
    321                 }
    322             case 'q':
    323                 ++mCursor;
    324                 if (!isEscapedCharAhead('{')) {
    325                     ParseFailure("Malformed grapheme-boundary property expression");
    326                 }
    327                 ++mCursor;
    328                 ++mCursor;
    329                 ParseFailure("Literal grapheme cluster expressions not yet supported.");
    330                 if (!isEscapedCharAhead('}')) {
    331                     ParseFailure("Malformed grapheme-boundary property expression");
    332                 }
    333                 ++mCursor;
    334                 ++mCursor;
    335                 return complemented ? makeComplement(re) : re;
    336             case 'p':
    337                 ++mCursor;
    338                 if (!isEscapedCharAhead('{')) {
    339                     ParseFailure("Malformed property expression");
    340                 }
    341                 ++mCursor;
    342                 ++mCursor;
    343                 re = parsePropertyExpression();
    344                 if (!isEscapedCharAhead('}')) {
    345                     ParseFailure("Malformed property expression");
    346                 }
    347                 ++mCursor;
    348                 ++mCursor;
    349                 return complemented ? makeComplement(re) : re;
    350             case 'N':
    351                 ++mCursor;
    352                 if (!isEscapedCharAhead('{')) {
    353                     ParseFailure("Malformed \\N expression");
    354                 }
    355                 ++mCursor;
    356                 ++mCursor;
    357                 re = parseNamePatternExpression();
    358                 if (!isEscapedCharAhead('}')) {
    359                     ParseFailure("Malformed \\N expression");
    360                 }
    361                 ++mCursor;
    362                 ++mCursor;
    363                 assert (re);
    364                 return re;
    365             default:
    366                 return RE_Parser::parseEscapedSet();
    367         }
    368     }
    369 }
Note: See TracChangeset for help on using the changeset viewer.