Changeset 5787


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

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

Location:
icGREP/icgrep-devel/icgrep
Files:
17 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/UCD/resolve_properties.cpp

    r5786 r5787  
    110110            property->setDefinition(makeDiff(makeAny(), unassigned));
    111111            return true;
    112         } else if (value == "GCB" || value == "NonGCB") {
     112        } else if (value == "\\b{g}" || value == "\\B{g}") {
    113113            generateGraphemeClusterBoundaryRule(property);
    114114            return true;
  • icGREP/icgrep-devel/icgrep/grep_engine.cpp

    r5784 r5787  
    123123
    124124    for(unsigned i = 0; i < n; ++i){
     125#define USE_MULTIPLEX_CC
     126#ifdef USE_MULTIPLEX_CC
    125127        std::tie<re::RE*, std::vector<re::CC *>>(REs[i], charclasses[i]) = multiplexing_passes(REs[i]);
    126128        const auto numOfCharacterClasses = charclasses[i].size();
     
    131133        kernel::Kernel * icgrepK = mGrepDriver->addKernelInstance<kernel::ICGrepKernel>(idb, REs[i], numOfCharacterClasses);
    132134        mGrepDriver->makeKernelCall(icgrepK, {CharClasses, LineBreakStream, CRLFStream, RequiredStreams}, {MatchResults});
     135#else
     136        REs[i] = regular_expression_passes(REs[i]);
     137        StreamSetBuffer * MatchResults = mGrepDriver->addBuffer<CircularBuffer>(idb, idb->getStreamSetTy(1, 1), segmentSize * bufferSegments);
     138        kernel::Kernel * icgrepK = mGrepDriver->addKernelInstance<kernel::ICGrepKernel>(idb, REs[i]);
     139        mGrepDriver->makeKernelCall(icgrepK, {BasisBits, LineBreakStream, CRLFStream, RequiredStreams}, {MatchResults});
     140#endif
    133141        MatchResultsBufs[i] = MatchResults;
    134142    }
  • icGREP/icgrep-devel/icgrep/kernels/charclasses.cpp

    r5786 r5787  
    7979    std::vector<Name *> names;
    8080    for (unsigned i = 0; i < n; i++) {
    81         Name * name = re::makeName("cc" + std::to_string(i), mCCs[i]);
     81        Name * name = re::makeName("mpx_basis" + std::to_string(i), mCCs[i]);
    8282        nameMap.emplace(name, nullptr);
    8383        names.push_back(name);
  • icGREP/icgrep-devel/icgrep/re/grapheme_clusters.cpp

    r5772 r5787  
    3838        if (n->getType() == Name::Type::ZeroWidth) {
    3939            const std::string nameString = n->getName();
    40             return (nameString == "GCB") || (nameString == "nonGCB");
     40            return (nameString == "\\b{g}") || (nameString == "\\B{g}");
    4141        }
    42         return hasGraphemeClusterBoundary(n->getDefinition());
     42        return false;
    4343    } else if (const Alt * alt = dyn_cast<Alt>(re)) {
    4444        for (const RE * re : *alt) {
     
    7171    if (isa<Name>(re)) {
    7272        if (inGraphemeMode && (cast<Name>(re)->getName() == "."))
    73             return makeSeq({makeAny(), makeRep(makeSeq({makeZeroWidth("NonGCB"), makeAny()}), 0, Rep::UNBOUNDED_REP), makeZeroWidth("GCB")});
     73            return makeSeq({makeAny(), makeRep(makeSeq({makeZeroWidth("\\B{g}"), makeAny()}), 0, Rep::UNBOUNDED_REP), makeZeroWidth("\\b{g}")});
    7474        else return re;
    7575    }
    7676    else if (isa<CC>(re)) {
    77         if (inGraphemeMode) return makeSeq({re, makeZeroWidth("GCB")});
     77        if (inGraphemeMode) return makeSeq({re, makeZeroWidth("\\b{g}")});
    7878        else return re;
    7979    }
     
    8484            bool atSingleChar = isa<CC>(re) && (cast<CC>(re)->count() == 1);
    8585            if (afterSingleChar && inGraphemeMode && !atSingleChar)
    86                 list.push_back(makeZeroWidth("GCB"));
     86                list.push_back(makeZeroWidth("\\b{g}"));
    8787            if (isa<CC>(re)) list.push_back(*i);
    8888            else {
     
    9191            afterSingleChar = atSingleChar;
    9292        }
    93         if (afterSingleChar && inGraphemeMode) list.push_back(makeZeroWidth("GCB"));
     93        if (afterSingleChar && inGraphemeMode) list.push_back(makeZeroWidth("\\b{g}"));
    9494        return makeSeq(list.begin(), list.end());
    9595    } else if (Group * g = dyn_cast<Group>(re)) {
  • icGREP/icgrep-devel/icgrep/re/parse_fixed_strings.cpp

    r5754 r5787  
    1212namespace re {
    1313
    14 bool FixedStringParser::accept_alt_mark() {
    15     if (!mCursor.more() || (*mCursor != '\n')) return false;
    16     mCursor++;
    17     return true;
     14RE * FixedStringParser::parse_alt() {
     15    std::vector<RE *> alt;
     16    do {
     17        alt.push_back(parse_seq());
     18    }
     19    while (accept('\n'));
     20    return makeAlt(alt.begin(), alt.end());
    1821}
    1922
    2023RE * FixedStringParser::parse_seq() {
    2124    std::vector<RE *> seq;
    22     while (mCursor.more() && (*mCursor != '\n')) {
     25    while (mCursor.more() && (!at('\n'))) {
    2326        seq.push_back(createCC(parse_literal_codepoint()));
    2427    }
  • icGREP/icgrep-devel/icgrep/re/parse_fixed_strings.h

    r5754 r5787  
    1515            mReSyntax = RE_Syntax::FixedStrings;
    1616        }
    17         bool accept_alt_mark () override;
     17        RE * parse_alt () override;
    1818        RE * parse_seq () override;
    1919    };
  • icGREP/icgrep-devel/icgrep/re/re_compiler.cpp

    r5786 r5787  
    108108        AlignMarkers(marker, zero, pb);
    109109        PabloAST * ze = markerVar(zero);
    110         if (nameString == "NonGCB") {
     110        if (nameString == "\\B{g}") {
    111111            ze = pb.createNot(ze);
    112112        }
  • icGREP/icgrep-devel/icgrep/re/re_multiplex.cpp

    r5784 r5787  
    88#include <re/re_intersect.h>
    99#include <re/re_assertion.h>
     10#include <re/re_group.h>
    1011#include <re/re_analysis.h>
    1112#include <re/re_memoizer.hpp>
     
    7879            ix->setLH(multiplex(ix->getLH()));
    7980            ix->setRH(multiplex(ix->getRH()));
     81        } else if (Group * g = dyn_cast<Group>(re)) {
     82            g->setRE(multiplex(g->getRE()));
    8083        }
    8184        return re;
  • icGREP/icgrep-devel/icgrep/re/re_name_gather.cpp

    r5763 r5787  
    99#include <re/re_intersect.h>
    1010#include <re/re_assertion.h>
     11#include <re/re_group.h>
    1112#include <re/re_analysis.h>
    1213#include <re/re_memoizer.hpp>
     
    5960            gather(cast<Intersect>(re)->getLH());
    6061            gather(cast<Intersect>(re)->getRH());
     62        } else if (isa<Group>(re)) {
     63            gather(cast<Group>(re)->getRE());
    6164        }
    6265    }
    63 
    6466    NameGather(NameMap & nameMap, Name *& zeroWidth)
    6567    : mZeroWidth(zeroWidth)
  • icGREP/icgrep-devel/icgrep/re/re_parser.cpp

    r5786 r5787  
    6363    parser->mGroupsOpen = 0;
    6464    parser->fNested = false;
    65     parser->fGraphemeBoundaryPending = false;
    6665    parser->mCaptureGroupCount = 0;
    6766    RE * re = parser->parse_RE();
     
    7776, fNested(false)
    7877, mGroupsOpen(0)
    79 , fGraphemeBoundaryPending(false)
    8078, fSupportNonCaptureGroup(false)
    8179, mCursor(regular_expression)
     
    105103        alt.push_back(parse_seq());
    106104    }
    107     while (accept_alt_mark());
     105    while (accept('|'));
    108106    return makeAlt(alt.begin(), alt.end());
    109107}
    110108   
    111 bool RE_Parser::accept_alt_mark() {
    112     if (!mCursor.more() || (*mCursor != '|')) return false;
    113     mCursor++;
    114     return true;
    115 }
    116 
    117109RE * RE_Parser::parse_seq() {
    118110    std::vector<RE *> seq;
     
    129121}
    130122
     123RE * createStart(ModeFlagSet flags) {
     124    if ((flags && ModeFlagType::MULTILINE_MODE_FLAG) == 0) return makeZeroWidth("^s");  //single-line mode
     125    if ((flags & ModeFlagType::UNIX_LINES_MODE_FLAG) != 0) {
     126        return makeNegativeLookBehindAssertion(makeByte(makeCC(makeCC(0, '\n'-1), makeCC('\n'+1, 0xFF))));
     127    }
     128    return makeStart();
     129}
     130RE * createEnd(ModeFlagSet flags) {
     131    if ((flags && ModeFlagType::MULTILINE_MODE_FLAG) == 0) return makeZeroWidth("$s");  //single-line mode
     132    if ((flags & ModeFlagType::UNIX_LINES_MODE_FLAG) != 0) {
     133        return makeNegativeLookAheadAssertion(makeByte(makeCC(makeCC(0, '\n'-1), makeCC('\n'+1, 0xFF))));
     134    }
     135    return makeEnd();
     136}
     137RE * createAny(ModeFlagSet flags) {
     138    return makeAny();
     139}
     140   
     141   
    131142RE * RE_Parser::parse_next_item() {
    132     RE * re = nullptr;
    133     if (fModeFlagSet & IGNORE_SPACE_MODE_FLAG) {
    134         while (mCursor.more() && *mCursor == ' ') {
    135             ++mCursor;
    136         }
    137     }
    138     if (mCursor.more()) {
    139         switch (*mCursor) {
    140             case '(':
    141                 ++mCursor;
    142                 return parse_group();
    143             case '^':
    144                 ++mCursor;
    145                 if ((fModeFlagSet & ModeFlagType::MULTILINE_MODE_FLAG) == 0) {
    146                     return makeZeroWidth("^s");  //single-line mode
    147                 }
    148                 if ((fModeFlagSet & ModeFlagType::UNIX_LINES_MODE_FLAG) != 0) {
    149                     return makeNegativeLookBehindAssertion(makeByte(makeCC(makeCC(0, '\n'-1), makeCC('\n'+1, 0xFF))));
    150                 }
    151                 return makeStart();
    152             case '$':
    153                 ++mCursor;
    154                 if ((fModeFlagSet & ModeFlagType::MULTILINE_MODE_FLAG) == 0) {
    155                     return makeZeroWidth("$s");  //single-line mode
    156                 }
    157                 if ((fModeFlagSet & ModeFlagType::UNIX_LINES_MODE_FLAG) != 0) {
    158                     return makeLookAheadAssertion(makeCC('\n'));
    159                 }
    160                 return makeEnd();
    161             case '|':
    162                 break;
    163             case ')':
    164                 if (mGroupsOpen > 0) break;
    165                 if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
    166                     return createCC(parse_literal_codepoint());
    167                 }
    168                 ParseFailure("Use  \\) for literal ).");
    169             case '*': case '+': case '?': case '{':
    170                 ParseFailure("Need something to repeat before *, +, ? or {.");
    171             case ']':
    172                 if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
    173                     return createCC(parse_literal_codepoint());
    174                 }
    175                 ParseFailure("Use  \\] for literal ].");
    176             case '}':
    177                 if (fNested) {
    178                     break;  //  a recursive invocation for a regexp in \N{...}
    179                 } else if (LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
    180                     return createCC(parse_literal_codepoint());
    181                 }
    182                 ParseFailure("Use \\} for literal }.");
    183             case '[':
    184                 mCursor++;
    185                 re = parse_charset();
    186                 break;
    187             case '.': // the 'any' metacharacter
    188                 mCursor++;
    189                 return makeAny();
    190             case '\\':  // escape processing
    191                 ++mCursor;
    192                 return parse_escaped();
    193             default:
    194                 re = createCC(parse_literal_codepoint());
    195         }
    196     }
    197     return re;
    198 }
    199 
     143    if (mCursor.noMore() || atany("*?+{|")) return nullptr;
     144    else if (((mGroupsOpen > 0) && at(')')) || (fNested && at('}'))) return nullptr;
     145    else if (accept('^')) return createStart(fModeFlagSet);
     146    else if (accept('$')) return createEnd(fModeFlagSet);
     147    else if (accept('.')) return createAny(fModeFlagSet);
     148    else if (accept('(')) return parse_group();
     149    else if (accept('[')) return parse_extended_bracket_expression();
     150    else if (accept('\\')) return parse_escaped();
     151    else return createCC(parse_literal_codepoint());
     152}
     153                                                         
    200154
    201155// Parse some kind of parenthesized group.  Input precondition: mCursor
     
    325279// Extend a RE item with one or more quantifiers
    326280RE * RE_Parser::extend_item(RE * re) {
    327     if (LLVM_UNLIKELY(!(mCursor.more()))) return re;
    328     int lb = 0, ub = 0;
    329     switch (*mCursor) {
    330         case '*':
    331             lb = 0;
    332             ub = Rep::UNBOUNDED_REP;
    333             break;
    334         case '?':
    335             lb = 0;
    336             ub = 1;
    337             break;
    338         case '+':
    339             lb = 1;
    340             ub = Rep::UNBOUNDED_REP;
    341             break;
    342         case '{':
    343             std::tie(lb, ub) = parse_range_bound();
    344             if ((ub != Rep::UNBOUNDED_REP) && (lb > ub)) {
    345                 ParseFailure("Lower bound cannot exceed upper bound in bounded repetition");
    346             }
    347             break;
    348         default:
    349             // No quantifiers
    350             return re;
    351     }
    352     ++mCursor;
    353     if (ENABLE_EXTENDED_QUANTIFIERS) {
    354         if (LLVM_UNLIKELY(!(mCursor.more()))) return makeRep(re, lb, ub);;
    355         if (*mCursor == '?') { // Non-greedy qualifier
    356             // Greedy vs. non-greedy makes no difference for icgrep.
    357             ++mCursor;
    358             re = makeRep(re, lb, ub);
    359         } else if (*mCursor == '+') {
    360             ++mCursor;
    361             if (ub == Rep::UNBOUNDED_REP) {
    362                 re = makeSeq({makeRep(re, lb, ub), makeNegativeLookAheadAssertion(re)});
    363             } else if (lb == ub) {
    364                 re = makeRep(re, ub, ub);
    365             } else /* if (lb < ub) */{
    366                 re = makeAlt({makeSeq({makeRep(re, lb, ub-1), makeNegativeLookAheadAssertion(re)}), makeRep(re, ub, ub)});
    367             }
    368         } else {
    369             re = makeRep(re, lb, ub);
    370         }
     281    int lb, ub;
     282    if (accept('*')) {lb = 0; ub = Rep::UNBOUNDED_REP;}
     283    else if (accept('?')) {lb = 0; ub = 1;}
     284    else if (accept('+')) {lb = 1; ub = Rep::UNBOUNDED_REP;}
     285    else if (accept('{')) std::tie(lb, ub) = parse_range_bound();
     286    else {
     287        // No quantifier found.
     288        return re;
     289    }
     290    if (ENABLE_EXTENDED_QUANTIFIERS && accept('?')) {
     291        // Non-greedy qualifier: no difference for Parabix RE matching
     292        re = makeRep(re, lb, ub);
     293    } else if (ENABLE_EXTENDED_QUANTIFIERS && accept('+')) {
     294        // Possessive qualifier
     295        if (ub == Rep::UNBOUNDED_REP) {
     296            re = makeSeq({makeRep(re, lb, ub), makeNegativeLookAheadAssertion(re)});
     297        } else if (lb == ub) {
     298            re = makeRep(re, ub, ub);
     299        } else /* if (lb < ub) */{
     300            re = makeAlt({makeSeq({makeRep(re, lb, ub-1), makeNegativeLookAheadAssertion(re)}), makeRep(re, ub, ub)});
     301        }
    371302    } else {
    372303        re = makeRep(re, lb, ub);
     
    377308
    378309std::pair<int, int> RE_Parser::parse_range_bound() {
    379     int lower_bound = 0, upper_bound = 0;
    380     if (*++mCursor != ',') {
    381         lower_bound = parse_int();
    382     }
    383     if (*mCursor == '}') {
    384         upper_bound = lower_bound;
    385     } else if (*mCursor != ',') {
    386         ParseFailure("Bad lower bound!");
    387     } else if (*++mCursor == '}') {
    388         upper_bound = Rep::UNBOUNDED_REP;
     310    int lb, ub;
     311    if (accept(',')) {
     312        lb = 0;
     313        ub = parse_int();
    389314    } else {
    390         upper_bound = parse_int();
    391         if (*mCursor != '}') {
    392             ParseFailure("Bad upper bound!");
    393         }
    394     }
    395     return std::make_pair(lower_bound, upper_bound);
     315        lb = parse_int();
     316        if (accept('}')) return std::make_pair(lb, lb);
     317        if (!accept(',')) ParseFailure("Expecting , or }");
     318        if (accept('}')) return std::make_pair(lb, Rep::UNBOUNDED_REP);
     319        ub = parse_int();
     320        if (ub < lb) ParseFailure("Upper bound less than lower bound");
     321    }
     322    if (accept('}')) return std::make_pair(lb, ub);
     323    else ParseFailure("Expecting }");
    396324}
    397325
     
    456384                    switch (*mCursor) {
    457385                        case 'g':
    458                             re = complemented ? makeZeroWidth("NonGCB") : makeZeroWidth("GCB");
     386                            re = complemented ? makeZeroWidth("\\B{g}") : makeZeroWidth("\\b{g}");
    459387                            ++mCursor;
    460388                            ++mCursor;
     
    523451            // to get to the next extended grapheme cluster boundary.
    524452            ++mCursor;
    525             return makeSeq({makeAny(), makeRep(makeSeq({makeZeroWidth("NonGCB"), makeAny()}), 0, Rep::UNBOUNDED_REP), makeZeroWidth("GCB")});
     453            return makeSeq({makeAny(), makeRep(makeSeq({makeZeroWidth("\\B{g}"), makeAny()}), 0, Rep::UNBOUNDED_REP), makeZeroWidth("\\b{g}")});
    526454        case 'N':
    527             if (*++mCursor != '{') {
    528                 ParseFailure("Malformed \\N expression");
    529             }
    530455            ++mCursor;
    531456            re = parseNamePatternExpression();
    532             if (*mCursor != '}') {
    533                 ParseFailure("Malformed \\N expression");
    534             }
    535             ++mCursor;
    536457            assert (re);
    537458            return re;
     
    705626Name * RE_Parser::parseNamePatternExpression(){
    706627
     628    if (!accept('{')) ParseFailure("Expecting { after \\N");
    707629    const auto start = mCursor.pos();
    708630    while (mCursor.more()) {
     
    719641    }
    720642    std::string nameRegexp = "/(?i)" + std::string(start, mCursor.pos());
     643    if (!accept('}')) ParseFailure("Expecting } after \\N{...");
    721644    return createName("na", nameRegexp);
    722645}
    723646
    724 bool RE_Parser::isUnsupportChartsetOperator(char c) {
    725     return false;
    726 }
    727 
    728 CharsetOperatorKind RE_Parser::getCharsetOperator() {
    729     if (isUnsupportChartsetOperator(*mCursor)) {
    730         return emptyOperator;
    731     }
    732     switch (*mCursor) {
    733         case '&':
    734             ++mCursor;
    735             if (*mCursor == '&') {
    736                 ++mCursor;
    737                 return intersectOp;
    738             } else if (*mCursor == '[') {
    739                 // Short-hand for intersectOp when a set follows
    740                 return intersectOp;
    741             }
    742             return ampChar;
    743         case '-':
    744             ++mCursor;
    745             if (*mCursor == '-') {
    746                 ++mCursor;
    747                 return setDiffOp;
    748             } else if (*mCursor == '[') {
    749                 return setDiffOp;
    750             } else if (*mCursor == ']') {
    751                 return hyphenChar;
    752             }
    753             return rangeHyphen;
    754         case '[':
    755             ++mCursor;
    756             if (*mCursor == ':') {
    757                 ++mCursor;
    758                 return posixPropertyOpener;
    759             }
    760             return setOpener;
    761         case ']':
    762             ++mCursor;
    763             return setCloser;
    764         case '\\':
    765             ++mCursor;
    766             return backSlash;
    767         default:
    768             return emptyOperator;
    769     }
    770 }
    771 
    772 // Precondition: cursor is immediately after opening '[' character
    773 RE * RE_Parser::parse_charset() {
    774     // Sets are accumulated using two variables:
    775     // subexprs accumulates set expressions such as \p{Lu}, [\w && \p{Greek}]
    776     // cc accumulates the literal and calculated codepoints and ranges
    777     std::vector<RE *> subexprs;
    778     CC * cc = makeCC();
    779     // When the last item deal with is a single literal charcacter or calculated codepoint,
    780     // a following hyphen can indicate a range.   When the last item is a set subexpression,
    781     // a following hyphen can indicate set subtraction.
    782     enum {NoItem, CodepointItem, RangeItem, SetItem, BrackettedSetItem} lastItemKind = NoItem;
    783 
    784     codepoint_t lastCodepointItem = 0;
    785     bool havePendingOperation = false;
    786     bool possibleByteCodeEscape = false;  // set to true when \x, \o or \0 hex or octal escapes seen.
    787     CharsetOperatorKind pendingOperationKind = intersectOp;
    788     RE * pendingOperand = nullptr;
    789 
    790     // If the first character after the [ is a ^ (caret) then the matching character class is complemented.
    791     bool negated = false;
    792     if (*mCursor == '^') {
    793         negated = true;
     647
     648// Parse a bracketted expression with possible && (intersection) or
     649// -- (set difference) operators.
     650// Initially, the opening bracket has been consumed.
     651RE * RE_Parser::parse_extended_bracket_expression () {
     652    bool negated = accept('^');
     653    RE * t1 = parse_bracketed_items();
     654    bool have_new_expr = true;
     655    while (have_new_expr) {
     656        if (accept("&&")) {
     657            RE * t2 = parse_bracketed_items();
     658            t1 = makeIntersect(t1, t2);
     659        } else if (accept("--")) {
     660            RE * t2 = parse_bracketed_items();
     661            t1 = makeDiff(t1, t2);
     662        }
     663        else have_new_expr = false;
     664    }
     665    if (!accept(']')) ParseFailure("Expecting ]");
     666    if (negated) return makeComplement(t1);
     667    else return t1;
     668}
     669
     670// Parsing items within a bracket expression.
     671// Items represent individual characters or sets of characters.
     672// Ranges may be formed by individual character items separated by '-'.
     673RE * RE_Parser::parse_bracketed_items () {
     674    std::vector<RE *> items;
     675    do {
     676        if (accept('[')) {
     677            if (accept('=')) items.push_back(parse_equivalence_class());
     678            else if (accept('.')) items.push_back(range_extend(parse_collation_element()));
     679            else if (accept(':')) items.push_back(parse_Posix_class());
     680            else items.push_back(parse_extended_bracket_expression());
     681        } else if (accept('\\')) {
     682            if (at('N') || !isSetEscapeChar(*mCursor)) items.push_back(range_extend(parse_escaped_char_item()));
     683            else items.push_back(parseEscapedSet());
     684        } else {
     685            items.push_back(range_extend(makeCC(parse_literal_codepoint())));
     686        }
     687    } while (mCursor.more() && !at(']') && !at("&&") && (!at("--") || at("--]")));
     688    return makeAlt(items.begin(), items.end());
     689}
     690
     691//  Given an individual character expression, check for and parse
     692//  a range extension if one exists, or return the individual expression.
     693RE * RE_Parser::range_extend(RE * char_expr1) {
     694    // A range extension is signalled by a hyphen '-', except for special cases:
     695    // (a) if the following character is "]" the hyphen is a literal set character.
     696    // (b) if the following character is "-" the hyphen is part of a set subtract
     697    // operator, unless it the set is immediately closed by "--]".
     698    if (!at('-') || at("-]") || (at("--") && !at("--]"))) return char_expr1;
     699    accept('-');
     700    RE * char_expr2 = nullptr;
     701    if (accept('\\')) char_expr2 = parse_escaped_char_item();
     702    else if (accept('[')) {
     703        if (accept('.')) char_expr2 = parse_collation_element();
     704        else ParseFailure("Error in range expression");
     705    } else {
     706        char_expr2 = makeCC(parse_literal_codepoint());
     707    }
     708    return makeRange(char_expr1, char_expr2);
     709}
     710
     711RE * RE_Parser::parse_equivalence_class() {
     712    const auto start = mCursor.pos() - 1;
     713    while (mCursor.more() && !at('=')) {
    794714        ++mCursor;
    795715    }
    796     // Legacy rule: an unescaped ] may appear as a literal set character
    797     // if and only if it appears immediately after the opening [ or [^
    798     if ( *mCursor == ']' && LEGACY_UNESCAPED_RBRAK_RBRACE_ALLOWED) {
    799         insert(cc, ']');
    800         lastItemKind = CodepointItem;
    801         lastCodepointItem = static_cast<codepoint_t> (']');
     716    std::string name = std::string(start, mCursor.pos());
     717    if (!accept("=]")) ParseFailure("Posix equivalence class improperly terminated.");
     718    return createName(name);
     719}
     720RE * RE_Parser::parse_collation_element() {
     721    const auto start = mCursor.pos() - 1;
     722    while (mCursor.more() && !at('.')) {
    802723        ++mCursor;
    803     } else if ( *mCursor == '-' && LEGACY_UNESCAPED_HYPHEN_ALLOWED) {
    804         ++mCursor;
    805         insert(cc, '-');
    806         lastItemKind = CodepointItem;
    807         lastCodepointItem = static_cast<codepoint_t> ('-');
    808         if (*mCursor == '-') {
    809             ParseFailure("Set operator has no left operand.");
    810         }
    811     }
    812     while (mCursor.more()) {
    813         const CharsetOperatorKind op = getCharsetOperator();
    814         switch (op) {
    815             case intersectOp:
    816             case setDiffOp: {
    817                 if (lastItemKind == NoItem) {
    818                     ParseFailure("Set operator has no left operand.");
    819                 }
    820                 if (!cc->empty()) {
    821                     subexprs.push_back(mMemoizer.memoize(cc));
    822                 }
    823                 RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
    824                 subexprs.clear();
    825                 cc = makeCC();
    826                 if (havePendingOperation) {
    827                     if (pendingOperationKind == intersectOp) {
    828                         pendingOperand = makeIntersect(pendingOperand, newOperand);
    829                     }
    830                     else {
    831                         pendingOperand = makeDiff(pendingOperand, newOperand);
    832                     }
    833                 }
    834                 else {
    835                     pendingOperand = newOperand;
    836                 }
    837                 havePendingOperation = true;
    838                 pendingOperationKind = op;
    839                 lastItemKind = NoItem;
    840             }
    841             break;
    842             case setCloser: {
    843                 if (lastItemKind == NoItem) {
    844                     ParseFailure("Set operator has no right operand.");
    845                 }
    846                 if (!cc->empty()) {
    847                     if (possibleByteCodeEscape && (cc->max_codepoint() <= 0xFF) && subexprs.empty() && !havePendingOperation) {
    848                         subexprs.push_back(makeByte(cc));
    849                     }
    850                     else {
    851                         subexprs.push_back(mMemoizer.memoize(cc));
    852                     }
    853                 }
    854                 RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
    855                 if (havePendingOperation) {
    856                     if (pendingOperationKind == intersectOp) {
    857                         newOperand = makeIntersect(pendingOperand, newOperand);
    858                     }
    859                     else {
    860                         newOperand = makeDiff(pendingOperand, newOperand);
    861                     }
    862                 }
    863                 return negated ? makeComplement(newOperand) : newOperand;
    864             }
    865             case setOpener:
    866             case posixPropertyOpener: {
    867                 if (lastItemKind != NoItem) {
    868                     if (!cc->empty()) {
    869                         subexprs.push_back(mMemoizer.memoize(cc));
    870                     }
    871                     RE * newOperand = makeAlt(subexprs.begin(), subexprs.end());
    872                     subexprs.clear();
    873                     cc = makeCC();
    874                     if (havePendingOperation) {
    875                         if (pendingOperationKind == intersectOp) {
    876                             pendingOperand = makeIntersect(pendingOperand, newOperand);
    877                         } else {
    878                             pendingOperand = makeDiff(pendingOperand, newOperand);
    879                         }
    880                     }
    881                     else {
    882                         pendingOperand = newOperand;
    883                     }
    884                     subexprs.push_back(pendingOperand);
    885                     havePendingOperation = false;
    886                 }
    887                 if (op == setOpener) {
    888                     subexprs.push_back(parse_charset());
    889                     lastItemKind = SetItem;
    890                 }
    891                 else if (op == posixPropertyOpener) {
    892                     bool negated = false;
    893                     if (*mCursor == '^') {
    894                         negated = true;
    895                         mCursor++;
    896                     }
    897                     RE * posixSet = parsePropertyExpression();
    898                     subexprs.push_back(negated ? makeComplement(posixSet) : posixSet);
    899                     lastItemKind = BrackettedSetItem;
    900                     if (*mCursor++ != ':' || *mCursor++ != ']')
    901                         ParseFailure("Posix set expression improperly terminated.");
    902                 }
    903             }
    904             break;
    905             case rangeHyphen:
    906                 if (lastItemKind != CodepointItem) {
    907                     ParseFailure("Range operator - has illegal left operand.");
    908                 }
    909                 if (*mCursor == '\\') {
    910                     mCursor++;
    911                     if ((*mCursor == 'x') || (*mCursor == 'o') || (*mCursor == '0')) possibleByteCodeEscape = true;
    912                     insert_range(cc, lastCodepointItem, parse_escaped_codepoint());
    913                     //subexprs.push_back(makeRange(makeCC(lastCodepointItem), makeCC(parse_escaped_codepoint())));
    914                 } else {
    915                     insert_range(cc, lastCodepointItem, parse_literal_codepoint());
    916                     //subexprs.push_back(makeRange(makeCC(lastCodepointItem), makeCC(parse_literal_codepoint())));
    917                 }
    918                 lastItemKind = RangeItem;
    919                 break;
    920             case hyphenChar:
    921                 insert(cc, '-');
    922                 lastItemKind = CodepointItem;
    923                 lastCodepointItem = static_cast<codepoint_t> ('-');
    924                 break;
    925             case ampChar:
    926                 insert(cc, '&');
    927                 lastItemKind = CodepointItem;
    928                 lastCodepointItem = static_cast<codepoint_t> ('&');
    929                 break;
    930             case backSlash:
    931                 if (isSetEscapeChar(*mCursor)) {
    932                     subexprs.push_back(parseEscapedSet());
    933                     lastItemKind = SetItem;
    934                 }
    935                 else {
    936                     if ((*mCursor == 'x') || (*mCursor == 'o') || (*mCursor == '0')) possibleByteCodeEscape = true;
    937                     lastCodepointItem = parse_escaped_codepoint();
    938                     insert(cc, lastCodepointItem);
    939                     lastItemKind = CodepointItem;
    940                 }
    941                 break;
    942             case emptyOperator:
    943                 lastCodepointItem = parse_literal_codepoint();
    944                 insert(cc, lastCodepointItem);
    945                 lastItemKind = CodepointItem;
    946                 break;
    947         }
    948     }
    949     ParseFailure("Set expression not properly terminated.");
     724    }
     725    std::string name = std::string(start, mCursor.pos());
     726    if (!accept(".]")) ParseFailure("Posix equivalence class improperly terminated.");
     727    return createName(name);
     728}
     729
     730RE * RE_Parser::parse_Posix_class() {
     731    bool negated = accept('^');
     732    RE * posixSet = parsePropertyExpression();
     733    if (!accept(":]")) ParseFailure("Posix set expression improperly terminated.");
     734    if (negated) return makeComplement(posixSet);
     735    else return posixSet;
     736}
     737
     738RE * RE_Parser::parse_escaped_char_item() {
     739    if (accept('N')) return parseNamePatternExpression();
     740    else return makeCC(parse_escaped_codepoint());
    950741}
    951742
     
    965756codepoint_t RE_Parser::parse_escaped_codepoint() {
    966757    codepoint_t cp_value;
    967     switch (*mCursor) {
    968         case 'a': ++mCursor; return 0x07; // BEL
    969         case 'e': ++mCursor; return 0x1B; // ESC
    970         case 'f': ++mCursor; return 0x0C; // FF
    971         case 'n': ++mCursor; return 0x0A; // LF
    972         case 'r': ++mCursor; return 0x0D; // CR
    973         case 't': ++mCursor; return 0x09; // HT
    974         case 'v': ++mCursor; return 0x0B; // VT
    975         case 'c': // Control-escape based on next char
    976             ++mCursor;
     758    if (accept('a')) return 0x07; // BEL
     759    else if (accept('e')) return 0x1B; // ESC
     760    else if (accept('f')) return 0x0C; // FF
     761    else if (accept('n')) return 0x0A; // LF
     762    else if (accept('r')) return 0x0D; // CR
     763    else if (accept('t')) return 0x09; // HT
     764    else if (accept('v')) return 0x0B; // VT
     765    else if (accept('c')) {// Control-escape based on next char
    977766            // \c@, \cA, ... \c_, or \ca, ..., \cz
    978767            if (((*mCursor >= '@') && (*mCursor <= '_')) || ((*mCursor >= 'a') && (*mCursor <= 'z'))) {
     
    981770                return cp_value;
    982771            }
    983             else if (*mCursor++ == '?') return 0x7F;  // \c? ==> DEL
     772            else if (accept('?')) return 0x7F;  // \c? ==> DEL
    984773            else ParseFailure("Illegal \\c escape sequence");
    985         case '0': // Octal escape:  0 - 0377
    986             ++mCursor;
    987             return parse_octal_codepoint(0,3);
    988         case 'o':
    989             ++mCursor;
    990             if (*mCursor == '{') {
    991                 ++mCursor;
    992                 cp_value = parse_octal_codepoint(1, 7);
    993                 if (*mCursor++ != '}') ParseFailure("Malformed octal escape sequence");
    994                 return cp_value;
    995             }
    996             else {
    997                 ParseFailure("Malformed octal escape sequence");
    998             }
    999         case 'x':
    1000             ++mCursor;
    1001             if (*mCursor == '{') {
    1002               ++mCursor;
    1003               cp_value = parse_hex_codepoint(1, 6);
    1004               if (*mCursor++ != '}') ParseFailure("Malformed hex escape sequence");
    1005               return cp_value;
    1006             }
    1007             else {
    1008                 return parse_hex_codepoint(1,2);  // ICU compatibility
    1009             }
    1010         case 'u':
    1011             ++mCursor;
    1012             if (*mCursor == '{') {
    1013                 ++mCursor;
    1014                 cp_value = parse_hex_codepoint(1, 6);
    1015                 if (*mCursor++ != '}') ParseFailure("Malformed hex escape sequence");
    1016                 return cp_value;
    1017             }
    1018             else {
    1019                 return parse_hex_codepoint(4,4);  // ICU compatibility
    1020             }
    1021         case 'U':
    1022             ++mCursor;
    1023             return parse_hex_codepoint(8,8);  // ICU compatibility
    1024         default:
    1025             // Escaped letters should be reserved for special functions.
    1026             if (((*mCursor >= 'A') && (*mCursor <= 'Z')) || ((*mCursor >= 'a') && (*mCursor <= 'z'))){
    1027                 //Escape unknown letter will be parse as normal letter
    1028                 return parse_literal_codepoint();
    1029                 //ParseFailure("Undefined or unsupported escape sequence");
    1030             }
    1031             else if ((*mCursor < 0x20) || (*mCursor >= 0x7F))
    1032                 ParseFailure("Illegal escape sequence");
    1033             else return static_cast<codepoint_t>(*mCursor++);
     774    } else if (accept('0')) {
     775        return parse_octal_codepoint(0,3);
     776    } else if (accept('o')) {
     777        if (!accept('{')) ParseFailure("Malformed octal escape sequence");
     778        cp_value = parse_octal_codepoint(1, 7);
     779        if (!accept('}')) ParseFailure("Malformed octal escape sequence");
     780        return cp_value;
     781    } else if (accept('x')) {
     782        if (!accept('{')) return parse_hex_codepoint(1,2);  // ICU compatibility
     783        cp_value = parse_hex_codepoint(1, 6);
     784        if (!accept('}')) ParseFailure("Malformed hex escape sequence");
     785        return cp_value;
     786    } else if (accept('u')) {
     787        if (!accept('{')) return parse_hex_codepoint(4,4);  // ICU compatibility
     788        cp_value = parse_hex_codepoint(1, 6);
     789        if (!accept('}')) ParseFailure("Malformed hex escape sequence");
     790        return cp_value;
     791    } else if (accept('U')) {
     792        return parse_hex_codepoint(8,8);  // ICU compatibility
     793    } else {
     794        if (((*mCursor >= 'A') && (*mCursor <= 'Z')) || ((*mCursor >= 'a') && (*mCursor <= 'z'))){
     795            //Escape unknown letter will be parse as normal letter
     796            return parse_literal_codepoint();
     797            //ParseFailure("Undefined or unsupported escape sequence");
     798        }
     799        else if ((*mCursor < 0x20) || (*mCursor >= 0x7F))
     800            ParseFailure("Illegal escape sequence");
     801        else return static_cast<codepoint_t>(*mCursor++);
    1034802    }
    1035803}
  • icGREP/icgrep-devel/icgrep/re/re_parser.h

    r5754 r5787  
    1818
    1919enum CharsetOperatorKind
    20     {intersectOp, setDiffOp, ampChar, hyphenChar, rangeHyphen, posixPropertyOpener, setOpener, setCloser, backSlash, emptyOperator};
    21 
     20    {intersectOp, setDiffOp, ampChar, hyphenChar, rangeHyphen, posixPropertyOpener, setOpener, setCloser, backSlash, emptyOperator};   
     21   
    2222enum ModeFlagType : unsigned {
    2323    DEFAULT_MODE = 0,
    2424    CASE_INSENSITIVE_MODE_FLAG = 1,
    25     MULTILINE_MODE_FLAG = 2,      // not currently implemented
     25    MULTILINE_MODE_FLAG = 2,
    2626    DOTALL_MODE_FLAG = 4,         // not currently implemented
    2727    IGNORE_SPACE_MODE_FLAG = 8,
     
    2929    GRAPHEME_CLUSTER_MODE = 32
    3030};
    31 
    32 const int MAX_REPETITION_LOWER_BOUND = 1024;
    33 const int MAX_REPETITION_UPPER_BOUND = 2048;
    3431
    3532using ModeFlagSet = unsigned;
     
    9188            return mCursor;
    9289        }
    93 
     90       
     91       
    9492        Cursor(const std::string & expression) : mCursor(expression.cbegin()), mEnd(expression.cend()) {}
    9593        Cursor(const Cursor & cursor) : mCursor(cursor.mCursor), mEnd(cursor.mEnd) {}
     
    104102    };
    105103
     104   
     105   
     106    inline bool at(char c) {
     107        return (mCursor.more()) && (*mCursor == c);
     108    }
     109   
     110    inline bool accept(char c) {
     111        if (at(c)) {
     112            mCursor++;
     113            return true;
     114        }
     115        return false;
     116    }
     117   
     118    inline bool atany(std::string s) {
     119        if (mCursor.noMore()) return false;
     120        for (unsigned i = 0; i < s.length(); i++) {
     121            if (s[i] == *mCursor) return true;
     122        }
     123        return false;
     124    }
     125   
     126    inline bool at(std::string s) {
     127        Cursor tmp = mCursor;
     128        for (unsigned i = 0; i < s.length(); i++) {
     129            if (tmp.noMore() || (s[i] != *tmp)) return false;
     130            tmp++;
     131        }
     132        return true;
     133    }
     134   
     135    inline bool accept(std::string s) {
     136        for (unsigned i = 0; i < s.length(); i++) {
     137            if (mCursor.noMore() || (s[i] != *mCursor)) return false;
     138            mCursor++;
     139        }
     140        return true;
     141    }
     142   
     143
    106144    RE_Parser(const std::string & regular_expression);
    107145
     
    111149
    112150    virtual RE * parse_alt();
    113    
    114     virtual bool accept_alt_mark();
    115151   
    116152    virtual RE * parse_seq();
     
    157193    Name * createName(std::string prop, std::string value);
    158194
    159     virtual bool isUnsupportChartsetOperator(char c);
    160     CharsetOperatorKind getCharsetOperator();
    161 
    162     RE * parse_charset();
    163 
     195    RE * parse_extended_bracket_expression();
     196    RE * parse_bracketed_items();
     197    RE * range_extend(RE * e1);
     198   
     199    RE * parse_equivalence_class();
     200    RE * parse_collation_element();
     201    RE * parse_Posix_class();
     202    RE * parse_escaped_char_item();
     203   
    164204    codepoint_t parse_codepoint();
    165205
     
    183223    bool                        fNested;
    184224    unsigned                    mGroupsOpen;
    185     bool                        fGraphemeBoundaryPending;
    186225    bool                        fSupportNonCaptureGroup;
    187226    Cursor                      mCursor;
  • 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 }
  • icGREP/icgrep-devel/icgrep/re/re_parser_bre.h

    r5737 r5787  
    99
    1010#include <re/re_parser.h>
     11#include <re/re_parser_ere.h>
    1112
    1213namespace re {
    13     class RE_Parser_BRE : public RE_Parser  {
     14    class RE_Parser_BRE : public RE_Parser_ERE  {
    1415    public:
    15         RE_Parser_BRE(const std::string & regular_expression) : RE_Parser(regular_expression) {
     16        RE_Parser_BRE(const std::string & regular_expression) : RE_Parser_ERE(regular_expression) {
    1617            mReSyntax = RE_Syntax::BRE;
    1718        }
    1819
    1920    protected:
    20         virtual bool isSetEscapeChar(char c) override;
    21         virtual bool isUnsupportChartsetOperator(char c) override;
    22         virtual RE * parse_alt() override;
    23         virtual RE * parse_next_item() override ;
    24         virtual RE * parse_escaped() override;
    25         virtual RE * extend_item(RE * re) override;
    26         virtual RE * parse_group() override;
    27         virtual std::pair<int, int> parse_range_bound() override;
    28         virtual codepoint_t parse_escaped_codepoint() override;
    29         virtual RE * parsePropertyExpression() override;
    30         virtual RE * parseEscapedSet() override;
    31 
    32     private:
    33         bool isEscapedCharAhead(char c);
    34 
     21        RE * parse_alt() override;
     22        RE * parse_seq() override;
     23        RE * parse_next_item() override ;
     24        RE * extend_item(RE * re) override;
     25        RE * parse_group() override;
     26        std::pair<int, int> parse_range_bound() override;
    3527    };
    3628}
  • icGREP/icgrep-devel/icgrep/re/re_parser_ere.cpp

    r5181 r5787  
    66
    77#include <re/re_parser_ere.h>
    8 #include <re/re_parser_helper.h>
     8#include <re/re_start.h>
     9#include <re/re_end.h>
     10#include <re/re_any.h>
     11#include <re/re_alt.h>
     12#include <re/re_seq.h>
    913
    10 namespace re{
     14namespace re {
    1115
    12     // \d and \D removed
    13     const uint64_t setEscapeCharacters = bit3C('b') | bit3C('p') | bit3C('q') | bit3C('w') | bit3C('s') | bit3C('<') | bit3C('>') |
    14                                          bit3C('B') | bit3C('P') | bit3C('Q') | bit3C('W') | bit3C('S') | bit3C('N') | bit3C('X');
    1516
    16     bool RE_Parser_ERE::isSetEscapeChar(char c) {
    17         return c >= 0x3C && c <= 0x7B && ((setEscapeCharacters >> (c - 0x3C)) & 1) == 1;
    18     }
     17RE * RE_Parser_ERE::parse_next_item() {
     18    if (mCursor.noMore() || atany("*?+{|")) return nullptr;
     19    else if ((mGroupsOpen > 0) && at(')')) return nullptr;
     20    else if (accept('^')) return makeStart();
     21    else if (accept('$')) return makeEnd();
     22    else if (accept('.')) return makeAny();
     23    else if (accept('(')) return parse_group();
     24    else if (accept('[')) return parse_bracket_expr();
     25    else if (accept('\\')) return parse_escaped();
     26    else return createCC(parse_literal_codepoint());
     27}
    1928
    20     inline bool RE_Parser_ERE::isUnsupportChartsetOperator(char c) {
    21         switch (c) {
    22             case '\\':
    23                 return true;
    24             default:
    25                 return false;
     29// A parenthesized group.  Input precondition: the opening ( has been consumed
     30RE * RE_Parser_ERE::parse_group() {
     31    // Capturing paren group.
     32    mGroupsOpen++;
     33    RE * captured = parse_alt();
     34    mCaptureGroupCount++;
     35    std::string captureName = "\\" + std::to_string(mCaptureGroupCount);
     36    Name * const capture  = mMemoizer.memoize(makeCapture(captureName, captured));
     37    auto key = std::make_pair("", captureName);
     38    mNameMap.insert(std::make_pair(std::move(key), capture));
     39    if (!accept(')')) ParseFailure("Closing parenthesis required.");
     40    mGroupsOpen--;
     41    return capture;
     42}
     43
     44RE * RE_Parser_ERE::parse_escaped() {
     45    if (accept('b')) return makeWordBoundary();
     46    if (accept('B')) return makeWordNonBoundary();
     47    if (accept('s')) return makeWhitespaceSet();
     48    if (accept('S')) return makeComplement(makeWhitespaceSet());
     49    if (accept('<')) return makeWordBegin();
     50    if (accept('>')) return makeWordEnd();
     51    if (isdigit(*mCursor)) {
     52        mCursor++;
     53        std::string backref = std::string(mCursor.pos()-2, mCursor.pos());
     54        auto key = std::make_pair("", backref);
     55        auto f = mNameMap.find(key);
     56        if (f != mNameMap.end()) {
     57            return makeReference(backref, f->second);
     58        }
     59        else {
     60            ParseFailure("Back reference " + backref + " without prior capture group.");
    2661        }
    2762    }
     63    else {
     64        return createCC(parse_literal_codepoint());
     65    }
    2866}
     67
     68
     69// Parsing items within a bracket expression.
     70// Items represent individual characters or sets of characters.
     71// Ranges may be formed by individual character items separated by '-'.
     72RE * RE_Parser_ERE::parse_bracket_expr () {
     73    bool negated = accept('^');
     74    std::vector<RE *> items;
     75    do {
     76        if (accept('[')) {
     77            if (accept('=')) items.push_back(parse_equivalence_class());
     78            else if (accept('.')) items.push_back(range_extend(parse_collation_element()));
     79            else if (accept(':')) items.push_back(parse_Posix_class());
     80            else items.push_back(parse_bracket_expr());
     81        } else {
     82            items.push_back(range_extend(makeCC(parse_literal_codepoint())));
     83        }
     84    } while (mCursor.more() && !at(']'));
     85    RE * t = makeAlt(items.begin(), items.end());
     86    if (!accept(']')) ParseFailure("Expecting ]");
     87    if (negated) return makeComplement(t);
     88    else return t;
     89}
     90}
  • icGREP/icgrep-devel/icgrep/re/re_parser_ere.h

    r5267 r5787  
    1818
    1919    protected:
    20         virtual bool isSetEscapeChar(char c) override;
    21         virtual bool isUnsupportChartsetOperator(char c) override;
     20       virtual RE * parse_next_item() override;
     21
     22       virtual RE * parse_group() override;
     23
     24       virtual RE * parse_escaped() override;
     25       
     26       RE * parse_bracket_expr();
     27
     28       
    2229    };
    2330}
  • icGREP/icgrep-devel/icgrep/re/re_parser_prosite.cpp

    r5267 r5787  
    104104                int lb = 0, ub = 0;
    105105                std::tie(lb, ub) = parse_range_bound();
    106                 if (lb > MAX_REPETITION_LOWER_BOUND || ub > MAX_REPETITION_UPPER_BOUND) {
    107                     ParseFailure("Bounded repetition exceeds icgrep implementation limit");
    108                 }
    109106                if ((ub != Rep::UNBOUNDED_REP) && (lb > ub)) {
    110107                    ParseFailure("Lower bound cannot exceed upper bound in bounded repetition");
  • icGREP/icgrep-devel/icgrep/re/re_range.cpp

    r5764 r5787  
    55 */
    66
    7 #include "re_range.h"
    8 #include "re_cc.h"
     7#include <re/re_range.h>
     8#include <re/re_cc.h>
     9#include <re/re_name.h>
    910#include <llvm/Support/Casting.h>
    1011
     
    1920        return makeCC(dyn_cast<CC>(lo)->front().first, dyn_cast<CC>(hi)->front().first);
    2021    }
     22    else if (isa<Name>(lo) && (cast<Name>(lo)->getDefinition() != nullptr)) {
     23        return makeRange(cast<Name>(lo)->getDefinition(), hi);
     24    }
     25    else if (isa<Name>(hi) && (cast<Name>(hi)->getDefinition() != nullptr)) {
     26        return makeRange(lo, cast<Name>(hi)->getDefinition());
     27    }
    2128    else if (lo == hi) { // TODO: general check for equality, not just instance equality
    2229        return lo;
Note: See TracChangeset for help on using the changeset viewer.