Moved SCL parser generator to platform repository.

[simantics/platform.git] / bundles / org.simantics.scl.compiler / src / org / simantics / scl / compiler / parser / regexp / ROr.java

diff --git a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/parser/regexp/ROr.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/parser/regexp/ROr.java
new file mode 100644 (file)
index 0000000..e46131e
--- /dev/null
+++ b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/parser/regexp/ROr.java
@@ -0,0 +1,188 @@
+package org.simantics.scl.compiler.parser.regexp;
+
+import gnu.trove.set.hash.THashSet;
+
+import java.util.Arrays;
+import java.util.Iterator;
+
+import org.simantics.scl.compiler.parser.regexp.automata.NFA;
+
+public class ROr extends Regexp {
+    public final Regexp[] exps;
+
+    ROr(Regexp[] exps) {
+        this.exps = exps;
+    }
+
+    @Override
+    protected void buildAutomaton(NFA aut, int inState, int outState) {
+        for(Regexp exp : exps)
+            exp.buildAutomaton(aut, inState, outState);
+    }
+        
+    @Override
+    protected void toString(StringBuilder b, int prec) {
+        if(prec >= 1)
+            b.append('(');
+        boolean first = true;
+        for(Regexp exp : exps) {
+            if(first)
+                first = false;
+            else
+                b.append(" | ");
+            exp.toString(b, 1);
+        }
+        if(prec >= 1)
+            b.append(')');
+    }
+    
+    @Override
+    public void toString(StringBuilder b, Namer grammar, int prec) {
+        if(prec >= 1)
+            b.append('(');
+        boolean first = true;
+        for(Regexp exp : exps) {
+            if(first)
+                first = false;
+            else
+                b.append(" | ");
+            exp.toString(b, grammar, 1);
+        }
+        if(prec >= 1)
+            b.append(')');
+    }
+    
+    @Override
+    protected int getTypeId() {
+        return OR;
+    }
+    
+    @Override
+    public boolean equals(Object obj) {
+        if(obj == this)
+            return true;
+        if(obj == null || obj.getClass() != getClass())
+            return false;
+        ROr other = (ROr)obj;
+        return Arrays.equals(exps, other.exps);
+    }
+    
+    @Override
+    public int hashCode() {
+        int r = 34235;
+        for(Regexp exp : exps) {
+            r *= 31;
+            r += exp.hashCode();
+        }
+        return r;
+    }
+    
+    @Override
+    public boolean isNullable() {
+        for(Regexp exp : exps)
+            if(exp.isNullable())
+                return true;
+        return false;
+    }
+    
+    private Regexp simplify(THashSet<Regexp> set) {
+        boolean qm = set.remove(ONE);
+        
+        Regexp exp;
+        simpl: {
+            if(set.size() > 1) {
+                frontLoop: {
+                    Iterator<Regexp> it = set.iterator();
+                    Regexp common = front(it.next());
+                    while(it.hasNext()) {
+                        Regexp temp = front(it.next());
+                        if(!temp.equals(common))
+                            break frontLoop;
+                    }
+                    
+                    THashSet<Regexp> set2 = new THashSet<Regexp>();
+                    for(Regexp e : set)
+                        set2.add(removeFront(e));
+                    
+                    exp = seq(common, simplify(set2)); 
+                    break simpl;
+                }
+            
+                backLoop: {
+                    Iterator<Regexp> it = set.iterator();
+                    Regexp common = back(it.next());
+                    while(it.hasNext()) {
+                        Regexp temp = back(it.next());
+                        if(!temp.equals(common))
+                            break backLoop;
+                    }
+                    
+                    THashSet<Regexp> set2 = new THashSet<Regexp>();
+                    for(Regexp e : set)
+                        set2.add(removeBack(e));
+                    
+                    exp = seq(simplify(set2), common); 
+                    break simpl;
+                }
+            }
+        
+            exp = or(set);
+        }
+        
+        if(qm && !exp.isNullable())
+            exp = new ROp(exp, '?');
+        return exp;
+    }
+    
+    @Override
+    public Regexp simplify() {
+        if(exps.length == 0)
+            return this;
+        THashSet<Regexp> set = new THashSet<Regexp>();
+        for(Regexp exp : exps) {
+            exp = exp.simplify();
+            or(set, exp);
+        }
+        return simplify(set);
+    }
+    
+    private static Regexp front(Regexp exp) {
+        if(exp instanceof RSeq) {
+            Regexp[] exps = ((RSeq)exp).exps;
+            if(exps.length == 0)
+                return null;
+            return exps[0];
+        }
+        else
+            return exp;
+    }
+    
+    private static Regexp removeFront(Regexp exp) {
+        if(exp instanceof RSeq) {
+            Regexp[] exps = ((RSeq)exp).exps;
+            return seq_(Arrays.asList(exps).subList(1, exps.length));
+        }
+        else
+            return ONE;
+    }
+    
+    private static Regexp back(Regexp exp) {
+        if(exp instanceof RSeq) {
+            Regexp[] exps = ((RSeq)exp).exps; 
+            if(exps.length == 0)
+                return null;
+            return exps[exps.length-1];
+        }
+        else
+            return exp;
+    }
+    
+    private static Regexp removeBack(Regexp exp) {
+        if(exp instanceof RSeq) {
+            Regexp[] exps = ((RSeq)exp).exps;
+            return seq_(Arrays.asList(exps).subList(0, exps.length-1));
+        }
+        else
+            return ONE;
+    }
+}