Merge pull request #3 from dibyendumajumdar/main

Chapter 1 implementation

6 files changed, 416 insertions, 0 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..8fb1ebaf
--- /dev/null
+++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java
@@ -0,0 +1,274 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.ConstantNode;
+import com.seaofnodes.simple.node.Node;
+import com.seaofnodes.simple.node.ReturnNode;
+import com.seaofnodes.simple.node.StartNode;
+
+/**
+ * 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.
+ *
+ * This is a simple recursive descent parser. All lexical analysis is done here as well.
+ */
+public class Parser {
+
+    /**
+     * Current token from lexer
+     */
+    private Token _curTok;
+
+    private StartNode _startNode;
+
+    public StartNode parse(String source) {
+        Lexer lexer = new Lexer(source);
+        nextToken(lexer);
+        return parseProgram(lexer);
+    }
+
+    private StartNode parseProgram(Lexer lexer) {
+        _startNode = new StartNode();
+        parseReturnStatement(lexer);
+        return _startNode;
+    }
+
+    /**
+     * Parses return statement.
+     *
+     * <pre>
+     *     return expr ;
+     * </pre>
+     */
+    private ReturnNode parseReturnStatement(Lexer lexer) {
+        matchIdentifier(lexer, "return");
+        var returnExpr = parseExpression(lexer);
+        matchPunctuation(lexer, ";");
+        return new ReturnNode(_startNode, returnExpr);
+    }
+
+    /**
+     * Parse an expression of the form:
+     *
+     * <pre>
+     *     expr : primaryExpr
+     * </pre>
+     */
+    private Node parseExpression(Lexer lexer) {
+        return parsePrimary(lexer);
+    }
+
+    /**
+     * Parse a primary expression:
+     *
+     * <pre>
+     *     primaryExpr : integerLiteral
+     * </pre>
+     */
+    private Node parsePrimary(Lexer lexer) {
+        switch (_curTok._kind) {
+            case NUM -> {
+                return parseIntegerLiteral(lexer);
+            }
+            default -> {
+                error(_curTok, "syntax error, expected integer literal");
+                return null;
+            }
+        }
+    }
+
+    /**
+     * Parse integer literal
+     *
+     * <pre>
+     *     integerLiteral: [1-9][0-9]*
+     * </pre>
+     */
+    private ConstantNode parseIntegerLiteral(Lexer lexer) {
+        var constantNode = new ConstantNode(_curTok._num.longValue(), _startNode);
+        nextToken(lexer);
+        return constantNode;
+    }
+
+    //////////////////////////////////
+    // Utilities for lexical analysis
+
+    private void nextToken(Lexer lexer) {
+        _curTok = 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 (_curTok._kind == Token.Kind.PUNCT && isToken(_curTok, value)) {
+            nextToken(lexer);
+        } else {
+            error(_curTok, "syntax error, expected " + value + " got " + _curTok._str);
+        }
+    }
+
+    private void matchIdentifier(Lexer lexer, String identifier) {
+        if (_curTok._kind == Token.Kind.IDENT && isToken(_curTok, identifier)) {
+            nextToken(lexer);
+        } else {
+            error(_curTok, "syntax error, expected " + identifier);
+        }
+    }
+
+    ////////////////////////////////////
+    // Lexer components
+
+    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);
+
+        @Override
+        public String toString() { return _str; }
+    }
+
+    static class Lexer {
+
+        // Input buffer; an array of text bytes read from a file or a string
+        private final byte[] _input;
+        // Tracks current position in input buffer
+        private int _position = 0;
+
+        /**
+         * Record the source text for lexing
+         */
+        public Lexer(String source) { this(source.getBytes());  }
+        public Lexer(byte[] buf) {  _input = buf;  }
+
+        // True if at EOF
+        private boolean isEOF() {  return _position >= _input.length;  }
+
+        private char nextChar() {
+            char ch = peek();
+            _position++;
+            return ch;
+        }
+        // Peek next character, or report EOF
+        private char peek() {
+            return isEOF() ? Character.MAX_VALUE   // Special value that causes parsing to terminate
+                : (char)_input[_position];
+        }
+
+        // True if a white space
+        private boolean isWhiteSpace(char c) {
+            return c <= ' '; // Includes all the use space, tab, newline, CR
+        }
+
+        /**
+         * Return the next non-white-space character
+         */
+        private char skipWhiteSpace() {
+            char c = nextChar();
+            while( isWhiteSpace(c) )
+                c = nextChar();
+            return c;
+        }
+
+        private boolean isDigit(char ch) {
+            return ('0'<=ch && ch<='9');
+        }
+
+        private Token parseNumber() {
+            int start = _position-1;
+            while( Character.isDigit( nextChar() ) ) ;
+            String snum = new String(_input,start,--_position-start);
+            if (snum.length() > 1 && snum.charAt(0) == '0')
+                throw error("syntax error: integer values cannot start with '0'");
+            return Token.newNum(Integer.parseInt(snum),snum);
+        }
+
+        // First letter of an identifier 
+        private boolean isIdentifierStart(char ch) {
+            return Character.isAlphabetic(ch) || ch == '_';
+        }
+
+        // All characters of an identifier, e.g. "_x123"
+        private boolean isIdentifierLetter(char ch) {
+            return Character.isLetterOrDigit(ch) || ch == '_';
+        }
+
+        private Token parseIdentifier() {
+            int start = _position-1;
+            while( isIdentifierLetter(nextChar()) );
+            return Token.newIdent(new String(_input,start,--_position-start));
+        }
+
+        // 
+        private boolean isPunctuation(char ch) {
+            return "=;[]<>()+-/*".indexOf(ch) != -1;
+        }
+
+        private Token parsePuncuation() {
+            int start = _position-1;
+            while( isPunctuation(nextChar()) );
+            return Token.newPunct(new String(_input,start,--_position-start));            
+        }
+            
+        /**
+         * Gets the next Token
+         */
+        public Token next() {
+            char ch = skipWhiteSpace();
+            if (ch == Character.MAX_VALUE)
+                return Token.EOF;
+            if (isDigit(ch))
+                return parseNumber();
+            if (isIdentifierStart(ch))
+                return parseIdentifier();
+            if (isPunctuation(ch))
+                return parsePuncuation();
+            
+            throw error("syntax error: unexpected input '" + ch + "'");
+        }
+
+        private RuntimeException error(String msg) {
+            throw new RuntimeException(msg);
+        }
+    }
+
+}
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
new file mode 100644
index 00000000..7644daf2
--- /dev/null
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -0,0 +1,23 @@
+package com.seaofnodes.simple.node;
+
+/**
+ * A Constant node represents a constant value.  At present, the only constants
+ * that we allow are integer literals; therefore Constants contain an integer
+ * value. As we add other types of constants, we will refactor how we represent
+ * Constants.
+ * <p>
+ * Constants have no semantic inputs. However, we set Start as an input to
+ * Constants to enable a forward graph walk.  This edge carries no semantic
+ * meaning, and it is present <em>solely</em> to allow visitation.
+ * <p>
+ * The Constant's value is the value stored in it.
+ */
+public class ConstantNode extends Node {
+
+    public final long _value;
+
+    public ConstantNode(long value, StartNode startNode) {
+        super(startNode);
+        _value = value;
+    }
+}
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/Control.java b/chapter01/src/main/java/com/seaofnodes/simple/node/Control.java
new file mode 100644
index 00000000..48cf2b7a
--- /dev/null
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Control.java
@@ -0,0 +1,9 @@
+package com.seaofnodes.simple.node;
+
+
+/**
+ * Control interface is a marker interface to be implemented
+ * by Control nodes.
+ */
+public interface Control {
+}
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java
new file mode 100644
index 00000000..6b2a19b8
--- /dev/null
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -0,0 +1,80 @@
+package com.seaofnodes.simple.node;
+
+import java.util.ArrayList;
+import java.util.Collections;
+
+/**
+ * All Nodes in the Sea of Nodes IR inherit from the Node class.
+ * The Node class provides common functionality used by all subtypes.
+ * Subtypes of Node specialize by overriding methods.
+ */
+public abstract class Node {
+
+    /**
+     * Each node has a unique dense Node ID within a compilation context
+     * The ID is useful for debugging, for using as an offset in a bitvector,
+     * as well as for computing equality of nodes (to be implemented later).
+     */
+    public final int _nid;
+
+    /**
+     * Inputs to the node. These are use-def references to Nodes.
+     * <p>
+     * Generally fixed length, ordered, nulls allowed, no unused trailing space.
+     * Ordering is required because e.g. "a/b" is different from "b/a".
+     * The first input (offset 0) is often a Control node.
+     * @see Control
+     */
+    public final ArrayList<Node> _inputs;
+
+    /**
+     * Outputs reference Nodes that are not null and have this Node as an
+     * input.  These nodes are users of this node, thus these are def-use
+     * references to Nodes.
+     * <p>
+     * Outputs directly match inputs, making a directed graph that can be
+     * walked in either direction.  These outputs are typically used for
+     * efficient optimizations but otherwise have no semantics meaning.
+     */
+    public final ArrayList<Node> _outputs;
+
+    /**
+     * A private Global Static mutable counter, for unique node id generation.
+     * To make the compiler multi-threaded, this field will have to move into a TLS.
+     * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values.
+     * */
+    private static int UNIQUE_ID = 1;
+
+    protected Node(Node ...inputs) {
+        _nid = UNIQUE_ID++; // allocate unique dense ID
+        _inputs = new ArrayList<>();
+        Collections.addAll(_inputs,inputs);
+        _outputs = new ArrayList<>();
+        for( Node n : _inputs ) {
+            if( n != null )
+                n._outputs.add( this );
+      }
+    }
+
+    /**
+     * Gets the ith input node
+     * @param i Offset of the input node
+     * @return Input node or null
+     */
+    public Node in(int i) { return _inputs.get(i); }
+
+    public int nIns() { return _inputs.size(); }
+
+    /**
+     * Gets the ith output node
+     * @param i Offset of the output node
+     * @return Output node (not null)
+     */
+    public Node out(int i) { return _outputs.get(i); }
+
+    public int nOuts() { return _outputs.size(); }
+
+    /*
+     * hashCode and equals implementation to be added in later chapter.
+     */
+}
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
new file mode 100644
index 00000000..12a5b464
--- /dev/null
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -0,0 +1,17 @@
+package com.seaofnodes.simple.node;
+
+/**
+ * The Return node has two inputs.  The first input is a control node and the
+ * second is the data node that supplies the return value.
+ * <p>
+ * In this presentation, Return functions as a Stop node, since multiple <code>return</code> statements are not possible.
+ * The Stop node will be introduced in Chapter 6 when we implement <code>if</code> statements.
+ * <p>
+ * The Return's output is the value from the data node.
+ */
+public class ReturnNode extends Node implements Control {
+
+    public ReturnNode(Node ctrl, Node data) {
+        super(ctrl, data);
+    }
+}
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java
new file mode 100644
index 00000000..c29ba53c
--- /dev/null
+++ b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -0,0 +1,13 @@
+package com.seaofnodes.simple.node;
+
+/**
+ * The Start node represents the start of the function.  For now, we do not have any inputs to Start because our function does not
+ * yet accept parameters.  When we add parameters the value of Start will be a tuple, and will require Projections to extract the values.
+ * We discuss this in detail in Chapter 9: Functions and Calls.
+ */
+public class StartNode extends Node implements Control {
+
+    public StartNode(/*arguments go here*/) {
+        super();
+    }
+}