Commits

Anonymous committed 0ab5a46

Enhancing the determinization algorithm to handle (almost) any visibly push-down automaton.

Comments (0)

Files changed (4)

src/info/lahoda/papers/code/DPDA.java

 package info.lahoda.papers.code;
 
 import java.util.BitSet;
+import java.util.Collection;
+import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
+import java.util.LinkedHashSet;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
-import java.util.Objects;
+import java.util.Map.Entry;
 import java.util.Set;
 import java.util.Stack;
 
      */
     public static DPDA create(NPDA npda) {
         DPDAState emptyState = DPDAState.createEmpty(npda.states.size());
-        DPDAPushDown emptyPushDown = DPDAPushDown.createEmpty(npda.states.size());
-        DPDAState startingState = emptyState.add(Constants.nostate, 0);
-        Set<DPDAState> states = new HashSet<DPDAState>();
+        DPDAPushDown emptyPushDown = DPDAPushDown.createEmpty(npda.pushdownSymbols);
+        Set<DPDAState> states = new LinkedHashSet<DPDAState>();
         Set<DPDAPushDown> pushdownSymbols = new HashSet<DPDAPushDown>();
         Map<DPDAKey, DPDATarget> transitionTable = new HashMap<DPDAKey, DPDATarget>();
         List<DPDAState> todoStates = new LinkedList<DPDAState>();
         List<DPDAPushDown> todoPushdown = new LinkedList<DPDAPushDown>();
 
+        Set<Character> callAlphabet = new HashSet<Character>();
+        Set<Character> innerAlphabet = new HashSet<Character>();
+        Set<Character> returnAlphabet = new HashSet<Character>();
+
+        for (Entry<PDAKey, Collection<PDATarget>> t : npda.getTransitionTable().entrySet()) {
+            boolean ret = false;
+
+            if (t.getKey().getPushDown() != Constants.epsilon) {
+                returnAlphabet.add(t.getKey().getInput());
+                ret = true;
+            }
+
+            Boolean call = null;
+
+            for (PDATarget v : t.getValue()) {
+                if (v.pushDown != Constants.epsilon) {
+                    if (call == Boolean.FALSE) {
+                        throw new IllegalStateException("Not a visibly push-down automaton ('" + t.getKey().getInput() + "' is used in call and internal transitions)");
+                    }
+                    call = true;
+                } else {
+                    if (call == Boolean.TRUE) {
+                        throw new IllegalStateException("Not a visibly push-down automaton ('" + t.getKey().getInput() + "' is used in call and internal transitions)");
+                    }
+                    call = false;
+                }
+            }
+
+            if (call) callAlphabet.add(t.getKey().getInput());
+            else if (!ret) innerAlphabet.add(t.getKey().getInput());
+        }
+
+        if (!Collections.disjoint(callAlphabet, innerAlphabet)) {
+            throw new IllegalStateException("Not a visibly push-down automaton (call alphabet=" + callAlphabet + ", inner alphabet=" + innerAlphabet + ", return alphabet=" + returnAlphabet + ")");
+        }
+
+        if (!Collections.disjoint(callAlphabet, returnAlphabet)) {
+            throw new IllegalStateException("Not a visibly push-down automaton (call alphabet=" + callAlphabet + ", inner alphabet=" + innerAlphabet + ", return alphabet=" + returnAlphabet + ")");
+        }
+
+        if (!Collections.disjoint(innerAlphabet, returnAlphabet)) {
+            throw new IllegalStateException("Not a visibly push-down automaton (call alphabet=" + callAlphabet + ", inner alphabet=" + innerAlphabet + ", return alphabet=" + returnAlphabet + ")");
+        }
+
+        DPDAState startingState = emptyState;
+
+        for (int init : npda.initialStates) {
+            startingState = startingState.add(npda.initialPushdownSymbol, init);
+        }
+
         todoStates.add(startingState);
         
         boolean modified = true;
                 DPDAState state = todoStates.remove(0);
 
                 //call:
-                for (char a : npda.alphabet) {
-                    assert a != Constants.UP; //should not currently happen
+                for (char a : callAlphabet) {
                     DPDAState targetState = emptyState;
                     DPDAPushDown targetPushdown = emptyPushDown;
 
 
                 //return for currently existing pushdownSymbols:
                 for (DPDAPushDown pdE : pushdownSymbols) {
-                    DPDAState stateE = state;
+                    for (char r : returnAlphabet) {
+                        DPDAState stateE = state;
+                        DPDAState targetState = emptyState;
+
+                        for (DPDAStateElement pq : stateE) {
+                            for (DPDAPushDownElement pd : pdE) {
+                                if (pd.getSecond() != pq.getPushdown()) continue;
+
+                                for (PDATarget t : npda.getTarget(new PDAKey(pq.getState(), r, pd.getSecond()))) {
+                                    targetState = targetState.add(pd.getFirst(), t.state);
+                                }
+                            }
+                        }
+
+                        transitionTable.put(new DPDAKey(stateE, r, pdE), new DPDATarget(targetState, null));
+
+                        if (states.add(targetState)) {
+                            todoStates.add(targetState);
+                            modified = true;
+                        }
+                    }
+                }
+
+                //internal:
+                for (char i : innerAlphabet) {
                     DPDAState targetState = emptyState;
 
-                    for (DPDAStateElement pq : stateE) {
-                        for (DPDAPushDownElement pd : pdE) {
-                            if (pd.getSecond() != pq.getPushdown()) continue;
-
-                            for (PDATarget t : npda.getTarget(new PDAKey(pq.getState(), Constants.UP, pd.getSecond()))) {
-                                targetState = targetState.add(pd.getFirst(), t.state);
-                            }
+                    for (DPDAStateElement pq : state) {
+                        for (PDATarget t : npda.getTarget(new PDAKey(pq.getState(), i, Constants.epsilon))) {
+                            assert t.pushDown == Constants.epsilon;
+                            targetState = targetState.add(pq.getPushdown(), t.state);
                         }
                     }
 
-                    transitionTable.put(new DPDAKey(stateE, Constants.UP, pdE), new DPDATarget(targetState, null));
+                    transitionTable.put(new DPDAKey(state, i, null), new DPDATarget(targetState, null));
 
                     if (states.add(targetState)) {
                         todoStates.add(targetState);
             //return for newly created pushdown symbols:
             while (!todoPushdown.isEmpty()) {
                 DPDAPushDown pdE = todoPushdown.remove(0);
-                for (DPDAState stateE : new HashSet<DPDAState>(states)) {
-                    DPDAState targetState = emptyState;
+                for (char r : returnAlphabet) {
+                    for (DPDAState stateE : new HashSet<DPDAState>(states)) {
+                        DPDAState targetState = emptyState;
 
-                    for (DPDAStateElement pq : stateE) {
-                        for (DPDAPushDownElement pd : pdE) {
-                            if (pd.getSecond() != pq.getPushdown()) continue;
+                        for (DPDAStateElement pq : stateE) {
+                            for (DPDAPushDownElement pd : pdE) {
+                                if (pd.getSecond() != pq.getPushdown()) continue;
 
-                            for (PDATarget t : npda.getTarget(new PDAKey(pq.getState(), Constants.UP, pd.getSecond()))) {
-                                targetState = targetState.add(pd.getFirst(), t.state);
+                                for (PDATarget t : npda.getTarget(new PDAKey(pq.getState(), r, pd.getSecond()))) {
+                                    targetState = targetState.add(pd.getFirst(), t.state);
+                                }
                             }
                         }
-                    }
 
-                    transitionTable.put(new DPDAKey(stateE, Constants.UP, pdE), new DPDATarget(targetState, null));
-                    
-                    if (states.add(targetState)) {
-                        todoStates.add(targetState);
-                        modified = true;
+                        transitionTable.put(new DPDAKey(stateE, r, pdE), new DPDATarget(targetState, null));
+
+                        if (states.add(targetState)) {
+                            todoStates.add(targetState);
+                            modified = true;
+                        }
                     }
                 }
             }
         return new DPDA(states, pushdownSymbols, startingState, transitionTable, finalStates);
     }
 
-    public List<Integer> match(TreeNode text) {
+    public List<Integer> match(Iterable<? extends Character> input) {
         List<Integer> result = new LinkedList<Integer>();
         DPDAState state = starting;
         int pos = 0;
         Stack<DPDAPushDown> pushDownStore = new Stack<DPDAPushDown>();
 
-        for (char c : text.serialize()) {
+        for (char c : input) {
             pos++;
 
             DPDATarget t = transitionTable.get(new DPDAKey(state, c, null));
     public int getPushDownSymbolsCount() {
         return pushDownSymbols.size();
     }
-    
+
+    @Override
+    public String toString() {
+        return transitionTable.toString();
+    }
+
     public static class DPDAKey {
         private final DPDAState state;
         private final char input;
     private static final class DPDAPushDown implements Iterable<DPDAPushDownElement> {
         private final DPDAPushDown empty;
         private final int maxPushdown;
+        private final Map<Integer, Integer> pushdown2Internal;
+        private final Map<Integer, Integer> internal2Pushdown;
         private final BitSet elements;
         private final Map<BitSet, DPDAPushDown> bitset2PushDown;
         
-        private DPDAPushDown(int maxPushdown) {
+        private DPDAPushDown(Set<Integer> pushdownSymbol) {
             this.empty = this;
-            this.maxPushdown = maxPushdown;
+            this.pushdown2Internal = new HashMap<Integer, Integer>();
+            this.internal2Pushdown = new HashMap<Integer, Integer>();
+            int currentInternal = 0;
+            for (Integer p : pushdownSymbol) {
+                pushdown2Internal.put(p, currentInternal);
+                internal2Pushdown.put(currentInternal, p);
+                currentInternal++;
+            }
+            this.maxPushdown = currentInternal;
             this.elements = new BitSet(0);
             this.bitset2PushDown = new HashMap<BitSet, DPDAPushDown>();
         }
         
         private DPDAPushDown(DPDAPushDown empty, BitSet elements) {
             this.empty = empty;
+            this.pushdown2Internal = empty.pushdown2Internal;
+            this.internal2Pushdown = empty.internal2Pushdown;
             this.maxPushdown = empty.maxPushdown;
             this.elements = elements;
             this.bitset2PushDown = null;
                     return bit >= 0;
                 }
                 public DPDAPushDownElement next() {
-                    DPDAPushDownElement res = new DPDAPushDownElement(bit / (maxPushdown + 1) - 1, (bit % (maxPushdown + 1)) - 1);
+                    int first = internal2Pushdown.get(bit / maxPushdown);
+                    int second = internal2Pushdown.get(bit % maxPushdown);
+                    DPDAPushDownElement res = new DPDAPushDownElement(first, second);
                     
                     bit = elements.nextSetBit(bit + 1);
                     
         }
         
         public DPDAPushDown add(int first, int second) {
-            int el = (first + 1) * (maxPushdown + 1) + second + 1;
+            int el = pushdown2Internal.get(first) * maxPushdown + pushdown2Internal.get(second);
             
             if (!elements.get(el)) {
                 BitSet bs = new BitSet(Math.max(elements.length(), el));
             return this;
         }
 
-        public static DPDAPushDown createEmpty(int maxPushdown) {
-            return new DPDAPushDown(maxPushdown);
+        public static DPDAPushDown createEmpty(Set<Integer> pushdownSymbols) {
+            pushdownSymbols = new HashSet<Integer>(pushdownSymbols);
+            pushdownSymbols.add(Constants.epsilon);
+            return new DPDAPushDown(pushdownSymbols);
         }
     }
 }

src/info/lahoda/papers/code/NPDA.java

 public final class NPDA {
     /*private*/ final Set<Integer> states;
     /*private*/ final Set<Integer> pushdownSymbols;
+    /*private*/ final Set<Integer> initialStates;
+    /*private*/ final Integer initialPushdownSymbol;
     /*private*/ final char[] alphabet;
     private final Map<PDAKey, Collection<PDATarget>> transitionTable;
     private final Set<Integer> finalStates;
     
-    public NPDA(Set<Integer> states, char[] alphabet, Set<Integer> pushdownSymbols, Map<PDAKey, Collection<PDATarget>> transitionTable, Set<Integer> finalStates) {
+    public NPDA(Set<Integer> states, char[] alphabet, Set<Integer> pushdownSymbols, Map<PDAKey, Collection<PDATarget>> transitionTable, Set<Integer> initialStates, Integer initialPushdownSymbol, Set<Integer> finalStates) {
         this.states = states;
         this.alphabet = alphabet;
         this.pushdownSymbols = pushdownSymbols;
         this.transitionTable = transitionTable;
+        this.initialStates = initialStates;
+        this.initialPushdownSymbol = initialPushdownSymbol;
         this.finalStates = finalStates;
     }
 

src/info/lahoda/papers/code/TPM.java

 
         add(transitionTable, new PDAKey(0, UP, nostate), new PDATarget(0, epsilon));
 
-        return new NPDA(states, alphabet, pushdownSymbols, transitionTable, Collections.singleton(currentState - 1));
+        pushdownSymbols.add(Constants.nostate);
+        
+        return new NPDA(states, alphabet, pushdownSymbols, transitionTable, Collections.singleton(0), Constants.nostate, Collections.singleton(currentState - 1));
     }
 
     private static void add(Map<PDAKey, Collection<PDATarget>> transitionTable, PDAKey PDAKey, PDATarget PDATarget) {

test/info/lahoda/papers/code/DPDATest.java

 package info.lahoda.papers.code;
 
 import java.util.Arrays;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
 import java.util.regex.Matcher;
 import java.util.regex.Pattern;
 import junit.framework.Assert;
 
         NPDA npda = TPM.create(pattern, '0', '1', '2');
         DPDA dpda = DPDA.create(npda);
-        Assert.assertEquals(Arrays.asList(15, 22, 33), dpda.match(text));
+        Assert.assertEquals(Arrays.asList(15, 22, 33), dpda.match(text.serialize()));
+    }
+
+    @Test
+    public void testDeterminization() {
+        Map<PDAKey, Collection<PDATarget>> transitionTable = new HashMap<PDAKey, Collection<PDATarget>>();
+
+        transitionTable.put(new PDAKey(0, 'x', Constants.epsilon), Arrays.asList(new PDATarget(0, Constants.epsilon), new PDATarget(1, Constants.epsilon)));
+        transitionTable.put(new PDAKey(0, 'd', Constants.epsilon), Arrays.asList(new PDATarget(0, 'd')));
+        transitionTable.put(new PDAKey(0, 'u', 'd'), Arrays.asList(new PDATarget(0, Constants.epsilon)));
+        
+        transitionTable.put(new PDAKey(1, 'd', Constants.epsilon), Arrays.asList(new PDATarget(2, 'd')));
+        transitionTable.put(new PDAKey(2, 'x', Constants.epsilon), Arrays.asList(new PDATarget(3, Constants.epsilon)));
+        transitionTable.put(new PDAKey(3, 'd', Constants.epsilon), Arrays.asList(new PDATarget(4, 'd')));
+        transitionTable.put(new PDAKey(4, 'x', Constants.epsilon), Arrays.asList(new PDATarget(5, Constants.epsilon)));
+        transitionTable.put(new PDAKey(5, 'u', 'd'), Arrays.asList(new PDATarget(6, Constants.epsilon)));
+        transitionTable.put(new PDAKey(6, 'x', Constants.epsilon), Arrays.asList(new PDATarget(7, Constants.epsilon)));
+        transitionTable.put(new PDAKey(7, 'u', 'd'), Arrays.asList(new PDATarget(8, Constants.epsilon)));
+        
+        NPDA npda = new NPDA(new HashSet<Integer>(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8)), new char[] {'x', 'd', 'u'}, new HashSet<Integer>(Arrays.asList(Constants.nostate, (int)'d')), transitionTable, new HashSet<Integer>(Arrays.asList(0)), Constants.nostate, new HashSet<Integer>(Arrays.asList(8)));
+
+        DPDA dpda = DPDA.create(npda);
+        List<Integer> result = dpda.match(Arrays.<Character>asList('d', 'd', 'x', 'd', 'x', 'd', 'x', 'u', 'x', 'u', 'u', 'u'));
+
+        Assert.assertEquals(Arrays.asList(10), result);
     }
 
 //    @Test
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.