summaryrefslogtreecommitdiff
path: root/chapter01
diff options
context:
space:
mode:
Diffstat (limited to 'chapter01')
-rw-r--r--chapter01/README.md0
-rw-r--r--chapter01/docs/01-grammar.md0
-rw-r--r--chapter01/pom.xml22
-rw-r--r--chapter01/src/main/java/com/seaofnodes/simple/parser/Ast.java132
-rw-r--r--chapter01/src/main/java/com/seaofnodes/simple/parser/Parser.java259
-rw-r--r--chapter01/src/test/java/com/seaofnodes/simple/lexer/TestParser.java68
6 files changed, 481 insertions, 0 deletions
diff --git a/chapter01/README.md b/chapter01/README.md
new file mode 100644
index 00000000..e69de29b
--- /dev/null
+++ b/chapter01/README.md
diff --git a/chapter01/docs/01-grammar.md b/chapter01/docs/01-grammar.md
new file mode 100644
index 00000000..e69de29b
--- /dev/null
+++ b/chapter01/docs/01-grammar.md
diff --git a/chapter01/pom.xml b/chapter01/pom.xml
new file mode 100644
index 00000000..842e67e9
--- /dev/null
+++ b/chapter01/pom.xml
@@ -0,0 +1,22 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<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>
+ <parent>
+ <groupId>com.seaofnodes</groupId>
+ <artifactId>simple</artifactId>
+ <version>1.0</version>
+ </parent>
+ <artifactId>chapter01</artifactId>
+ <packaging>jar</packaging>
+ <name>Chapter 1</name>
+
+ <dependencies>
+ <dependency>
+ <groupId>com.seaofnodes</groupId>
+ <artifactId>common</artifactId>
+ <version>1.0</version>
+ </dependency>
+ </dependencies>
+</project> \ No newline at end of file
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/parser/Ast.java b/chapter01/src/main/java/com/seaofnodes/simple/parser/Ast.java
new file mode 100644
index 00000000..a93b230f
--- /dev/null
+++ b/chapter01/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/chapter01/src/main/java/com/seaofnodes/simple/parser/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/parser/Parser.java
new file mode 100644
index 00000000..b36942d4
--- /dev/null
+++ b/chapter01/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.simple.common.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/chapter01/src/test/java/com/seaofnodes/simple/lexer/TestParser.java b/chapter01/src/test/java/com/seaofnodes/simple/lexer/TestParser.java
new file mode 100644
index 00000000..a89c1f6a
--- /dev/null
+++ b/chapter01/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.Assert;
+import org.junit.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();
+ Assert.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();
+ Assert.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();
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2026-10-15 13:58:21 +0000