GitHub PullRequestReviewCommentEvent at 2014-03-28 17:20:37
Repository: k
Actor: dwightguth
Payload: {"comment":{"url":"https://api.github.com/repos/kframework/k/pulls/comments/11075880","id":11075880,"diff_hunk":"@@ -0,0 +1,466 @@\n+package org.kframework.parser.concrete2;\n+\n+import java.io.Serializable;\n+import java.util.ArrayList;\n+import java.util.Arrays;\n+import java.util.HashMap;\n+import java.util.HashSet;\n+import java.util.List;\n+import java.util.Map;\n+import java.util.Map.Entry;\n+import java.util.Set;\n+import java.util.regex.Matcher;\n+import java.util.regex.Pattern;\n+\n+import org.kframework.kil.KSorts;\n+import org.kframework.parser.concrete2.Grammar.State.OrderingInfo;\n+import org.kframework.parser.concrete2.Rule.DeleteRule;\n+\n+\n+/**\n+ * The classes used by the parser to represent the internal structure of a grammar.\n+ * A grammar consists of NFAs generated for each non-terminal from a EBNF style grammar\n+ * (in this case the K syntax declarations).\n+ * The main object is the {@link NonTerminal}, containing a unique {@link NonTerminalId},\n+ * and two states: entry and exit.\n+ *\n+ * There are five main types of states: {@link EntryState}, {@link NonTerminalState},\n+ * {@link PrimitiveState}, @{@link RuleState} and {@link ExitState}.\n+ * The first four extend {@link NextableState} in order to make accommodate connections\n+ * between the sates. ExitState signifies the end of a NonTerminal so it doesn't have a 'next' field.\n+ *\n+ * Each {@link NonTerminal} contains exactly one {@link EntryState}\n+ * and one {@link ExitState}. Depending on the grammar it may contain\n+ * multiple {@link NonTerminalState}, {@link PrimitiveState} or {@link RuleState}.\n+ *\n+ * Example of a NonTerminal NFA structure:\n+ * E ::= E \"+\" E\n+ *     | E \"*\" E\n+ *     | {E, \",\"}+\n+ *\n+ *     |->[E]-->(\"+\")--->[E]--|\n+ *     |                      |\n+ * (|--|->[E]-->(\"*\")--->[E]--|->|)\n+ *     |                      |\n+ *     |   |------------------|\n+ *     |->[E]-->(\",\")\n+ *         ^------|\n+ *\n+ * (| - EntryState\n+ * |) - ExitState\n+ * [] - NonTerminalState\n+ * () - PrimitiveState\n+ * <> - RuleState\n+ *\n+ * NOTE: compile() must be called on a grammar before it is handed to the parser\n+ */\n+public class Grammar implements Serializable {\n+\n+    /// The set of \"root\" NonTerminals\n+    private Map<NonTerminalId, NonTerminal> startNonTerminals = new HashMap<>();\n+\n+    public boolean add(NonTerminal newNT) {\n+        if (startNonTerminals.containsKey(newNT.nonTerminalId)) {\n+            return false;\n+        } else {\n+            startNonTerminals.put(newNT.nonTerminalId, newNT);\n+            return true;\n+        }\n+    }\n+\n+    public Set<NonTerminal> getAllNonTerminals() {\n+        return getNonTerminalCallers().keySet();\n+    }\n+\n+    public NonTerminal get(String ntSymbol) {\n+        return startNonTerminals.get(new NonTerminalId(ntSymbol));\n+    }\n+\n+    public Map<NonTerminal, Set<NonTerminalState>> getNonTerminalCallers() {\n+        Map<NonTerminal, Set<NonTerminalState>> reachableNonTerminals = new HashMap<>();\n+        Set<State> visited = new HashSet<>();\n+        for (NonTerminal nt : startNonTerminals.values()) {\n+            if (!reachableNonTerminals.containsKey(nt)) {\n+                // if it is the start symbol it won't have any callers, so add it here first\n+                reachableNonTerminals.put(nt, new HashSet<NonTerminalState>());\n+            }\n+            collectNTCallers(nt.entryState, visited, reachableNonTerminals);\n+        }\n+        return reachableNonTerminals;\n+    }\n+\n+    public void addWhiteSpace() {\n+        // TODO: Move out of grammar and into a post processing of KSyntax\n+        // TODO: Put whitespace at start of NT so we don't need the extra NT names\n+        // TODO: (once we don't need extra NT names), make nt.nonTerminalId be final\n+        // TODO: make whitespace able to return comments somehow\n+        // create a NonTerminal which parses a list of whitespace characters.\n+        // the NT is a star list that has 3 branches\n+        // 1. whitespace, 2. single line comment, 3. multiple lines comment\n+        Pattern pattern = Pattern.compile(\"((/\\\\*([^*]|[\\\\r\\\\n]|(\\\\*+([^*/]|[\\\\r\\\\n])))*\\\\*+/)|(//.*)|([ \\n\\r\\t]))*\");\n+        int seed = 0;\n+\n+        // create a whitespace PrimitiveState after every every terminal that can match a character\n+        for (NonTerminal nonTerminal : getAllNonTerminals()) {\n+            for (State s : nonTerminal.getReachableStates()) {\n+                if (s instanceof PrimitiveState) {\n+                    PrimitiveState ps = ((PrimitiveState) s);\n+                    PrimitiveState whitespace = new RegExState(\n+                        new StateId(\"whitespace\" + seed++), s.nt, pattern, KSorts.K);\n+                    RuleState deleteToken = new RuleState(\n+                        new StateId(\"whitespace-D-\" + seed++), s.nt, new DeleteRule(1, true));\n+                    whitespace.next.add(deleteToken);\n+                    deleteToken.next.addAll(ps.next);\n+                    ps.next.clear();\n+                    ps.next.add(whitespace);\n+                }\n+            }\n+        }\n+        // create a new state for every start state that can have whitespace at the beginning\n+        for (Entry<NonTerminalId, NonTerminal> entry : startNonTerminals.entrySet()) {\n+            // create a new NT that calls the the startNT and has whitespace available at the beginning.\n+            // the NonTerminalId is copied into the new NT to keep the reference in the Map\n+            // the startNT gets another Id to eliminate confusion.\n+            NonTerminal nt = entry.getValue();\n+            NonTerminal whiteStartNt = new NonTerminal(new NonTerminalId(nt.nonTerminalId.name));\n+            PrimitiveState whitespace = new RegExState(\n+                new StateId(\"whitespace-\" + seed++), whiteStartNt, pattern, KSorts.K);\n+            NonTerminalState nts = new NonTerminalState(\n+                new StateId(\"white-calls-\" + nt.nonTerminalId.name), whiteStartNt, nt, false);\n+            RuleState deleteToken = new RuleState(\n+                new StateId(\"whitespace-D-\" + seed++), whiteStartNt, new DeleteRule(1, true));\n+            nt.nonTerminalId = new NonTerminalId(nt.nonTerminalId.name + \"-afterWhite\");\n+            whiteStartNt.entryState.next.add(whitespace);\n+            whitespace.next.add(deleteToken);\n+            deleteToken.next.add(nts);\n+            nts.next.add(whiteStartNt.exitState);\n+            entry.setValue(whiteStartNt);\n+        }\n+    }\n+\n+    public void compile() {\n+        // 1. get all nullable states\n+        Nullability nullability = new Nullability(this);\n+\n+        // 2. make an array with all the states\n+        List<State> allStates = new ArrayList<>();\n+        for (NonTerminal nonTerminal : getAllNonTerminals()) {\n+            allStates.addAll(nonTerminal.getReachableStates());\n+        }\n+        // 3. prepare the inverse relation\n+        Map<State, Integer> inverseAllStates = new HashMap<>();\n+        for (int i = 0; i < allStates.size(); i++) {\n+            inverseAllStates.put(allStates.get(i), i);\n+        }\n+\n+        // prepare the Tarjan input data\n+        // TODO: java doesn't allow arrays of generic types so we need to move from arrays to ArrayList\n+        @SuppressWarnings(\"unchecked\")\n+        List<Integer>[] predecessors = new List[allStates.size()];\n+        for (int i = 0; i < predecessors.length; i++) {\n+            predecessors[i] = new ArrayList<>();\n+        }\n+\n+        for (State s : allStates) {\n+            if (s instanceof NextableState) {\n+                NextableState ns = (NextableState) s;\n+                for (State nextState : ns.next) {\n+                    if (nullability.isNullable(nextState)) {\n+                        predecessors[inverseAllStates.get(nextState)].add(inverseAllStates.get(s));\n+                    }\n+                    if (nextState instanceof NonTerminalState) {\n+                        EntryState es = ((NonTerminalState) nextState).child.entryState;\n+                        predecessors[inverseAllStates.get(es)].add(inverseAllStates.get(s));\n+                    }\n+                }\n+                if (ns instanceof NonTerminalState) {\n+                    ExitState es = ((NonTerminalState) ns).child.exitState;\n+                    predecessors[inverseAllStates.get(es)].add(inverseAllStates.get(s));\n+                }\n+            }\n+        }\n+\n+        List<List<Integer>> components = new SCCTarjan().scc(predecessors);\n+\n+        // assign the OrderingInfo for states\n+        for (int i = 0; i < components.size(); i++) {\n+            for (int j : components.get(i)) {\n+                State state = allStates.get(j);\n+                state.orderingInfo = new OrderingInfo(i);\n+            }\n+        }\n+    }\n+\n+    /**\n+     * Recursive DFS that traverses all the states and returns a set of all reachable {@Link NonTerminal}.\n+     * @param start The state from which to run the collector.\n+     * @param visited Start with an empty Set<State>. Used as intermediate data.\n+     * @return A set of all reachable {@Link NonTerminal}.\n+     */\n+    private static void collectNTCallers(State start, Set<State> visited,\n+        Map<NonTerminal, Set<NonTerminalState>> reachableNonTerminals) {\n+        if (!visited.contains(start)) {\n+            visited.add(start);\n+            if (start instanceof NextableState) {\n+                NextableState ns = (NextableState) start;\n+                for (State st : ns.next) {\n+                    if (st instanceof NonTerminalState) {\n+                        NonTerminalState nts = (NonTerminalState) st;\n+                        if (!reachableNonTerminals.containsKey(nts.child)) {\n+                            reachableNonTerminals.put(\n+                                nts.child, new HashSet<NonTerminalState>(Arrays.asList(nts)));\n+                        }\n+                        reachableNonTerminals.get(nts.child).add(nts);\n+                        collectNTCallers(((NonTerminalState) st).child.entryState,\n+                            visited, reachableNonTerminals);\n+                    }\n+                    collectNTCallers(st, visited, reachableNonTerminals);\n+                }\n+            }\n+        }\n+    }\n+\n+    ///////////////////\n+    // Inner Classes //\n+    ///////////////////\n+\n+    // Positions are 'int' because CharSequence uses 'int' // Position in the text\n+    public static class StateId implements Comparable<StateId>, Serializable { // Used only by rules\n+        public final String name;\n+        public StateId(String name) { this.name = name; }\n+        public int compareTo(StateId that) { return this.name.compareTo(that.name); }\n+\n+        @Override\n+        public boolean equals(Object o) {\n+            if (this == o) return true;\n+            if (o == null || getClass() != o.getClass()) return false;\n+\n+            StateId stateId = (StateId) o;\n+\n+            if (!name.equals(stateId.name)) return false;\n+\n+            return true;\n+        }\n+\n+        @Override\n+        public int hashCode() {\n+            return name.hashCode();\n+        }\n+    }\n+\n+    public static class NonTerminalId implements Comparable<NonTerminalId>, Serializable {\n+        public final String name;\n+        public NonTerminalId(String name) { this.name = name; }\n+        public int compareTo(NonTerminalId that) { return this.name.compareTo(that.name); }\n+\n+        @Override\n+        public boolean equals(Object o) {\n+            if (this == o) return true;\n+            if (o == null || getClass() != o.getClass()) return false;\n+\n+            NonTerminalId that = (NonTerminalId) o;\n+\n+            if (!name.equals(that.name)) return false;\n+\n+            return true;\n+        }\n+\n+        @Override\n+        public int hashCode() {\n+            return name.hashCode();\n+        }\n+    }\n+\n+    public static class NonTerminal implements Comparable<NonTerminal>, Serializable {\n+        public NonTerminalId nonTerminalId; // TODO: make final once whitespace is refactored\n+        public final EntryState entryState;\n+        public final ExitState exitState;\n+        private final Set<NextableState> intermediaryStates = new HashSet<>();\n+        public final OrderingInfo orderingInfo = null; // TODO: unused until we fix lookahead\n+\n+        static class OrderingInfo implements Comparable<OrderingInfo> {\n+            final int key;\n+            public OrderingInfo(int key) { this.key = key; }\n+            public int compareTo(OrderingInfo that) { return Integer.compare(this.key, that.key); }\n+        }\n+\n+        public NonTerminal(NonTerminalId nonTerminalId,\n+                           StateId entryStateId,\n+                           StateId exitStateId) {\n+            this.nonTerminalId = nonTerminalId;\n+            this.entryState = new EntryState(entryStateId, this);\n+            this.exitState = new ExitState(exitStateId, this);\n+        }\n+\n+        public NonTerminal(NonTerminalId nonTerminalId) {\n+            this.nonTerminalId = nonTerminalId;\n+            this.entryState = new EntryState(new StateId(nonTerminalId.name + \"-entry\"), this);\n+            this.exitState = new ExitState(new StateId(nonTerminalId.name + \"-exit\"), this);\n+        }\n+\n+        public int compareTo(NonTerminal that) {\n+            return this.nonTerminalId.compareTo(that.nonTerminalId);\n+        }\n+\n+        public Set<NextableState> getIntermediaryStates() {\n+            return intermediaryStates;\n+        }\n+\n+        public Set<State> getReachableStates() {\n+            Set<State> states = new HashSet<>();\n+            states.add(this.exitState);\n+            states.add(this.entryState);\n+            // TODO: replace this with a recursive collector\n+            states.addAll(this.intermediaryStates);\n+            return states;\n+        }\n+\n+        @Override\n+        public boolean equals(Object o) {\n+            if (this == o) return true;\n+            if (o == null || getClass() != o.getClass()) return false;\n+\n+            NonTerminal that = (NonTerminal) o;\n+\n+            if (!nonTerminalId.equals(that.nonTerminalId)) return false;\n+\n+            return true;\n+        }\n+\n+        @Override\n+        public int hashCode() {\n+            return nonTerminalId.hashCode();\n+        }\n+    }\n+\n+    public abstract static class State implements Comparable<State>, Serializable {\n+        public final StateId stateId;\n+        public final NonTerminal nt;\n+        OrderingInfo orderingInfo = null;\n+\n+        static class OrderingInfo implements Comparable<OrderingInfo>, Serializable {\n+            final int key;\n+            public OrderingInfo(int key) { this.key = key; }\n+            public int compareTo(OrderingInfo that) { return Integer.compare(this.key, that.key); }\n+        }\n+\n+        public State(StateId stateId, NonTerminal nt) {\n+            this.stateId = stateId; this.nt = nt;\n+        }\n+\n+        public int compareTo(State that) { return this.stateId.compareTo(that.stateId); }\n+\n+        @Override\n+        public boolean equals(Object o) {\n+            if (this == o) return true;\n+            if (o == null || getClass() != o.getClass()) return false;\n+\n+            State state = (State) o;\n+\n+            if (!nt.equals(state.nt)) return false;\n+            if (!stateId.equals(state.stateId)) return false;\n+\n+            return true;\n+        }\n+\n+        @Override\n+        public int hashCode() {\n+            int result = stateId.hashCode();\n+            //result = 31 * result + nt.hashCode();\n+            return result;\n+        }\n+    }\n+\n+    public static class ExitState extends State {\n+        public ExitState(StateId stateId, NonTerminal nt) {\n+            super(stateId, nt);\n+        }\n+    }\n+\n+    public abstract static class NextableState extends State {\n+        public final Set<State> next = new HashSet<State>() {\n+            @Override\n+            public boolean add(State s) {\n+                assert s.nt == NextableState.this.nt :\n+                    \"States \" + NextableState.this.stateId.name + \" and \" +\n+                        s.stateId.name + \" are not in the same NonTerminal.\";\n+                return super.add(s);\n+            }\n+        };\n+        NextableState(StateId stateId, NonTerminal nt, boolean intermediary) {\n+            super(stateId, nt);\n+            if (intermediary) { nt.intermediaryStates.add(this); }\n+        }\n+    }\n+\n+    public static class EntryState extends NextableState {\n+        public EntryState(StateId stateId, NonTerminal nt) {","path":"src/javasources/KTool/src/org/kframework/parser/concrete2/Grammar.java","position":397,"original_position":397,"commit_id":"4d42b4aba40b79247c50aa4578fec55c3995f9b9","original_commit_id":"4d42b4aba40b79247c50aa4578fec55c3995f9b9","user":{"login":"dwightguth","id":5104541,"avatar_url":"https://avatars.githubusercontent.com/u/5104541?","gravatar_id":"183661b9191d8435d50f2a69f188b2da","url":"https://api.github.com/users/dwightguth","html_url":"https://github.com/dwightguth","followers_url":"https://api.github.com/users/dwightguth/followers","following_url":"https://api.github.com/users/dwightguth/following{/other_user}","gists_url":"https://api.github.com/users/dwightguth/gists{/gist_id}","starred_url":"https://api.github.com/users/dwightguth/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dwightguth/subscriptions","organizations_url":"https://api.github.com/users/dwightguth/orgs","repos_url":"https://api.github.com/users/dwightguth/repos","events_url":"https://api.github.com/users/dwightguth/events{/privacy}","received_events_url":"https://api.github.com/users/dwightguth/received_events","type":"User","site_admin":false},"body":"this should probably be package-private","created_at":"2014-03-28T17:20:37Z","updated_at":"2014-03-28T17:20:37Z","html_url":"https://github.com/kframework/k/pull/318#discussion_r11075880","pull_request_url":"https://api.github.com/repos/kframework/k/pulls/318","_links":{"self":{"href":"https://api.github.com/repos/kframework/k/pulls/comments/11075880"},"html":{"href":"https://github.com/kframework/k/pull/318#discussion_r11075880"},"pull_request":{"href":"https://api.github.com/repos/kframework/k/pulls/318"}}}}