Implement Pratt parser.

13 files changed, 1004 insertions, 0 deletions

diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/ParserException.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/ParserException.java
new file mode 100644
index 0000000..67812de
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/ParserException.java
@@ -0,0 +1,28 @@
+package bjc.utils.parserutils;
+
+/**
+ * General superclass for exceptions thrown during parsing.
+ * 
+ * @author EVE
+ *
+ */
+public class ParserException extends Exception {
+	/**
+	 * Create a new exception with the provided message.
+	 * 
+	 * @param msg The message for the exception.
+	 */
+	public ParserException(String msg) {
+		super(msg);
+	}
+	
+	/**
+	 * Create a new exception with the provided message and cause.
+	 * 
+	 * @param msg The message for the exception.
+	 * @param cause The cause of the exception.
+	 */
+	public ParserException(String msg, Exception cause) {
+		super(msg, cause);
+	}
+}
diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/DefaultLeftCommand.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/DefaultLeftCommand.java
new file mode 100644
index 0000000..24802a6
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/DefaultLeftCommand.java
@@ -0,0 +1,17 @@
+package bjc.utils.parserutils.pratt;
+
+import bjc.utils.data.ITree;
+
+class DefaultLeftCommand<K, V, C> extends LeftCommand<K, V, C> {
+
+	@Override
+	public ITree<Token<K, V>> leftDenote(ITree<Token<K, V>> operand, Token<K, V> operator, ParserContext<K, V, C> ctx) {
+		throw new UnsupportedOperationException("Default command has no left denotation");
+	}
+
+	@Override
+	public int leftBinding() {
+		return -1;
+	}
+
+}
diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/DefaultNullCommand.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/DefaultNullCommand.java
new file mode 100644
index 0000000..04216f9
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/DefaultNullCommand.java
@@ -0,0 +1,25 @@
+package bjc.utils.parserutils.pratt;
+
+import bjc.utils.data.ITree;
+import bjc.utils.parserutils.ParserException;
+
+/**
+ * Default implementation of null command.
+ * 
+ * @author EVE
+ *
+ * @param <K>
+ *                The key type of the token.
+ * @param <V>
+ *                The value type of the token.
+ * 
+ * @param <C>
+ *                The state type of the parser.
+ */
+public class DefaultNullCommand<K, V, C> extends NullCommand<K, V, C> {
+	@Override
+	public ITree<Token<K, V>> nullDenotation(Token<K, V> operator, ParserContext<K, V, C> ctx)
+			throws ParserException {
+		throw new ParserException("Unexpected token " + operator);
+	}
+}
diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/LeftCommand.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/LeftCommand.java
new file mode 100644
index 0000000..747c207
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/LeftCommand.java
@@ -0,0 +1,63 @@
+package bjc.utils.parserutils.pratt;
+
+import bjc.utils.data.ITree;
+import bjc.utils.parserutils.ParserException;
+
+/**
+ * Represents a non-initial command in parsing.
+ * 
+ * @author EVE
+ * 
+ * @param <K>
+ *                The key type for the tokens.
+ * 
+ * @param <V>
+ *                The value type for the tokens.
+ * 
+ * @param <C>
+ *                The state type of the parser.
+ *
+ */
+public abstract class LeftCommand<K, V, C> {
+	/**
+	 * Construct the left denotation of this command.
+	 * 
+	 * @param operand
+	 *                The left-hand operand of this command.
+	 * @param operator
+	 *                The operator for this command.
+	 * 
+	 * @param ctx
+	 *                The state needed for commands.
+	 * 
+	 * @return The tree this command forms.
+	 * 
+	 * @throws ParserException
+	 *                 If something went wrong during parsing.
+	 */
+	public abstract ITree<Token<K, V>> leftDenote(ITree<Token<K, V>> operand, Token<K, V> operator,
+			ParserContext<K, V, C> ctx) throws ParserException;
+
+	/**
+	 * Get the left-binding power of this command.
+	 * 
+	 * This represents the general precedence of this command.
+	 * 
+	 * @return The left-binding power of this command.
+	 */
+	public abstract int leftBinding();
+
+	/**
+	 * Get the next-binding power of this command.
+	 * 
+	 * This represents the highest precedence of command this command can be
+	 * the left operand of.
+	 * 
+	 * This is the same as the left-binding power by default.
+	 * 
+	 * @return The next-binding power of this command.
+	 */
+	public int nextBinding() {
+		return leftBinding();
+	}
+}
diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/LeftCommands.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/LeftCommands.java
new file mode 100644
index 0000000..30f3af8
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/LeftCommands.java
@@ -0,0 +1,317 @@
+package bjc.utils.parserutils.pratt;
+
+import bjc.utils.data.ITree;
+import bjc.utils.data.Tree;
+import bjc.utils.parserutils.ParserException;
+
+import java.util.Set;
+
+/**
+ * Contains factory methods for producing common implementations of
+ * {@link LeftCommand}
+ * 
+ * @author EVE
+ *
+ */
+public class LeftCommands {
+	/*
+	 * A command with constant binding power.
+	 */
+	private static abstract class BinaryPostCommand<K, V, C> extends LeftCommand<K, V, C> {
+		private final int leftPower;
+
+		public BinaryPostCommand(int power) {
+			leftPower = power;
+		}
+
+		@Override
+		public int leftBinding() {
+			return leftPower;
+		}
+	}
+
+	private static abstract class BinaryCommand<K, V, C> extends BinaryPostCommand<K, V, C> {
+		public BinaryCommand(int leftPower) {
+			super(leftPower);
+		}
+
+		protected abstract int rightBinding();
+
+		@Override
+		public ITree<Token<K, V>> leftDenote(ITree<Token<K, V>> operand, Token<K, V> operator,
+				ParserContext<K, V, C> ctx) throws ParserException {
+			ITree<Token<K, V>> opr = ctx.parse.parseExpression(rightBinding(), ctx.tokens, ctx.state);
+
+			return new Tree<>(operator, operand, opr);
+		}
+	}
+
+	private static class LeftBinaryCommand<K, V, C> extends BinaryCommand<K, V, C> {
+		public LeftBinaryCommand(int leftPower) {
+			super(leftPower);
+		}
+
+		@Override
+		protected int rightBinding() {
+			return 1 + leftBinding();
+		}
+	}
+
+	private static class RightBinaryCommand<K, V, C> extends BinaryCommand<K, V, C> {
+		public RightBinaryCommand(int leftPower) {
+			super(leftPower);
+		}
+
+		@Override
+		protected int rightBinding() {
+			return leftBinding();
+		}
+	}
+
+	private static class NonBinaryCommand<K, V, C> extends BinaryCommand<K, V, C> {
+		public NonBinaryCommand(int leftPower) {
+			super(leftPower);
+		}
+
+		@Override
+		protected int rightBinding() {
+			return 1 + leftBinding();
+		}
+
+		@Override
+		public int nextBinding() {
+			return leftBinding() - 1;
+		}
+	}
+
+	private static class PostCircumfixCommand<K, V, C> extends BinaryPostCommand<K, V, C> {
+		private int		insidePrec;
+		private K		term;
+		private Token<K, V>	mark;
+
+		public PostCircumfixCommand(int leftPower, int insidePower, K terminator, Token<K, V> marker) {
+			super(leftPower);
+
+			insidePrec = insidePower;
+			term = terminator;
+			mark = marker;
+		}
+
+		@SuppressWarnings("unchecked")
+		@Override
+		public ITree<Token<K, V>> leftDenote(ITree<Token<K, V>> operand, Token<K, V> operator,
+				ParserContext<K, V, C> ctx) throws ParserException {
+			ITree<Token<K, V>> inside = ctx.parse.parseExpression(insidePrec, ctx.tokens, ctx.state);
+
+			ctx.tokens.expect(term);
+
+			return new Tree<>(mark, operand, inside);
+		}
+	}
+
+	private static class PostfixCommand<K, V, C> extends BinaryPostCommand<K, V, C> {
+		public PostfixCommand(int leftPower) {
+			super(leftPower);
+		}
+
+		@Override
+		public ITree<Token<K, V>> leftDenote(ITree<Token<K, V>> operand, Token<K, V> operator,
+				ParserContext<K, V, C> ctx) throws ParserException {
+			return new Tree<>(operator, operand);
+		}
+	}
+
+	private static class TernaryCommand<K, V, C> extends BinaryPostCommand<K, V, C> {
+		private K term;
+
+		private int innerExp;
+
+		private Token<K, V> mark;
+
+		private boolean nonassoc;
+
+		public TernaryCommand(int leftPower, K terminator, Token<K, V> mark, boolean isNonassoc) {
+			super(leftPower);
+			nonassoc = isNonassoc;
+		}
+
+		@SuppressWarnings("unchecked")
+		@Override
+		public ITree<Token<K, V>> leftDenote(ITree<Token<K, V>> operand, Token<K, V> operator,
+				ParserContext<K, V, C> ctx) throws ParserException {
+			ITree<Token<K, V>> inner = ctx.parse.parseExpression(innerExp, ctx.tokens, ctx.state);
+
+			ctx.tokens.expect(term);
+
+			ITree<Token<K, V>> outer = ctx.parse.parseExpression(1 + leftBinding(), ctx.tokens, ctx.state);
+
+			return new Tree<>(mark, inner, operand, outer);
+		}
+
+		@Override
+		public int nextBinding() {
+			if(nonassoc) {
+				return leftBinding() - 1;
+			} else {
+				return super.nextBinding();
+			}
+		}
+	}
+
+	private static class ChainCommand<K, V, C> extends BinaryPostCommand<K, V, C> {
+		private Set<K> chainWith;
+
+		private Token<K, V> chain;
+
+		public ChainCommand(int leftPower, Set<K> chainSet, Token<K, V> chainMarker) {
+			super(leftPower);
+
+			chainWith = chainSet;
+			chain = chainMarker;
+		}
+
+		@Override
+		public ITree<Token<K, V>> leftDenote(ITree<Token<K, V>> operand, Token<K, V> operator,
+				ParserContext<K, V, C> ctx) throws ParserException {
+			ITree<Token<K, V>> tree = ctx.parse.parseExpression(1 + leftBinding(), ctx.tokens, ctx.state);
+
+			ITree<Token<K, V>> res = new Tree<>(operator, operand, tree);
+
+			if(chainWith.contains(ctx.tokens.current().getKey())) {
+				Token<K, V> tok = ctx.tokens.current();
+				ctx.tokens.next();
+
+				ITree<Token<K, V>> other = leftDenote(tree, tok,
+						new ParserContext<>(ctx.tokens, ctx.parse, ctx.state));
+
+				return new Tree<>(chain, res, other);
+			} else {
+				return res;
+			}
+		}
+
+		@Override
+		public int nextBinding() {
+			return leftBinding() - 1;
+		}
+	}
+
+	/**
+	 * Create a left-associative infix operator.
+	 * 
+	 * @param precedence
+	 *                The precedence of the operator.
+	 * 
+	 * @return A command implementing that operator.
+	 */
+	public static <K, V, C> LeftCommand<K, V, C> infixLeft(int precedence) {
+		return new LeftBinaryCommand<>(precedence);
+	}
+
+	/**
+	 * Create a right-associative infix operator.
+	 * 
+	 * @param precedence
+	 *                The precedence of the operator.
+	 * 
+	 * @return A command implementing that operator.
+	 */
+	public static <K, V, C> LeftCommand<K, V, C> infixRight(int precedence) {
+		return new RightBinaryCommand<>(precedence);
+	}
+
+	/**
+	 * Create a non-associative infix operator.
+	 * 
+	 * @param precedence
+	 *                The precedence of the operator.
+	 * 
+	 * @return A command implementing that operator.
+	 */
+	public static <K, V, C> LeftCommand<K, V, C> infixNon(int precedence) {
+		return new NonBinaryCommand<>(precedence);
+	}
+
+	/**
+	 * Create a chained operator.
+	 * 
+	 * @param precedence
+	 *                The precedence of the operator.
+	 * 
+	 * @param chainSet
+	 *                The operators it forms a chain with.
+	 * 
+	 * @param marker
+	 *                The token to use as the AST node for the chained
+	 *                operators.
+	 * 
+	 * @return A command implementing that operator.
+	 */
+	public static <K, V, C> LeftCommand<K, V, C> chain(int precedence, Set<K> chainSet, Token<K, V> marker) {
+		return new ChainCommand<>(precedence, chainSet, marker);
+	}
+
+	/**
+	 * Create a postfix operator.
+	 * 
+	 * @param precedence
+	 *                The precedence of the operator.
+	 * 
+	 * @return A command implementing that operator.
+	 */
+	public static <K, V, C> LeftCommand<K, V, C> postfix(int precedence) {
+		return new PostfixCommand<>(precedence);
+	}
+
+	/**
+	 * Create a post-circumfix operator.
+	 * 
+	 * This is an operator in form similar to array indexing.
+	 * 
+	 * @param precedence
+	 *                The precedence of this operator
+	 * 
+	 * @param insidePrecedence
+	 *                The precedence of the expression inside the operator
+	 * 
+	 * @param closer
+	 *                The token that closes the circumfix.
+	 * 
+	 * @param marker
+	 *                The token to use as the AST node for the operator.
+	 * 
+	 * @return A command implementing that operator.
+	 */
+	public static <K, V, C> LeftCommand<K, V, C> postCircumfix(int precedence, int insidePrecedence, K closer,
+			Token<K, V> marker) {
+		return new PostCircumfixCommand<>(precedence, insidePrecedence, closer, marker);
+	}
+
+	/**
+	 * Create a ternary operator.
+	 * 
+	 * This is like C's ?: operator.
+	 * 
+	 * @param precedence
+	 *                The precedence of the operator.
+	 * 
+	 * @param insidePrecedence
+	 *                The precedence of the inner section of the operator.
+	 * 
+	 * @param closer
+	 *                The token that marks the end of the inner section.
+	 * 
+	 * @param marker
+	 *                The token to use as the AST node for the operator.
+	 * 
+	 * @param nonassoc
+	 *                True if the command is non-associative, false
+	 *                otherwise.
+	 * 
+	 * @return A command implementing this operator.
+	 */
+	public static <K, V, C> LeftCommand<K, V, C> ternary(int precedence, int insidePrecedence, K closer,
+			Token<K, V> marker, boolean nonassoc) {
+		return new TernaryCommand<>(insidePrecedence, closer, marker, nonassoc);
+	}
+}
diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/NullCommand.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/NullCommand.java
new file mode 100644
index 0000000..c105361
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/NullCommand.java
@@ -0,0 +1,38 @@
+package bjc.utils.parserutils.pratt;
+
+import bjc.utils.data.ITree;
+import bjc.utils.parserutils.ParserException;
+
+/**
+ * Represents an initial command in parsing.
+ * 
+ * @author EVE
+ * 
+ * @param <K>
+ *                The key type for the tokens.
+ * 
+ * @param <V>
+ *                The value type for the tokens.
+ * 
+ * @param <C>
+ *                The state type of the parser.
+ * 
+ *
+ */
+public abstract class NullCommand<K, V, C> {
+	/**
+	 * Construct the null denotation of this command.
+	 * 
+	 * @param operator
+	 *                The operator for this command.
+	 * @param ctx
+	 *                The context for the command.
+	 * 
+	 * @return The tree for this command.
+	 * 
+	 * @throws ParserException
+	 *                 If something goes wrong during parsing.
+	 */
+	public abstract ITree<Token<K, V>> nullDenotation(Token<K, V> operator, ParserContext<K, V, C> ctx)
+			throws ParserException;
+}
diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/NullCommands.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/NullCommands.java
new file mode 100644
index 0000000..cf57241
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/NullCommands.java
@@ -0,0 +1,115 @@
+package bjc.utils.parserutils.pratt;
+
+import bjc.utils.data.ITree;
+import bjc.utils.data.Tree;
+import bjc.utils.parserutils.ParserException;
+
+/**
+ * * Contains factory methods for producing common implementations of
+ * {@link NullCommand}
+ * 
+ * @author EVE
+ *
+ */
+public class NullCommands {
+	private static abstract class AbstractNullCommand<K, V, C> extends NullCommand<K, V, C> {
+		@Override
+		public ITree<Token<K, V>> nullDenotation(Token<K, V> operator, ParserContext<K, V, C> ctx)
+				throws ParserException {
+			//tokens.next();
+
+			return intNullDenotation(operator, ctx);
+		}
+
+		protected abstract ITree<Token<K, V>> intNullDenotation(Token<K, V> operator, ParserContext<K, V, C> ctx)
+				throws ParserException;
+
+	}
+
+	private static class UnaryCommand<K, V, C> extends AbstractNullCommand<K, V, C> {
+		private final int nullPwer;
+
+		public UnaryCommand(int nullPower) {
+			nullPwer = nullPower;
+		}
+
+		@Override
+		protected ITree<Token<K, V>> intNullDenotation(Token<K, V> operator, ParserContext<K, V, C> ctx)
+				throws ParserException {
+			ITree<Token<K, V>> opr = ctx.parse.parseExpression(nullPwer, ctx.tokens, ctx.state);
+
+			return new Tree<>(operator, opr);
+		}
+	}
+
+	private static class GroupingCommand<K, V, C> extends AbstractNullCommand<K, V, C> {
+		private K		term;
+		private Token<K, V>	mark;
+		private int		inner;
+
+		public GroupingCommand(int innerPrec, K terminator, Token<K, V> marker) {
+			inner = innerPrec;
+			term = terminator;
+			mark = marker;
+		}
+
+		@SuppressWarnings("unchecked")
+		@Override
+		protected ITree<Token<K, V>> intNullDenotation(Token<K, V> operator, ParserContext<K, V, C> ctx)
+				throws ParserException {
+			ITree<Token<K, V>> opr = ctx.parse.parseExpression(inner, ctx.tokens, ctx.state);
+
+			ctx.tokens.expect(term);
+
+			return new Tree<>(mark, opr);
+		}
+	}
+
+	private static class LeafCommand<K, V, C> extends NullCommand<K, V, C> {
+		@Override
+		public ITree<Token<K, V>> nullDenotation(Token<K, V> operator, ParserContext<K, V, C> ctx)
+				throws ParserException {
+
+			return new Tree<>(operator);
+		}
+	}
+
+	/**
+	 * Create a new unary operator.
+	 * 
+	 * @param precedence
+	 *                The precedence of the operator.
+	 * 
+	 * @return A command implementing that operator.
+	 */
+	public static <K, V, C> NullCommand<K, V, C> unary(int precedence) {
+		return new UnaryCommand<>(precedence);
+	}
+
+	/**
+	 * Create a new grouping operator.
+	 * 
+	 * @param precedence
+	 *                The precedence of the expression in the operator.
+	 * 
+	 * @param term
+	 *                The type that closes the group.
+	 * 
+	 * @param mark
+	 *                The token for the AST node of the group.
+	 * 
+	 * @return A command implementing the operator.
+	 */
+	public static <K, V, C> NullCommand<K, V, C> grouping(int precedence, K term, Token<K, V> mark) {
+		return new GroupingCommand<>(precedence, term, mark);
+	}
+
+	/**
+	 * Create a new leaf operator.
+	 * 
+	 * @return A command implementing the operator.
+	 */
+	public static <K, V, C> NullCommand<K, V, C> leaf() {
+		return new LeafCommand<>();
+	}
+}
diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/ParserContext.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/ParserContext.java
new file mode 100644
index 0000000..55b5e98
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/ParserContext.java
@@ -0,0 +1,47 @@
+package bjc.utils.parserutils.pratt;
+
+/**
+ * Represents the contextual state passed to a command.
+ * 
+ * @author EVE
+ *
+ * @param <K>
+ *                The key type of the tokens.
+ * @param <V>
+ *                The value type of the tokens.
+ * 
+ * @param <C>
+ *                The state type of the parser.
+ */
+public class ParserContext<K, V, C> {
+	/**
+	 * The source of tokens.
+	 */
+	public TokenStream<K, V>	tokens;
+	/**
+	 * The parser for sub-expressions.
+	 */
+	public PrattParser<K, V, C>	parse;
+	/**
+	 * The state of the parser.
+	 */
+	public C			state;
+
+	/**
+	 * Create a new parser context.
+	 * 
+	 * @param tokens
+	 *                The source of tokens.
+	 * 
+	 * @param parse
+	 *                The parser to call for sub expressions.
+	 * 
+	 * @param state
+	 *                Any state needing to be kept during parsing.
+	 */
+	public ParserContext(TokenStream<K, V> tokens, PrattParser<K, V, C> parse, C state) {
+		this.tokens = tokens;
+		this.parse = parse;
+		this.state = state;
+	}
+}
\ No newline at end of file
diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/PrattParser.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/PrattParser.java
new file mode 100644
index 0000000..a2cefda
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/PrattParser.java
@@ -0,0 +1,121 @@
+package bjc.utils.parserutils.pratt;
+
+import bjc.utils.data.ITree;
+import bjc.utils.funcutils.NumberUtils;
+import bjc.utils.parserutils.ParserException;
+
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * A configurable Pratt parser for expressions.
+ * 
+ * @author EVE
+ * 
+ * @param <K>
+ *                The key type for the tokens.
+ * 
+ * @param <V>
+ *                The value type for the tokens.
+ * 
+ * @param <C>
+ *                The state type of the parser.
+ * 
+ *
+ */
+public class PrattParser<K, V, C> {
+	private final LeftCommand<K, V, C>	DEFAULT_LEFT_COMMAND	= new DefaultLeftCommand<>();
+	private final NullCommand<K, V, C>	DEFAULT_NULL_COMMAND	= new DefaultNullCommand<>();
+
+	private Map<K, LeftCommand<K, V, C>>	leftCommands;
+	private Map<K, NullCommand<K, V, C>>	nullCommands;
+
+	/**
+	 * Create a new Pratt parser.
+	 * 
+	 * @param terminal
+	 *                The terminal symbol.
+	 */
+	public PrattParser() {
+		leftCommands = new HashMap<>();
+		nullCommands = new HashMap<>();
+	}
+
+	/**
+	 * Parse an expression.
+	 * 
+	 * @param precedence
+	 *                The initial precedence for the expression.
+	 * 
+	 * @param tokens
+	 *                The tokens for the expression.
+	 * 
+	 * @param state
+	 *                The state of the parser.
+	 * 
+	 * @return The expression as an AST.
+	 * 
+	 * @throws ParserException
+	 *                 If something goes wrong during parsing.
+	 */
+	public ITree<Token<K, V>> parseExpression(int precedence, TokenStream<K, V> tokens, C state)
+			throws ParserException {
+		if(precedence < 0) {
+			throw new IllegalArgumentException("Precedence must be greater than zero");
+		}
+
+		Token<K, V> initToken = tokens.current();
+		tokens.next();
+
+		ITree<Token<K, V>> ast = nullCommands.getOrDefault(initToken.getKey(), DEFAULT_NULL_COMMAND)
+				.nullDenotation(initToken, new ParserContext<>(tokens, this, state));
+
+		int rightPrec = Integer.MAX_VALUE;
+
+		while(true) {
+			Token<K, V> tok = tokens.current();
+
+			K key = tok.getKey();
+
+			LeftCommand<K, V, C> command = leftCommands.getOrDefault(key, DEFAULT_LEFT_COMMAND);
+			int leftBind = command.leftBinding();
+
+			if(NumberUtils.between(precedence, rightPrec, leftBind)) {
+				tokens.next();
+
+				ast = command.leftDenote(ast, tok, new ParserContext<>(tokens, this, state));
+				rightPrec = command.nextBinding();
+			} else {
+				break;
+			}
+		}
+
+		return ast;
+	}
+
+	/**
+	 * Add a non-initial command to this parser.
+	 * 
+	 * @param marker
+	 *                The key that marks the command.
+	 * 
+	 * @param comm
+	 *                The command.
+	 */
+	public void addNonInitialCommand(K marker, LeftCommand<K, V, C> comm) {
+		leftCommands.put(marker, comm);
+	}
+
+	/**
+	 * Add a initial command to this parser.
+	 * 
+	 * @param marker
+	 *                The key that marks the command.
+	 * 
+	 * @param comm
+	 *                The command.
+	 */
+	public void addInitialCommand(K marker, NullCommand<K, V, C> comm) {
+		nullCommands.put(marker, comm);
+	}
+}
diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/StringToken.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/StringToken.java
new file mode 100644
index 0000000..957e6fa
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/StringToken.java
@@ -0,0 +1,71 @@
+package bjc.utils.parserutils.pratt;
+
+/**
+ * Simple token implementation for strings.
+ * 
+ * @author EVE
+ *
+ */
+public class StringToken implements Token<String, String> {
+	private String	key;
+	private String	val;
+
+	/**
+	 * Create a new string token.
+	 * 
+	 * @param ky
+	 *                The key for the token.
+	 * 
+	 * @param vl
+	 *                The value for the token.
+	 */
+	public StringToken(String ky, String vl) {
+		key = ky;
+		val = vl;
+	}
+
+	@Override
+	public String getKey() {
+		return key;
+	}
+
+	@Override
+	public String getValue() {
+		return val;
+	}
+
+	@Override
+	public int hashCode() {
+		final int prime = 31;
+
+		int result = 1;
+		result = prime * result + ((key == null) ? 0 : key.hashCode());
+		result = prime * result + ((val == null) ? 0 : val.hashCode());
+
+		return result;
+	}
+
+	@Override
+	public boolean equals(Object obj) {
+		if(this == obj) return true;
+		if(obj == null) return false;
+		if(!(obj instanceof StringToken)) return false;
+
+		StringToken other = (StringToken) obj;
+
+		if(key == null) {
+			if(other.key != null) return false;
+		} else if(!key.equals(other.key)) return false;
+
+		if(val == null) {
+			if(other.val != null) return false;
+		} else if(!val.equals(other.val)) return false;
+
+		return true;
+	}
+
+	@Override
+	public String toString() {
+		return String.format("StringToken [key=%s, val=%s]", key, val);
+	}
+}
diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/StringTokenStream.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/StringTokenStream.java
new file mode 100644
index 0000000..8caeef9
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/StringTokenStream.java
@@ -0,0 +1,44 @@
+package bjc.utils.parserutils.pratt;
+
+import java.util.Iterator;
+
+/**
+ * Simple implementation of token stream for strings.
+ * 
+ * The terminal token here is represented by a token with type '(end)' and null
+ * value.
+ * 
+ * @author EVE
+ *
+ */
+public class StringTokenStream implements TokenStream<String, String> {
+	private Iterator<Token<String, String>> iter;
+
+	private Token<String, String> curr;
+
+	/**
+	 * Create a new token stream from a iterator.
+	 * 
+	 * @param itr
+	 *                The iterator to use.
+	 * 
+	 */
+	public StringTokenStream(Iterator<Token<String, String>> itr) {
+		iter = itr;
+
+	}
+
+	@Override
+	public Token<String, String> current() {
+		return curr;
+	}
+
+	@Override
+	public void next() {
+		if(iter.hasNext()) {
+			curr = iter.next();
+		} else {
+			curr = new StringToken("(end)", null);
+		}
+	}
+}
diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/Token.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/Token.java
new file mode 100644
index 0000000..6db8b63
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/Token.java
@@ -0,0 +1,30 @@
+package bjc.utils.parserutils.pratt;
+
+/**
+ * Represents a simple parsing token.
+ * 
+ * @author EVE
+ * 
+ * @param <K>
+ *                The key type of this token. Represents the type of the token.
+ * 
+ * @param <V>
+ *                The value type of this token. Represents any additional data
+ *                for the token.
+ *
+ */
+public interface Token<K, V> {
+	/**
+	 * Get the key for this token.
+	 * 
+	 * @return The key for this token
+	 */
+	K getKey();
+
+	/**
+	 * Get the value for this token.
+	 * 
+	 * @return The value for this token.
+	 */
+	V getValue();
+}
diff --git a/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/TokenStream.java b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/TokenStream.java
new file mode 100644
index 0000000..8decc09
--- /dev/null
+++ b/BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/TokenStream.java
@@ -0,0 +1,88 @@
+package bjc.utils.parserutils.pratt;
+
+import bjc.utils.funcutils.StringUtils;
+import bjc.utils.parserutils.ParserException;
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.Set;
+
+/**
+ * A stream of tokens.
+ * 
+ * @author EVE
+ *
+ * @param <K>
+ *                The key type of the token.
+ * 
+ * @param <V>
+ *                The value type of the token.
+ */
+public interface TokenStream<K, V> {
+	/**
+	 * The exception thrown when an expectation fails.
+	 * 
+	 * @author EVE
+	 *
+	 */
+	public static class ExpectationException extends ParserException {
+		/**
+		 * Create a new exception with the specified message.
+		 * 
+		 * @param msg
+		 *                The message of the exception.
+		 */
+		public ExpectationException(String msg) {
+			super(msg);
+		}
+	}
+
+	/**
+	 * Get the current token.
+	 * 
+	 * @return The current token.
+	 */
+	Token<K, V> current();
+
+	/**
+	 * Advance to the next token in the stream.
+	 * 
+	 * Has no effect when the end of the stream is reached.
+	 */
+	void next();
+
+	/**
+	 * Utility method for checking that the next token is one of a specific
+	 * set of types, and then consuming it.
+	 * 
+	 * @param expectedKeys
+	 *                The expected values
+	 * 
+	 * @throws ExpectationException
+	 *                 If the token is not one of the expected types.
+	 */
+	default void expect(Set<K> expectedKeys) throws ExpectationException {
+		K curKey = current().getKey();
+
+		if(!expectedKeys.contains(curKey)) {
+			String expectedList = StringUtils.toEnglishList(expectedKeys.toArray(), false);
+
+			throw new ExpectationException("One of '" + expectedList + "' was expected, not " + curKey);
+		} else {
+			next();
+		}
+	}
+
+	/**
+	 * Utility method for checking that the next token is one of a specific
+	 * set of types, and then consuming it.
+	 * 
+	 * @param expectedKeys
+	 *                The expected values
+	 * 
+	 * @throws ExpectationException
+	 *                 If the token is not one of the expected types.
+	 */
+	default void expect(@SuppressWarnings("unchecked") K... expectedKeys) throws ExpectationException {
+		expect(new HashSet<>(Arrays.asList(expectedKeys)));
+	}
+}