From 41c2a41eaf3c2dd158a2a51947180f402918229e Mon Sep 17 00:00:00 2001 From: bjculkin Date: Fri, 24 Mar 2017 09:54:17 -0400 Subject: Implement Pratt parser. --- .../parserutils/pratt/DefaultLeftCommand.java | 17 ++ .../parserutils/pratt/DefaultNullCommand.java | 25 ++ .../bjc/utils/parserutils/pratt/LeftCommand.java | 63 ++++ .../bjc/utils/parserutils/pratt/LeftCommands.java | 317 +++++++++++++++++++++ .../bjc/utils/parserutils/pratt/NullCommand.java | 38 +++ .../bjc/utils/parserutils/pratt/NullCommands.java | 115 ++++++++ .../bjc/utils/parserutils/pratt/ParserContext.java | 47 +++ .../bjc/utils/parserutils/pratt/PrattParser.java | 121 ++++++++ .../bjc/utils/parserutils/pratt/StringToken.java | 71 +++++ .../utils/parserutils/pratt/StringTokenStream.java | 44 +++ .../java/bjc/utils/parserutils/pratt/Token.java | 30 ++ .../bjc/utils/parserutils/pratt/TokenStream.java | 88 ++++++ 12 files changed, 976 insertions(+) create mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/DefaultLeftCommand.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/DefaultNullCommand.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/LeftCommand.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/LeftCommands.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/NullCommand.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/NullCommands.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/ParserContext.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/PrattParser.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/StringToken.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/StringTokenStream.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/Token.java create mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/TokenStream.java (limited to 'BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt') 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 extends LeftCommand { + + @Override + public ITree> leftDenote(ITree> operand, Token operator, ParserContext 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 + * The key type of the token. + * @param + * The value type of the token. + * + * @param + * The state type of the parser. + */ +public class DefaultNullCommand extends NullCommand { + @Override + public ITree> nullDenotation(Token operator, ParserContext 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 + * The key type for the tokens. + * + * @param + * The value type for the tokens. + * + * @param + * The state type of the parser. + * + */ +public abstract class LeftCommand { + /** + * 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> leftDenote(ITree> operand, Token operator, + ParserContext 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 extends LeftCommand { + private final int leftPower; + + public BinaryPostCommand(int power) { + leftPower = power; + } + + @Override + public int leftBinding() { + return leftPower; + } + } + + private static abstract class BinaryCommand extends BinaryPostCommand { + public BinaryCommand(int leftPower) { + super(leftPower); + } + + protected abstract int rightBinding(); + + @Override + public ITree> leftDenote(ITree> operand, Token operator, + ParserContext ctx) throws ParserException { + ITree> opr = ctx.parse.parseExpression(rightBinding(), ctx.tokens, ctx.state); + + return new Tree<>(operator, operand, opr); + } + } + + private static class LeftBinaryCommand extends BinaryCommand { + public LeftBinaryCommand(int leftPower) { + super(leftPower); + } + + @Override + protected int rightBinding() { + return 1 + leftBinding(); + } + } + + private static class RightBinaryCommand extends BinaryCommand { + public RightBinaryCommand(int leftPower) { + super(leftPower); + } + + @Override + protected int rightBinding() { + return leftBinding(); + } + } + + private static class NonBinaryCommand extends BinaryCommand { + public NonBinaryCommand(int leftPower) { + super(leftPower); + } + + @Override + protected int rightBinding() { + return 1 + leftBinding(); + } + + @Override + public int nextBinding() { + return leftBinding() - 1; + } + } + + private static class PostCircumfixCommand extends BinaryPostCommand { + private int insidePrec; + private K term; + private Token mark; + + public PostCircumfixCommand(int leftPower, int insidePower, K terminator, Token marker) { + super(leftPower); + + insidePrec = insidePower; + term = terminator; + mark = marker; + } + + @SuppressWarnings("unchecked") + @Override + public ITree> leftDenote(ITree> operand, Token operator, + ParserContext ctx) throws ParserException { + ITree> inside = ctx.parse.parseExpression(insidePrec, ctx.tokens, ctx.state); + + ctx.tokens.expect(term); + + return new Tree<>(mark, operand, inside); + } + } + + private static class PostfixCommand extends BinaryPostCommand { + public PostfixCommand(int leftPower) { + super(leftPower); + } + + @Override + public ITree> leftDenote(ITree> operand, Token operator, + ParserContext ctx) throws ParserException { + return new Tree<>(operator, operand); + } + } + + private static class TernaryCommand extends BinaryPostCommand { + private K term; + + private int innerExp; + + private Token mark; + + private boolean nonassoc; + + public TernaryCommand(int leftPower, K terminator, Token mark, boolean isNonassoc) { + super(leftPower); + nonassoc = isNonassoc; + } + + @SuppressWarnings("unchecked") + @Override + public ITree> leftDenote(ITree> operand, Token operator, + ParserContext ctx) throws ParserException { + ITree> inner = ctx.parse.parseExpression(innerExp, ctx.tokens, ctx.state); + + ctx.tokens.expect(term); + + ITree> 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 extends BinaryPostCommand { + private Set chainWith; + + private Token chain; + + public ChainCommand(int leftPower, Set chainSet, Token chainMarker) { + super(leftPower); + + chainWith = chainSet; + chain = chainMarker; + } + + @Override + public ITree> leftDenote(ITree> operand, Token operator, + ParserContext ctx) throws ParserException { + ITree> tree = ctx.parse.parseExpression(1 + leftBinding(), ctx.tokens, ctx.state); + + ITree> res = new Tree<>(operator, operand, tree); + + if(chainWith.contains(ctx.tokens.current().getKey())) { + Token tok = ctx.tokens.current(); + ctx.tokens.next(); + + ITree> 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 LeftCommand 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 LeftCommand 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 LeftCommand 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 LeftCommand chain(int precedence, Set chainSet, Token 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 LeftCommand 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 LeftCommand postCircumfix(int precedence, int insidePrecedence, K closer, + Token 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 LeftCommand ternary(int precedence, int insidePrecedence, K closer, + Token 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 + * The key type for the tokens. + * + * @param + * The value type for the tokens. + * + * @param + * The state type of the parser. + * + * + */ +public abstract class NullCommand { + /** + * 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> nullDenotation(Token operator, ParserContext 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 extends NullCommand { + @Override + public ITree> nullDenotation(Token operator, ParserContext ctx) + throws ParserException { + //tokens.next(); + + return intNullDenotation(operator, ctx); + } + + protected abstract ITree> intNullDenotation(Token operator, ParserContext ctx) + throws ParserException; + + } + + private static class UnaryCommand extends AbstractNullCommand { + private final int nullPwer; + + public UnaryCommand(int nullPower) { + nullPwer = nullPower; + } + + @Override + protected ITree> intNullDenotation(Token operator, ParserContext ctx) + throws ParserException { + ITree> opr = ctx.parse.parseExpression(nullPwer, ctx.tokens, ctx.state); + + return new Tree<>(operator, opr); + } + } + + private static class GroupingCommand extends AbstractNullCommand { + private K term; + private Token mark; + private int inner; + + public GroupingCommand(int innerPrec, K terminator, Token marker) { + inner = innerPrec; + term = terminator; + mark = marker; + } + + @SuppressWarnings("unchecked") + @Override + protected ITree> intNullDenotation(Token operator, ParserContext ctx) + throws ParserException { + ITree> opr = ctx.parse.parseExpression(inner, ctx.tokens, ctx.state); + + ctx.tokens.expect(term); + + return new Tree<>(mark, opr); + } + } + + private static class LeafCommand extends NullCommand { + @Override + public ITree> nullDenotation(Token operator, ParserContext 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 NullCommand 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 NullCommand grouping(int precedence, K term, Token mark) { + return new GroupingCommand<>(precedence, term, mark); + } + + /** + * Create a new leaf operator. + * + * @return A command implementing the operator. + */ + public static NullCommand 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 + * The key type of the tokens. + * @param + * The value type of the tokens. + * + * @param + * The state type of the parser. + */ +public class ParserContext { + /** + * The source of tokens. + */ + public TokenStream tokens; + /** + * The parser for sub-expressions. + */ + public PrattParser 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 tokens, PrattParser 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 + * The key type for the tokens. + * + * @param + * The value type for the tokens. + * + * @param + * The state type of the parser. + * + * + */ +public class PrattParser { + private final LeftCommand DEFAULT_LEFT_COMMAND = new DefaultLeftCommand<>(); + private final NullCommand DEFAULT_NULL_COMMAND = new DefaultNullCommand<>(); + + private Map> leftCommands; + private Map> 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> parseExpression(int precedence, TokenStream tokens, C state) + throws ParserException { + if(precedence < 0) { + throw new IllegalArgumentException("Precedence must be greater than zero"); + } + + Token initToken = tokens.current(); + tokens.next(); + + ITree> ast = nullCommands.getOrDefault(initToken.getKey(), DEFAULT_NULL_COMMAND) + .nullDenotation(initToken, new ParserContext<>(tokens, this, state)); + + int rightPrec = Integer.MAX_VALUE; + + while(true) { + Token tok = tokens.current(); + + K key = tok.getKey(); + + LeftCommand 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 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 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 { + 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 { + private Iterator> iter; + + private Token curr; + + /** + * Create a new token stream from a iterator. + * + * @param itr + * The iterator to use. + * + */ + public StringTokenStream(Iterator> itr) { + iter = itr; + + } + + @Override + public Token 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 + * The key type of this token. Represents the type of the token. + * + * @param + * The value type of this token. Represents any additional data + * for the token. + * + */ +public interface Token { + /** + * 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 + * The key type of the token. + * + * @param + * The value type of the token. + */ +public interface TokenStream { + /** + * 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 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 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))); + } +} -- cgit v1.2.3