bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/parser/regexp/Regexp.java

   1 package org.simantics.scl.compiler.parser.regexp;
   2
   3 import gnu.trove.set.hash.THashSet;
   4
   5 import java.util.ArrayList;
   6 import java.util.Arrays;
   7 import java.util.Collection;
   8 import java.util.List;
   9 import java.util.concurrent.atomic.AtomicReference;
  10
  11 import org.simantics.scl.compiler.parser.regexp.automata.NFA;
  12
  13 public abstract class Regexp implements Comparable<Regexp> {
  14     static final int ATOM = 0;
  15     static final int OP = 1;
  16     static final int OR = 2;
  17     static final int SEQ = 3;
  18
  19     protected abstract void buildAutomaton(NFA aut, int inState, int outState);
  20
  21     public static final Regexp ONE = new RSeq(new Regexp[0]);
  22     public static final Regexp ZERO = new ROr(new Regexp[0]);
  23
  24     Regexp() {
  25     }
  26
  27     public NFA toAutomaton() {
  28         NFA aut = new NFA();
  29         int inState = aut.newState();
  30         int outState = aut.newState();
  31         buildAutomaton(aut, inState, outState);
  32         aut.setInitialState(inState);
  33         aut.setAccepts(outState, true);
  34         return aut;
  35     }
  36
  37     @Override
  38     public String toString() {
  39         StringBuilder b = new StringBuilder();
  40         toString(b, 0);
  41         return b.toString();
  42     }
  43
  44     protected abstract void toString(StringBuilder b, int prec);
  45
  46     protected abstract int getTypeId();
  47
  48     public abstract boolean isNullable();
  49
  50     public Regexp simplify() {
  51         return this;
  52     }
  53
  54     private static int parseRegexp(int pos, String regexp, AtomicReference<Regexp> result) {
  55         ArrayList<Regexp> dc = new ArrayList<Regexp>();
  56         ArrayList<Regexp> cc = new ArrayList<Regexp>();
  57         loop: while(true) {
  58             if(pos == regexp.length())
  59                 break loop;
  60             char c = regexp.charAt(pos++);
  61             switch(c) {
  62             case '(': {
  63                 AtomicReference<Regexp> child = new AtomicReference<Regexp>();
  64                 pos = parseRegexp(pos, regexp, child);
  65                 cc.add(child.get());
  66             } break;
  67             case ')':
  68                 break loop;
  69             case '|': {
  70                 dc.add(seq(cc));
  71                 cc.clear();
  72             } break;
  73             case '*': {
  74                 if(cc.isEmpty())
  75                     throw new IllegalArgumentException("Encountered * that is not front of anything.");
  76                 int p = cc.size()-1;
  77                 cc.set(p, Regexp.star(cc.get(p)));
  78             } break;
  79             case '?': {
  80                 if(cc.isEmpty())
  81                     throw new IllegalArgumentException("Encountered ? that is not front of anything.");
  82                 int p = cc.size()-1;
  83                 cc.set(p, Regexp.optional(cc.get(p)));
  84             } break;
  85             case '+': {
  86                 if(cc.isEmpty())
  87                     throw new IllegalArgumentException("Encountered + that is not front of anything.");
  88                 int p = cc.size()-1;
  89                 cc.set(p, Regexp.plus(cc.get(p)));
  90             } break;
  91             default:
  92                 cc.add(new RAtom(c));
  93             }
  94         }
  95         dc.add(seq(cc));
  96         result.set(or(dc));
  97         return pos;
  98     }
  99
 100     public static Regexp of(String regexp) {
 101         AtomicReference<Regexp> result = new AtomicReference<Regexp>();
 102         int finalPos = parseRegexp(0, regexp, result);
 103         if(finalPos < regexp.length())
 104             throw new IllegalArgumentException("Extra closing parenteses");
 105         return result.get();
 106     }
 107
 108     static void seq(ArrayList<Regexp> l, Regexp exp) {
 109         if(l.size() > 0 && l.get(0) == ZERO)
 110             return;
 111         if(exp instanceof RSeq)
 112             for(Regexp e : ((RSeq)exp).exps)
 113                 seq(l, e);
 114         else if(exp == ZERO) {
 115             l.clear();
 116             l.add(exp);
 117         }
 118         else
 119             l.add(exp);
 120     }
 121
 122     static Regexp seq_(List<Regexp> es) {
 123         if(es.size() == 0)
 124             return ONE;
 125         if(es.size() == 1)
 126             return es.get(0);
 127         Regexp[] eArray = es.toArray(new Regexp[es.size()]);
 128         return new RSeq(eArray);
 129     }
 130
 131     public static Regexp seq(Regexp ... exps) {
 132         if(exps.length == 0)
 133             return ONE;
 134         if(exps.length == 1)
 135             return exps[0];
 136         ArrayList<Regexp> es = new ArrayList<Regexp>();
 137         for(Regexp exp : exps)
 138             seq(es, exp);
 139         return seq_(es);
 140     }
 141
 142     public static Regexp seq(Collection<Regexp> exps) {
 143         return seq(exps.toArray(new Regexp[exps.size()]));
 144     }
 145
 146     static void or(THashSet<Regexp> s, Regexp exp) {
 147         if(exp instanceof ROr)
 148             for(Regexp e : ((ROr)exp).exps)
 149                 or(s, e);
 150         else
 151             s.add(exp);
 152     }
 153
 154     static Regexp or_(THashSet<Regexp> es) {
 155         if(es.size() == 0)
 156             return ZERO;
 157         if(es.size() == 1)
 158             return es.iterator().next();
 159         Regexp[] eArray = es.toArray(new Regexp[es.size()]);
 160         Arrays.sort(eArray);
 161         return new ROr(eArray);
 162     }
 163
 164     public static Regexp or(Regexp ... exps) {
 165         if(exps.length == 0)
 166             return ZERO;
 167         if(exps.length == 1)
 168             return exps[0];
 169         THashSet<Regexp> es = new THashSet<Regexp>();
 170         for(Regexp exp : exps)
 171             or(es, exp);
 172         return or_(es);
 173     }
 174
 175     public static Regexp star(Regexp exp) {
 176         if(exp == ONE || exp == ZERO)
 177             return ONE;
 178         return new ROp(exp, '*');
 179     }
 180
 181     public static Regexp plus(Regexp exp) {
 182         return new ROp(exp, '+');
 183     }
 184
 185     public static Regexp optional(Regexp exp) {
 186         return new ROp(exp, '?');
 187     }
 188
 189     public static Regexp or(Collection<Regexp> exps) {
 190         return or(exps.toArray(new Regexp[exps.size()]));
 191     }
 192
 193     @Override
 194     public int compareTo(Regexp o) {
 195         int tA = getTypeId();
 196         int tB = o.getTypeId();
 197         if(tA < tB)
 198             return -1;
 199         if(tA > tB)
 200             return 1;
 201         switch(tA) {
 202         case ATOM: {
 203             int sA = ((RAtom)this).symbolId;
 204             int sB = ((RAtom)o).symbolId;
 205             if(sA < sB)
 206                 return -1;
 207             if(sA > sB)
 208                 return 1;
 209             return 0;
 210         }
 211         case OP: {
 212             ROp a = (ROp)this;
 213             ROp b = (ROp)o;
 214             if(a.op < b.op)
 215                 return -1;
 216             if(a.op > b.op)
 217                 return 1;
 218             return a.exp.compareTo(b.exp);
 219         }
 220         case OR:
 221             return compare(((ROr)this).exps, ((ROr)o).exps);
 222         case SEQ: {
 223             return compare(((RSeq)this).exps, ((RSeq)o).exps);
 224         }
 225         default:
 226             throw new IllegalArgumentException();
 227         }
 228     }
 229
 230     private static int compare(Regexp[] a, Regexp[] b) {
 231         if(a.length < b.length)
 232             return -1;
 233         if(a.length > b.length)
 234             return 1;
 235         for(int i=0;i<a.length;++i) {
 236             int temp = a[i].compareTo(b[i]);
 237             if(temp != 0)
 238                 return temp;
 239         }
 240         return 0;
 241     }
 242
 243     public abstract void toString(StringBuilder b, Namer grammar, int prec);
 244 }