Changeset 5866


Ignore:
Timestamp:
Feb 8, 2018, 2:11:29 PM (9 months ago)
Author:
cameron
Message:

Revised canonical form for nullable expressions; extended star-normal xfrm

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

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/re/re_alt.h

    r5835 r5866  
    7171
    7272    bool nullable = false;
    73     RE * emptySeq = nullptr;
     73    RE * nullableSeq = nullptr;
    7474    for (auto i = begin; i != end; ++i) {
    7575        if (CC * cc = llvm::dyn_cast<CC>(*i)) {
     
    8282                if (CC * cc = llvm::dyn_cast<CC>(a)) {
    8383                    combineCC(cc);
    84                 } else if (isEmptySeq(a)) {
     84                } else if (isEmptySeq(a) && !nullable) {
    8585                    nullable = true;
    86                     emptySeq = a;
     86                    nullableSeq = a;
    8787                } else {
    8888                    newAlt->push_back(a);
     
    9191        } else if (const Rep * rep = llvm::dyn_cast<Rep>(*i)) {
    9292            if (rep->getLB() == 0) {
    93                 nullable = true;
    94                 newAlt->push_back(makeRep(rep->getRE(), 1, rep->getUB()));
     93                if (nullable) {
     94                    // Already have a nullable case.
     95                    newAlt->push_back(makeRep(rep->getRE(), 1, rep->getUB()));
     96                }
     97                else {
     98                    // This will be the nullable case.
     99                    nullableSeq = *i;
     100                    nullable = true;
     101                }
    95102            } else {
    96103                newAlt->push_back(*i);
    97104            }
    98105        } else if (isEmptySeq(*i)) {
    99             nullable = true;
    100             emptySeq = *i;
     106            if (!nullable) {
     107                nullable = true;
     108                nullableSeq = *i;
     109            }
    101110        } else {
    102111            newAlt->push_back(*i);
     
    105114    newAlt->insert(newAlt->end(), CCs.begin(), CCs.end());
    106115    if (nullable) {
    107         if (emptySeq == nullptr) {
    108             emptySeq = makeSeq();
     116        if (nullableSeq == nullptr) {
     117            nullableSeq = makeSeq();
    109118        }
    110         newAlt->push_back(emptySeq);
     119        newAlt->push_back(nullableSeq);
    111120    }
    112121    return newAlt->size() == 1 ? newAlt->front() : newAlt;
  • icGREP/icgrep-devel/icgrep/re/re_star_normal.cpp

    r5835 r5866  
    1818namespace re {
    1919
    20 RE * RE_Star_Normal::optimize(RE * re) {
    21     if (Alt * alt = dyn_cast<Alt>(re)) {
    22         std::vector<RE *> list;
    23         list.reserve(alt->size());
    24         for (RE * re : *alt) {
    25             list.push_back(optimize(re));
    26         }
    27         re = makeAlt(list.begin(), list.end());
    28     } else if (Seq * seq = dyn_cast<Seq>(re)) {
    29         RE * head = *(seq->begin());
    30         RE * tail = makeSeq(seq->begin() + 1, seq->end());
    31         const auto headNullable = RE_Nullable::isNullable(head);
    32         head = headNullable ? optimize(head) : star_normal(head);
    33         const auto tailNullable = RE_Nullable::isNullable(tail);
    34         tail = tailNullable ? optimize(tail) : star_normal(tail);
    35         if (LLVM_UNLIKELY(headNullable && tailNullable)) {
    36             re = makeAlt({head, tail});
    37         } else {
    38             re = makeSeq({head, tail});
    39         }
    40     } else if (Assertion * a = dyn_cast<Assertion>(re)) {
    41         re = makeAssertion(optimize(a->getAsserted()), a->getKind(), a->getSense());
    42     } else if (Rep * rep = dyn_cast<Rep>(re)) {
    43         RE * const expr = optimize(rep->getRE());
    44         if (rep->getLB() == 0 && rep->getUB() == Rep::UNBOUNDED_REP) {
    45             re = expr;
    46         } else {
    47             re = makeRep(expr, rep->getLB(), rep->getUB());
    48         }
    49     } else if (Diff * diff = dyn_cast<Diff>(re)) {
    50         re = makeDiff(optimize(diff->getLH()), optimize(diff->getRH()));
    51     } else if (Intersect * e = dyn_cast<Intersect>(re)) {
    52         re = makeIntersect(optimize(e->getLH()), optimize(e->getRH()));
    53     } else if (Name * name = dyn_cast<Name>(re)) {
    54         if (name->getDefinition()) {
    55             name->setDefinition(optimize(name->getDefinition()));
     20RE * RE_Star_Normal::star_rule(RE * re) {
     21    if (Seq * seq = dyn_cast<Seq>(re)) {
     22        if (RE_Nullable::isNullable(re)) {
     23            std::vector<RE *> list;
     24            list.reserve(seq->size());
     25            for (RE * r : *seq) {
     26                if (Rep * rep = dyn_cast<Rep>(r)) {
     27                    if (rep->getLB() == 0) {
     28                        list.push_back(rep->getRE());
     29                    }
     30                } else if (!isEmptySeq(r)) {
     31                    list.push_back(r);
     32                }
     33            }
     34            return makeAlt(list.begin(), list.end());
    5635        }
    5736    }
     
    7756        re = makeAssertion(star_normal(a->getAsserted()), a->getKind(), a->getSense());
    7857    } else if (Rep * rep = dyn_cast<Rep>(re)) {
    79          if (rep->getLB() == 0 && rep->getUB() == Rep::UNBOUNDED_REP) {
    80             RE * expr = optimize(rep->getRE());
    81             re = makeRep(expr, 0, rep->getUB());
     58        RE * expr = star_normal(rep->getRE());
     59        if (rep->getLB() == 0 && rep->getUB() == Rep::UNBOUNDED_REP) {
     60            re = makeRep(star_rule(expr), 0, rep->getUB());
    8261        } else {
    83             RE * expr = star_normal(rep->getRE());
    8462            re = makeRep(expr, rep->getLB(), rep->getUB());
    8563        }
  • icGREP/icgrep-devel/icgrep/re/re_star_normal.h

    r5835 r5866  
    2020        static RE * star_normal(RE * re);
    2121private:
    22     static RE * optimize(RE * re);
     22    static RE * star_rule(RE * re);
    2323};
    2424
Note: See TracChangeset for help on using the changeset viewer.