Changeset 5509


Ignore:
Timestamp:
Jun 15, 2017, 12:17:33 PM (5 months ago)
Author:
cameron
Message:

Bounded repetition optimizations and bug fix; test case

Location:
icGREP/icgrep-devel
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/QA/greptest.xml

    r5372 r5509  
    476476<grepcase regexp="=[a-z]{7,}" datafile="bounded_charclass" grepcount="20"/>
    477477<grepcase regexp="=[a-z]{5,15};" datafile="bounded_charclass" grepcount="11"/>
     478<grepcase regexp="=(?:[a-z]{3,5}){2,};" datafile="bounded_charclass" grepcount="21"/>
     479<grepcase regexp="=(?:[a-z]{4,5}){2,};" datafile="bounded_charclass" grepcount="18"/>
    478480<grepcase regexp="(([wxy]{2}){3}){2}" datafile="bounded_charclass" grepcount="3"/>
    479481<grepcase regexp="(([wxy]{2}?){3}?){2}?" datafile="bounded_charclass" grepcount="3"/>
  • icGREP/icgrep-devel/icgrep/re/re_nullable.h

    r5267 r5509  
    1212    static RE * removeNullableSuffix(RE * re);
    1313    static RE * removeNullableAssertion(RE * re);
    14     static RE * removeNullableAfterAssertion(RE * re);
     14    static RE * removeNullableAfterAssertion(RE * re);
     15    static bool isNullable(const RE * re);
     16    static bool hasNullablePrefix(const RE * re);
     17    static bool hasNullableSuffix(const RE * re);
    1518private:
    1619    static bool isNullableAfterAssertion(const RE * re);
    1720    static RE * removeNullableAfterAssertion_helper(RE * re);
    18     static bool isNullable(const RE * re);
    1921    static bool isNullable(const Vector * vec);
    20     static bool hasNullablePrefix(const RE * re);
    21     static bool hasNullableSuffix(const RE * re);
    2222};
    2323
  • icGREP/icgrep-devel/icgrep/re/re_rep.cpp

    r5267 r5509  
    11/*
    2  *  Copyright (c) 2014 International Characters.
     2 *  Copyright (c) 2017 International Characters.
    33 *  This software is licensed to the public under the Open Software License 3.0.
    44 *  icgrep is a trademark of International Characters.
     
    88#include "re_assertion.h"
    99#include "re_seq.h"
     10#include "re_alt.h"
     11#include "re_nullable.h"
    1012#include <llvm/Support/Casting.h>
    1113
     
    2224    }
    2325}
    24 
    25 RE * makeRep(RE * re, const int lb, const int ub) {
     26   
     27RE * makeRep(RE * re, int lb, const int ub) {
     28    if (RE_Nullable::isNullable(re)) {
     29        if (ub == 1) {
     30            return re;
     31        }
     32        lb = 0;
     33    }
    2634    if (Rep * rep = dyn_cast<Rep>(re)) {
    27         if (rep->getUB() == Rep::UNBOUNDED_REP && ((lb > 0) || (rep->getLB() <= 1))) {
    28             return new Rep(rep->getRE(), rep->getLB() * lb, Rep::UNBOUNDED_REP);
     35        int l = rep->getLB();
     36        int u = rep->getUB();
     37        if (u == Rep::UNBOUNDED_REP) {
     38            if (l == 0) {
     39                /*  R{0,}{lb, ub} = R{0,} */
     40                return rep;
     41            } else if (l == 1) {
     42                /*  R{1,}{lb, ub} = R{lb,} */
     43                return new Rep(rep->getRE(), lb, Rep::UNBOUNDED_REP);
     44            } else if (lb == 0) {
     45                /*  R{l,}{0, ub} = R{l,}? */
     46                return new Rep(rep, 0, 1);
     47            } else {
     48                /* R{l,}{lb, ub} = R{l * lb,} */
     49                return new Rep(rep->getRE(), l * lb, Rep::UNBOUNDED_REP);
     50            }
    2951        }
    30         else if ((rep->getUB() == Rep::UNBOUNDED_REP) && (lb == 0)) {
    31             return new Rep(rep, 0, 1);
    32         }
    33         else if (lb == ub) {
    34             return new Rep(rep->getRE(), lb * rep->getLB(), ub * rep->getUB());
    35         }
    36         else if ((rep->getUB() * lb) >= (rep->getLB() * (lb + 1) - 1)) {
    37             return new Rep(rep->getRE(), rep->getUB() * lb, ubCombine(rep->getUB(), ub));
     52        else if (u > l) {
     53            // Calculate the smallest number of repetitions n such that n * u + 1 >= (n + 1) * l
     54            int n = (u - 2)/(u-l);
     55            if (lb >= n) {
     56                return new Rep(rep->getRE(), l * lb, ubCombine(u, ub));
     57            }
     58            if ((ub == Rep::UNBOUNDED_REP) || (ub >= n)) {
     59                RE * r1 = new Rep(rep->getRE(), n * l, ubCombine(u, ub));
     60                RE * r2 = new Rep(rep, lb, n - 1);
     61                return makeAlt({r1, r2});
     62            }
    3863        }
    3964    }
Note: See TracChangeset for help on using the changeset viewer.