Calc.java

package com.example.calc;

import java.lang.annotation.Annotation;
import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.List;

public class Calc extends Grammar {
	public static void main(String[] args) throws ParseException {
		System.out.println(eval("1+2*3*4+5-6/(7+8-9)"));
	}
	private static Integer eval(String source) throws ParseException {
		Parser<Integer> expr = new Calc().ref("expr");
		Parsed<Seq2<Integer, Eof>> result = seq(expr, eof()).parse(source);
		return result.getValue().getValue1();
	}
	@ParserRule
	public Parser<Integer> expr(@ParserRef("term") Parser<Integer> term,
			@ParserRef("addition") BinaryOperator<Integer> addition,
			@ParserRef("subtract") BinaryOperator<Integer> subtract) {
		return term.infixl(chr('+').bind(addition).or(chr('-').bind(subtract)));
	}
	@ParserRule
	public Parser<Integer> term(@ParserRef("primary") Parser<Integer> primary,
			@ParserRef("multiplication") BinaryOperator<Integer> multiplication,
			@ParserRef("division") BinaryOperator<Integer> division,
			@ParserRef("modulo") BinaryOperator<Integer> modulo) {
		return primary.infixl(chr('*').bind(multiplication)
				.or(chr('/').bind(division)).or(chr('%').bind(modulo)));
	}
	@ParserRule
	public Parser<Integer> primary(@ParserRef("number") Parser<Integer> number,
			@ParserRef("expr") Parser<Integer> expr) {
		return number.or(expr.enclosedBy(chr('('), chr(')')));
	}
	@ParserRule
	public Parser<List<Character>> number() {
		return notPred(seq(chr('0'), notPred(chr('0'), empty())), range('0', '9').oneOrMore());
	}
	@ParserAction
	public Integer number(List<Character> digits) {
		int result = 0;
		for (char digit : digits) {
			result = result * 10 + digit - '0';
		}
		return result;
	}
	@ParserBinaryOperator
	public Integer addition(Integer left, Integer right) {
		return left + right;
	}
	@ParserBinaryOperator
	public Integer subtract(Integer left, Integer right) {
		return left - right;
	}
	@ParserBinaryOperator
	public Integer multiplication(Integer left, Integer right) {
		return left * right;
	}
	@ParserBinaryOperator
	public Integer division(Integer left, Integer right) {
		return left / right;
	}
	@ParserBinaryOperator
	public Integer modulo(Integer left, Integer right) {
		return left % right;
	}
}

@Target(ElementType.PARAMETER)
@Retention(RetentionPolicy.RUNTIME)
@interface ParserRef {
	public String value();
}
@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
@interface ParserRule {
}
@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
@interface ParserAction {
}
@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
@interface ParserBinaryOperator {
}

abstract class Grammar {
	public <T> Parser<T> ref(String name) {
		Parser rule = refRule(name);
		try {
			Action action = refAction(name);
			return rule.bind(action);
		} catch (RuntimeException e) {
			return rule;
		}
	}
	public <T> Parser<T> refRule(String name) {
		return new RuleRef<T>(name, this);
	}
	public <F, T> Action<F, T> refAction(String name) {
		return new ActionRef<F, T>(name, this);
	}
	public <T> BinaryOperator<T> refBinaryOperator(String name) {
		return new BinaryOperatorRef<T>(name, this);
	}
	public Method getSingleAnnotatedMethod(String name, Class<? extends Annotation> annotation) {
		Method resultMethod = null;
		for (Method method : this.getClass().getMethods()) {
			if (method.getName().equals(name) && method.isAnnotationPresent(annotation)) {
				if (resultMethod == null) {
					resultMethod = method;
				} else {
					throw new RuntimeException();
				}
			}
		}
		if (resultMethod == null) {
			throw new RuntimeException();
		}
		return resultMethod;
	}
	public static <T1, T2, T3> Parser<Seq3<T1, T2, T3>> seq(Parser<T1> parser1, Parser<T2> parser2, Parser<T3> parser3) {
		return new Seq3Parser<T1, T2, T3>(parser1, parser2, parser3);
	}
	public static <T1, T2> Parser<Seq2<T1, T2>> seq(Parser<T1> parser1, Parser<T2> parser2) {
		return new Seq2Parser<T1, T2>(parser1, parser2);
	}
	public static <C, T> Parser<T> andPred(Parser<C> condition, Parser<T> parser) {
		return new AndPredParser<C, T>(condition, parser);
	}
	public static <C, T> Parser<T> notPred(Parser<C> condition, Parser<T> parser) {
		return new NotPredParser<C, T>(condition, parser);
	}
	public static Parser<Character> range(char start, char end) {
		if (start < end) {
			return chr(start).or(range((char) (start + 1), end));
		} else if (start > end) {
			return chr(start).or(range((char) (start - 1), end));
		} else {
			return chr(start);
		}
	}
	public static Parser<Character> chr(char ch) {
		return new CharParser(ch);
	}
	public static Parser<Eof> eof() {
		return new EofParser();
	}
	public static Parser<Empty> empty() {
		return new EmptyParser();
	}
}

interface Parser<T> {
	public Parsed<T> parse(String source) throws ParseException;
	public Parser<T> infixl(Parser<BinaryOperator<T>> operator);
	public <L, R> Parser<T> enclosedBy(Parser<L> lhs, Parser<R> rhs);
	public <N> Parser<N> bind(Action<T, N> action);
	public <N> Parser<BinaryOperator<N>> bind(BinaryOperator<N> operator);
	public Parser<List<T>> oneOrMore();
	public Parser<List<T>> zeroOrMore();
	public Parser<T> or(Parser<T> otherwise);
}
abstract class ParserBase<T> extends Grammar implements Parser<T> {
	@Override
	public Parser<T> infixl(final Parser<BinaryOperator<T>> operator) {
		return new Infixl(operator).ref("infixl");
	}
	private class Infixl extends Grammar {
		private Parser<T> operand;
		private Parser<BinaryOperator<T>> operator;
		public Infixl(Parser<BinaryOperator<T>> operator) {
			this.operand = ParserBase.this;
			this.operator = operator;
		}
		@SuppressWarnings("unused")
		@ParserRule
		public Parser<Seq2<T, List<Seq2<BinaryOperator<T>, T>>>> infixl() {
			return seq(operand, seq(operator, operand).zeroOrMore());
		}
		@SuppressWarnings("unused")
		@ParserAction
		public T infixl(Seq2<T, List<Seq2<BinaryOperator<T>, T>>> value) {
			T result = value.getValue1();
			for (Seq2<BinaryOperator<T>, T> trailing : value.getValue2()) {
				result = trailing.getValue1().apply(result, trailing.getValue2());
			}
			return result;
		}
	}
	@Override
	public <L, R> Parser<T> enclosedBy(Parser<L> lhs, Parser<R> rhs) {
		return seq(lhs, this, rhs).bind(new Action<Seq3<L, T, R>, T>() {
			@Override
			public T parsed(Seq3<L, T, R> value) {
				return value.getValue2();
			}
		});
	}
	@Override
	public <N> Parser<N> bind(Action<T, N> action) {
		return new ActionParser<T, N>(this, action);
	}
	@Override
	public <N> Parser<BinaryOperator<N>> bind(final BinaryOperator<N> operator) {
		return this.bind(new Action<T, BinaryOperator<N>>() {
			@Override
			public BinaryOperator<N> parsed(T value) {
				return operator;
			}
		});
	}
	@Override
	public Parser<List<T>> oneOrMore() {
		return andPred(this, this.zeroOrMore());
	}
	@Override
	public Parser<List<T>> zeroOrMore() {
		return new ZeroOrMoreParser<T>(this);
	}
	@Override
	public Parser<T> or(Parser<T> otherwise) {
		return new OrderedChoiceParser<T>(this, otherwise);
	}
}
abstract class Rule<T> extends ParserBase<T> {
	protected String name;
	private Parser<T> cached = null;
	public Rule() {
	}
	public Rule(String name) {
		this.name = name;
	}
	protected abstract Parser<T> rule();
	@Override
	public Parsed<T> parse(String source) throws ParseException {
		if (cached == null) {
			cached = rule();
		}
		return cached.parse(source);
	}
}
class RuleRef<T> extends Rule<T> {
	private Grammar grammar;
	private Method method;
	public RuleRef(String name, Grammar grammar) {
		this.name = name;
		this.grammar = grammar;
		this.method = grammar.getSingleAnnotatedMethod(name, ParserRule.class);
		if (!Parser.class.isAssignableFrom(method.getReturnType())) {
			throw new IllegalArgumentException();
		}
	}
	@Override
	protected Parser<T> rule() {
		try {
			return (Parser) method.invoke(grammar, getParameterValues());
		} catch (IllegalArgumentException e) {
			throw new RuntimeException("rule name: " + name, e);
		} catch (IllegalAccessException e) {
			throw new RuntimeException("rule name: " + name, e);
		} catch (InvocationTargetException e) {
			throw new RuntimeException("rule name: " + name, e);
		}
	}
	private Object[] getParameterValues() {
		Class<?>[] parameterTypes = method.getParameterTypes();
		Annotation[][] parameterAnnotations = method.getParameterAnnotations();
		Object[] parameterValues = new Object[parameterTypes.length];
		for (int i = 0; i < parameterTypes.length; i++) {
			Class<?> parameterType = parameterTypes[i];
			Annotation[] annotations = parameterAnnotations[i];
			String refName = null;
			for (Annotation annotation : annotations) {
				if (annotation instanceof ParserRef) {
					ParserRef ref = (ParserRef) annotation;
					refName = ref.value();
				}
			}
			if (refName == null) {
				throw new RuntimeException();
			}
			if (Parser.class.isAssignableFrom(parameterType)) {
				parameterValues[i] = grammar.ref(refName);
			} else if (Action.class.isAssignableFrom(parameterType)) {
				parameterValues[i] = grammar.refAction(refName);
			} else if (BinaryOperator.class.isAssignableFrom(parameterType)) {
				parameterValues[i] = grammar.refBinaryOperator(refName);
			} else {
				throw new RuntimeException();
			}
		}
		return parameterValues;
	}
}
interface BinaryOperator<T> {
	public T apply(T left, T right);
}
class BinaryOperatorRef<T> implements BinaryOperator<T> {
	protected String name;
	private Grammar grammar;
	private Method method;
	public BinaryOperatorRef(String name, Grammar grammar) {
		this.name = name;
		this.grammar = grammar;
		this.method = grammar.getSingleAnnotatedMethod(name, ParserBinaryOperator.class);
		Class<?>[] parameterTypes = method.getParameterTypes();
		if (parameterTypes.length != 2) {
			throw new RuntimeException();
		}
	}
	@Override
	public T apply(T left, T right) {
		try {
			return (T) method.invoke(grammar, left, right);
		} catch (IllegalArgumentException e) {
			throw new RuntimeException("binary operator name: " + name, e);
		} catch (IllegalAccessException e) {
			throw new RuntimeException("binary operator name: " + name, e);
		} catch (InvocationTargetException e) {
			throw new RuntimeException("binary operator name: " + name, e);
		}
	}
}
interface Action<F, T> {
	public T parsed(F value);
}
abstract class NamedAction<F, T> implements Action<F, T> {
	protected String name;
	public NamedAction() {
	}
	public NamedAction(String name) {
		this.name = name;
	}
}
class ActionRef<F, T> implements Action<F, T> {
	protected String name;
	private Grammar grammar;
	private Method method;
	public ActionRef(String name, Grammar grammar) {
		this.name = name;
		this.grammar = grammar;
		this.method = grammar.getSingleAnnotatedMethod(name, ParserAction.class);
		if (method.getParameterTypes().length != 1) {
			throw new RuntimeException();
		}
	}
	@Override
	public T parsed(F value) {
		try {
			return (T) method.invoke(grammar, value);
		} catch (IllegalArgumentException e) {
			throw new RuntimeException("action name: " + name, e);
		} catch (IllegalAccessException e) {
			throw new RuntimeException("action name: " + name, e);
		} catch (InvocationTargetException e) {
			throw new RuntimeException("action name: " + name, e);
		}
	}
}
class ActionParser<F, T> extends ParserBase<T> {
	private Parser<F> parser;
	private Action<F, T> action;
	public ActionParser(Parser<F> parser, Action<F, T> action) {
		this.parser = parser;
		this.action = action;
	}
	@Override
	public Parsed<T> parse(String source) throws ParseException {
		Parsed<F> result = parser.parse(source);
		return new Parsed<T>(action.parsed(result.getValue()), result.getRest());
	}
}
class ZeroOrMoreParser<T> extends ParserBase<List<T>> {
	private Parser<T> parser;
	public ZeroOrMoreParser(Parser<T> parser) {
		this.parser = parser;
	}
	@Override
	public Parsed<List<T>> parse(String source) throws ParseException {
		List<T> values = new ArrayList<T>();
		try {
			for (;;) {
				Parsed<T> result = parser.parse(source);
				values.add(result.getValue());
				source = result.getRest();
			}
		} catch (ParseException e) {
			return new Parsed<List<T>>(values, source);
		}
	}
}
class Seq3<T1, T2, T3> {
	private final T1 value1;
	private final T2 value2;
	private final T3 value3;
	public Seq3(T1 value1, T2 value2, T3 value3) {
		this.value1 = value1;
		this.value2 = value2;
		this.value3 = value3;
	}
	public T1 getValue1() {
		return value1;
	}
	public T2 getValue2() {
		return value2;
	}
	public T3 getValue3() {
		return value3;
	}
}
class Seq3Parser<T1, T2, T3> extends ParserBase<Seq3<T1, T2, T3>> {
	private Parser<T1> parser1;
	private Parser<T2> parser2;
	private Parser<T3> parser3;
	public Seq3Parser(Parser<T1> parser1, Parser<T2> parser2, Parser<T3> parser3) {
		this.parser1 = parser1;
		this.parser2 = parser2;
		this.parser3 = parser3;
	}
	@Override
	public Parsed<Seq3<T1, T2, T3>> parse(String source) throws ParseException {
		Parsed<T1> result1 = parser1.parse(source);
		Parsed<T2> result2 = parser2.parse(result1.getRest());
		Parsed<T3> result3 = parser3.parse(result2.getRest());
		Seq3<T1, T2, T3> seq3 = new Seq3<T1, T2, T3>(result1.getValue(), result2.getValue(), result3.getValue());
		return new Parsed<Seq3<T1,T2,T3>>(seq3, result3.getRest());
	}
}
class Seq2<T1, T2> {
	private final T1 value1;
	private final T2 value2;
	public Seq2(T1 value1, T2 value2) {
		this.value1 = value1;
		this.value2 = value2;
	}
	public T1 getValue1() {
		return value1;
	}
	public T2 getValue2() {
		return value2;
	}
}
class Seq2Parser<T1, T2> extends ParserBase<Seq2<T1, T2>> {
	private Parser<T1> parser1;
	private Parser<T2> parser2;
	public Seq2Parser(Parser<T1> parser1, Parser<T2> parser2) {
		this.parser1 = parser1;
		this.parser2 = parser2;
	}
	@Override
	public Parsed<Seq2<T1, T2>> parse(String source) throws ParseException {
		Parsed<T1> result1 = parser1.parse(source);
		Parsed<T2> result2 = parser2.parse(result1.getRest());
		Seq2<T1, T2> seq2 = new Seq2<T1, T2>(result1.getValue(), result2.getValue());
		return new Parsed<Seq2<T1,T2>>(seq2, result2.getRest());
	}
}
class OrderedChoiceParser<T> extends ParserBase<T> {
	private Parser<T> left;
	private Parser<T> right;
	public OrderedChoiceParser(Parser<T> left, Parser<T> right) {
		this.left = left;
		this.right = right;
	}
	@Override
	public Parsed<T> parse(String source) throws ParseException {
		try {
			return left.parse(source);
		} catch (ParseException e) {
			return right.parse(source);
		}
	}
}
class AndPredParser<C, T> extends ParserBase<T> {
	private Parser<C> condition;
	private Parser<T> parser;
	public AndPredParser(Parser<C> condition, Parser<T> parser) {
		this.condition = condition;
		this.parser = parser;
	}
	@Override
	public Parsed<T> parse(String source) throws ParseException {
		condition.parse(source);
		return parser.parse(source);
	}
}
class NotPredParser<C, T> extends ParserBase<T> {
	private Parser<C> condition;
	private Parser<T> parser;
	public NotPredParser(Parser<C> condition, Parser<T> parser) {
		this.condition = condition;
		this.parser = parser;
	}
	@Override
	public Parsed<T> parse(String source) throws ParseException {
		try {
			condition.parse(source);
			throw new ParseException();
		} catch (ParseException e) {
			return parser.parse(source);
		}
	}
}
class CharParser extends ParserBase<Character> {
	private char ch;
	public CharParser(char ch) {
		this.ch = ch;
	}
	public Parsed<Character> parse(String source) throws ParseException {
		if (source != null && source.length() != 0 && source.charAt(0) == ch) {
			return new Parsed<Character>(ch, source.substring(1));
		} else {
			throw new ParseException("parser:" + this + "; source:" + source);
		}
	}
}
enum Eof { EOF }
class EofParser extends ParserBase<Eof> {
	@Override
	public Parsed<Eof> parse(String source) throws ParseException {
		if (source == null || source.length() == 0) {
			return new Parsed<Eof>(Eof.EOF, source);
		} else {
			throw new ParseException("parser:" + this + "; source:" + source);
		}
	}
}
enum Empty { EMPTY }
class EmptyParser extends ParserBase<Empty> {
	@Override
	public Parsed<Empty> parse(String source) throws ParseException {
		return new Parsed<Empty>(Empty.EMPTY, source);
	}
}

class Parsed<T> {
	private final T value;
	private final String rest;
	public Parsed(T value, String rest) {
		this.value = value;
		this.rest = rest;
	}
	public T getValue() {
		return value;
	}
	public String getRest() {
		return rest;
	}
}
class ParseException extends Exception {
	private static final long serialVersionUID = 1L;
	public ParseException() {
		super();
	}
	public ParseException(String message, Throwable cause) {
		super(message, cause);
	}
	public ParseException(String message) {
		super(message);
	}
	public ParseException(Throwable cause) {
		super(cause);
	}
}