Start on parser

7 files changed, 278 insertions, 30 deletions

diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java
new file mode 100644
index 00000000..bf9791a8
--- /dev/null
+++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java
@@ -0,0 +1,254 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+
+import java.text.NumberFormat;
+import java.text.ParseException;
+
+/**
+ * The Parser converts a Simple source program to the Sea of Nodes intermediate representation
+ * directly in one pass. There is no intermediate Abstract Syntax Tree structure. The parser also
+ * does the lexical analysis of the input source.
+ */
+public class Parser {
+
+    private Token currentToken;
+    private final NodeIDGenerator _idGenerator;
+    private StartNode _startNode;
+
+    public Parser() {
+        _idGenerator = new NodeIDGenerator();
+    }
+
+    public Node parse(String source) {
+        Lexer lexer = new Lexer(source);
+        _startNode = new StartNode(_idGenerator, new Node[0]);
+        nextToken(lexer);
+        return parseProgram(lexer);
+    }
+
+    private Node parseProgram(Lexer lexer) {
+        parseReturnStatement(lexer);
+        return _startNode;
+    }
+
+    private void nextToken(Lexer lexer) {
+        currentToken = lexer.next();
+    }
+
+    private boolean isToken(Token token, String value) {
+        return token._str.equals(value);
+    }
+
+    private void error(Token t, String errorMessage) {
+        throw new RuntimeException(errorMessage + ": " + t.toString());
+    }
+
+    private void matchPunctuation(Lexer lexer, String value) {
+        if (currentToken._kind == Token.Kind.PUNCT && isToken(currentToken, value)) {
+            nextToken(lexer);
+        } else {
+            error(currentToken, "syntax error, expected " + value + " got " + currentToken._str);
+        }
+    }
+
+    private void matchIdentifier(Lexer lexer, String identifier) {
+        if (currentToken._kind == Token.Kind.IDENT && isToken(currentToken, identifier)) {
+            nextToken(lexer);
+        } else {
+            error(currentToken, "syntax error, expected " + identifier);
+        }
+    }
+
+    private Node parsePrimary(Lexer lexer) {
+        switch (currentToken._kind) {
+            case PUNCT -> {
+                /* Nested expression */
+                return parseNestedExpr(lexer);
+            }
+            case NUM -> {
+                return parseNumberConstant(lexer);
+            }
+            default -> {
+                error(currentToken, "syntax error, expected nested expr or integer literal");
+                return null;
+            }
+        }
+    }
+
+    private ConstantNode parseNumberConstant(Lexer lexer) {
+        var constantNode = new ConstantNode(_idGenerator, currentToken._num.longValue(), _startNode);
+        nextToken(lexer);
+        return constantNode;
+    }
+
+    private Node parseNestedExpr(Lexer lexer) {
+        matchPunctuation(lexer, "(");
+        nextToken(lexer);
+        var node = parsePrimary(lexer);
+        matchPunctuation(lexer, ")");
+        return node;
+    }
+
+    private Node parseReturnStatement(Lexer lexer) {
+        matchIdentifier(lexer, "return");
+        var returnExpr = parsePrimary(lexer);
+        matchPunctuation(lexer, ";");
+        return new ReturnNode(_idGenerator, _startNode, returnExpr);
+    }
+
+    static class Token {
+
+        enum Kind {
+            IDENT,
+            NUM,
+            PUNCT,
+            EOZ     // Special kind to signal end of file
+        }
+
+        public final Kind _kind;
+        /**
+         * String representation of a token - always
+         * populated
+         */
+        public final String _str;
+        /**
+         * The parsed number value, only populated for Kind.NUM
+         */
+        public final Number _num;
+
+        public Token(Kind kind, String str, Number num) {
+            _kind = kind;
+            _str = str;
+            _num = num;
+        }
+
+        public static Token newIdent(String str) {
+            return new Token(Kind.IDENT, str.intern(), null);
+        }
+        public static Token newNum(Number num, String str) {
+            return new Token(Kind.NUM, str, num);
+        }
+        public static Token newPunct(String str) {
+            return new Token(Kind.PUNCT, str.intern(), null);
+        }
+
+        /**
+         * Special token that indicates that source has been exhausted
+         */
+        public static Token EOF = new Token(Kind.EOZ, "", null);
+
+        public String toString() {
+            return _str;
+        }
+    }
+
+    static class Lexer {
+
+        private final char[] _input;
+        /**
+         * Tracks current position in input buffer
+         */
+        private int _position = 0;
+        private char _curCh = ' ';
+
+        private final NumberFormat numberFormat;
+
+        public Lexer(String source) {
+            _input = source.toCharArray();
+            numberFormat = NumberFormat.getInstance();
+            numberFormat.setGroupingUsed(false);
+        }
+
+        private boolean isEOF() {
+            return _position >= _input.length;
+        }
+
+        private char advance() {
+            if (isEOF())
+                return 0;   // Special value that causes parsing to terminate
+            return _input[_position++];
+        }
+
+        private boolean nextToken() {
+            _curCh = advance();
+            return true;
+        }
+
+        /**
+         * Note that EOF is not whitespace!
+         */
+        private boolean isWhiteSpace(char c) {
+            return c == ' ' ||
+                    c == '\t' ||
+                    c == '\n' ||
+                    c == '\r';
+        }
+
+        private void skipWhitespace() {
+            while (isWhiteSpace(_curCh))
+                nextToken();
+        }
+
+        /**
+         * Parses number in format nnn[.nnn]
+         * where n is a digit
+         */
+        private Token parseNumber() {
+            assert Character.isDigit(_curCh);
+            StringBuilder sb = new StringBuilder();
+            sb.append(_curCh);
+            while (nextToken() && Character.isDigit(_curCh))
+                sb.append(_curCh);
+            if (_curCh == '.') {
+                sb.append(_curCh);
+                while (nextToken() && Character.isDigit(_curCh))
+                    sb.append(_curCh);
+            }
+            String str = sb.toString();
+            Number number = parseNumber(str);
+            return Token.newNum(number, str);
+        }
+
+        private Number parseNumber(String str) {
+            try {
+                return numberFormat.parse(str);
+            } catch (ParseException e) {
+                throw new RuntimeException("Failed to parse number " + str, e);
+            }
+        }
+
+        private boolean isIdentifierStart(char ch) {
+            return Character.isAlphabetic(ch) || ch == '_';
+        }
+
+        private boolean isIdentifierLetter(char ch) {
+            return Character.isLetterOrDigit(ch) || ch == '_';
+        }
+
+        private Token parseIdentifier() {
+            assert isIdentifierStart(_curCh);
+            StringBuilder sb = new StringBuilder();
+            sb.append(_curCh);
+            while (nextToken() && isIdentifierLetter(_curCh))
+                sb.append(_curCh);
+            return Token.newIdent(sb.toString());
+        }
+
+        /**
+         * Gets the next token
+         */
+        public Token next() {
+            skipWhitespace();
+            if (_curCh == 0)
+                return Token.EOF;
+            if (Character.isDigit(_curCh))
+                return parseNumber();
+            if (isIdentifierLetter(_curCh))
+                return parseIdentifier();
+            Token token = Token.newPunct(Character.toString(_curCh));
+            _curCh = ' ';
+            return token;
+        }
+    }
+}
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index 7f798301..d2f51cd8 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -4,13 +4,8 @@ public class ConstantNode extends Node {
 
     long _value;
 
-    public ConstantNode(int nid, long value) {
-        super(nid, OP_CONSTANT);
-        _value = value;
-    }
-
-    public ConstantNode(NodeIDGenerator idGenerator, long value) {
-        super(idGenerator, OP_CONSTANT);
+    public ConstantNode(NodeIDGenerator idGenerator, long value, StartNode startNode) {
+        super(idGenerator, OP_CONSTANT, startNode);
         _value = value;
     }
 }
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java
index 0c6cdd3f..c3562b5d 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple.node;
 
+import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.List;
 
@@ -34,18 +35,18 @@ public class Node {
      */
     public final List<Node> _inputs;
 
-    protected Node(int nid, byte opCode, Node ...inputs)
-    {
-        _nid = nid;
-        _opCode = opCode;
-        _inputs = Arrays.asList(inputs);
-    }
+    public final List<Node> _refs = new ArrayList<>();
 
     protected Node(NodeIDGenerator idGenerator, byte opCode, Node ...inputs)
     {
         _nid = idGenerator.newNodeID();
         _opCode = opCode;
         _inputs = Arrays.asList(inputs);
+        for (int i = 0; i < _inputs.size(); i++) {
+            Node n = _inputs.get(i);
+            if (n != null)
+                n._refs.add(this);
+        }
     }
 
     /**
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/RegionNode.java
deleted file mode 100644
index b740deff..00000000
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ /dev/null
@@ -1,11 +0,0 @@
-package com.seaofnodes.simple.node;
-
-public class RegionNode extends Node implements Control {
-    public RegionNode(int nid, Node... inputs) {
-        super(nid, OP_REGION, inputs);
-    }
-
-    public RegionNode(NodeIDGenerator idGenerator, Node... inputs) {
-        super(idGenerator, OP_REGION, inputs);
-    }
-}
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index 655fd11f..9c017eef 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -1,9 +1,6 @@
 package com.seaofnodes.simple.node;
 
 public class ReturnNode extends Node implements Control {
-    public ReturnNode(int nid, Node... inputs) {
-        super(nid, OP_RETURN, inputs);
-    }
 
     public ReturnNode(NodeIDGenerator idGenerator, Node... inputs) {
         super(idGenerator, OP_RETURN, inputs);
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 8117c4f6..4ae7f71a 100644
--- a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -1,9 +1,6 @@
 package com.seaofnodes.simple.node;
 
 public class StartNode extends Node implements Control {
-    public StartNode(int nid, Node... inputs) {
-        super(nid, OP_START, inputs);
-    }
 
     public StartNode(NodeIDGenerator idGenerator, Node... inputs) {
         super(idGenerator, OP_START, inputs);
diff --git a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java
new file mode 100644
index 00000000..9f4a9a2e
--- /dev/null
+++ b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java
@@ -0,0 +1,15 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.Node;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class ParserTest {
+
+    @Test
+    public void testSimpleProgram() {
+        Parser parser = new Parser();
+        Node startNode = parser.parse("return 1;");
+        Assert.assertNotNull(startNode);
+    }
+}