Implement parser for a simple language that roughly corresponds to appendix A in Aho's 2nd edition

6 files changed, 480 insertions, 6 deletions

diff --git a/src/main/java/com/seaofnodes/simple/common/CompilerException.java b/src/main/java/com/seaofnodes/simple/common/CompilerException.java
new file mode 100644
index 00000000..518dcde6
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/common/CompilerException.java
@@ -0,0 +1,11 @@
+package com.seaofnodes.simple.common;
+
+public class CompilerException extends RuntimeException {
+    public CompilerException(String message) {
+        super(message);
+    }
+
+    public CompilerException(String message, Throwable cause) {
+        super(message, cause);
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/lexer/Lexer.java b/src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java
index 06c8f28a..162cdea1 100644
--- a/src/main/java/com/seaofnodes/simple/lexer/Lexer.java
+++ b/src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java
@@ -14,7 +14,7 @@
  * APL may be obtained from:
  * http://www.apache.org/licenses/LICENSE-2.0
  */
-package com.seaofnodes.simple.lexer;
+package com.seaofnodes.simple.lexer.aa;
 
 import com.seaofnodes.util.AryInt;
 import com.seaofnodes.util.SB;
diff --git a/src/main/java/com/seaofnodes/simple/parser/Ast.java b/src/main/java/com/seaofnodes/simple/parser/Ast.java
new file mode 100644
index 00000000..a93b230f
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/parser/Ast.java
@@ -0,0 +1,132 @@
+package com.seaofnodes.simple.parser;
+
+import com.seaofnodes.simple.common.CompilerException;
+import com.seaofnodes.simple.lexer.ecstasy.Token;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public abstract class Ast {
+
+    public static class Node {
+    }
+
+    public static class Expr extends Node {
+        public final Token op;
+
+        public Expr(Token op) {
+            this.op = op;
+        }
+    }
+
+    public static class Identifier extends Expr {
+        public final String name;
+        public Identifier(Token op) {
+            super(op);
+            name = op.getValueText();
+        }
+    }
+
+    public static class Symbol extends Expr {
+        public final String name;
+        public Symbol(Token op) {
+            super(op);
+            name = op.getValueText();
+        }
+    }
+
+    public static class Binary extends Expr {
+        public final Expr expr1, expr2;
+
+        public Binary(Token op, Expr expr1, Expr expr2) {
+            super(op);
+            this.expr1 = expr1;
+            this.expr2 = expr2;
+        }
+    }
+
+    public static class Unary extends Expr {
+        public final Expr expr;
+
+        public Unary(Token op, Expr expr) {
+            super(op);
+            this.expr = expr;
+        }
+    }
+
+    public static class Constant extends Expr {
+        public Constant(Token op) {
+            super(op);
+        }
+    }
+
+    public static class Statement extends Node {
+    }
+
+    public static class IfElse extends Statement {
+        public final Expr expr;
+        public final Statement ifStmt, elseStmt;
+
+        public IfElse(Expr expr, Statement ifStmt, Statement elseStmt) {
+            this.expr = expr;
+            this.ifStmt = ifStmt;
+            this.elseStmt = elseStmt;
+        }
+    }
+
+    public static class While extends Statement {
+        public Expr expr;
+        public Statement stmt;
+
+        public While() {
+        }
+        public void init(Expr expr, Statement stmt) {
+            this.expr = expr;
+            this.stmt = stmt;
+        }
+    }
+
+    public static class Break extends Statement {
+        public final Statement stmt;
+
+        public Break(Statement stmt) {
+            if (stmt == null)
+            {
+                throw new CompilerException("uneclosed break");
+            }
+            this.stmt = stmt;
+        }
+    }
+
+    public static class Assign extends Statement {
+        public final Identifier identifier;
+        public final Expr expr;
+
+        public Assign(Identifier identifier, Expr expr) {
+            this.identifier = identifier;
+            this.expr = expr;
+        }
+    }
+
+    public static class Type extends Node {
+        public final Token.Id typeId;
+
+        public Type(Token.Id typeId) {
+            this.typeId = typeId;
+        }
+    }
+
+    public static class Declare extends Statement {
+        public final Type type;
+        public final Identifier identifier;
+
+        public Declare(Type type, Identifier identifier) {
+            this.type = type;
+            this.identifier = identifier;
+        }
+    }
+
+    public static class Block extends Statement {
+        public final List<Statement> stmtList = new ArrayList<>();
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/parser/Parser.java b/src/main/java/com/seaofnodes/simple/parser/Parser.java
new file mode 100644
index 00000000..f7b29f40
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/parser/Parser.java
@@ -0,0 +1,259 @@
+/**
+ * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER.
+ *
+ * Contributor(s):
+ *
+ * The Initial Developer of the Original Software is Dibyendu Majumdar.
+ *
+ * This file is part of the Sea Of Nodes Simple Programming language
+ * implementation. See https://github.com/SeaOfNodes/Simple
+ *
+ * The contents of this file are subject to the terms of the
+ * Apache License Version 2 (the "APL"). You may not use this
+ * file except in compliance with the License. A copy of the
+ * APL may be obtained from:
+ * http://www.apache.org/licenses/LICENSE-2.0
+ */
+package com.seaofnodes.simple.parser;
+
+import com.seaofnodes.simple.common.CompilerException;
+import com.seaofnodes.simple.lexer.ecstasy.Lexer;
+import com.seaofnodes.simple.lexer.ecstasy.Token;
+import com.seaofnodes.util.Severity;
+
+public class Parser {
+    final Lexer lexer;
+    Token look;
+    Ast.Statement statementEnclosing;
+
+    public Parser(Lexer lexer) {
+        this.lexer = lexer;
+    }
+
+    Token nextOrEof() {
+        if (lexer.hasNext())
+            return lexer.next();
+        return new Token(look.getStartPosition(), look.getEndPosition(), Token.Id.EOF);
+    }
+
+    void nextToken() {
+        look = nextOrEof();
+        while (look.isComment()) {
+            look = nextOrEof();
+        }
+        if (look.isContextSensitive() &&
+                look.getId() == Token.Id.IDENTIFIER) {
+            look = look.convertToKeyword();
+        }
+    }
+
+    void error(Token t, String errorMessage) {
+        lexer.log(Severity.ERROR, errorMessage, t.getStartPosition(), t.getEndPosition());
+        throw new CompilerException(errorMessage + ": " + t.toDebugString());
+    }
+
+    void match(Token.Id tag) {
+        if (look.getId() == tag) {
+            nextToken();
+        } else {
+            error(look, "syntax error, expected " + tag);
+        }
+    }
+
+    public Ast.Node parse() {
+        nextToken();
+        return parseProgram();
+    }
+
+    Ast.Statement parseProgram() {
+        var block = new Ast.Block();
+        parseDeclarations(block);
+        parseStatements(block);
+        return block;
+    }
+
+    void parseDeclarations(Ast.Block block) {
+        while (look.getId() == Token.Id.VAR) {
+            nextToken();
+            var tok = look;
+            match(Token.Id.IDENTIFIER);
+            match(Token.Id.COLON);
+            var type = parseType();
+            match(Token.Id.SEMICOLON);
+            var identifier = new Ast.Identifier(tok);
+            block.stmtList.add(new Ast.Declare(type, identifier));
+        }
+    }
+
+    Ast.Type parseType() {
+        if (look.getId() == Token.Id.LIT_INTA) {
+            nextToken();
+            return new Ast.Type(look.getId());
+        }
+        error(look, "syntax error: unsupported type (at present only Int type is allowed)");
+        return null;
+    }
+
+    void parseStatements(Ast.Block block) {
+        while (look.getId() != Token.Id.EOF &&
+                look.getId() != Token.Id.R_CURLY) {
+            block.stmtList.add(parseStatement());
+        }
+    }
+
+    Ast.Statement parseStatement() {
+        Ast.Expr x;
+        Ast.Statement s1;
+        Ast.Statement s2;
+
+        switch (look.getId()) {
+            case IF -> {
+                match(Token.Id.IF);
+                match(Token.Id.L_PAREN);
+                x = parseBool();
+                match(Token.Id.R_PAREN);
+                s1 = parseStatement();
+                if (look.getId() != Token.Id.ELSE) {
+                    return new Ast.IfElse(x, s1, null);
+                }
+                s2 = parseStatement();
+                return new Ast.IfElse(x, s1, s2);
+            }
+            case WHILE -> {
+                var whilenode = new Ast.While();
+                var savedStmt = statementEnclosing;
+                statementEnclosing = whilenode;
+                match(Token.Id.WHILE);
+                match(Token.Id.L_PAREN);
+                x = parseBool();
+                match(Token.Id.R_PAREN);
+                s1 = parseStatement();
+                whilenode.init(x, s1);
+                statementEnclosing = savedStmt;
+                return whilenode;
+            }
+            case BREAK -> {
+                match(Token.Id.BREAK);
+                match(Token.Id.SEMICOLON);
+                return new Ast.Break(statementEnclosing);
+            }
+            case L_CURLY -> {
+                return parseBlock();
+            }
+            default -> {
+                return parseAssign();
+            }
+        }
+    }
+
+    Ast.Statement parseBlock() {
+        match(Token.Id.L_CURLY);
+        var block = new Ast.Block();
+        parseDeclarations(block);
+        parseStatements(block);
+        match(Token.Id.R_CURLY);
+        return block;
+    }
+
+    Ast.Statement parseAssign() {
+        match(Token.Id.IDENTIFIER);
+        Ast.Identifier identifier = new Ast.Identifier(look);
+        match(Token.Id.ASN);
+        var s = new Ast.Assign(identifier, parseBool());
+        match(Token.Id.SEMICOLON);
+        return s;
+    }
+
+    Ast.Expr parseBool() {
+        var x = parseAnd();
+        while (look.getId() == Token.Id.COND_OR) {
+            var tok = look;
+            nextToken();
+            x = new Ast.Binary(tok, x, parseAnd());
+        }
+        return x;
+    }
+
+    Ast.Expr parseAnd() {
+        var x = parseRelational();
+        while (look.getId() == Token.Id.COND_AND) {
+            var tok = look;
+            nextToken();
+            x = new Ast.Binary(tok, x, parseRelational());
+        }
+        return x;
+    }
+
+    Ast.Expr parseRelational() {
+        var x = parseAddition();
+        while (look.getId() == Token.Id.COMP_EQ ||
+                look.getId() == Token.Id.COMP_NEQ ||
+                look.getId() == Token.Id.COMP_LT ||
+                look.getId() == Token.Id.COMP_GT ||
+                look.getId() == Token.Id.COMP_GTEQ ||
+                look.getId() == Token.Id.COMP_LTEQ) {
+            var tok = look;
+            nextToken();
+            x = new Ast.Binary(tok, x, parseAddition());
+        }
+        return x;
+    }
+
+    Ast.Expr parseAddition() {
+        var x = parseMultiplication();
+        while (look.getId() == Token.Id.ADD ||
+                look.getId() == Token.Id.SUB) {
+            var tok = look;
+            nextToken();
+            x = new Ast.Binary(tok, x, parseMultiplication());
+        }
+        return x;
+    }
+
+    Ast.Expr parseMultiplication() {
+        var x = parseUnary();
+        while (look.getId() == Token.Id.MUL ||
+                look.getId() == Token.Id.DIV) {
+            var tok = look;
+            nextToken();
+            x = new Ast.Binary(tok, x, parseUnary());
+        }
+        return x;
+    }
+
+    Ast.Expr parseUnary() {
+        if (look.getId() == Token.Id.SUB ||
+                look.getId() == Token.Id.NOT) {
+            var tok = look;
+            nextToken();
+            return new Ast.Unary(tok, parseUnary());
+        } else {
+            return parsePrimary();
+        }
+    }
+
+    Ast.Expr parsePrimary() {
+        switch (look.getId()) {
+            case L_PAREN -> {
+                nextToken();
+                var x = parseBool();
+                match(Token.Id.R_PAREN);
+                return x;
+            }
+            case LIT_INT -> {
+                var x = new Ast.Constant(look);
+                nextToken();
+                return x;
+            }
+            case IDENTIFIER -> {
+                var x = new Ast.Symbol(look);
+                nextToken();
+                return x;
+            }
+            default -> {
+                error(look, "syntax error, expected nested expr, integer value or variable");
+                return null;
+            }
+        }
+    }
+}
diff --git a/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java b/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java
index 335bcf5e..18a4634d 100644
--- a/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java
+++ b/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java
@@ -3,8 +3,6 @@
  *
  * Contributor(s):
  *
- * The Initial Developer of the Original Software is Cliff Click.
- *
  * This file is part of the Sea Of Nodes Simple Programming language
  * implementation. See https://github.com/SeaOfNodes/Simple
  *
@@ -17,6 +15,10 @@
 
 package com.seaofnodes.simple.lexer;
 
+import com.seaofnodes.simple.common.ErrorListener;
+import com.seaofnodes.simple.lexer.ecstasy.Lexer;
+import com.seaofnodes.simple.lexer.ecstasy.Source;
+import com.seaofnodes.simple.lexer.ecstasy.Token;
 import org.junit.jupiter.api.Assertions;
 import org.junit.jupiter.api.Test;
 
@@ -26,8 +28,10 @@ public class TestLexer {
     public void testLexLineComment()
     {
         final String source = "//a comment\nx";
-        Lexer lexer = new Lexer("test", source);
-        String token = lexer.token();
-        Assertions.assertEquals("x", token);
+        Lexer lexer = new Lexer(new Source(source), new ErrorListener());
+        Token token = lexer.next();
+        Assertions.assertEquals(token.getId(), Token.Id.EOL_COMMENT);
+        token = lexer.next();
+        Assertions.assertEquals("x", token.getValueText());
     }
 }
diff --git a/src/test/java/com/seaofnodes/simple/lexer/TestParser.java b/src/test/java/com/seaofnodes/simple/lexer/TestParser.java
new file mode 100644
index 00000000..7d2f3752
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/lexer/TestParser.java
@@ -0,0 +1,68 @@
+/**
+ * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER.
+ *
+ * Contributor(s):
+ *
+ * This file is part of the Sea Of Nodes Simple Programming language
+ * implementation. See https://github.com/SeaOfNodes/Simple
+ *
+ * The contents of this file are subject to the terms of the
+ * Apache License Version 2 (the "APL"). You may not use this
+ * file except in compliance with the License. A copy of the
+ * APL may be obtained from:
+ * http://www.apache.org/licenses/LICENSE-2.0
+ */
+
+package com.seaofnodes.simple.lexer;
+
+import com.seaofnodes.simple.common.ErrorListener;
+import com.seaofnodes.simple.lexer.ecstasy.Lexer;
+import com.seaofnodes.simple.lexer.ecstasy.Source;
+import com.seaofnodes.simple.parser.Ast;
+import com.seaofnodes.simple.parser.Parser;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+public class TestParser {
+
+    @Test
+    public void testParseSingleDecl()
+    {
+        final String source = "var i: Int;";
+        Lexer lexer = new Lexer(new Source(source), new ErrorListener());
+        Parser parser = new Parser(lexer);
+        var ast = parser.parse();
+        Assertions.assertTrue(ast instanceof Ast.Block
+            && ((Ast.Block) ast).stmtList.size() == 1);
+    }
+
+    @Test
+    public void testParseTwoDecls() {
+        final String source = "var i: Int;\nvar j: Int;";
+        Lexer lexer = new Lexer(new Source(source), new ErrorListener());
+        Parser parser = new Parser(lexer);
+        var ast = parser.parse();
+        Assertions.assertTrue(ast instanceof Ast.Block
+                && ((Ast.Block) ast).stmtList.size() == 2);
+    }
+
+    @Test
+    public void testIfAndWhile() {
+        final String source =
+                """
+                var i: Int;
+                var j: Int;
+                
+                i = 0;
+                j = 100;
+                while ( 1 ) {
+                    i = i + 1;
+                    j = j - 1;
+                    if ( i >= j ) break;
+                }
+                """;
+        Lexer lexer = new Lexer(new Source(source), new ErrorListener());
+        Parser parser = new Parser(lexer);
+        var ast = parser.parse();
+    }
+}