構文解析ハンズオン（ https://github.com/kmizu/parser_hands_on ） JSONの構文解析

AbstractJSONParser.java

package com.github.kmizu.parser_hands_on.json;

import com.github.kmizu.parser_hands_on.AbstractParser;

public abstract class AbstractJSONParser extends AbstractParser<JSONNode> {
}

AbstractParser.java

package com.github.kmizu.parser_hands_on;

import java.util.Stack;

public abstract class AbstractParser<T> {
    protected int position;
    protected Stack<Integer> stack = new Stack<>();
    public void save() {
        stack.push(position);
    }
    public void restore() {
        position = stack.pop();
    }
    public abstract T parse(String input);
}

JSONNode.java

package com.github.kmizu.parser_hands_on.json;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class JSONNode {
    public static class Pair<A, B> {
        public final A _1;
        public final B _2;
        public Pair(A _1, B _2) {
            this._1 = _1;
            this._2 = _2;
        }

        @Override
        public int hashCode() {
            return _1.hashCode() + _2.hashCode();
        }

        @Override
        public boolean equals(Object obj) {
            if(!(obj instanceof Pair<?, ?>)) {
                return false;
            } else {
                Pair<A, B> that = (Pair<A, B>)obj;
                return _1.equals(that._1) && _2.equals(that._2);
            }
        }

        @Override
        public String toString() {
            return "(" + _1 + ", " + _2 + ")";
        }
    }

    public static class JSONString extends JSONNode {
        public final String value;
        public JSONString(String value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object obj) {
            if(!(obj instanceof JSONString)) {
                return false;
            } else {
                JSONString that = (JSONString)obj;
                return value.equals(that.value);
            }
        }

        @Override
        public String toString() {
            return "\"" + value.toString() + "\"";
        }
    }
    public static class JSONBoolean extends JSONNode {
        public final boolean value;
        public JSONBoolean(boolean value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object obj) {
            if(!(obj instanceof JSONBoolean)) {
                return false;
            } else {
                JSONBoolean that = (JSONBoolean)obj;
                return value == that.value;
            }
        }

        @Override
        public String toString() {
            return "" + value;
        }
    }
    public static class JSONNumber extends JSONNode {
        public final double value;
        public JSONNumber(double value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object obj) {
            if(!(obj instanceof JSONNumber)) {
                return false;
            } else {
                JSONNumber that = (JSONNumber)obj;
                return value == that.value;
            }
        }

        @Override
        public String toString() {
            return "" + value;
        }
    }
    public static class JSONNull extends JSONNode {
        /**
         * nullの構文木のインスタンスは一つだけでいい（位置情報を持ちたい場合は別）
         */
        private static final JSONNull instance = new JSONNull();
        private JSONNull() {}
        public static JSONNull getInstance() {
            return instance;
        }

        @Override
        public int hashCode() {
            return super.hashCode();
        }

        @Override
        public boolean equals(Object obj) {
            return super.equals(obj);
        }

        @Override
        public String toString() {
            return "null";
        }
    }
    public static class JSONObject extends JSONNode {
        public final Map<String, JSONNode> properties;
        public JSONObject(Map<String, JSONNode> properties) {
            this.properties = properties;
        }

        @Override
        public boolean equals(Object obj) {
            if(!(obj instanceof JSONObject)) {
                return false;
            } else {
                JSONObject that = (JSONObject)obj;
                return properties.equals(that.properties);
            }
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("{\n");
            if(properties.size() != 0) {
                for(Map.Entry<String, JSONNode> p : properties.entrySet()) {
                    builder.append(p.getKey());
                    builder.append(" : ");
                    builder.append(p.getValue());
                }
            }
            builder.append("}\n");
            return new String(builder);
        }
    }
    public static class JSONArray extends JSONNode {
        public final List<? extends JSONNode> elements;
        public JSONArray(List<JSONNode> elements) {
            this.elements = elements;
        }

        @Override
        public boolean equals(Object obj) {
            if(!(obj instanceof JSONArray)) {
                return false;
            } else {
                JSONArray that = (JSONArray) obj;
                return elements.equals(that.elements);
            }
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("[");
            if(elements.size() != 0) {
                builder.append(elements.get(0).toString());
                for(JSONNode e : elements.subList(1, elements.size())) {
                    builder.append(", ");
                    builder.append(e.toString());
                }
            }
            builder.append("]");
            return new String(builder);
        }
    }

    public static JSONObject jobject(Pair<String, JSONNode>... pairs) {
        Map<String, JSONNode> properties = new HashMap<>();
        for(Pair<String, JSONNode> p:pairs) {
            properties.put(p._1, p._2);
        }
        return new JSONObject(properties);
    }

    public static JSONArray jarray(JSONNode... elements) {
        List<JSONNode> es = new ArrayList<>();
        for(JSONNode e:elements) {
            es.add(e);
        }
        return new JSONArray(es);
    }

    public static JSONNull jnull() {
        return JSONNull.getInstance();
    }

    public static JSONNumber jnumber(double value) {
        return new JSONNumber(value);
    }

    public static JSONBoolean jboolean(boolean value) {
        return new JSONBoolean(value);
    }

    public static JSONString jstring(String value) {
        return new JSONString(value);
    }

    public static Pair<String, JSONNode> property(String key, JSONNode value) {
        return new Pair<>(key ,value);
    }

    public static Pair<String, JSONNode> p(String key, JSONNode value) {
        return property(key, value);
    }
}

MyJSONParser.java

package com.github.kmizu.parser_hands_on.my_parser;

import com.github.kmizu.parser_hands_on.ParseFailure;
import com.github.kmizu.parser_hands_on.json.AbstractJSONParser;
import com.github.kmizu.parser_hands_on.json.JSONNode;

import java.util.*;

/**
 * jvalue = jobject | jarray | jboolean | jnull | jstring | jnumber;
 * jobject = '{' [jstring ':' jvalue {',' jstring ':' jvalue}] '}';
 * jarray = '[' jvalue {',' jvalue} ']';
 * jboolean = 'true' | 'false';
 * jnull = 'null';
 * jstring = '"' ... '"';
 * jnumber = integer;
 */
public class MyJSONParser extends AbstractJSONParser {
    private String input;

    @Override
    public JSONNode parse(String input) {
        this.input = input;
        this.position = 0;
        this.stack = new Stack<>();
        JSONNode result = jvalue();

        if (input.length() != position) {
            throw new ParseFailure("unconsumed input remains: " + input.substring(position));
        } else {
            return result;
        }
    }

    public JSONNode jvalue() {
        try {
            save();
            return jobject();
        } catch (ParseFailure e) {
            restore();
        }
        try {
            save();
            return jarray();
        } catch (ParseFailure e) {
            restore();
        }
        try {
            save();
            return jboolean();
        } catch (ParseFailure e) {
            restore();
        }
        try {
            save();
            return jnull();
        } catch (ParseFailure e) {
            restore();
        }
        try {
            save();
            return jstring();
        } catch (ParseFailure e) {
            restore();

            save();
            return jnumber();
        }
    }

    public JSONNode.JSONObject jobject() {
        Map<String, JSONNode> objectMap = new HashMap<>();

        save();
        accept('{');

        try {
            save();
            JSONNode.JSONString key = jstring();

            save();
            accept(':');

            save();
            objectMap.put(key.value, jvalue());

            while(true) {
                save();
                accept(',');

                save();
                key = jstring();

                save();
                accept(':');

                save();
                objectMap.put(key.value, jvalue());
            }
        } catch (ParseFailure e) {
            restore();
            accept('}');
            return new JSONNode.JSONObject(objectMap);
        }
    }

    public JSONNode.JSONArray jarray() {
        List<JSONNode> array = new ArrayList<>();

        save();
        accept('[');

        try {
            array.add(jvalue());

            while(true) {
                save();
                accept(',');

                save();
                array.add(jvalue());
            }
        } catch (ParseFailure e) {
            restore();
            accept(']');
            return new JSONNode.JSONArray(array);
        }
    }

    public JSONNode.JSONBoolean jboolean() {
        try {
            accept('t');
            accept('r');
            accept('u');
            accept('e');
            return new JSONNode.JSONBoolean(true);
        } catch (ParseFailure e) {
            accept('f');
            accept('a');
            accept('l');
            accept('s');
            accept('e');
            return new JSONNode.JSONBoolean(false);
        }
    }

    public JSONNode.JSONNull jnull() {
        accept('n');
        accept('u');
        accept('l');
        accept('l');
        return JSONNode.JSONNull.getInstance();
    }

    public JSONNode.JSONString jstring() {
        StringBuilder sb = new StringBuilder();
        accept('"');
        try {
            while (true) {
                sb.append(acceptAll());
            }
        } catch (ParseFailure e) {
            accept('"');
        }
        return JSONNode.jstring(sb.toString());
    }

    public JSONNode.JSONNumber jnumber() {
        Integer integer = integer();
        return new JSONNode.JSONNumber(integer);
    }

    public JSONNode computeObject(JSONNode.JSONString lhs, JSONNode rhs) {
        Map<String, JSONNode> m = new HashMap<>();
        m.put(lhs.toString(), rhs);
        return new JSONNode.JSONObject(m);
    }

    public Integer integer() {
        Integer result;
        try {
            save();
            return zero();
        } catch (ParseFailure e) {
            restore();

            result = digitFirst();

            while (true) { // {digitRest}
                try {
                    save();
                    result = compute(result, digitRest());
                } catch (ParseFailure e1) {
                    restore();
                    return result;
                }
            }
        }
    }

    private char accept(char x) {
        if (input.length() - 1 < position) {
            throw new ParseFailure("current position is over range");
        }
        char c = input.charAt(position);
        if (c == x) {
            position++;
            return x;
        } else {
            throw new ParseFailure("current character is not " + c);
        }
    }

    private char acceptAll() {
        if (input.length() - 1 < position) {
            throw new ParseFailure("current position is over range");
        }
        char c = input.charAt(position);
        if (c != '"') {
            position++;
            return c;
        } else {
            throw new ParseFailure("current character is \"");
        }
    }

    private Integer zero() {
        if (input.length() - 1 < position) {
            throw new ParseFailure("current position is over range");
        }

        char c = input.charAt(position);
        int x = c - '0';
        if (x == 0) {
            position++;
            return 0;
        } else {
            throw new ParseFailure("zero should be 0");
        }
    }

    private Integer digitFirst() {
        if (input.length() - 1 < position) {
            throw new ParseFailure("current position is over range");
        }

        char c = input.charAt(position);
        int x = c - '0';
        if (x == 0) {
            throw new ParseFailure("digitFirst should not 0");
        }
        if (1 <= x && x <= 9) {
            position++;
            return x;
        } else {
            throw new ParseFailure("input contains no digit character");
        }
    }

    private Integer digitRest() {
        if (input.length() - 1 < position) {
            throw new ParseFailure("current position is over range");
        }

        char c = input.charAt(position);
        int x = c - '0';
        if (0 <= x && x <= 9) {
            position++;
            return x;
        } else {
            throw new ParseFailure("input contains no digit character");
        }
    }

    private Integer compute(Integer result, int parseResult) {
        return result * 10 + parseResult;
    }
}