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

AbstractExpressionParser.java

package com.github.kmizu.parser_hands_on.expression;

import com.github.kmizu.parser_hands_on.AbstractParser;

public abstract class AbstractExpressionParser extends  AbstractParser<ExpressionNode> {
}

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);
}

ExpressionNode.java

package com.github.kmizu.parser_hands_on.expression;

/*
 * 算術式の抽象構文木を表すクラス群
 */
public class ExpressionNode {
    public ExpressionNode add(ExpressionNode that) {
        return new Addition(this, that);
    }
    public ExpressionNode add(int that) {
        return new Addition(this, integer(that));
    }
    public ExpressionNode subtract(ExpressionNode that) {
        return new Subtraction(this, that);
    }
    public ExpressionNode subtract(int that) {
        return new Subtraction(this, integer(that));
    }
    public ExpressionNode multiply(ExpressionNode that) {
        return new Multiplication(this, that);
    }
    public ExpressionNode multiply(int that) {
        return new Multiplication(this, integer(that));
    }
    public ExpressionNode divide(ExpressionNode that) {
        return new Division(this, that);
    }
    public ExpressionNode divide(int that) {
        return new Division(this, integer(that));
    }
    public static class Addition extends ExpressionNode {
        public final ExpressionNode lhs, rhs;
        public Addition(ExpressionNode lhs, ExpressionNode rhs) {
            this.lhs = lhs;
            this.rhs = rhs;
        }

        @Override
        public boolean equals(Object that) {
            if(!(that instanceof Addition)) return false;
            Addition addition = (Addition)that;
            return lhs.equals(addition.lhs) && rhs.equals(addition.rhs);
        }

        @Override
        public String toString() {
            return "Addition(" + lhs + ", " + rhs + ")";
        }
    }
    public static class Subtraction extends ExpressionNode {
        public final ExpressionNode lhs, rhs;
        public Subtraction(ExpressionNode lhs, ExpressionNode rhs) {
            this.lhs = lhs;
            this.rhs = rhs;
        }

        @Override
        public boolean equals(Object that) {
            if(!(that instanceof Subtraction)) return false;
            Subtraction subtraction = (Subtraction)that;
            return lhs.equals(subtraction.lhs) && rhs.equals(subtraction.rhs);
        }

        @Override
        public String toString() {
            return "Subtraction(" + lhs + ", " + rhs + ")";
        }
    }
    public static class Multiplication extends ExpressionNode {
        public final ExpressionNode lhs, rhs;
        public Multiplication(ExpressionNode lhs, ExpressionNode rhs) {
            this.lhs = lhs;
            this.rhs = rhs;
        }

        @Override
        public boolean equals(Object that) {
            if(!(that instanceof Multiplication)) return false;
            Multiplication multiplication = (Multiplication)that;
            return lhs.equals(multiplication.lhs) && rhs.equals(multiplication.rhs);
        }

        @Override
        public String toString() {
            return "Multiplication(" + lhs + ", " + rhs + ")";
        }
    }
    public static class Division extends ExpressionNode {
        public final ExpressionNode lhs, rhs;
        public Division(ExpressionNode lhs, ExpressionNode rhs) {
            this.lhs = lhs;
            this.rhs = rhs;
        }

        @Override
        public boolean equals(Object that) {
            if(!(that instanceof Division)) return false;
            Division division = (Division) that;
            return lhs.equals(division.lhs) && rhs.equals(division.rhs);
        }

        @Override
        public String toString() {
            return "Division(" + lhs + ", " + rhs + ")";
        }
    }
    public static class ValueNode extends ExpressionNode {
        public final int value;
        public ValueNode(int value ) {
            this.value = value;
        }

        @Override
        public boolean equals(Object that) {
            if(that == null) return false;
            if(!(that instanceof ValueNode)) return false;
            ValueNode thatNode = (ValueNode)that;
            return this.value == thatNode.value;
        }

        @Override
        public int hashCode() {
            return value;
        }

        @Override
        public String toString() {
            return "ValueNode(" + value + ")";
        }
    }

    public static ValueNode integer(int value) {
        return new ValueNode(value);
    }
}

MyExpressionParser.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.expression.AbstractExpressionParser;
import com.github.kmizu.parser_hands_on.expression.ExpressionNode;

import java.util.Stack;

/**
 * expression = multitive {'+' multitive | '-' multitive};
 * multitive = primary {'*' primary | '/' primary};
 * primary = '(' expression ')' | integer;
 */
public class MyExpressionParser extends AbstractExpressionParser {
    private String input;

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

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

    public ExpressionNode expression() {
        ExpressionNode result = multitive();
        while(true) {
            try {
                save();
                accept('+');

                save();
                result = compute(result, '+', multitive());
                continue;
            } catch (ParseFailure e1) {
                restore();
            }
            try {
                save();
                accept('-');

                save();
                result = compute(result, '-', multitive());
                continue;
            } catch (ParseFailure e1) {
                restore();
            }
            return result;
        }
    }

    public ExpressionNode multitive() {
        ExpressionNode result = primary();
        while(true) {
            try {
                save();
                accept('*');

                save();
                result = compute(result, '*', primary());
                continue;
            } catch (ParseFailure e1) {
                restore();
            }
            try {
                save();
                accept('/');

                save();
                result = compute(result, '/', primary());
                continue;
            } catch (ParseFailure e1) {
                restore();
            }
            return result;
        }
    }

    public ExpressionNode primary() {
        ExpressionNode result;
        try {
            save();
            accept('(');
            result = expression();
            accept(')');
            return result;
        } catch (ParseFailure e) {
            restore();

            save();
            Integer integerResult = integer();
            result = new ExpressionNode.ValueNode(integerResult);
            return result;
        }
    }

    public ExpressionNode compute(ExpressionNode lhs, char operator, ExpressionNode rhs) {
        switch (operator) {
            case '+':
                return new ExpressionNode.Addition(lhs, rhs);
            case '-':
                return new ExpressionNode.Subtraction(lhs, rhs);
            case '*':
                return new ExpressionNode.Multiplication(lhs, rhs);
            case '/':
                return new ExpressionNode.Division(lhs, rhs);
        }
        throw new ParseFailure("unsupported operator");
    }

    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 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;
    }
}