From 1422d647cddb577fafc19ee97e33a394aefc560b Mon Sep 17 00:00:00 2001 From: Elias Haugsbakk Date: Sun, 20 Sep 2026 03:12:03 +0200 Subject: add rules to semantics analyzer --- docs/example_IR | 18 +++ .../eliashaugsbakk/kompilator/parsing/Parser.java | 64 ++++---- .../no/eliashaugsbakk/kompilator/parsing/Type.java | 18 ++- .../parsing/node/expression/FunctionCall.java | 9 ++ .../parsing/node/expression/Identifier.java | 2 +- .../parsing/node/statement/Assignment.java | 2 +- .../node/statement/IdentifierDeclaration.java | 6 +- .../kompilator/semanticAnalysis/Analyzer.java | 167 +++++++++++++++++++-- .../kompilator/semanticAnalysis/Symbol.java | 23 +++ .../kompilator/tokenization/Lexer.java | 4 +- .../kompilator/parsing/ParserTest.java | 4 +- 11 files changed, 255 insertions(+), 62 deletions(-) create mode 100644 src/main/java/no/eliashaugsbakk/kompilator/semanticAnalysis/Symbol.java diff --git a/docs/example_IR b/docs/example_IR index e492c21..3a20feb 100644 --- a/docs/example_IR +++ b/docs/example_IR @@ -1,3 +1,21 @@ # v0.0.1 str1 = "Hello World" skriv(str1) + +# v0.0.2 +# support for arithmetic operators: +# + plus +# - minus +# * multiplications +# / division +# % modulo +# ** exponential + +# (1 + 2) * 3 +t0 = 1 +t1 = 2 +t2 = int1 + int 2 +t3 = 3 +t4 = t2 * t3 +skriv(int3) + diff --git a/src/main/java/no/eliashaugsbakk/kompilator/parsing/Parser.java b/src/main/java/no/eliashaugsbakk/kompilator/parsing/Parser.java index 356a6d7..f959daf 100644 --- a/src/main/java/no/eliashaugsbakk/kompilator/parsing/Parser.java +++ b/src/main/java/no/eliashaugsbakk/kompilator/parsing/Parser.java @@ -108,9 +108,11 @@ public class Parser { private Statement parseKeyword() throws ParserException { Token token = tokens.get(current); if (token.value().contentEquals("set")) { - return parseIdentifierStatement(); + current++; // consume "set" + return parseDeclaration(false); } else if (token.value().contentEquals("mut")) { - return parseIdentifierStatement(); + current++; // consume "mut" + return parseDeclaration(true); } else if (token.value().contentEquals("skriv")) { return parseExpressionStatement(); } else { @@ -130,60 +132,50 @@ public class Parser { return new ExpressionStatement(expression); } - - private Statement parseIdentifierStatement() throws ParserException { - // this is either: - // - declaration of a new variable with an associated value - // - declaration of a new variable without an associated value - // - reassigning an existing variable - - /* - mut x: string?; IDENTIFIER, COLON, TYPE, SEMICOLON - set x: string = "string"; IDENTIFIER, COLON, TYPE, ASSIGN, STRING, SEMICOLON - x = "string"; IDENTIFIER, ASSIGN, STRING, SEMICOLON - */ - - boolean mutable = false; - - if (tokens.get(current).value().contentEquals("mut")) { - mutable = true; - current++; - } else if (tokens.get(current).value().contentEquals("set")) { - current++; - } - String identifier = tokens.get(current).value(); - current++; + current++; // consume identifier Token next = tokens.get(current); - if (next.type() == COLON) { - // x: string = "hello"; - return parseDeclaration(identifier, mutable); - } else if (next.type() == ASSIGN) { - // x = "hello"; + if (next.type() == ASSIGN) { return parseAssignment(identifier); + } else if (next.type() == LPAREN) { + // Future expansion: standalone function calls like `doSomething();` + current--; // rewind to identifier + Expression expr = parseFunctionCall(); + expectSemicolon(); + return new ExpressionStatement(expr); } else { - throw new ParserException(next.line(), next.column(), "Expected : or = after: " + identifier); + throw new ParserException(next.line(), next.column(), "Unexpected token after identifier: " + next.value()); } } - private Statement parseDeclaration(String identifier, boolean mutable) throws ParserException { - // x: type; - current++; // skip colon + private Statement parseDeclaration(boolean isMutable) throws ParserException { + Token nameToken = tokens.get(current); + if (nameToken.type() != IDENTIFIER) { + throw new ParserException(nameToken.line(), nameToken.column(), + "Expected identifier after declaration keyword, got: " + nameToken.value()); + } + String identifier = nameToken.value(); + current++; // consume identifier + + if (tokens.get(current).type() != COLON) { + throw new ParserException(tokens.get(current).line(), tokens.get(current).column(), + "Expected : after identifier in declaration"); + } + current++; // skip : Type type = parseType(); Expression initializer = null; - // x: type = "hello"; if (tokens.get(current).type() == ASSIGN) { current++; // skip = initializer = parseExpression(); } expectSemicolon(); - return new IdentifierDeclaration(identifier, type, initializer, mutable); + return new IdentifierDeclaration(identifier, type, initializer, isMutable); } private Statement parseAssignment(String identifier) throws ParserException { diff --git a/src/main/java/no/eliashaugsbakk/kompilator/parsing/Type.java b/src/main/java/no/eliashaugsbakk/kompilator/parsing/Type.java index d707696..6b1007c 100644 --- a/src/main/java/no/eliashaugsbakk/kompilator/parsing/Type.java +++ b/src/main/java/no/eliashaugsbakk/kompilator/parsing/Type.java @@ -1,12 +1,28 @@ package no.eliashaugsbakk.kompilator.parsing; +import java.util.Objects; + public class Type { - final String type; + public final String type; public final boolean nullable; public Type(String type, boolean nullable) { this.type = type; this.nullable = nullable; } + + @Override + public boolean equals(Object o) { + if (o instanceof Type t) { + return this.type.equals(t.type) && this.nullable == t.nullable; + } else { + return false; + } + } + + @Override + public int hashCode() { + return Objects.hash(type, nullable); + } } diff --git a/src/main/java/no/eliashaugsbakk/kompilator/parsing/node/expression/FunctionCall.java b/src/main/java/no/eliashaugsbakk/kompilator/parsing/node/expression/FunctionCall.java index 3c46ec4..2537d9c 100644 --- a/src/main/java/no/eliashaugsbakk/kompilator/parsing/node/expression/FunctionCall.java +++ b/src/main/java/no/eliashaugsbakk/kompilator/parsing/node/expression/FunctionCall.java @@ -1,6 +1,7 @@ package no.eliashaugsbakk.kompilator.parsing.node.expression; import java.util.List; +import no.eliashaugsbakk.kompilator.parsing.Type; /** * Represents a function call statement (e.g., print("Hello, world")). @@ -13,4 +14,12 @@ public class FunctionCall extends Expression { this.functionName = functionName; this.arguments = arguments; } + + public Type getReturnType() { + if (functionName.equals("skriv")) { + return new Type("void", false); + } + // TODO: Look up return type in function table when you add more functions + return null; + } } diff --git a/src/main/java/no/eliashaugsbakk/kompilator/parsing/node/expression/Identifier.java b/src/main/java/no/eliashaugsbakk/kompilator/parsing/node/expression/Identifier.java index c1f475f..91607f8 100644 --- a/src/main/java/no/eliashaugsbakk/kompilator/parsing/node/expression/Identifier.java +++ b/src/main/java/no/eliashaugsbakk/kompilator/parsing/node/expression/Identifier.java @@ -4,7 +4,7 @@ package no.eliashaugsbakk.kompilator.parsing.node.expression; * Resolves to a variable's value */ public class Identifier extends Expression { - final String name; + public final String name; public Identifier(String name) { this.name = name; diff --git a/src/main/java/no/eliashaugsbakk/kompilator/parsing/node/statement/Assignment.java b/src/main/java/no/eliashaugsbakk/kompilator/parsing/node/statement/Assignment.java index bca16df..01d207d 100644 --- a/src/main/java/no/eliashaugsbakk/kompilator/parsing/node/statement/Assignment.java +++ b/src/main/java/no/eliashaugsbakk/kompilator/parsing/node/statement/Assignment.java @@ -4,7 +4,7 @@ import no.eliashaugsbakk.kompilator.parsing.node.expression.Expression; public class Assignment extends Statement { public final String identifier; - final Expression expression; + public final Expression expression; public Assignment(String identifier, Expression expression) { this.identifier = identifier; diff --git a/src/main/java/no/eliashaugsbakk/kompilator/parsing/node/statement/IdentifierDeclaration.java b/src/main/java/no/eliashaugsbakk/kompilator/parsing/node/statement/IdentifierDeclaration.java index d3c5474..69b0f1b 100644 --- a/src/main/java/no/eliashaugsbakk/kompilator/parsing/node/statement/IdentifierDeclaration.java +++ b/src/main/java/no/eliashaugsbakk/kompilator/parsing/node/statement/IdentifierDeclaration.java @@ -12,14 +12,14 @@ public class IdentifierDeclaration extends Statement { // identifier initialization: my_var: type [4]; // may be null: my_var: type?; - public final Expression expression; // may be null: x: int?; + public final Expression initializer; // may be null: x: int?; public final boolean mutable; - public IdentifierDeclaration(String identifier, Type type, Expression expression, boolean mutable) { + public IdentifierDeclaration(String identifier, Type type, Expression initializer, boolean mutable) { this.identifier = identifier; this.type = type; - this.expression = expression; + this.initializer = initializer; this.mutable = mutable; } } diff --git a/src/main/java/no/eliashaugsbakk/kompilator/semanticAnalysis/Analyzer.java b/src/main/java/no/eliashaugsbakk/kompilator/semanticAnalysis/Analyzer.java index b7cc7af..a01c6bf 100644 --- a/src/main/java/no/eliashaugsbakk/kompilator/semanticAnalysis/Analyzer.java +++ b/src/main/java/no/eliashaugsbakk/kompilator/semanticAnalysis/Analyzer.java @@ -1,17 +1,22 @@ package no.eliashaugsbakk.kompilator.semanticAnalysis; -import static no.eliashaugsbakk.kompilator.tokenization.Keywords.KEYWORDS; - +import java.util.HashMap; +import java.util.Map; import no.eliashaugsbakk.kompilator.parsing.AST; +import no.eliashaugsbakk.kompilator.parsing.Type; import no.eliashaugsbakk.kompilator.parsing.node.Program; import no.eliashaugsbakk.kompilator.parsing.node.expression.Expression; import no.eliashaugsbakk.kompilator.parsing.node.expression.FunctionCall; +import no.eliashaugsbakk.kompilator.parsing.node.expression.Identifier; import no.eliashaugsbakk.kompilator.parsing.node.expression.literal.StringLiteral; +import no.eliashaugsbakk.kompilator.parsing.node.statement.Assignment; import no.eliashaugsbakk.kompilator.parsing.node.statement.ExpressionStatement; +import no.eliashaugsbakk.kompilator.parsing.node.statement.IdentifierDeclaration; import no.eliashaugsbakk.kompilator.parsing.node.statement.Statement; public class Analyzer { private final AST ast; + private Map symbolTable = new HashMap<>(); public Analyzer(AST ast) { this.ast = ast; @@ -27,32 +32,162 @@ public class Analyzer { private void analyzeStatement(Statement stmt) throws SemanticException { if (stmt instanceof ExpressionStatement exprStmt) { - analyzeExpression(exprStmt.expression); + typeOf(exprStmt.expression); + } else if (stmt instanceof Assignment assignment) { + analyzeAssignment(assignment); + } else if (stmt instanceof IdentifierDeclaration decl) { + analyzeIdentifierDeclaration(decl); } else { - // Analyze the statement - // NO other statements implemented + throw new SemanticException("Unrecognized statement"); } } - private void analyzeExpression(Expression expr) throws SemanticException { - if (expr instanceof FunctionCall call) { - checkFunctionCall(call); - } else { - // analyze the expression + /** + * Analyzes identifier declaration: set/mut x: type [= value]; + */ + private void analyzeIdentifierDeclaration(IdentifierDeclaration decl) throws SemanticException { + boolean initialized = decl.initializer != null; + boolean nullable = decl.type.nullable; + Type declaredType = decl.type; + + // Ensure the type exists + // string is the only type implemented, but should look in a type table or something in the future + if (!declaredType.type.equals("string")) { + throw new SemanticException("Unknown type declaration: " + declaredType.type); + } + + // Immutable variables must always be initialized on declaration + if (!decl.mutable && !initialized) { + throw new SemanticException( + "Immutable variable " + decl.identifier + " must be initialized upon declaration."); + } + + // If no initializer, ensure type is nullable + if (!initialized && !nullable) { + throw new SemanticException("Non-nullable type requires initialization"); + } + + // If initializer exists, validate type matches declared type + if (initialized) { + Type implementedType = typeOf(decl.initializer); + checkAssignable(declaredType, implementedType); } + + // Shadowing is allowed; do not check to see if the symbol already exists + symbolTable.put(decl.identifier, + new Symbol(decl.identifier, declaredType, decl.mutable, initialized)); + } + + /** + * Analyzes assignment: x = value; + */ + private void analyzeAssignment(Assignment assignment) throws SemanticException { + Symbol symbol = symbolTable.get(assignment.identifier); + + // Check existence + if (symbol == null) { + throw new SemanticException("Variable not declared: " + assignment.identifier); + } + + // Check mutability + if (!symbol.mutable) { + throw new SemanticException("Cannot assign to immutable value: " + assignment.identifier); + } + + // Type and Nullability Check + Type assignedType = typeOf(assignment.expression); + checkAssignable(symbol.type, assignedType); + + // Update symbol state + symbol.initialized = true; } - private void checkFunctionCall(FunctionCall call) throws SemanticException { - if (!KEYWORDS.contains(call.functionName)) { - throw new SemanticException("unknown function: " + call.functionName); + /** + * Analyzes identifier usage (variable reference). + */ + private void analyzeIdentifier(Identifier identifier) throws SemanticException { + // Check if identifier is declared + if (!symbolTable.containsKey(identifier.name)) { + throw new SemanticException("Identifier does not exist: " + identifier.name); } + // Check if identifier is initialized + if (!symbolTable.get(identifier.name).initialized) { + throw new SemanticException("Identifier is not initialized: " + identifier.name); + } + } + + /** + * Analyzes function call. + */ + private void analyzeFunctionCall(FunctionCall call) throws SemanticException { + // Validate function exists + // skriv() is the only implemented function + // Should ref. function table in the future + if (!call.functionName.equals("skriv")) { + throw new SemanticException("Function calls are not supported: " + call.functionName); + } + + // Validate argument count if (call.arguments.size() != 1) { - throw new SemanticException("print expects 1 argument, got " + call.arguments.size()); + throw new SemanticException("skriv() supports only one argument"); } - if (!(call.arguments.getFirst() instanceof StringLiteral)) { - throw new SemanticException("print expects String argument only"); + // Validate argument types + for (Expression argument : call.arguments) { + Type argType = typeOf(argument); + + if (!argType.type.equals("string")) { + throw new SemanticException("skriv() only supports string literals"); + } + + if (argType.nullable) { + throw new SemanticException("Cannot print nullable string: " + argType.type + "?."); + } } } + + private void checkAssignable(Type target, Type value) throws SemanticException { + if (!target.type.equals(value.type)) { + throw new SemanticException( + "Type mismatch: expected " + target.type + ", found " + value.type); + } + if (value.nullable && !target.nullable) { + throw new SemanticException( + "Cannot assign nullable " + value.type + " to non-nullable " + target.type); + } + } + + /** + * Analyzes an expression, ensures all identifiers are declared and initialized, recursively + * validates sub-expressions, and returns the resulting Type. + */ + private Type typeOf(Expression expr) throws SemanticException { + switch (expr) { + case null -> throw new SemanticException("Expression cannot be null"); + case StringLiteral stringLiteral -> { + return new Type("string", false); + } + case Identifier id -> { + Symbol symbol = symbolTable.get(id.name); + + if (symbol == null) { + throw new SemanticException("Undeclared identifier: " + id.name); + } + if (!symbol.initialized) { + throw new SemanticException("Identifier is not initialized: " + id.name); + } + + return symbol.type; + } + case FunctionCall call -> { + analyzeFunctionCall(call); + return call.getReturnType(); + } + default -> { + } + } + + throw new SemanticException("Unknown expression type: " + expr.getClass().getSimpleName()); + } } diff --git a/src/main/java/no/eliashaugsbakk/kompilator/semanticAnalysis/Symbol.java b/src/main/java/no/eliashaugsbakk/kompilator/semanticAnalysis/Symbol.java new file mode 100644 index 0000000..c86d2f7 --- /dev/null +++ b/src/main/java/no/eliashaugsbakk/kompilator/semanticAnalysis/Symbol.java @@ -0,0 +1,23 @@ +package no.eliashaugsbakk.kompilator.semanticAnalysis; + +import no.eliashaugsbakk.kompilator.parsing.Type; + +class Symbol { + final String name; + final Type type; + boolean mutable; + boolean initialized; + + Symbol(String name, Type type, boolean mutable, boolean initialized) { + this.name = name; + this.type = type; + this.mutable = mutable; + this.initialized = initialized; + } + + @Override + public String toString() { + return String.format("Symbol{name='%s', type=%s, mutable=%b, initialized=%b}", + name, type, mutable, initialized); + } +} diff --git a/src/main/java/no/eliashaugsbakk/kompilator/tokenization/Lexer.java b/src/main/java/no/eliashaugsbakk/kompilator/tokenization/Lexer.java index d705ca5..9e9ebfd 100644 --- a/src/main/java/no/eliashaugsbakk/kompilator/tokenization/Lexer.java +++ b/src/main/java/no/eliashaugsbakk/kompilator/tokenization/Lexer.java @@ -66,7 +66,7 @@ public class Lexer { } tokens.add(new Token(EOF, "End of File", line, column)); - tokens.forEach(token -> IO.println(token.type().toString() + ": " + token.value())); + //tokens.forEach(token -> IO.println(token.type().toString() + ": " + token.value())); return tokens; } @@ -131,7 +131,7 @@ public class Lexer { } private void inWord() { - if (Character.isWhitespace(current) || current == ':' || current == '(' || current == ')') { + if (!isWordCharacter(current)) { state = NORMAL; characterizeWord(); } else { diff --git a/src/test/java/no/eliashaugsbakk/kompilator/parsing/ParserTest.java b/src/test/java/no/eliashaugsbakk/kompilator/parsing/ParserTest.java index fcd47c7..dc2d786 100644 --- a/src/test/java/no/eliashaugsbakk/kompilator/parsing/ParserTest.java +++ b/src/test/java/no/eliashaugsbakk/kompilator/parsing/ParserTest.java @@ -20,7 +20,7 @@ class ParserTest { @Test void validSyntaxBuildsCorrectTree() throws ParserException { List tokens = List.of( - new Token(KEYWORD, "print", 1, 0), + new Token(KEYWORD, "skriv", 1, 0), new Token(LPAREN, "(", 1, 5), new Token(STRING_LITERAL, "Hello", 1, 6), new Token(RPAREN, ")", 1, 13), @@ -39,7 +39,7 @@ class ParserTest { assertInstanceOf(FunctionCall.class, stmt.expression); FunctionCall call = (FunctionCall) stmt.expression; - assertEquals("print", call.functionName); + assertEquals("skriv", call.functionName); assertEquals(1, call.arguments.size()); assertEquals("Hello", ((StringLiteral) call.arguments.getFirst()).value); } -- cgit v1.2.3