]> gerrit.simantics Code Review - simantics/platform.git/blob - bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/parser/regexp/Regexp.java
Merge "Redirect document commandRelation and commandExecutorRelation terminals"
[simantics/platform.git] / 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 }