Changeset 5515


Ignore:
Timestamp:
Jun 17, 2017, 2:53:30 PM (3 months ago)
Author:
cameron
Message:

Allow repeated quantifiers in parsing, support possessive quantifiers, further optimizations

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

Legend:

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

    r5481 r5515  
    309309}
    310310
     311// TODO: Set ENABLE_EXTENDED_QUANTIFIERS false for ERE, BRE
     312#define ENABLE_EXTENDED_QUANTIFIERS true
     313   
     314// Extend a RE item with one or more quantifiers
    311315RE * RE_Parser::extend_item(RE * re) {
    312     if (LLVM_LIKELY(mCursor.more())) {
    313         int lb = 0, ub = 0;
    314         bool hasRep = true;
    315         switch (*mCursor) {
    316             case '*':
    317                 lb = 0;
    318                 ub = Rep::UNBOUNDED_REP;
    319                 break;
    320             case '?':
    321                 lb = 0;
    322                 ub = 1;
    323                 break;
    324             case '+':
    325                 lb = 1;
    326                 ub = Rep::UNBOUNDED_REP;
    327                 break;
    328             case '{':
    329                 std::tie(lb, ub) = parse_range_bound();
    330                 break;
    331             default:
    332                 hasRep = false;
    333         }
    334         if (hasRep) {
    335             if (lb > MAX_REPETITION_LOWER_BOUND || ub > MAX_REPETITION_UPPER_BOUND) {
    336                 ParseFailure("Bounded repetition exceeds icgrep implementation limit");
    337             }
     316    if (LLVM_UNLIKELY(!(mCursor.more()))) return re;
     317    int lb = 0, ub = 0;
     318    switch (*mCursor) {
     319        case '*':
     320            lb = 0;
     321            ub = Rep::UNBOUNDED_REP;
     322            break;
     323        case '?':
     324            lb = 0;
     325            ub = 1;
     326            break;
     327        case '+':
     328            lb = 1;
     329            ub = Rep::UNBOUNDED_REP;
     330            break;
     331        case '{':
     332            std::tie(lb, ub) = parse_range_bound();
    338333            if ((ub != Rep::UNBOUNDED_REP) && (lb > ub)) {
    339334                ParseFailure("Lower bound cannot exceed upper bound in bounded repetition");
    340335            }
    341             ++mCursor;
    342             if (*mCursor == '?') { // Non-greedy qualifier
    343                 // Greedy vs. non-greedy makes no difference for icgrep.
    344                 ++mCursor;
    345             } else if (*mCursor == '+') {
    346                 ++mCursor;
    347                 ParseFailure("Possessive repetition is not supported in icgrep 1.0");
    348             }
     336            break;
     337        default:
     338            // No quantifiers
     339            return re;
     340    }
     341    ++mCursor;
     342    if (ENABLE_EXTENDED_QUANTIFIERS) {
     343        if (LLVM_UNLIKELY(!(mCursor.more()))) return makeRep(re, lb, ub);;
     344        if (*mCursor == '?') { // Non-greedy qualifier
     345            // Greedy vs. non-greedy makes no difference for icgrep.
     346            ++mCursor;
    349347            re = makeRep(re, lb, ub);
    350         }
    351     }
    352     return re;
     348        } else if (*mCursor == '+') {
     349            ++mCursor;
     350            if (ub == Rep::UNBOUNDED_REP) {
     351                re = makeSeq({makeRep(re, lb, ub), makeNegativeLookAheadAssertion(re)});
     352            } else if (lb == ub) {
     353                re = makeRep(re, ub, ub);
     354            } else /* if (lb < ub) */{
     355                re = makeAlt({makeSeq({makeRep(re, lb, ub-1), makeNegativeLookAheadAssertion(re)}), makeRep(re, ub, ub)});
     356            }
     357        } else {
     358            re = makeRep(re, lb, ub);
     359        }
     360    } else {
     361        re = makeRep(re, lb, ub);
     362    }
     363    // The quantified expression may be extended with a further quantifier, e,g., [a-z]{6,7}{2,3}
     364    return extend_item(re);
    353365}
    354366
  • icGREP/icgrep-devel/icgrep/re/re_rep.cpp

    r5509 r5515  
    3535        int l = rep->getLB();
    3636        int u = rep->getUB();
    37         if (u == Rep::UNBOUNDED_REP) {
     37        if (lb == ub) {
     38            return new Rep(rep->getRE(), l * lb, ubCombine(u, ub));
     39        }
     40        else if (u == Rep::UNBOUNDED_REP) {
    3841            if (l == 0) {
    3942                /*  R{0,}{lb, ub} = R{0,} */
     
    5861            if ((ub == Rep::UNBOUNDED_REP) || (ub >= n)) {
    5962                RE * r1 = new Rep(rep->getRE(), n * l, ubCombine(u, ub));
    60                 RE * r2 = new Rep(rep, lb, n - 1);
     63                RE * r2 = makeRep(rep, lb, n - 1);  // makeRep recursive simplifies.
    6164                return makeAlt({r1, r2});
    6265            }
Note: See TracChangeset for help on using the changeset viewer.