Handle precedence when parsing expressions

3 files changed, 131 insertions, 74 deletions

diff --git a/src/main/java/org/shedlang/compiler/parser/OperationParser.java b/src/main/java/org/shedlang/compiler/parser/OperationParser.java
new file mode 100644
index 00000000..6f3e170e
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/parser/OperationParser.java
@@ -0,0 +1,12 @@
+package org.shedlang.compiler.parser;
+
+import org.shedlang.compiler.ast.untyped.UntypedExpressionNode;
+import org.shedlang.compiler.tokeniser.TokenIterator;
+
+import java.util.stream.Stream;
+
+public interface OperationParser {
+    OperatorPrecedence precedence();
+    Stream<TokenType> operatorTokenTypes();
+    UntypedExpressionNode parse(UntypedExpressionNode left, TokenIterator<TokenType> tokens);
+}
diff --git a/src/main/java/org/shedlang/compiler/parser/OperatorPrecedence.java b/src/main/java/org/shedlang/compiler/parser/OperatorPrecedence.java
new file mode 100644
index 00000000..109499de
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/parser/OperatorPrecedence.java
@@ -0,0 +1,16 @@
+package org.shedlang.compiler.parser;
+
+public enum OperatorPrecedence {
+    ADD(1),
+    CALL(2);
+
+    private final int precedence;
+
+    OperatorPrecedence(int precedence) {
+        this.precedence = precedence;
+    }
+
+    public int precedence() {
+        return precedence;
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/parser/Parser.java b/src/main/java/org/shedlang/compiler/parser/Parser.java
index d6cef7d4..0915f1bd 100644
--- a/src/main/java/org/shedlang/compiler/parser/Parser.java
+++ b/src/main/java/org/shedlang/compiler/parser/Parser.java
@@ -9,64 +9,61 @@ import org.shedlang.compiler.types.NamespaceName;
 import java.math.BigInteger;
 import java.util.ArrayList;
 import java.util.List;
+import java.util.Map;
 import java.util.Optional;
 import java.util.function.BooleanSupplier;
 import java.util.function.Supplier;
 import java.util.regex.Pattern;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
 
 public class Parser {
     private Parser() {
     }
 
-    private static UntypedExpressionNode parseAdd(
-        UntypedExpressionNode left,
-        TokenIterator<TokenType> tokens
-    ) {
-        return parseBinaryOperation(
-            TokenType.SYMBOL_PLUS,
-            UntypedBinaryOperator.ADD,
-            left,
-            tokens
-        );
-    }
-
-    private static UntypedExpressionNode parseBinaryOperation(
-        TokenType operatorTokenType,
-        UntypedBinaryOperator operator,
-        UntypedExpressionNode left,
-        TokenIterator<TokenType> tokens
-    ) {
-        var start = left.source().start();
-
-        tokens.skip(operatorTokenType);
-
-        // TODO: precedence
-        var right = parseTopLevelExpression(tokens);
+    private static class BinaryOperationParser implements OperationParser {
+        private final TokenType operatorTokenType;
+        private final OperatorPrecedence precedence;
+        private final UntypedBinaryOperator operator;
+
+        private BinaryOperationParser(
+            TokenType operatorTokenType,
+            OperatorPrecedence precedence,
+            UntypedBinaryOperator operator
+        ) {
+            this.operatorTokenType = operatorTokenType;
+            this.precedence = precedence;
+            this.operator = operator;
+        }
 
-        var end = tokens.position();
-        var source = start.to(end);
+        @Override
+        public OperatorPrecedence precedence() {
+            return precedence;
+        }
 
-        return new UntypedBinaryOperationNode(
-            operator,
-            left,
-            right,
-            source
-        );
-    }
+        @Override
+        public Stream<TokenType> operatorTokenTypes() {
+            return Stream.of(operatorTokenType);
+        }
 
-    private static UntypedExpressionNode parseCall(UntypedExpressionNode receiver, TokenIterator<TokenType> tokens) {
-        var start = receiver.source().start();
+        @Override
+        public UntypedExpressionNode parse(UntypedExpressionNode left, TokenIterator<TokenType> tokens) {
+            var start = left.source().start();
 
-        var hasEffects = tokens.trySkip(TokenType.SYMBOL_BANG);
+            tokens.skip(operatorTokenType);
 
-        tokens.skip(TokenType.SYMBOL_PAREN_OPEN);
-        var args = parseArgs(tokens);
-        tokens.skip(TokenType.SYMBOL_PAREN_CLOSE);
+            var right = parseSubExpression(tokens, precedence);
 
-        var end = tokens.position();
-        var source = start.to(end);
+            var end = tokens.position();
+            var source = start.to(end);
 
-        return new UntypedCallNode(receiver, args, hasEffects, source);
+            return new UntypedBinaryOperationNode(
+                operator,
+                left,
+                right,
+                source
+            );
+        }
     }
 
     private static UntypedArgsNode parseArgs(TokenIterator<TokenType> tokens) {
@@ -128,6 +125,67 @@ public class Parser {
         }
     }
 
+    private static class CallParser implements OperationParser {
+        @Override
+        public OperatorPrecedence precedence() {
+            return OperatorPrecedence.CALL;
+        }
+
+        @Override
+        public Stream<TokenType> operatorTokenTypes() {
+            return Stream.of(TokenType.SYMBOL_BANG, TokenType.SYMBOL_PAREN_OPEN);
+        }
+
+        @Override
+        public UntypedExpressionNode parse(UntypedExpressionNode left, TokenIterator<TokenType> tokens) {
+            var start = left.source().start();
+
+            var hasEffects = tokens.trySkip(TokenType.SYMBOL_BANG);
+
+            tokens.skip(TokenType.SYMBOL_PAREN_OPEN);
+            var args = parseArgs(tokens);
+            tokens.skip(TokenType.SYMBOL_PAREN_CLOSE);
+
+            var end = tokens.position();
+            var source = start.to(end);
+
+            return new UntypedCallNode(left, args, hasEffects, source);
+        }
+    }
+
+    private static final Map<TokenType, OperationParser> OPERATION_PARSERS = Stream.of(
+        new BinaryOperationParser(TokenType.SYMBOL_PLUS, OperatorPrecedence.ADD, UntypedBinaryOperator.ADD),
+        new BinaryOperationParser(TokenType.SYMBOL_MINUS, OperatorPrecedence.ADD, UntypedBinaryOperator.SUB),
+        new CallParser()
+    )
+        .flatMap(parser ->
+            parser.operatorTokenTypes().map(tokenType -> Map.entry(tokenType, parser))
+        )
+        .collect(Collectors.toMap(
+            x -> x.getKey(),
+            x -> x.getValue()
+        ));
+
+    static UntypedExpressionNode parseExpression(
+        TokenIterator<TokenType> tokens,
+        Optional<OperatorPrecedence> parentPrecedence
+    ) {
+        var left = parsePrimaryExpression(tokens);
+
+        while (true) {
+            var operationParser = OPERATION_PARSERS.get(tokens.peek().tokenType());
+            if (
+                operationParser == null || (
+                    parentPrecedence.isPresent() &&
+                    operationParser.precedence().precedence() <= parentPrecedence.get().precedence()
+                )
+            ) {
+                return left;
+            }
+            left = operationParser.parse(left, tokens);
+        }
+    }
+
     private static UntypedFunctionStatementNode parseExpressionStatement(TokenIterator<TokenType> tokens) {
         var start = tokens.position();
 
@@ -321,41 +379,12 @@ public class Parser {
         };
     }
 
-    private static UntypedExpressionNode parseSub(
-        UntypedExpressionNode left,
-        TokenIterator<TokenType> tokens
-    ) {
-        return parseBinaryOperation(
-            TokenType.SYMBOL_MINUS,
-            UntypedBinaryOperator.SUB,
-            left,
-            tokens
-        );
+    static UntypedExpressionNode parseSubExpression(TokenIterator<TokenType> tokens, OperatorPrecedence parentPrecedence) {
+        return parseExpression(tokens, Optional.of(parentPrecedence));
     }
 
     static UntypedExpressionNode parseTopLevelExpression(TokenIterator<TokenType> tokens) {
-        var left = parsePrimaryExpression(tokens);
-
-        while (true) {
-            switch (tokens.peek().tokenType()) {
-                // TODO: precedence
-                case SYMBOL_PLUS -> {
-                    left = parseAdd(left, tokens);
-                }
-
-                case SYMBOL_MINUS -> {
-                    left = parseSub(left, tokens);
-                }
-
-                case SYMBOL_BANG, SYMBOL_PAREN_OPEN -> {
-                    left = parseCall(left, tokens);
-                }
-
-                default -> {
-                    return left;
-                }
-            }
-        }
+        return parseExpression(tokens, Optional.empty());
     }
 
     static UntypedTypeLevelExpressionNode parseTopLevelTypeLevelExpression(TokenIterator<TokenType> tokens) {