From f48c702780581edb1022fab7f938260089432d06 Mon Sep 17 00:00:00 2001 From: Michael Williamson Date: Sat, 8 Jul 2023 21:20:15 +0100 Subject: Handle precedence when parsing expressions --- .../shedlang/compiler/parser/OperationParser.java | 12 ++ .../compiler/parser/OperatorPrecedence.java | 16 ++ .../java/org/shedlang/compiler/parser/Parser.java | 177 ++++++++++++--------- 3 files changed, 131 insertions(+), 74 deletions(-) create mode 100644 src/main/java/org/shedlang/compiler/parser/OperationParser.java create mode 100644 src/main/java/org/shedlang/compiler/parser/OperatorPrecedence.java (limited to 'src/main/java') 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 operatorTokenTypes(); + UntypedExpressionNode parse(UntypedExpressionNode left, TokenIterator 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 tokens - ) { - return parseBinaryOperation( - TokenType.SYMBOL_PLUS, - UntypedBinaryOperator.ADD, - left, - tokens - ); - } - - private static UntypedExpressionNode parseBinaryOperation( - TokenType operatorTokenType, - UntypedBinaryOperator operator, - UntypedExpressionNode left, - TokenIterator 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 operatorTokenTypes() { + return Stream.of(operatorTokenType); + } - private static UntypedExpressionNode parseCall(UntypedExpressionNode receiver, TokenIterator tokens) { - var start = receiver.source().start(); + @Override + public UntypedExpressionNode parse(UntypedExpressionNode left, TokenIterator 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 tokens) { @@ -128,6 +125,67 @@ public class Parser { } } + private static class CallParser implements OperationParser { + @Override + public OperatorPrecedence precedence() { + return OperatorPrecedence.CALL; + } + + @Override + public Stream operatorTokenTypes() { + return Stream.of(TokenType.SYMBOL_BANG, TokenType.SYMBOL_PAREN_OPEN); + } + + @Override + public UntypedExpressionNode parse(UntypedExpressionNode left, TokenIterator 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 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 tokens, + Optional 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 tokens) { var start = tokens.position(); @@ -321,41 +379,12 @@ public class Parser { }; } - private static UntypedExpressionNode parseSub( - UntypedExpressionNode left, - TokenIterator tokens - ) { - return parseBinaryOperation( - TokenType.SYMBOL_MINUS, - UntypedBinaryOperator.SUB, - left, - tokens - ); + static UntypedExpressionNode parseSubExpression(TokenIterator tokens, OperatorPrecedence parentPrecedence) { + return parseExpression(tokens, Optional.of(parentPrecedence)); } static UntypedExpressionNode parseTopLevelExpression(TokenIterator 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 tokens) { -- cgit v1.2.3