diff options
48 files changed, 2842 insertions, 0 deletions
diff --git a/JPratt/.classpath b/JPratt/.classpath new file mode 100644 index 0000000..a22b331 --- /dev/null +++ b/JPratt/.classpath @@ -0,0 +1,16 @@ +<?xml version="1.0" encoding="UTF-8"?> +<classpath> + <classpathentry kind="src" path="src/main/java"/> + <classpathentry kind="src" path="src/examples/java"/> + <classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.8"> + <attributes> + <attribute name="maven.pomderived" value="true"/> + </attributes> + </classpathentry> + <classpathentry kind="con" path="org.eclipse.m2e.MAVEN2_CLASSPATH_CONTAINER"> + <attributes> + <attribute name="maven.pomderived" value="true"/> + </attributes> + </classpathentry> + <classpathentry kind="output" path="target/classes"/> +</classpath> diff --git a/JPratt/.gitignore b/JPratt/.gitignore new file mode 100644 index 0000000..09e3bc9 --- /dev/null +++ b/JPratt/.gitignore @@ -0,0 +1,2 @@ +/bin/ +/target/ diff --git a/JPratt/.project b/JPratt/.project new file mode 100644 index 0000000..a78486a --- /dev/null +++ b/JPratt/.project @@ -0,0 +1,23 @@ +<?xml version="1.0" encoding="UTF-8"?> +<projectDescription> + <name>JPratt</name> + <comment></comment> + <projects> + </projects> + <buildSpec> + <buildCommand> + <name>org.eclipse.jdt.core.javabuilder</name> + <arguments> + </arguments> + </buildCommand> + <buildCommand> + <name>org.eclipse.m2e.core.maven2Builder</name> + <arguments> + </arguments> + </buildCommand> + </buildSpec> + <natures> + <nature>org.eclipse.m2e.core.maven2Nature</nature> + <nature>org.eclipse.jdt.core.javanature</nature> + </natures> +</projectDescription> diff --git a/JPratt/.settings/org.eclipse.jdt.core.prefs b/JPratt/.settings/org.eclipse.jdt.core.prefs new file mode 100644 index 0000000..714351a --- /dev/null +++ b/JPratt/.settings/org.eclipse.jdt.core.prefs @@ -0,0 +1,5 @@ +eclipse.preferences.version=1 +org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.8 +org.eclipse.jdt.core.compiler.compliance=1.8 +org.eclipse.jdt.core.compiler.problem.forbiddenReference=warning +org.eclipse.jdt.core.compiler.source=1.8 diff --git a/JPratt/.settings/org.eclipse.m2e.core.prefs b/JPratt/.settings/org.eclipse.m2e.core.prefs new file mode 100644 index 0000000..f897a7f --- /dev/null +++ b/JPratt/.settings/org.eclipse.m2e.core.prefs @@ -0,0 +1,4 @@ +activeProfiles= +eclipse.preferences.version=1 +resolveWorkspaceProjects=true +version=1 diff --git a/JPratt/pom.xml b/JPratt/pom.xml new file mode 100644 index 0000000..a1ef7a9 --- /dev/null +++ b/JPratt/pom.xml @@ -0,0 +1,28 @@ +<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"> + <modelVersion>4.0.0</modelVersion> + <groupId>bjc</groupId> + <artifactId>JPratt</artifactId> + <version>0.0.1-SNAPSHOT</version> + <name>JPratt</name> + <description>Pratt parser in java</description> + <build> + <sourceDirectory>src</sourceDirectory> + <plugins> + <plugin> + <artifactId>maven-compiler-plugin</artifactId> + <version>3.5.1</version> + <configuration> + <source>1.8</source> + <target>1.8</target> + </configuration> + </plugin> + </plugins> + </build> + <dependencies> + <dependency> + <groupId>bjc</groupId> + <artifactId>BJC-Utils2</artifactId> + <version>0.1.0-SNAPSHOT</version> + </dependency> + </dependencies> +</project>
\ No newline at end of file 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 diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/InitialCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/InitialCommand.java new file mode 100644 index 0000000..716b99e --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/InitialCommand.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. + * + * + */ +@FunctionalInterface +public interface InitialCommand<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. + */ + ITree<Token<K, V>> denote(Token<K, V> operator, ParserContext<K, V, C> ctx) throws ParserException; +} diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/NonInitialCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/NonInitialCommand.java new file mode 100644 index 0000000..b6797d3 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/NonInitialCommand.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 NonInitialCommand<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>> denote(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/JPratt/src/main/java/bjc/utils/parserutils/pratt/ParseBlock.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/ParseBlock.java new file mode 100644 index 0000000..4542107 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/ParseBlock.java @@ -0,0 +1,37 @@ +package bjc.utils.parserutils.pratt; + +import bjc.utils.data.ITree; +import bjc.utils.parserutils.ParserException; + +/** + * Represents a embedded block in an expression. + * + * @author bjculkin + * + * @param <K> + * The key type of the token. + * + * @param <V> + * The value type of the token. + * + * @param <C> + * The state type of the parser. + */ +@FunctionalInterface +public interface ParseBlock<K, V, C> { + + /** + * Parse the block this represents. + * + * @param ctx + * The context for parsing. + * + * @return A AST for this block. + * + * @throws ParserException + * If something goes wrong during parsing, or the block + * fails validation. + */ + ITree<Token<K, V>> parse(ParserContext<K, V, C> ctx) throws ParserException; + +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/ParserContext.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/ParserContext.java new file mode 100644 index 0000000..55b5e98 --- /dev/null +++ b/JPratt/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/JPratt/src/main/java/bjc/utils/parserutils/pratt/PrattParser.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/PrattParser.java new file mode 100644 index 0000000..c53b4e1 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/PrattParser.java @@ -0,0 +1,190 @@ +package bjc.utils.parserutils.pratt; + +import bjc.utils.data.ITree; +import bjc.utils.funcutils.NumberUtils; +import bjc.utils.parserutils.ParserException; +import bjc.utils.parserutils.pratt.commands.DefaultNonInitialCommand; +import bjc.utils.parserutils.pratt.commands.DefaultInitialCommand; + +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> { + /* + * Default commands that error when used. + */ + private final NonInitialCommand<K, V, C> DEFAULT_LEFT_COMMAND = new DefaultNonInitialCommand<>(); + private final InitialCommand<K, V, C> DEFAULT_NULL_COMMAND = new DefaultInitialCommand<>(); + + /* + * Left-commands that depend on what the null command was. + */ + private Map<K, Map<K, NonInitialCommand<K, V, C>>> dependantLeftCommands; + + /* + * The left commands. + */ + private Map<K, NonInitialCommand<K, V, C>> leftCommands; + /* + * The initial commands. + */ + private Map<K, InitialCommand<K, V, C>> nullCommands; + /* + * Initial commands only checked for statements. + */ + private Map<K, InitialCommand<K, V, C>> statementCommands; + + /** + * Create a new Pratt parser. + * + */ + public PrattParser() { + dependantLeftCommands = new HashMap<>(); + + leftCommands = new HashMap<>(); + nullCommands = new HashMap<>(); + statementCommands = 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. + * + * @param isStatement + * Whether or not to parse statements. + * + * @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, + boolean isStatement) throws ParserException { + if (precedence < 0) { + throw new IllegalArgumentException("Precedence must be greater than zero"); + } + + Token<K, V> initToken = tokens.current(); + tokens.next(); + + K initKey = initToken.getKey(); + + ITree<Token<K, V>> ast; + + if (isStatement && statementCommands.containsKey(initKey)) { + ast = statementCommands.getOrDefault(initKey, DEFAULT_NULL_COMMAND).denote(initToken, + new ParserContext<>(tokens, this, state)); + } else { + ast = nullCommands.getOrDefault(initKey, DEFAULT_NULL_COMMAND).denote(initToken, + new ParserContext<>(tokens, this, state)); + } + + int rightPrec = Integer.MAX_VALUE; + + while (true) { + Token<K, V> tok = tokens.current(); + + K key = tok.getKey(); + + NonInitialCommand<K, V, C> command = leftCommands.getOrDefault(key, DEFAULT_LEFT_COMMAND); + + if (dependantLeftCommands.containsKey(initKey)) { + command = dependantLeftCommands.get(initKey).getOrDefault(key, command); + } + + int leftBind = command.leftBinding(); + + if (NumberUtils.between(precedence, rightPrec, leftBind)) { + tokens.next(); + + ast = command.denote(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, NonInitialCommand<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, InitialCommand<K, V, C> comm) { + nullCommands.put(marker, comm); + } + + /** + * Add a statement command to this parser. + * + * The difference between statements and initial commands is that + * statements can only appear at the start of the expression. + * + * @param marker + * The key that marks the command. + * + * @param comm + * The command. + */ + public void addStatementCommand(K marker, InitialCommand<K, V, C> comm) { + statementCommands.put(marker, comm); + } + + /** + * Add a dependant non-initial command to this parser. + */ + public void addDependantCommand(K dependant, K marker, NonInitialCommand<K, V, C> comm) { + if (dependantLeftCommands.containsKey(dependant)) { + dependantLeftCommands.get(dependant).put(marker, comm); + } else { + Map<K, NonInitialCommand<K, V, C>> comms = new HashMap<>(); + + comms.put(marker, comm); + + dependantLeftCommands.put(dependant, comms); + } + } +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/Token.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/Token.java new file mode 100644 index 0000000..6db8b63 --- /dev/null +++ b/JPratt/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/JPratt/src/main/java/bjc/utils/parserutils/pratt/TokenStream.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/TokenStream.java new file mode 100644 index 0000000..227e9a1 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/TokenStream.java @@ -0,0 +1,95 @@ +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.Iterator; +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 abstract class TokenStream<K, V> implements Iterator<Token<K, V>> { + /** + * The exception thrown when an expectation fails. + * + * @author EVE + * + */ + public static class ExpectationException extends ParserException { + private static final long serialVersionUID = 4299299480127680805L; + + /** + * 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. + */ + public abstract Token<K, V> current(); + + @Override + public abstract Token<K, V> next(); + + @Override + public abstract boolean hasNext(); + + /** + * 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. + */ + public 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. + */ + @SafeVarargs + public final void expect(K... expectedKeys) throws ExpectationException { + expect(new HashSet<>(Arrays.asList(expectedKeys))); + } + + public boolean headIs(K val) { + return current().getKey().equals(val); + } +} diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/blocks/ParseBlocks.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/blocks/ParseBlocks.java new file mode 100644 index 0000000..9df8355 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/blocks/ParseBlocks.java @@ -0,0 +1,84 @@ +package bjc.utils.parserutils.pratt.blocks; + +import java.util.function.Predicate; +import java.util.function.UnaryOperator; + +import bjc.utils.data.ITree; +import bjc.utils.parserutils.pratt.ParseBlock; +import bjc.utils.parserutils.pratt.Token; + +/** + * Utility class for creating common implementations of {@link ParseBlock} + * + * @author bjculkin + * + */ +public class ParseBlocks { + /** + * Create a new repeating parse block. + * + * @param inner + * The parse block to repeat. + * + * @param delim + * The token type that seperates repetitions. + * + * @param term + * The token type that terminates repititions. + * + * @param mark + * The token to use as the node in the AST. + * + * @param action + * The action to perform on the state after every + * repitition. + * + * @return A configured repeating parse block. + */ + public static <K, V, C> ParseBlock<K, V, C> repeating(ParseBlock<K, V, C> inner, K delim, K term, + Token<K, V> mark, UnaryOperator<C> action) { + return new RepeatingParseBlock<>(inner, delim, term, mark, action); + } + + /** + * Create a new triggered parse block. + * + * @param source + * The block to trigger around. + * + * @param onEnter + * The action to perform upon the state before entering + * the block. + * + * @param onExit + * The action to perform upon the state after exiting the + * block. + * + * @return A configured trigger parse block. + */ + public static <K, V, C> ParseBlock<K, V, C> trigger(ParseBlock<K, V, C> source, UnaryOperator<C> onEnter, + UnaryOperator<C> onExit) { + return new TriggeredParseBlock<>(onEnter, onExit, source); + } + + /** + * Create a new simple parse block. + * + * @param precedence + * The precedence of the expression inside the block. + * + * @param terminator + * The key type of the token expected after this block, + * or null if none is expected. + * + * @param validator + * The predicate to use to validate parsed expressions, + * or null if none is used. + * + * @return A configured simple parse block. + */ + public static <K, V, C> ParseBlock<K, V, C> simple(int precedence, K terminator, + Predicate<ITree<Token<K, V>>> validator) { + return new SimpleParseBlock<>(precedence, terminator, validator); + } +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/blocks/RepeatingParseBlock.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/blocks/RepeatingParseBlock.java new file mode 100644 index 0000000..08a4bae --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/blocks/RepeatingParseBlock.java @@ -0,0 +1,96 @@ +package bjc.utils.parserutils.pratt.blocks; + +import java.util.function.UnaryOperator; + +import bjc.utils.data.ITree; +import bjc.utils.data.Tree; +import bjc.utils.parserutils.ParserException; +import bjc.utils.parserutils.pratt.ParseBlock; +import bjc.utils.parserutils.pratt.ParserContext; +import bjc.utils.parserutils.pratt.Token; + +/** + * A parse block that can parse a sequnce of zero or more occurances of another + * block. + * + * @author bjculkin + * + * @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 RepeatingParseBlock<K, V, C> implements ParseBlock<K, V, C> { + private ParseBlock<K, V, C> innerBlock; + + private K delim; + private K term; + + private UnaryOperator<C> onDelim; + + private Token<K, V> mark; + + /** + * Create a new repeating block. + * + * @param inner + * The inner block for elements. + * + * @param delimiter + * The token that delimits elements in the sequence. + * + * @param terminator + * The token that terminates the sequence. + * + * @param marker + * The token to use as the node in the AST. + * + * @param action + * The action to apply to the state after every + * delimiter. + */ + public RepeatingParseBlock(ParseBlock<K, V, C> inner, K delimiter, K terminator, Token<K, V> marker, + UnaryOperator<C> action) { + super(); + + if (inner == null) + throw new NullPointerException("Inner block must not be null"); + else if (delimiter == null) + throw new NullPointerException("Delimiter must not be null"); + else if (terminator == null) throw new NullPointerException("Terminator must not be null"); + + innerBlock = inner; + + delim = delimiter; + term = terminator; + + mark = marker; + + onDelim = action; + } + + @Override + public ITree<Token<K, V>> parse(ParserContext<K, V, C> ctx) throws ParserException { + ITree<Token<K, V>> ret = new Tree<>(mark); + + Token<K, V> tok = ctx.tokens.current(); + + while (!tok.getKey().equals(term)) { + ITree<Token<K, V>> kid = innerBlock.parse(ctx); + ret.addChild(kid); + + tok = ctx.tokens.current(); + + ctx.tokens.expect(delim, term); + + if (onDelim != null) ctx.state = onDelim.apply(ctx.state); + } + + return ret; + } + +} diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/blocks/SimpleParseBlock.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/blocks/SimpleParseBlock.java new file mode 100644 index 0000000..c2e9e54 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/blocks/SimpleParseBlock.java @@ -0,0 +1,101 @@ +package bjc.utils.parserutils.pratt.blocks; + +import java.util.function.Predicate; + +import bjc.utils.data.ITree; +import bjc.utils.parserutils.ParserException; +import bjc.utils.parserutils.pratt.ParseBlock; +import bjc.utils.parserutils.pratt.ParserContext; +import bjc.utils.parserutils.pratt.Token; + +/** + * Simple implementation of {@link ParseBlock} + * + * @author bjculkin + * + * @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 SimpleParseBlock<K, V, C> implements ParseBlock<K, V, C> { + private int pow; + + private K term; + + private Predicate<ITree<Token<K, V>>> validatr; + + /** + * Create a new block. + * + * @param precedence + * The precedence of this block. + * + * @param terminator + * The token type that terminates the block. If this is + * null, don't check for a terminator. + * + * @param validator + * The predicate to apply to blocks. + */ + public SimpleParseBlock(int precedence, K terminator, Predicate<ITree<Token<K, V>>> validator) { + if (precedence < 0) throw new IllegalArgumentException("Precedence must be non-negative"); + + pow = precedence; + term = terminator; + validatr = validator; + } + + @Override + public ITree<Token<K, V>> parse(ParserContext<K, V, C> ctx) throws ParserException { + ITree<Token<K, V>> res = ctx.parse.parseExpression(pow, ctx.tokens, ctx.state, false); + + if (term != null) { + ctx.tokens.expect(term); + } + + if (validatr == null || validatr.test(res)) { + return res; + } + + throw new ParserException("Block failed validation"); + } + + @Override + public int hashCode() { + final int prime = 31; + + int result = 1; + + result = prime * result + pow; + result = prime * result + ((term == null) ? 0 : term.hashCode()); + + return result; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) return true; + if (obj == null) return false; + if (!(obj instanceof SimpleParseBlock)) return false; + + SimpleParseBlock<?, ?, ?> other = (SimpleParseBlock<?, ?, ?>) obj; + + if (pow != other.pow) return false; + + if (term == null) { + if (other.term != null) return false; + } else if (!term.equals(other.term)) return false; + + return true; + } + + @Override + public String toString() { + return String.format("ParseBlock [pow=%s, term='%s']", pow, term); + } +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/blocks/TriggeredParseBlock.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/blocks/TriggeredParseBlock.java new file mode 100644 index 0000000..fbfc61b --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/blocks/TriggeredParseBlock.java @@ -0,0 +1,61 @@ +package bjc.utils.parserutils.pratt.blocks; + +import java.util.function.UnaryOperator; + +import bjc.utils.data.ITree; +import bjc.utils.parserutils.ParserException; +import bjc.utils.parserutils.pratt.ParseBlock; +import bjc.utils.parserutils.pratt.ParserContext; +import bjc.utils.parserutils.pratt.Token; + +/** + * A parse block that can adjust the state before handling its context. + * + * @author bjculkin + * + * @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 TriggeredParseBlock<K, V, C> implements ParseBlock<K, V, C> { + private UnaryOperator<C> onEnter; + private UnaryOperator<C> onExit; + + private ParseBlock<K, V, C> source; + + /** + * Create a new triggered parse block. + * + * @param onEnter + * The action to fire before parsing the block. + * + * @param onExit + * The action to fire after parsing the block. + * + * @param source + * The block to use for parsing. + */ + public TriggeredParseBlock(UnaryOperator<C> onEnter, UnaryOperator<C> onExit, ParseBlock<K, V, C> source) { + super(); + this.onEnter = onEnter; + this.onExit = onExit; + this.source = source; + } + + @Override + public ITree<Token<K, V>> parse(ParserContext<K, V, C> ctx) throws ParserException { + C newState = onEnter.apply(ctx.state); + + ParserContext<K, V, C> newCtx = new ParserContext<>(ctx.tokens, ctx.parse, newState); + + ITree<Token<K, V>> res = source.parse(newCtx); + + ctx.state = onExit.apply(newState); + + return res; + } + +} diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/AbstractInitialCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/AbstractInitialCommand.java new file mode 100644 index 0000000..3c3a89b --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/AbstractInitialCommand.java @@ -0,0 +1,32 @@ +package bjc.utils.parserutils.pratt.commands; + +import bjc.utils.data.ITree; +import bjc.utils.parserutils.ParserException; +import bjc.utils.parserutils.pratt.InitialCommand; +import bjc.utils.parserutils.pratt.ParserContext; +import bjc.utils.parserutils.pratt.Token; + +/** + * Abstract base for initial commands. + * + * @author bjculkin + * + * @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 abstract class AbstractInitialCommand<K, V, C> implements InitialCommand<K, V, C> { + @Override + public ITree<Token<K, V>> denote(Token<K, V> operator, ParserContext<K, V, C> ctx) throws ParserException { + return intNullDenotation(operator, ctx); + } + + protected abstract ITree<Token<K, V>> intNullDenotation(Token<K, V> operator, ParserContext<K, V, C> ctx) + throws ParserException; + +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/BinaryCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/BinaryCommand.java new file mode 100644 index 0000000..781309c --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/BinaryCommand.java @@ -0,0 +1,43 @@ +package bjc.utils.parserutils.pratt.commands; + +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; + +/** + * A binary operator. + * + * @author bjculkin + * + * @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 abstract class BinaryCommand<K, V, C> extends BinaryPostCommand<K, V, C> { + /** + * Create a new binary operator with the specified precedence. + * + * @param precedence + * The precedence of the operator. + */ + public BinaryCommand(int precedence) { + super(precedence); + } + + protected abstract int rightBinding(); + + @Override + public ITree<Token<K, V>> denote(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, false); + + return new Tree<>(operator, operand, opr); + } +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/BinaryPostCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/BinaryPostCommand.java new file mode 100644 index 0000000..806f2f3 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/BinaryPostCommand.java @@ -0,0 +1,40 @@ +package bjc.utils.parserutils.pratt.commands; + +import bjc.utils.parserutils.pratt.NonInitialCommand; + +/** + * A operator with fixed precedence. + * + * @author bjculkin + * + * @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 abstract class BinaryPostCommand<K, V, C> extends NonInitialCommand<K, V, C> { + private final int leftPower; + + /** + * Create a new operator with fixed precedence. + * + * @param precedence + * The precedence of the operator. + */ + public BinaryPostCommand(int precedence) { + if (precedence < 0) { + throw new IllegalArgumentException("Precedence must be non-negative"); + } + + leftPower = precedence; + } + + @Override + public int leftBinding() { + return leftPower; + } +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/ChainCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/ChainCommand.java new file mode 100644 index 0000000..1324586 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/ChainCommand.java @@ -0,0 +1,73 @@ +package bjc.utils.parserutils.pratt.commands; + +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 java.util.Set; + +/** + * Create a new chained operator. + * + * @author bjculkin + * + * @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 ChainCommand<K, V, C> extends BinaryPostCommand<K, V, C> { + private Set<K> chainWith; + + private Token<K, V> chain; + + /** + * Create a new chained operator. + * + * @param precedence + * The precedence of this operator. + * + * @param chainSet + * The operators to chain with. + * + * @param chainMarker + * The token to use as the node in the AST. + */ + public ChainCommand(int precedence, Set<K> chainSet, Token<K, V> chainMarker) { + super(precedence); + + chainWith = chainSet; + chain = chainMarker; + } + + @Override + public ITree<Token<K, V>> denote(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, false); + + 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 = denote(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; + } +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/ConstantCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/ConstantCommand.java new file mode 100644 index 0000000..10ff184 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/ConstantCommand.java @@ -0,0 +1,40 @@ +package bjc.utils.parserutils.pratt.commands; + +import bjc.utils.data.ITree; +import bjc.utils.parserutils.ParserException; +import bjc.utils.parserutils.pratt.InitialCommand; +import bjc.utils.parserutils.pratt.ParserContext; +import bjc.utils.parserutils.pratt.Token; + +/** + * A command that represents a specific tree. + * + * @author bjculkin + * + * @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 ConstantCommand<K, V, C> implements InitialCommand<K, V, C> { + private ITree<Token<K, V>> val; + + /** + * Create a new constant. + * + * @param con + * The tree this constant represents. + */ + public ConstantCommand(ITree<Token<K, V>> con) { + val = con; + } + + @Override + public ITree<Token<K, V>> denote(Token<K, V> operator, ParserContext<K, V, C> ctx) throws ParserException { + return val; + } +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/DefaultInitialCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/DefaultInitialCommand.java new file mode 100644 index 0000000..7409755 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/DefaultInitialCommand.java @@ -0,0 +1,28 @@ +package bjc.utils.parserutils.pratt.commands; + +import bjc.utils.data.ITree; +import bjc.utils.parserutils.ParserException; +import bjc.utils.parserutils.pratt.InitialCommand; +import bjc.utils.parserutils.pratt.ParserContext; +import bjc.utils.parserutils.pratt.Token; + +/** + * Default implementation of an initial 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 DefaultInitialCommand<K, V, C> implements InitialCommand<K, V, C> { + @Override + public ITree<Token<K, V>> denote(Token<K, V> operator, ParserContext<K, V, C> ctx) throws ParserException { + throw new ParserException("Unexpected token " + operator); + } +} diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/DefaultNonInitialCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/DefaultNonInitialCommand.java new file mode 100644 index 0000000..887dd25 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/DefaultNonInitialCommand.java @@ -0,0 +1,32 @@ +package bjc.utils.parserutils.pratt.commands; + +import bjc.utils.data.ITree; +import bjc.utils.parserutils.pratt.NonInitialCommand; +import bjc.utils.parserutils.pratt.ParserContext; +import bjc.utils.parserutils.pratt.Token; + +/** + * Default implementation of a non-initial 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 DefaultNonInitialCommand<K, V, C> extends NonInitialCommand<K, V, C> { + @Override + public ITree<Token<K, V>> denote(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/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/DenestingCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/DenestingCommand.java new file mode 100644 index 0000000..567e608 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/DenestingCommand.java @@ -0,0 +1,45 @@ +package bjc.utils.parserutils.pratt.commands; + +import bjc.utils.data.ITree; +import bjc.utils.parserutils.ParserException; +import bjc.utils.parserutils.pratt.InitialCommand; +import bjc.utils.parserutils.pratt.ParserContext; +import bjc.utils.parserutils.pratt.Token; + +/** + * A command that denests a input tree. + * + * Useful for processing the result of passing a complex parse group to a + * command. + * + * @author bjculkin + * + * @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 DenestingCommand<K, V, C> extends AbstractInitialCommand<K, V, C> { + private InitialCommand<K, V, C> wrapped; + + /** + * Create a new transforming initial command. + * + * @param internal + * The initial command to delegate to. + */ + public DenestingCommand(InitialCommand<K, V, C> internal) { + wrapped = internal; + } + + @Override + protected ITree<Token<K, V>> intNullDenotation(Token<K, V> operator, ParserContext<K, V, C> ctx) + throws ParserException { + return wrapped.denote(operator, ctx).getChild(0); + } +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/GroupingCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/GroupingCommand.java new file mode 100644 index 0000000..37cc6ee --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/GroupingCommand.java @@ -0,0 +1,51 @@ +package bjc.utils.parserutils.pratt.commands; + +import bjc.utils.data.ITree; +import bjc.utils.data.Tree; +import bjc.utils.parserutils.ParserException; +import bjc.utils.parserutils.pratt.ParseBlock; +import bjc.utils.parserutils.pratt.ParserContext; +import bjc.utils.parserutils.pratt.Token; + +/** + * A grouping operator. + * + * @author bjculkin + * + * @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 GroupingCommand<K, V, C> extends AbstractInitialCommand<K, V, C> { + private ParseBlock<K, V, C> innerBlock; + + private Token<K, V> mark; + + /** + * Create a new grouping command. + * + * @param inner + * The inner block. + * + * @param marker + * The token to use as the node in the AST. + */ + public GroupingCommand(ParseBlock<K, V, C> inner, Token<K, V> marker) { + innerBlock = inner; + + mark = marker; + } + + @Override + protected ITree<Token<K, V>> intNullDenotation(Token<K, V> operator, ParserContext<K, V, C> ctx) + throws ParserException { + ITree<Token<K, V>> opr = innerBlock.parse(ctx); + + return new Tree<>(mark, opr); + } +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/InitialCommands.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/InitialCommands.java new file mode 100644 index 0000000..eac357a --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/InitialCommands.java @@ -0,0 +1,168 @@ +package bjc.utils.parserutils.pratt.commands; + +import bjc.utils.data.ITree; +import bjc.utils.parserutils.pratt.InitialCommand; +import bjc.utils.parserutils.pratt.ParseBlock; +import bjc.utils.parserutils.pratt.Token; + +import java.util.function.UnaryOperator; + +import static bjc.utils.parserutils.pratt.blocks.ParseBlocks.*; + +/** + * * Contains factory methods for producing common implementations of + * {@link InitialCommand} + * + * @author EVE + * + */ +public class InitialCommands { + /** + * Create a new unary operator. + * + * @param precedence + * The precedence of the operator. + * + * @return A command implementing that operator. + */ + public static <K, V, C> InitialCommand<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> InitialCommand<K, V, C> grouping(int precedence, K term, Token<K, V> mark) { + ParseBlock<K, V, C> innerBlock = simple(precedence, term, null); + + return new GroupingCommand<>(innerBlock, mark); + } + + /** + * Create a new leaf operator. + * + * @return A command implementing the operator. + */ + public static <K, V, C> InitialCommand<K, V, C> leaf() { + return new LeafCommand<>(); + } + + /** + * Create a new pre-ternary operator, like an if-then-else statement. + * + * @param cond1 + * The priority of the first block. + * + * @param block1 + * The priority of the second block. + * + * @param block2 + * The priority of the third block. + * + * @param mark1 + * The marker that ends the first block. + * + * @param mark2 + * The marker that ends the second block. + * + * @param term + * The token for the AST node of the group. + * + * @return A command implementing the operator. + */ + public static <K, V, C> InitialCommand<K, V, C> preTernary(int cond1, int block1, int block2, K mark1, K mark2, + Token<K, V> term) { + ParseBlock<K, V, C> condBlock = simple(cond1, mark1, null); + ParseBlock<K, V, C> opblock1 = simple(block1, mark2, null); + ParseBlock<K, V, C> opblock2 = simple(block2, null, null); + + return new PreTernaryCommand<>(condBlock, opblock1, opblock2, term); + } + + /** + * Create a new named constant. + * + * @param val + * The value of the constant. + * + * @return A command implementing the constant. + */ + public static <K, V, C> InitialCommand<K, V, C> constant(ITree<Token<K, V>> val) { + return new ConstantCommand<>(val); + } + + /** + * Create a new delimited command. This is for block-like constructs. + * + * @param inner + * The precedence of the inner blocks. + * + * @param delim + * The marker between sub-blocks. + * + * @param mark + * The block terminator. + * + * @param term + * The token for the AST node of the group. + * + * @param onEnter + * The function to apply to the state on entering the + * block. + * + * @param onDelim + * The function to apply to the state on finishing a + * sub-block. + * + * @param onExit + * The function to apply to the state on exiting the + * block. + * + * @param statement + * Whether or not the sub-blocks are statements or + * expressions. + * + * @return A command implementing the operator. + */ + public static <K, V, C> InitialCommand<K, V, C> delimited(int inner, K delim, K mark, Token<K, V> term, + UnaryOperator<C> onEnter, UnaryOperator<C> onDelim, UnaryOperator<C> onExit, + boolean statement) { + ParseBlock<K, V, C> innerBlock = simple(inner, null, null); + ParseBlock<K, V, C> delimsBlock = repeating(innerBlock, delim, mark, term, onDelim); + ParseBlock<K, V, C> scopedBlock = trigger(delimsBlock, onEnter, onExit); + + GroupingCommand<K, V, C> command = new GroupingCommand<>(scopedBlock, term); + + /* + * Remove the wrapper layer from grouping-command on top of + * RepeatingParseBlock. + */ + return denest(command); + } + + /** + * Create a new denesting command. + * + * This removes one tree-level, and is useful when combining complex + * parse blocks with commands. + * + * @param comm + * The command to denest. + * + * @return A command that denests the result of the provided command. + */ + public static <K, V, C> InitialCommand<K, V, C> denest(InitialCommand<K, V, C> comm) { + return new DenestingCommand<>(comm); + } +} diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/LeafCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/LeafCommand.java new file mode 100644 index 0000000..3937f5f --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/LeafCommand.java @@ -0,0 +1,29 @@ +package bjc.utils.parserutils.pratt.commands; + +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; + +/** + * A operator that stands for itself. + * + * @author bjculkin + * + * @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 LeafCommand<K, V, C> implements InitialCommand<K, V, C> { + @Override + public ITree<Token<K, V>> denote(Token<K, V> operator, ParserContext<K, V, C> ctx) throws ParserException { + return new Tree<>(operator); + } +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/LeftBinaryCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/LeftBinaryCommand.java new file mode 100644 index 0000000..58d7261 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/LeftBinaryCommand.java @@ -0,0 +1,32 @@ +package bjc.utils.parserutils.pratt.commands; + +/** + * A left-associative operator. + * + * @author bjculkin + * + * @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 LeftBinaryCommand<K, V, C> extends BinaryCommand<K, V, C> { + /** + * Create a new left-associative operator. + * + * @param precedence + * The precedence of the operator. + */ + public LeftBinaryCommand(int precedence) { + super(precedence); + } + + @Override + protected int rightBinding() { + return 1 + leftBinding(); + } +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/NonBinaryCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/NonBinaryCommand.java new file mode 100644 index 0000000..d32a1a7 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/NonBinaryCommand.java @@ -0,0 +1,37 @@ +package bjc.utils.parserutils.pratt.commands; + +/** + * A non-associative operator. + * + * @author bjculkin + * + * @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 NonBinaryCommand<K, V, C> extends BinaryCommand<K, V, C> { + /** + * Create a new non-associative operator. + * + * @param precedence + * The precedence of the operator. + */ + public NonBinaryCommand(int precedence) { + super(precedence); + } + + @Override + protected int rightBinding() { + return 1 + leftBinding(); + } + + @Override + public int nextBinding() { + return leftBinding() - 1; + } +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/NonInitialCommands.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/NonInitialCommands.java new file mode 100644 index 0000000..45bdc51 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/NonInitialCommands.java @@ -0,0 +1,140 @@ +package bjc.utils.parserutils.pratt.commands; + +import bjc.utils.parserutils.pratt.NonInitialCommand; +import bjc.utils.parserutils.pratt.ParseBlock; +import bjc.utils.parserutils.pratt.Token; +import bjc.utils.parserutils.pratt.blocks.SimpleParseBlock; + +import java.util.Set; + +/** + * Contains factory methods for producing common implementations of + * {@link NonInitialCommand} + * + * @author EVE + * + */ +public class NonInitialCommands { + /** + * Create a left-associative infix operator. + * + * @param precedence + * The precedence of the operator. + * + * @return A command implementing that operator. + */ + public static <K, V, C> NonInitialCommand<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> NonInitialCommand<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> NonInitialCommand<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> NonInitialCommand<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> NonInitialCommand<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> NonInitialCommand<K, V, C> postCircumfix(int precedence, int insidePrecedence, K closer, + Token<K, V> marker) { + ParseBlock<K, V, C> innerBlock = new SimpleParseBlock<>(insidePrecedence, closer, null); + + return new PostCircumfixCommand<>(precedence, innerBlock, 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> NonInitialCommand<K, V, C> ternary(int precedence, int insidePrecedence, K closer, + Token<K, V> marker, boolean nonassoc) { + ParseBlock<K, V, C> innerBlock = new SimpleParseBlock<>(insidePrecedence, closer, null); + + return new TernaryCommand<>(precedence, innerBlock, marker, nonassoc); + } +} diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/PostCircumfixCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/PostCircumfixCommand.java new file mode 100644 index 0000000..90fca00 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/PostCircumfixCommand.java @@ -0,0 +1,60 @@ +package bjc.utils.parserutils.pratt.commands; + +import bjc.utils.data.ITree; +import bjc.utils.data.Tree; +import bjc.utils.parserutils.ParserException; +import bjc.utils.parserutils.pratt.ParseBlock; +import bjc.utils.parserutils.pratt.ParserContext; +import bjc.utils.parserutils.pratt.Token; + +/** + * A post-circumfix operator, like array indexing. + * + * @author bjculkin + * + * @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 PostCircumfixCommand<K, V, C> extends BinaryPostCommand<K, V, C> { + private ParseBlock<K, V, C> innerBlock; + + private Token<K, V> mark; + + /** + * Create a new post-circumfix operator. + * + * @param precedence + * The precedence of the operator. + * + * @param inner + * The block inside the expression. + * + * @param marker + * The token to use as the node for the AST. + */ + public PostCircumfixCommand(int precedence, ParseBlock<K, V, C> inner, Token<K, V> marker) { + super(precedence); + + if (inner == null) { + throw new NullPointerException("Inner block must not be null"); + } + + innerBlock = inner; + + mark = marker; + } + + @Override + public ITree<Token<K, V>> denote(ITree<Token<K, V>> operand, Token<K, V> operator, ParserContext<K, V, C> ctx) + throws ParserException { + ITree<Token<K, V>> inside = innerBlock.parse(ctx); + + return new Tree<>(mark, operand, inside); + } +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/PostfixCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/PostfixCommand.java new file mode 100644 index 0000000..bab3de4 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/PostfixCommand.java @@ -0,0 +1,39 @@ +package bjc.utils.parserutils.pratt.commands; + +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; + +/** + * A postfix operator. + * + * @author bjculkin + * + * @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 PostfixCommand<K, V, C> extends BinaryPostCommand<K, V, C> { + /** + * Create a new postfix operator. + * + * @param precedence + * The precedence of the operator. + */ + public PostfixCommand(int precedence) { + super(precedence); + } + + @Override + public ITree<Token<K, V>> denote(ITree<Token<K, V>> operand, Token<K, V> operator, ParserContext<K, V, C> ctx) + throws ParserException { + return new Tree<>(operator, operand); + } +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/PreTernaryCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/PreTernaryCommand.java new file mode 100644 index 0000000..42d1a6e --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/PreTernaryCommand.java @@ -0,0 +1,75 @@ +package bjc.utils.parserutils.pratt.commands; + +import bjc.utils.data.ITree; +import bjc.utils.data.Tree; +import bjc.utils.parserutils.ParserException; +import bjc.utils.parserutils.pratt.ParseBlock; +import bjc.utils.parserutils.pratt.ParserContext; +import bjc.utils.parserutils.pratt.Token; + +/** + * A prefix ternary operator, like an if/then/else group. + * + * @author bjculkin + * + * @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 PreTernaryCommand<K, V, C> extends AbstractInitialCommand<K, V, C> { + private Token<K, V> term; + + private ParseBlock<K, V, C> condBlock; + + private ParseBlock<K, V, C> opblock1; + private ParseBlock<K, V, C> opblock2; + + /** + * Create a new ternary statement. + * + * @param cond + * The block for handling the condition. + * + * @param op1 + * The block for handling the first operator. + * + * @param op2 + * The block for handling the second operator. + * + * @param term + * The token to use as the node for the AST. + */ + public PreTernaryCommand(ParseBlock<K, V, C> cond, ParseBlock<K, V, C> op1, ParseBlock<K, V, C> op2, + Token<K, V> term) { + super(); + + if (cond == null) + throw new NullPointerException("Cond block must not be null"); + else if (op1 == null) + throw new NullPointerException("Op block #1 must not be null"); + else if (op2 == null) throw new NullPointerException("Op block #2 must not be null"); + + this.condBlock = cond; + this.opblock1 = op1; + this.opblock2 = op2; + + this.term = term; + } + + @Override + protected ITree<Token<K, V>> intNullDenotation(Token<K, V> operator, ParserContext<K, V, C> ctx) + throws ParserException { + ITree<Token<K, V>> cond = condBlock.parse(ctx); + + ITree<Token<K, V>> op1 = opblock1.parse(ctx); + + ITree<Token<K, V>> op2 = opblock2.parse(ctx); + + return new Tree<>(term, cond, op1, op2); + } +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/RightBinaryCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/RightBinaryCommand.java new file mode 100644 index 0000000..5f3d9f2 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/RightBinaryCommand.java @@ -0,0 +1,30 @@ +package bjc.utils.parserutils.pratt.commands; + +/** + * A right-associative binary operator. + * + * @author bjculkin + * + * @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 RightBinaryCommand<K, V, C> extends BinaryCommand<K, V, C> { + /** + * Create a new right-associative operator. + * + * @param precedence + * The precedence of the operator. + */ + public RightBinaryCommand(int precedence) { + super(precedence); + } + + @Override + protected int rightBinding() { + return leftBinding(); + } +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/TernaryCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/TernaryCommand.java new file mode 100644 index 0000000..8f04368 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/TernaryCommand.java @@ -0,0 +1,77 @@ +package bjc.utils.parserutils.pratt.commands; + +import bjc.utils.data.ITree; +import bjc.utils.data.Tree; +import bjc.utils.parserutils.ParserException; +import bjc.utils.parserutils.pratt.ParseBlock; +import bjc.utils.parserutils.pratt.ParserContext; +import bjc.utils.parserutils.pratt.Token; + +/** + * A ternary command, like C's ?: + * + * @author bjculkin + * + * @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 TernaryCommand<K, V, C> extends BinaryPostCommand<K, V, C> { + private ParseBlock<K, V, C> innerBlck; + + private Token<K, V> mark; + + private boolean nonassoc; + + /** + * Create a new ternary command. + * + * @param precedence + * The precedence of this operator. + * + * @param innerBlock + * The representation of the inner block of the + * expression. + * + * @param marker + * The token to use as the root of the AST node. + * + * @param isNonassoc + * Whether or not the conditional is associative. + */ + public TernaryCommand(int precedence, ParseBlock<K, V, C> innerBlock, Token<K, V> marker, boolean isNonassoc) { + super(precedence); + + if (innerBlock == null) + throw new NullPointerException("Inner block must not be null"); + else if (marker == null) throw new NullPointerException("Marker must not be null"); + + innerBlck = innerBlock; + mark = marker; + nonassoc = isNonassoc; + } + + @Override + public ITree<Token<K, V>> denote(ITree<Token<K, V>> operand, Token<K, V> operator, ParserContext<K, V, C> ctx) + throws ParserException { + ITree<Token<K, V>> inner = innerBlck.parse(ctx); + + ITree<Token<K, V>> outer = ctx.parse.parseExpression(1 + leftBinding(), ctx.tokens, ctx.state, false); + + return new Tree<>(mark, inner, operand, outer); + } + + @Override + public int nextBinding() { + if (nonassoc) { + return leftBinding() - 1; + } else { + return leftBinding(); + } + } +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/TransformingInitialCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/TransformingInitialCommand.java new file mode 100644 index 0000000..88803df --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/TransformingInitialCommand.java @@ -0,0 +1,52 @@ +package bjc.utils.parserutils.pratt.commands; + +import java.util.function.UnaryOperator; + +import bjc.utils.data.ITree; +import bjc.utils.parserutils.ParserException; +import bjc.utils.parserutils.pratt.InitialCommand; +import bjc.utils.parserutils.pratt.ParserContext; +import bjc.utils.parserutils.pratt.Token; + +/** + * An initial command that transforms the result of another command. + * + * @author bjculkin + * + * @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 TransformingInitialCommand<K, V, C> extends AbstractInitialCommand<K, V, C> { + private InitialCommand<K, V, C> internal; + + private UnaryOperator<ITree<Token<K, V>>> transform; + + /** + * Create a new transforming initial command. + * + * @param internal + * The initial command to delegate to. + * + * @param transform + * The transform to apply to the returned tree. + */ + public TransformingInitialCommand(InitialCommand<K, V, C> internal, + UnaryOperator<ITree<Token<K, V>>> transform) { + super(); + this.internal = internal; + this.transform = transform; + } + + @Override + protected ITree<Token<K, V>> intNullDenotation(Token<K, V> operator, ParserContext<K, V, C> ctx) + throws ParserException { + return transform.apply(internal.denote(operator, ctx)); + } + +} diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/UnaryCommand.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/UnaryCommand.java new file mode 100644 index 0000000..c608362 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/commands/UnaryCommand.java @@ -0,0 +1,47 @@ +package bjc.utils.parserutils.pratt.commands; + +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; + +/** + * A unary operator. + * + * @author bjculkin + * + * @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 UnaryCommand<K, V, C> extends AbstractInitialCommand<K, V, C> { + private final int nullPwer; + + /** + * Create a new unary command. + * + * @param precedence + * The precedence of this operator. + */ + public UnaryCommand(int precedence) { + if(precedence < 0) { + throw new IllegalArgumentException("Precedence must be non-negative"); + } + + nullPwer = precedence; + } + + @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, false); + + return new Tree<>(operator, opr); + } +}
\ No newline at end of file diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/tokens/StringToken.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/tokens/StringToken.java new file mode 100644 index 0000000..f156f02 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/tokens/StringToken.java @@ -0,0 +1,84 @@ +package bjc.utils.parserutils.pratt.tokens; + +import bjc.utils.parserutils.pratt.Token; + +/** + * 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); + } + + public static StringToken litToken(String val) { + return new StringToken(val, val); + } +} diff --git a/JPratt/src/main/java/bjc/utils/parserutils/pratt/tokens/StringTokenStream.java b/JPratt/src/main/java/bjc/utils/parserutils/pratt/tokens/StringTokenStream.java new file mode 100644 index 0000000..75e86c4 --- /dev/null +++ b/JPratt/src/main/java/bjc/utils/parserutils/pratt/tokens/StringTokenStream.java @@ -0,0 +1,56 @@ +package bjc.utils.parserutils.pratt.tokens; + +import java.util.Iterator; + +import bjc.utils.parserutils.pratt.Token; +import bjc.utils.parserutils.pratt.TokenStream; + +import static bjc.utils.parserutils.pratt.tokens.StringToken.litToken; + +/** + * Simple implementation of token stream for strings. + * + * The terminal token here is represented by a token with type and value + * '(end)'. + * + * @author EVE + * + */ +public class StringTokenStream extends 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 Token<String, String> next() { + if (iter.hasNext()) { + curr = iter.next(); + } else { + curr = litToken("(end)"); + } + + return curr; + } + + @Override + public boolean hasNext() { + return iter.hasNext(); + } +} |