Move Pratt Parser to new project

8 files changed, 612 insertions, 0 deletions

diff --git a/JPratt/src/examples/java/bjc/utils/examples/parsing/AssignCommand.java b/JPratt/src/examples/java/bjc/utils/examples/parsing/AssignCommand.java
new file mode 100644
index 0000000..d743c21
--- /dev/null
+++ b/JPratt/src/examples/java/bjc/utils/examples/parsing/AssignCommand.java
@@ -0,0 +1,35 @@
+package bjc.utils.examples.parsing;
+
+import bjc.utils.data.ITree;
+import bjc.utils.data.Tree;
+import bjc.utils.parserutils.ParserException;
+import bjc.utils.parserutils.pratt.ParserContext;
+import bjc.utils.parserutils.pratt.Token;
+import bjc.utils.parserutils.pratt.commands.NonBinaryCommand;
+import bjc.utils.parserutils.pratt.tokens.StringToken;
+
+class AssignCommand extends NonBinaryCommand<String, String, TestContext> {
+	public AssignCommand() {
+		super(10);
+	}
+
+	@Override
+	public ITree<Token<String, String>> denote(ITree<Token<String, String>> operand, Token<String, String> operator,
+			ParserContext<String, String, TestContext> ctx) throws ParserException {
+		Token<String, String> name = operand.getHead();
+
+		switch(name.getKey()) {
+		case "(literal)":
+		case "(vref)":
+			break;
+		default:
+			throw new ParserException("Variable name must be simple");
+		}
+
+		ITree<Token<String, String>> body = ctx.parse.parseExpression(0, ctx.tokens, ctx.state, false);
+
+		ctx.state.scopes.top().putKey(name.getValue(), body);
+
+		return new Tree<>(new StringToken("assign", "assign"), operand, body);
+	}
+}
diff --git a/JPratt/src/examples/java/bjc/utils/examples/parsing/PrattParserTest.java b/JPratt/src/examples/java/bjc/utils/examples/parsing/PrattParserTest.java
new file mode 100644
index 0000000..522bf6f
--- /dev/null
+++ b/JPratt/src/examples/java/bjc/utils/examples/parsing/PrattParserTest.java
@@ -0,0 +1,299 @@
+package bjc.utils.examples.parsing;
+
+import bjc.utils.data.ITree;
+import bjc.utils.data.TransformIterator;
+import bjc.utils.esodata.Directory;
+import bjc.utils.parserutils.ParserException;
+import bjc.utils.parserutils.pratt.InitialCommand;
+import bjc.utils.parserutils.pratt.NonInitialCommand;
+import bjc.utils.parserutils.pratt.PrattParser;
+import bjc.utils.parserutils.pratt.Token;
+import bjc.utils.parserutils.pratt.tokens.StringToken;
+import bjc.utils.parserutils.pratt.tokens.StringTokenStream;
+import bjc.utils.parserutils.splitter.TokenSplitter;
+import bjc.utils.parserutils.splitter.TwoLevelSplitter;
+
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Scanner;
+import java.util.Set;
+import java.util.function.Function;
+import java.util.function.UnaryOperator;
+
+import static bjc.utils.parserutils.pratt.commands.NonInitialCommands.*;
+import static bjc.utils.parserutils.pratt.commands.InitialCommands.*;
+
+import static bjc.utils.parserutils.pratt.tokens.StringToken.litToken;
+
+import static bjc.utils.functypes.ID.id;
+
+/**
+ * Simple test for Pratt parser.
+ * 
+ * @author EVE
+ *
+ */
+public class PrattParserTest {
+	private static final class Tokenizer implements Function<String, Token<String, String>> {
+		private Set<String>	ops;
+		private Set<String>	reserved;
+		private TestContext	ctx;
+
+		public Tokenizer(Set<String> operators, Set<String> reservedWords, TestContext context) {
+			ops = operators;
+			reserved = reservedWords;
+			ctx = context;
+		}
+
+		@Override
+		public Token<String, String> apply(String strang) {
+			if (ops.contains(strang) || reserved.contains(strang)) {
+				return litToken(strang);
+			} else if (ctx.scopes.top().containsKey(strang)) {
+				return new StringToken("(vref)", strang);
+			} else {
+				return new StringToken("(literal)", strang);
+			}
+		}
+	}
+
+	private static final class BlockExit implements UnaryOperator<TestContext> {
+		@Override
+		public TestContext apply(TestContext state) {
+			state.scopes.pop();
+
+			state.blockCount.pop();
+
+			return state;
+		}
+	}
+
+	private static final class BlockEnter implements UnaryOperator<TestContext> {
+		@Override
+		public TestContext apply(TestContext state) {
+			Directory<String, ITree<Token<String, String>>> enclosing = state.scopes.top();
+			int currBlockNumber = state.blockCount.pop();
+
+			state.scopes.push(enclosing.newSubdirectory("block" + currBlockNumber));
+
+			state.blockCount.push(currBlockNumber + 1);
+			state.blockCount.push(0);
+
+			return state;
+		}
+	}
+
+	/**
+	 * Main method.
+	 * 
+	 * @param args
+	 *                Unused CLI arguments.
+	 */
+	public static void main(String[] args) {
+		/*
+		 * Use a linked hash set to preserve insertion order.
+		 */
+		Set<String> ops = new LinkedHashSet<>();
+
+		ops.add(":=");
+		ops.addAll(Arrays.asList("||", "&&"));
+		ops.addAll(Arrays.asList("<=", ">="));
+
+		ops.addAll(Arrays.asList(".", ",", ";", ":"));
+		ops.addAll(Arrays.asList("=", "<", ">"));
+		ops.addAll(Arrays.asList("+", "-", "*", "/"));
+		ops.addAll(Arrays.asList("^", "!"));
+		ops.addAll(Arrays.asList("(", ")"));
+		ops.addAll(Arrays.asList("[", "]"));
+		ops.addAll(Arrays.asList("{", "}"));
+
+		/*
+		 * Reserved words that represent themselves, not literals.
+		 */
+		Set<String> reserved = new LinkedHashSet<>();
+		reserved.addAll(Arrays.asList("if", "then", "else"));
+		reserved.addAll(Arrays.asList("and", "or"));
+		reserved.addAll(Arrays.asList("begin", "end"));
+		reserved.addAll(Arrays.asList("switch", "case"));
+		reserved.add("var");
+
+		TwoLevelSplitter split = new TwoLevelSplitter();
+
+		split.addCompoundDelim(":=");
+		split.addCompoundDelim("||", "&&");
+		split.addCompoundDelim("<=", ">=");
+
+		split.addSimpleDelim(".", ",", ";", ":");
+		split.addSimpleDelim("=", "<", ">");
+		split.addSimpleDelim("+", "-", "*", "/");
+		split.addSimpleDelim("^", "!");
+
+		split.addSimpleMulti("\\(", "\\)");
+		split.addSimpleMulti("\\[", "\\]");
+		split.addSimpleMulti("\\{", "\\}");
+
+		split.exclude(reserved.toArray(new String[0]));
+
+		split.compile();
+
+		PrattParser<String, String, TestContext> parser = createParser();
+
+		TestContext ctx = new TestContext();
+
+		Scanner scn = new Scanner(System.in);
+
+		System.out.print("Enter a command (blank line to exit): ");
+		String ln = scn.nextLine();
+
+		while (!ln.trim().equals("")) {
+			Iterator<Token<String, String>> tokens = preprocessInput(ops, split, ln, reserved, ctx);
+
+			try {
+				StringTokenStream tokenStream = new StringTokenStream(tokens);
+
+				/*
+				 * Prime stream.
+				 */
+				tokenStream.next();
+
+				ITree<Token<String, String>> tree = parser.parseExpression(0, tokenStream, ctx, true);
+
+				if (!tokenStream.headIs("(end)")) {
+					System.out.println("Multiple expressions on line");
+				}
+
+				System.out.println("Parsed expression:\n" + tree);
+			} catch (ParserException pex) {
+				pex.printStackTrace();
+			}
+
+			System.out.print("Enter a command (blank line to exit): ");
+			ln = scn.nextLine();
+		}
+
+		System.out.println();
+		System.out.println("Context is: " + ctx);
+
+		scn.close();
+	}
+
+	private static Iterator<Token<String, String>> preprocessInput(Set<String> ops, TokenSplitter split, String ln,
+			Set<String> reserved, TestContext ctx) {
+		String[] rawTokens = ln.split("\\s+");
+
+		List<String> splitTokens = new LinkedList<>();
+
+		for (String raw : rawTokens) {
+			boolean doSplit = false;
+
+			for (String op : ops) {
+				if (raw.contains(op)) {
+					doSplit = true;
+					break;
+				}
+			}
+
+			if (doSplit) {
+				String[] strangs = split.split(raw);
+
+				splitTokens.addAll(Arrays.asList(strangs));
+			} else {
+				splitTokens.add(raw);
+			}
+		}
+
+		System.out.println("Split string: " + splitTokens);
+
+		Iterator<String> source = splitTokens.iterator();
+
+		Iterator<Token<String, String>> tokens = new TransformIterator<>(source,
+				new Tokenizer(ops, reserved, ctx));
+		return tokens;
+	}
+
+	private static PrattParser<String, String, TestContext> createParser() {
+		/*
+		 * Set of which relational operators chain with each other.
+		 */
+		HashSet<String> relChain = new HashSet<>();
+		relChain.addAll(Arrays.asList("=", "<", ">", "<=", ">="));
+
+		/*
+		 * Token for marking chains.
+		 */
+		StringToken chainToken = litToken("and");
+
+		/*
+		 * ID function.
+		 */
+		UnaryOperator<TestContext> idfun = id();
+
+		PrattParser<String, String, TestContext> parser = new PrattParser<>();
+
+		parser.addNonInitialCommand(":", infixNon(3));
+
+		parser.addNonInitialCommand("if", ternary(5, 0, "else", litToken("cond"), false));
+
+		parser.addNonInitialCommand(":=", new AssignCommand());
+
+		NonInitialCommand<String, String, TestContext> nonSSRelJoin = infixLeft(13);
+		parser.addNonInitialCommand("and", nonSSRelJoin);
+		parser.addNonInitialCommand("or", nonSSRelJoin);
+
+		NonInitialCommand<String, String, TestContext> chainRelOp = chain(15, relChain, chainToken);
+		parser.addNonInitialCommand("=", chainRelOp);
+		parser.addNonInitialCommand("<", chainRelOp);
+		parser.addNonInitialCommand(">", chainRelOp);
+		parser.addNonInitialCommand("<=", chainRelOp);
+		parser.addNonInitialCommand(">=", chainRelOp);
+
+		NonInitialCommand<String, String, TestContext> ssRelJoin = infixRight(17);
+		parser.addNonInitialCommand("&&", ssRelJoin);
+		parser.addNonInitialCommand("||", ssRelJoin);
+
+		NonInitialCommand<String, String, TestContext> addSub = infixLeft(20);
+		parser.addNonInitialCommand("+", addSub);
+		parser.addNonInitialCommand("-", addSub);
+
+		NonInitialCommand<String, String, TestContext> mulDiv = infixLeft(30);
+		parser.addNonInitialCommand("*", mulDiv);
+		parser.addNonInitialCommand("/", mulDiv);
+
+		parser.addNonInitialCommand("!", postfix(40));
+
+		parser.addNonInitialCommand("^", infixRight(50));
+
+		parser.addNonInitialCommand(".", infixLeft(60));
+
+		parser.addNonInitialCommand("[", postCircumfix(60, 0, "]", litToken("idx")));
+
+		parser.addInitialCommand("if", preTernary(0, 0, 0, "then", "else", litToken("ifelse")));
+
+		parser.addInitialCommand("(", grouping(0, ")", litToken("parens")));
+
+		parser.addInitialCommand("begin", delimited(0, ";", "end", litToken("block"), new BlockEnter(), idfun,
+				new BlockExit(), true));
+
+		parser.addInitialCommand("[", delimited(0, ",", "]", litToken("array"), idfun, idfun, idfun, false));
+
+		parser.addInitialCommand("{", delimited(0, ",", "}", litToken("json"), idfun, idfun, idfun, false));
+
+		parser.addInitialCommand("case", unary(5));
+
+		parser.addInitialCommand("-", unary(30));
+
+		InitialCommand<String, String, TestContext> leaf = leaf();
+		parser.addInitialCommand("(literal)", leaf);
+		parser.addInitialCommand("(vref)", leaf);
+
+		parser.addInitialCommand("var", new VarCommand());
+
+		parser.addInitialCommand("switch", new SwitchCommand());
+
+		return parser;
+	}
+}
\ No newline at end of file
diff --git a/JPratt/src/examples/java/bjc/utils/examples/parsing/ShuntTest.java b/JPratt/src/examples/java/bjc/utils/examples/parsing/ShuntTest.java
new file mode 100644
index 0000000..5f84d6b
--- /dev/null
+++ b/JPratt/src/examples/java/bjc/utils/examples/parsing/ShuntTest.java
@@ -0,0 +1,37 @@
+package bjc.utils.examples.parsing;
+
+import bjc.utils.funcdata.FunctionalStringTokenizer;
+import bjc.utils.funcdata.IList;
+import bjc.utils.parserutils.ShuntingYard;
+
+import java.util.Scanner;
+
+/**
+ * Test of shunting yard
+ *
+ * @author ben
+ *
+ */
+public class ShuntTest {
+	/**
+	 * Main method
+	 *
+	 * @param args
+	 *                Unused CLI args
+	 */
+	public static void main(String[] args) {
+		Scanner inputSource = new Scanner(System.in);
+
+		System.out.print("Enter a expression to shunt: ");
+		String line = inputSource.nextLine();
+
+		ShuntingYard<String> yard = new ShuntingYard<>(true);
+
+		IList<String> preTokens = new FunctionalStringTokenizer(line).toList(strang -> strang);
+		IList<String> shuntedTokens = yard.postfix(preTokens, strang -> strang);
+
+		System.out.println(shuntedTokens.toString());
+
+		inputSource.close();
+	}
+}
diff --git a/JPratt/src/examples/java/bjc/utils/examples/parsing/SwitchCommand.java b/JPratt/src/examples/java/bjc/utils/examples/parsing/SwitchCommand.java
new file mode 100644
index 0000000..78d8093
--- /dev/null
+++ b/JPratt/src/examples/java/bjc/utils/examples/parsing/SwitchCommand.java
@@ -0,0 +1,21 @@
+package bjc.utils.examples.parsing;
+
+import bjc.utils.data.ITree;
+import bjc.utils.data.Tree;
+import bjc.utils.parserutils.ParserException;
+import bjc.utils.parserutils.pratt.InitialCommand;
+import bjc.utils.parserutils.pratt.ParserContext;
+import bjc.utils.parserutils.pratt.Token;
+import bjc.utils.parserutils.pratt.tokens.StringToken;
+
+class SwitchCommand implements InitialCommand<String, String, TestContext> {
+	@Override
+	public ITree<Token<String, String>> denote(Token<String, String> operator,
+			ParserContext<String, String, TestContext> ctx) throws ParserException {
+		ITree<Token<String, String>> object = ctx.parse.parseExpression(0, ctx.tokens, ctx.state, false);
+
+		ITree<Token<String, String>> body = ctx.parse.parseExpression(0, ctx.tokens, ctx.state, false);
+
+		return new Tree<>(new StringToken("switch", "switch"), object, body);
+	}
+}
diff --git a/JPratt/src/examples/java/bjc/utils/examples/parsing/TestContext.java b/JPratt/src/examples/java/bjc/utils/examples/parsing/TestContext.java
new file mode 100644
index 0000000..7f9986e
--- /dev/null
+++ b/JPratt/src/examples/java/bjc/utils/examples/parsing/TestContext.java
@@ -0,0 +1,42 @@
+package bjc.utils.examples.parsing;
+
+import bjc.utils.data.ITree;
+import bjc.utils.esodata.Directory;
+import bjc.utils.esodata.SimpleDirectory;
+import bjc.utils.esodata.SimpleStack;
+import bjc.utils.esodata.Stack;
+import bjc.utils.parserutils.pratt.Token;
+
+/**
+ * Simple context for the parser.
+ * 
+ * @author EVE
+ *
+ */
+public class TestContext {
+	/**
+	 * The variable scoping information.
+	 */
+	public Stack<Directory<String, ITree<Token<String, String>>>> scopes;
+
+	/**
+	 * The current number of scopes inside this scope.
+	 */
+	public Stack<Integer> blockCount;
+
+	/**
+	 * Create a new test context.
+	 */
+	public TestContext() {
+		scopes = new SimpleStack<>();
+		blockCount = new SimpleStack<>();
+
+		scopes.push(new SimpleDirectory<>());
+		blockCount.push(0);
+	}
+
+	@Override
+	public String toString() {
+		return String.format("TestContext [scopes=%s\n, blockCount=%s]", scopes, blockCount);
+	}
+}
diff --git a/JPratt/src/examples/java/bjc/utils/examples/parsing/TreeConstructTest.java b/JPratt/src/examples/java/bjc/utils/examples/parsing/TreeConstructTest.java
new file mode 100644
index 0000000..a78a3d5
--- /dev/null
+++ b/JPratt/src/examples/java/bjc/utils/examples/parsing/TreeConstructTest.java
@@ -0,0 +1,129 @@
+package bjc.utils.examples.parsing;
+
+import bjc.utils.data.IPair;
+import bjc.utils.data.ITree;
+import bjc.utils.data.Pair;
+import bjc.utils.data.Tree;
+import bjc.utils.funcdata.FunctionalMap;
+import bjc.utils.funcdata.FunctionalStringTokenizer;
+import bjc.utils.funcdata.IList;
+import bjc.utils.funcdata.IMap;
+import bjc.utils.funcutils.ListUtils;
+import bjc.utils.funcutils.StringUtils;
+import bjc.utils.parserutils.ShuntingYard;
+import bjc.utils.parserutils.TreeConstructor;
+
+import java.util.Deque;
+import java.util.LinkedList;
+import java.util.Scanner;
+import java.util.function.Function;
+import java.util.function.Predicate;
+
+/**
+ * Test of tree constructor
+ *
+ * @author ben
+ *
+ */
+public class TreeConstructTest {
+	private static final class OperatorPicker implements Predicate<String> {
+		@Override
+		public boolean test(String token) {
+			if(StringUtils.containsOnly(token, "\\["))      return true;
+			else if(StringUtils.containsOnly(token, "\\]")) return true;
+
+			switch(token) {
+			case "+":
+			case "-":
+			case "*":
+			case "/":
+				return true;
+			default:
+				return false;
+			}
+		}
+	}
+
+	/**
+	 * Main method
+	 *
+	 * @param args
+	 *                Unused CLI args
+	 */
+	@SuppressWarnings({ "resource", "deprecation" })
+	public static void main(String[] args) {
+		Scanner inputSource = new Scanner(System.in);
+
+		System.out.print("Enter a expression to parse: ");
+		String line = inputSource.nextLine();
+
+		IList<String> tokens = new FunctionalStringTokenizer(line).toList();
+
+		ShuntingYard<String> yard = new ShuntingYard<>(true);
+
+		Deque<IPair<String, String>> ops = new LinkedList<>();
+
+		ops.add(new Pair<>("+", "\\+"));
+		ops.add(new Pair<>("-", "-"));
+		ops.add(new Pair<>("*", "\\*"));
+		ops.add(new Pair<>("/", "/"));
+		ops.add(new Pair<>(":=", ":="));
+		ops.add(new Pair<>("=>", "=>"));
+
+		IList<String> semiExpandedTokens = ListUtils.splitTokens(tokens, ops);
+
+		ops = new LinkedList<>();
+		ops.add(new Pair<>("(", "\\("));
+		ops.add(new Pair<>(")", "\\)"));
+		ops.add(new Pair<>("[", "\\["));
+		ops.add(new Pair<>("]", "\\]"));
+
+		IList<String> fullyExpandedTokens = ListUtils.deAffixTokens(semiExpandedTokens, ops);
+		fullyExpandedTokens.removeIf((strang) -> strang.equals(""));
+
+		IList<String> shuntedTokens = yard.postfix(fullyExpandedTokens, (token) -> token);
+
+		System.out.println("Shunted: " + shuntedTokens.toString());
+
+		Predicate<String> specialPicker = (operator) -> {
+			if(StringUtils.containsOnly(operator, "\\["))      return true;
+			else if(StringUtils.containsOnly(operator, "\\]")) return true;
+
+			return false;
+		};
+
+		IMap<String, Function<Deque<ITree<String>>, ITree<String>>> operators
+			= new FunctionalMap<>();
+
+		operators.put("[", (queuedTrees) -> {
+			return null;
+		});
+
+		operators.put("[", (queuedTrees) -> {
+			Tree<String> openTree = new Tree<>("[");
+
+			queuedTrees.push(openTree);
+
+			return openTree;
+		});
+
+		operators.put("]", (queuedTrees) -> {
+			ITree<String> arrayTree = new Tree<>("[]");
+
+			while(!queuedTrees.peek().getHead().equals("[")) {
+				arrayTree.addChild(queuedTrees.pop());
+			}
+
+			queuedTrees.push(arrayTree);
+
+			return arrayTree;
+		});
+
+		ITree<String> constructedTree = TreeConstructor.constructTree(shuntedTokens,
+				new OperatorPicker(), specialPicker, operators::get);
+
+		System.out.println("AST: " + constructedTree.toString());
+
+		inputSource.close();
+	}
+}
diff --git a/JPratt/src/examples/java/bjc/utils/examples/parsing/VarCommand.java b/JPratt/src/examples/java/bjc/utils/examples/parsing/VarCommand.java
new file mode 100644
index 0000000..5cf4b25
--- /dev/null
+++ b/JPratt/src/examples/java/bjc/utils/examples/parsing/VarCommand.java
@@ -0,0 +1,36 @@
+package bjc.utils.examples.parsing;
+
+import bjc.utils.data.ITree;
+import bjc.utils.data.Tree;
+import bjc.utils.parserutils.ParserException;
+import bjc.utils.parserutils.pratt.ParserContext;
+import bjc.utils.parserutils.pratt.Token;
+import bjc.utils.parserutils.pratt.commands.AbstractInitialCommand;
+import bjc.utils.parserutils.pratt.tokens.StringToken;
+
+class VarCommand extends AbstractInitialCommand<String, String, TestContext> {
+
+	@Override
+	protected ITree<Token<String, String>> intNullDenotation(Token<String, String> operator,
+			ParserContext<String, String, TestContext> ctx) throws ParserException {
+		Token<String, String> name = ctx.tokens.current();
+
+		switch(name.getKey()) {
+		case "(literal)":
+		case "(vref)":
+			ctx.tokens.next();
+			break;
+		default:
+			throw new ParserException("Variable name must be simple");
+		}
+
+		ctx.tokens.expect("=");
+
+		ITree<Token<String, String>> body = ctx.parse.parseExpression(0, ctx.tokens, ctx.state, false);
+
+		ctx.state.scopes.top().putKey(name.getValue(), body);
+
+		return new Tree<>(new StringToken("var-bind", "var-bind"), new Tree<>(name), body);
+	}
+
+}
diff --git a/JPratt/src/examples/java/bjc/utils/examples/parsing/test.tree b/JPratt/src/examples/java/bjc/utils/examples/parsing/test.tree
new file mode 100644
index 0000000..795cc88
--- /dev/null
+++ b/JPratt/src/examples/java/bjc/utils/examples/parsing/test.tree
@@ -0,0 +1,13 @@
+test 1
+	1
+	1
+		2
+		2
+	1
+
+simp 1
+	2
+		3
+			4
+		3
+	2
\ No newline at end of file