Ignore:
Timestamp:
Sep 7, 2016, 4:01:45 PM (3 years ago)
Author:
xuedongx
Message:

remove nullable assertion

File:
1 edited

Legend:

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

    r5091 r5147  
    55#include <re/re_alt.h>
    66#include <re/re_rep.h>
     7#include <re/re_any.h>
     8#include <re/re_diff.h>
     9#include <re/re_intersect.h>
     10#include <re/re_assertion.h>
    711#include <re/re_name.h>
    812
     
    8488        }
    8589    }
     90    return re;
     91}
     92
     93// Deal with case: R1 (Assertion R2) R3
     94// If R2 is nullable, then R1 R3.
     95RE * RE_Nullable::removeNullableAssertion(RE * re) {
     96    if (Assertion * a = dyn_cast<Assertion>(re)) {
     97        if (isNullable(a->getAsserted())) {
     98            std::vector<RE *> seq;
     99            return makeSeq(seq.begin(), seq.end());
     100        } else {
     101            return re;
     102        }
     103    } else if (Seq * seq = dyn_cast<Seq>(re)) {
     104        std::vector<RE*> list;
     105        for (auto i = seq->begin(); i != seq->end(); ++i) {
     106            list.push_back(removeNullableAssertion(*i));
     107        }
     108        re = makeSeq(list.begin(), list.end());
     109    } else if (Alt * alt = dyn_cast<Alt>(re)) {
     110        std::vector<RE*> list;
     111        for (auto i = alt->begin(); i != alt->end(); ++i) {
     112            list.push_back(removeNullableAssertion(*i));
     113        }
     114        re = makeAlt(list.begin(), list.end());
     115    }
     116    return re;
     117}
     118
     119// Deal with case: R1 (Assertion R2) R3
     120// If R3 is nullable, then R1 R2.
     121RE * RE_Nullable::removeNullableAfterAssertion(RE * re) {
     122    if (isNullableAfterAssertion(re)) {
     123        re = removeNullableAfterAssertion_helper(re);
     124    }
     125    return re;
     126}
     127
     128bool RE_Nullable::isNullableAfterAssertion(const RE * re) {
     129    bool nullable = false;
     130    if (const Seq * seq = dyn_cast<const Seq>(re)) {
     131        nullable = isa<Assertion>(seq->back()) ? true : isNullableAfterAssertion(seq->back());
     132    } else if (const Alt * alt = dyn_cast<const Alt>(re)) {
     133        for (const RE * re : *alt) {
     134            if (isNullableAfterAssertion(re)) {
     135                nullable = true;
     136                break;
     137            }
     138        }
     139    }   
     140    return nullable;
     141}
     142
     143RE * RE_Nullable::removeNullableAfterAssertion_helper(RE * re) {
     144    if (Assertion * a = dyn_cast<Assertion>(re)) {
     145        if (a->getSense() == Assertion::Sense::Positive) {
     146            return a->getAsserted();
     147        } else {
     148            return makeDiff(makeAny(), a->getAsserted());
     149        }
     150    } else if (Seq * seq = dyn_cast<Seq>(re)) {
     151        std::vector<RE*> list;
     152        auto i = seq->begin();
     153        for (; i != seq->end() - 1; ++i) {
     154            list.push_back(*i);
     155        }
     156        list.push_back(removeNullableAfterAssertion_helper(*i));
     157        re = makeSeq(list.begin(), list.end());
     158    } else if (Alt * alt = dyn_cast<Alt>(re)) {
     159        std::vector<RE*> list;
     160        for (auto i = alt->begin(); i != alt->end(); ++i) {
     161            list.push_back(removeNullableAfterAssertion_helper(*i));
     162        }
     163        re = makeAlt(list.begin(), list.end());
     164    }
    86165    return re;
    87166}
     
    103182    } else if (const Rep* re_rep = dyn_cast<const Rep>(re)) {
    104183        return re_rep->getLB() == 0 ? true : isNullable(re_rep->getRE());
    105     }
     184    } else if (const Diff * diff = dyn_cast<const Diff>(re)) {
     185        return isNullable(diff->getLH()) && !isNullable(diff->getRH());
     186    } else if (const Intersect * e = dyn_cast<const Intersect>(re)) {
     187        return isNullable(e->getLH()) && isNullable(e->getRH());
     188    }
    106189    return false;
    107190}
Note: See TracChangeset for help on using the changeset viewer.