source: icGREP/icgrep-devel/icgrep/re/re_rep.cpp @ 5515

Last change on this file since 5515 was 5515, checked in by cameron, 2 years ago

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

File size: 2.5 KB
Line 
1/*
2 *  Copyright (c) 2017 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6
7#include "re_rep.h"
8#include "re_assertion.h"
9#include "re_seq.h"
10#include "re_alt.h"
11#include "re_nullable.h"
12#include <llvm/Support/Casting.h>
13
14using namespace llvm;
15
16namespace re {
17
18inline int ubCombine(const int h1, const int h2) {
19    if ((h1 == Rep::UNBOUNDED_REP) || (h2 == Rep::UNBOUNDED_REP)) {
20        return Rep::UNBOUNDED_REP;
21    }
22    else {
23        return h1 * h2;
24    }
25}
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    }
34    if (Rep * rep = dyn_cast<Rep>(re)) {
35        int l = rep->getLB();
36        int u = rep->getUB();
37        if (lb == ub) {
38            return new Rep(rep->getRE(), l * lb, ubCombine(u, ub));
39        }
40        else if (u == Rep::UNBOUNDED_REP) {
41            if (l == 0) {
42                /*  R{0,}{lb, ub} = R{0,} */
43                return rep;
44            } else if (l == 1) {
45                /*  R{1,}{lb, ub} = R{lb,} */
46                return new Rep(rep->getRE(), lb, Rep::UNBOUNDED_REP);
47            } else if (lb == 0) {
48                /*  R{l,}{0, ub} = R{l,}? */
49                return new Rep(rep, 0, 1);
50            } else {
51                /* R{l,}{lb, ub} = R{l * lb,} */
52                return new Rep(rep->getRE(), l * lb, Rep::UNBOUNDED_REP);
53            }
54        }
55        else if (u > l) {
56            // Calculate the smallest number of repetitions n such that n * u + 1 >= (n + 1) * l
57            int n = (u - 2)/(u-l);
58            if (lb >= n) {
59                return new Rep(rep->getRE(), l * lb, ubCombine(u, ub));
60            }
61            if ((ub == Rep::UNBOUNDED_REP) || (ub >= n)) {
62                RE * r1 = new Rep(rep->getRE(), n * l, ubCombine(u, ub));
63                RE * r2 = makeRep(rep, lb, n - 1);  // makeRep recursive simplifies.
64                return makeAlt({r1, r2});
65            }
66        }
67    }
68    else if (isa<Assertion>(re)) {
69        if (lb > 0) return re;
70        else return makeSeq();
71    }
72    else {
73        if (Seq * seq = dyn_cast<Seq>(re)) {
74            if (seq->empty()) {
75                return seq;
76            }
77        }
78        if ((lb == 0) && (ub == 0)) {
79            return makeSeq();
80        }
81        else if ((lb == 1) && (ub == 1)) {
82            return re;
83        }
84    }
85    return new Rep(re, lb, ub);
86}
87
88}
Note: See TracBrowser for help on using the repository browser.