From 41c2a41eaf3c2dd158a2a51947180f402918229e Mon Sep 17 00:00:00 2001 From: bjculkin Date: Fri, 24 Mar 2017 09:54:17 -0400 Subject: Implement Pratt parser. --- .../bjc/utils/parserutils/pratt/LeftCommands.java | 317 +++++++++++++++++++++ 1 file changed, 317 insertions(+) create mode 100644 BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/LeftCommands.java (limited to 'BJC-Utils2/src/main/java/bjc/utils/parserutils/pratt/LeftCommands.java') 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); + } +} -- cgit v1.2.3