Chapter 3 - add vars and lexical scope. (#7)

* Chapter 3 - add vars and lexical scope.

* Fix typo

* Overhaul graph viz

Makes the scopes pointing into the graph being build more visually appealing.
Constants are a printed with just the constant value.

* Fix control edge color

* Fix missing grouping operator parse

Add a parens test.
Shorten names 'Identifier' to 'Id'
_lexer.match -> match
require() passes a Node thru, so can be flow-coded.
Uniform syntax error messages.
Handy Lexer.toString for debugging.
Drop Optional for null returns; less total code; less objects; less confusion.
camelCase some fcns.

* All parser helpers return Node, not void.

Drop _ret.  parseBlock and parseStatement now the same.

* CLosely align chap2 and chap3 parsers

Mostly whitespace aligned; dragged a few functions around to make more sense.
I think the diff from Ch2 and Ch3 is down a few differences about what is a statement, plus all the symbol stuff for scopes and variables.

* Add examples illustrating the symbol table creation.

* Update docs and comments

---------

Co-authored-by: Cliff Click <cliffc@acm.org>

16 files changed, 1277 insertions, 0 deletions

diff --git a/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
new file mode 100644
index 00000000..5f3f52d0
--- /dev/null
+++ b/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -0,0 +1,145 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.ConstantNode;
+import com.seaofnodes.simple.node.Control;
+import com.seaofnodes.simple.node.Node;
+import com.seaofnodes.simple.node.StartNode;
+
+import java.util.*;
+
+/**
+ * Simple visualizer that outputs GraphViz dot format.
+ * The dot output must be saved to a file and run manually via dot to generate the SVG output.
+ * Currently, this is done manually.
+ */
+public class GraphVisualizer {
+
+    public String generateDotOutput(Parser parser) {
+
+        // Since the graph has cycles, we need to create a flat list of all the
+        // nodes in the graph.
+        Collection<Node> all = findAll(parser);
+        StringBuilder sb = new StringBuilder();
+        sb.append("digraph chapter03 {\n");
+        
+        // To keep the Scopes below the graph and pointing up into the graph we
+        // need to group the Nodes in a subgraph cluster, and the scopes into a
+        // different subgraph cluster.  THEN we can draw edges between the
+        // scopes and nodes.  If we try to cross subgraph cluster borders while
+        // still making the subgraphs DOT gets confused.
+        sb.append("\trankdir=BT;\n"); // Force Nodes before Scopes
+        
+        // Just the Nodes first, in a cluster no edges
+        nodes(sb, all);
+        
+        // Now the scopes, in a cluster no edges
+        scopes(sb, parser._scopes);
+
+        // Walk the Node edges
+        nodeEdges(sb, all);
+
+        // Walk the Scope edges
+        scopeEdges(sb, parser._scopes);
+        
+        sb.append("}\n");
+        return sb.toString();
+    }
+
+
+    private void nodes(StringBuilder sb, Collection<Node> all) {
+        // Just the Nodes first, in a cluster no edges
+        sb.append("\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name
+        for( Node n : all ) {
+            sb.append("\t\t").append(n.uniqueName()).append(" [ ");
+            // control nodes have box shape
+            // other nodes are ellipses, i.e. default shape
+            if( n instanceof Control )
+                sb.append("shape=box style=filled fillcolor=yellow ");
+            sb.append("label=\"").append(n.label()).append("\" ");
+            sb.append("];\n");
+        }
+        sb.append("\t}\n");     // End Node cluster
+    }
+
+    private void scopes( StringBuilder sb, Stack<HashMap<String,Node>> scopes) {
+        sb.append("\tnode [shape=plaintext];\n");
+        int level=0;
+        for( HashMap<String,Node> scope : scopes ) {
+            sb.append("\tsubgraph cluster_").append(level).append(" {\n"); // Magic "cluster_" in the subgraph name
+            String scopeName = makeScopeName(level);
+            sb.append("\t\t").append(scopeName).append(" [label=<\n");
+            sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n");
+            // Add the scope level
+            sb.append("\t\t\t<TR><TD BGCOLOR=\"aqua\">").append(level).append("</TD>");
+            for( String name : scope.keySet() )
+                sb.append("<TD PORT=\"").append(makePortName(scopeName, name)).append("\">").append(name).append("</TD>");
+            sb.append("</TR>\n");
+            sb.append("\t\t\t</TABLE>>];\n");
+            level++;
+        }
+        // Scope clusters nest, so the graphics shows the nested scopes, so
+        // they are not closed as they are printed; so they just keep nesting.
+        // We close them all at once here.
+        sb.append( "\t}\n".repeat( level ) ); // End all Scope clusters
+    }
+    
+    private String makeScopeName(int level) { return "scope" + level; }
+    private String makePortName(String scopeName, String varName) { return scopeName + "_" + varName; }
+
+    // Walk the node edges
+    private void nodeEdges(StringBuilder sb, Collection<Node> all) {
+        for( Node n : all )
+            for( Node out : n._inputs )
+                if( out != null ) {
+                    sb.append('\t').append(n.uniqueName()).append(" -> ").append(out.uniqueName());
+                    // Control edges are colored red
+                    if( n instanceof ConstantNode && out instanceof StartNode )
+                      sb.append(" [style=dotted]");
+                    else if( n instanceof Control && out instanceof Control )
+                      sb.append(" [color=red]");
+                    sb.append(";\n");
+                }
+    }
+    
+    // Walk the scope edges
+    private void scopeEdges( StringBuilder sb, Stack<HashMap<String,Node>> scopes) {
+        sb.append("\tedge [style=dashed color=cornflowerblue];\n");
+        int level=0;
+        for( HashMap<String,Node> scope : scopes ) {
+            String scopeName = makeScopeName(level);
+            for( String name : scope.keySet() )
+                sb.append("\t").append(scopeName).append(":").append(makePortName(scopeName, name)).append(" -> ").append(scope.get(name).uniqueName()).append(";\n");
+            level++;
+        }
+    }
+    
+    /**
+     * Walks the whole graph, starting from Start.
+     * Since Start is the input to all constants - we look at the outputs for
+     * Start, but for then subsequently we look at the inputs of each node.
+     * During graph construction not all nodes are reachable this way, so we
+     * also scan the symbol tables.
+     */
+    private Collection<Node> findAll(Parser parser) {
+        final StartNode start = Parser.START;
+        final HashMap<Integer, Node> all = new HashMap<>();
+        for( Node n : start._outputs )
+            walk(all, n);
+        // Scan symbol tables
+        for( HashMap<String,Node> scope : parser._scopes )
+            for (Node n : scope.values())
+                walk(all, n);
+        return all.values();
+    }
+
+    /**
+     * Walk a subgraph and populate distinct nodes in the all list.
+     */
+    private void walk(HashMap<Integer, Node> all, Node n) {
+        if (all.get(n._nid) != null) return; // Been there, done that
+        all.put(n._nid, n);
+        for (Node c : n._inputs)
+            if (c != null)
+                walk(all, c);
+    }
+}
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java
new file mode 100644
index 00000000..13b25e60
--- /dev/null
+++ b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java
@@ -0,0 +1,389 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.*;
+
+import java.util.*;
+
+/**
+ * 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.
+ * <p>
+ * This is a simple recursive descent parser. All lexical analysis is done here as well.
+ */
+public class Parser {
+
+    /**
+     * A Global Static, unique to each compilation.  This is a public, so we
+     * can make constants everywhere without having to thread the StartNode
+     * through the entire parser and optimizer.
+     * <p>
+     * To make the compiler multithreaded, this field will have to move into a TLS.
+     */
+    public static StartNode START;
+
+    private final Lexer _lexer;
+
+    /**
+     * Stack of lexical scopes, each scope is a symbol table
+     * that binds variable names to Nodes.
+     * The top of this stack represents current scope.
+     */
+    public Stack<HashMap<String, Node>> _scopes;
+
+    public Parser(String source) {
+        _lexer = new Lexer(source);
+        _scopes = new Stack<>();
+        Node.reset();
+        START = new StartNode();
+    }
+
+    public ReturnNode parse() {
+        return (ReturnNode) parseBlock();
+    }
+
+    // Create a new name in current scope
+    private Node define(String name, Node n) {
+        // new name
+        _scopes.lastElement().put(name, n);
+        return n;
+    }
+
+    // If the name is present in any scope, then redefine
+    private Node update(String name, Node n) {
+        for (int i = _scopes.size() - 1; i >= 0; i--) {
+            HashMap<String, Node> scope = _scopes.get(i);
+            Node old = scope.get(name);
+            if (old != null) { // Found prior def
+                if (old.nOuts() == 0) old.kill(); // Delete old ref
+                scope.put(name, n); // Update existing ref
+                return n;
+            }
+        }
+        throw error("Undefined name '" + name + "'");
+    }
+
+    // Lookup a name in all scopes
+    private Node lookup(String name) {
+        for (int i = _scopes.size() - 1; i >= 0; i--) {
+            var n = _scopes.get(i).get(name);
+            if (n != null) return n;
+        }
+        throw error("Undefined name '" + name + "'");
+    }
+
+    /**
+     * Parses a block
+     *
+     * <pre>
+     *     '{' statements '}'
+     * </pre>
+     */
+    private Node parseBlock() {
+        // Enter a new scope
+        _scopes.push(new HashMap<>());
+        Node n = null;
+        while (!match("}") && !_lexer.isEOF()) {
+            Node n0 = parseStatement();
+            if (n0 != null) n = n0; // Allow null returns from eg showGraph
+        }
+        // Exit scope
+        _scopes.pop();
+        return n;
+    }
+
+    /**
+     * Parses a statement
+     *
+     * <pre>
+     *     returnStatement | declStatement | blockStatement | expressionStatement
+     * </pre>
+     */
+    private Node parseStatement() {
+        if (match("return")) return parseReturn();
+        else if (match("int")) return parseDecl();
+        else if (match("{")) return parseBlock();
+        else if (match("#showGraph")) return showGraph();
+        else return parseExpressionStatement();
+    }
+
+    /**
+     * Parses returnStatement; "return" already parsed
+     *
+     * <pre>
+     *     'return' expr ;
+     * </pre>
+     */
+    private Node parseReturn() {
+        var expr = require(parseExpression(), ";");
+        return new ReturnNode(START, expr);
+    }
+
+    /**
+     * Dumps out the node graph
+     */
+    private Node showGraph() {
+        require(";");
+        System.out.println(new GraphVisualizer().generateDotOutput(this));
+        return null;
+    }
+
+    /**
+     * Parses an expression statement
+     *
+     * <pre>
+     *     name '=' expression ';'
+     * </pre>
+     */
+    private Node parseExpressionStatement() {
+        var name = requireId();
+        require("=");
+        var expr = require(parseExpression(), ";");
+        return update(name, expr);
+    }
+
+    /**
+     * Parses a declStatement
+     *
+     * <pre>
+     *     'int' name = expression ';'
+     * </pre>
+     */
+    private Node parseDecl() {
+        // Type is 'int' for now
+        var name = requireId();
+        require("=");
+        var expr = require(parseExpression(), ";");
+        return define(name, expr);
+    }
+
+    /**
+     * Parse an expression of the form:
+     *
+     * <pre>
+     *     expr : additiveExpr
+     * </pre>
+     */
+    private Node parseExpression() {return parseAddition();}
+
+    /**
+     * Parse an additive expression
+     *
+     * <pre>
+     *     additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)*
+     * </pre>
+     */
+    private Node parseAddition() {
+        var lhs = parseMultiplication();
+        if (match("+")) return new AddNode(lhs, parseAddition()).peephole();
+        if (match("-")) return new SubNode(lhs, parseAddition()).peephole();
+        return lhs;
+    }
+
+    /**
+     * Parse an multiplicativeExpr expression
+     *
+     * <pre>
+     *     multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)*
+     * </pre>
+     */
+    private Node parseMultiplication() {
+        var lhs = parseUnary();
+        if (match("*")) return new MulNode(lhs, parseMultiplication()).peephole();
+        if (match("/")) return new DivNode(lhs, parseMultiplication()).peephole();
+        return lhs;
+    }
+
+    /**
+     * Parse a unary minus expression.
+     *
+     * <pre>
+     *     unaryExpr : ('-') unaryExpr | primaryExpr
+     * </pre>
+     */
+    private Node parseUnary() {
+        if (match("-")) return new MinusNode(parseUnary()).peephole();
+        return parsePrimary();
+    }
+
+    /**
+     * Parse a primary expression:
+     *
+     * <pre>
+     *     primaryExpr : integerLiteral | Identifier | '(' expression ')'
+     * </pre>
+     */
+    private Node parsePrimary() {
+        if (_lexer.isNumber()) return parseIntegerLiteral();
+        if (match("(")) return require(parseExpression(), ")");
+        return lookup(requireId());
+    }
+
+    /**
+     * Parse integer literal
+     *
+     * <pre>
+     *     integerLiteral: [1-9][0-9]* | [0]
+     * </pre>
+     */
+    private ConstantNode parseIntegerLiteral() {
+        return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole();
+    }
+
+    //////////////////////////////////
+    // Utilities for lexical analysis
+
+    // Return true and skip if "syntax" is next in the stream.
+    private boolean match(String syntax) {return _lexer.match(syntax);}
+
+    // Require and return an identifier
+    private String requireId() {
+        String id = _lexer.matchId();
+        if (id != null) return id;
+        throw error("identifier");
+    }
+
+    // Require an exact match
+    private void require(String syntax) {require(null, syntax);}
+    private Node require(Node n, String syntax) {
+        if (match(syntax)) return n;
+        throw errorSyntax(syntax);
+    }
+
+    RuntimeException errorSyntax(String syntax) {
+        return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken());
+    }
+
+    static RuntimeException error(String errorMessage) {
+        return new RuntimeException(errorMessage);
+    }
+
+    ////////////////////////////////////
+    // Lexer components
+
+    private 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());
+        }
+
+        /**
+         * Direct from disk file source
+         */
+        public Lexer(byte[] buf) {
+            _input = buf;
+        }
+
+        // Very handy in the debugger, shows the unparsed program
+        @Override
+        public String toString() {
+            return new String(_input, _position, _input.length - _position);
+        }
+
+        // True if at EOF
+        private boolean isEOF() {
+            return _position >= _input.length;
+        }
+
+        // Peek next character, or report EOF
+        private char peek() {
+            return isEOF() ? Character.MAX_VALUE   // Special value that causes parsing to terminate
+                    : (char) _input[_position];
+        }
+
+        private char nextChar() {
+            char ch = peek();
+            _position++;
+            return ch;
+        }
+
+        // True if a white space
+        private boolean isWhiteSpace() {
+            return peek() <= ' '; // Includes all the use space, tab, newline, CR
+        }
+
+        /**
+         * Return the next non-white-space character
+         */
+        private void skipWhiteSpace() {
+            while (isWhiteSpace()) _position++;
+        }
+
+
+        // Return true, if we find "syntax" after skipping white space; also
+        // then advance the cursor past syntax.
+        // Return false otherwise, and do not advance the cursor.
+        boolean match(String syntax) {
+            skipWhiteSpace();
+            int len = syntax.length();
+            if (_position + len > _input.length) return false;
+            for (int i = 0; i < len; i++)
+                if ((char) _input[_position + i] != syntax.charAt(i)) return false;
+            _position += len;
+            return true;
+        }
+
+        // Return an identifier or null
+        String matchId() {
+            skipWhiteSpace();
+            return isIdStart(peek()) ? parseId() : null;
+        }
+
+        // Used for errors
+        String getAnyNextToken() {
+            if (isEOF()) return "";
+            if (isIdStart(peek())) return parseId();
+            if (isPunctuation(peek())) return parsePunctuation();
+            return String.valueOf(peek());
+        }
+
+        boolean isNumber() {return isNumber(peek());}
+        boolean isNumber(char ch) {return Character.isDigit(ch);}
+
+        private Type parseNumber() {
+            int start = _position;
+            while (isNumber(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 new TypeInteger(Long.parseLong(snum));
+        }
+
+        // First letter of an identifier 
+        private boolean isIdStart(char ch) {
+            return Character.isAlphabetic(ch) || ch == '_';
+        }
+
+        // All characters of an identifier, e.g. "_x123"
+        private boolean isIdLetter(char ch) {
+            return Character.isLetterOrDigit(ch) || ch == '_';
+        }
+
+        private String parseId() {
+            int start = _position;
+            while (isIdLetter(nextChar())) ;
+            return new String(_input, start, --_position - start);
+        }
+
+        // 
+        private boolean isPunctuation(char ch) {
+            return "=;[]<>()+-/*".indexOf(ch) != -1;
+        }
+
+        private String parsePunctuation() {
+            int start = _position;
+            if (isPunctuation(nextChar())) ;
+            return new String(_input, start, --_position - start);
+        }
+    }
+
+}
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java
new file mode 100644
index 00000000..015779dc
--- /dev/null
+++ b/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -0,0 +1,35 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.*;
+
+public class AddNode extends Node {
+    public AddNode(Node lhs, Node rhs) {
+        super(null, lhs, rhs);
+    }
+
+    @Override
+    public String label() { return "Add"; }
+
+    @Override
+    StringBuilder _print(StringBuilder sb) {
+        in(1)._print(sb.append("("));
+        in(2)._print(sb.append("+"));
+        return sb.append(")");
+    }
+  
+
+    @Override
+    public Type compute() {
+        if( in(1)._type instanceof TypeInteger i0 &&
+            in(2)._type instanceof TypeInteger i1 )
+            return new TypeInteger(i0._con + i1._con);
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize () {
+        // TODO: add of 0
+        return null;
+    }
+        
+}
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
new file mode 100644
index 00000000..798d40d5
--- /dev/null
+++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -0,0 +1,42 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.type.Type;
+
+/**
+ * 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 ConstantNode( Type type ) {
+        super(Parser.START);
+        _type = type;
+    }
+    
+    @Override
+    public String label() { return "#"+_type; }
+  
+    @Override
+    public String uniqueName() { return "Con_" + _nid; }
+
+    @Override
+    StringBuilder _print(StringBuilder sb) {
+        return _type._print(sb);
+    }
+    
+    @Override
+    public Type compute() { return _type; }
+
+    @Override
+    public Node idealize() { return null; }
+    
+}
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/Control.java b/chapter03/src/main/java/com/seaofnodes/simple/node/Control.java
new file mode 100644
index 00000000..48cf2b7a
--- /dev/null
+++ b/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java
new file mode 100644
index 00000000..bc129690
--- /dev/null
+++ b/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -0,0 +1,35 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeBot;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class DivNode extends Node {
+    public DivNode(Node lhs, Node rhs) {
+        super(null, lhs, rhs);
+    }
+
+    @Override
+    public String label() { return "Div"; }
+  
+    @Override
+    StringBuilder _print(StringBuilder sb) {
+        in(1)._print(sb.append("("));
+        in(2)._print(sb.append("/"));
+        return sb.append(")");
+    }
+  
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0 &&
+                in(2)._type instanceof TypeInteger i1) {
+            if (i1._con == 0)
+                throw new IllegalArgumentException("Divide by zero");
+            return new TypeInteger(i0._con / i1._con);
+        }
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java
new file mode 100644
index 00000000..7fab83b0
--- /dev/null
+++ b/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -0,0 +1,30 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeBot;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class MinusNode extends Node {
+    public MinusNode(Node in) {
+        super(null, in);
+    }
+
+    @Override
+    public String label() { return "Minus"; }
+  
+    @Override
+    StringBuilder _print(StringBuilder sb) {
+        in(1)._print(sb.append("(-"));
+        return sb.append(")");
+    }
+  
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0)
+            return new TypeInteger(-i0._con);
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java
new file mode 100644
index 00000000..e1a26858
--- /dev/null
+++ b/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -0,0 +1,32 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeBot;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class MulNode extends Node {
+    public MulNode(Node lhs, Node rhs) {
+        super(null, lhs, rhs);
+    }
+  
+    @Override
+    public String label() { return "Mul"; }
+  
+    @Override
+    StringBuilder _print(StringBuilder sb) {
+        in(1)._print(sb.append("("));
+        in(2)._print(sb.append("*"));
+        return sb.append(")");
+    }
+  
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0 &&
+                in(2)._type instanceof TypeInteger i1)
+            return new TypeInteger(i0._con * i1._con);
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java
new file mode 100644
index 00000000..5528f296
--- /dev/null
+++ b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -0,0 +1,213 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+
+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 );
+        // Do an initial type computation
+        _type = compute();
+    }
+
+    public abstract String label();
+
+    public String uniqueName() { return label() + _nid; }
+
+    @Override
+    public final String toString() {
+        // TODO: This needs a lot of work
+        return uniqueName();
+    }
+
+    // This is a *deep* print.  This version will fail on cycles, which we will
+    // correct later when we can parse programs with loops.
+    public final String print() {
+        return _print(new StringBuilder()).toString();
+    }
+    abstract StringBuilder _print(StringBuilder sb);
+
+    
+    /**
+     * 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(); }
+
+    /**
+     * We allow disabling peephole opt so that we can observe the
+     * full graph, vs the optimized graph.
+     */
+    public static boolean _disablePeephole = false;
+
+
+    /**
+     * Try to peephole at this node and return a better replacement Node if
+     * possible.  We check and replace:
+     * <ul>
+     * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li>
+     * <li>in a future chapter we will look for a
+     * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a>
+     * to eliminate.</li>
+     * <li>we ask the Node for a better replacement (again, none enabled in this chapter)</li>
+     * </ul>
+     */
+    public final Node peephole( ) {
+        if (_disablePeephole)
+            return this;        // Peephole optimizations turned off
+
+        // Replace constant computations from non-constants with a constant node
+        Type type = compute();
+        if (!(this instanceof ConstantNode) && type.isConstant()) {
+            kill();             // Kill `this` because replacing with a Constant
+            return new ConstantNode(type);
+        }
+
+        // Future chapter: Global Value Numbering goes here
+        
+        // Ask each node for a replacement
+        Node n = idealize();
+        if( n != null ) return n;
+        
+        return this;            // No progress
+    }
+
+    /**
+     * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em>
+     * to null.  This may recursively kill more Nodes and is basically dead
+     * code elimination.  This function is co-recursive with {@link #set_def}.
+     */
+  public void kill( ) {
+        assert nOuts()==0;    // Has no uses, so it is dead
+        for( int i=0; i<nIns(); i++ )
+            set_def(i,null);  // Set all inputs to null, recursively killing unused Nodes
+    }
+
+    /**
+     * Change a <em>def</em> into a Node.  Keeps the edges correct, by removing
+     * the corresponding <em>use->def</em> edge.  This may make the original
+     * <em>def</em> go dead.  This function is co-recursive with {@link #kill}.
+     *     
+     * @param idx which def to set
+     * @param new_def the new definition
+     */
+    void set_def(int idx, Node new_def ) {
+        Node old_def = in(idx);
+        if( old_def != null ) { // If the old def exists, remove a use->def edge
+            ArrayList<Node> outs = old_def._outputs;
+            int lidx = outs.size()-1; // Last index
+            
+            // This 1-line hack compresses an element out of an ArrayList
+            // without having to copy the contents.  The last element is
+            // stuffed over the deleted element, and then the size is reduced.            
+            outs.set(outs.indexOf(this),outs.get(lidx));
+            outs.remove(lidx);  // Reduce ArrayList size without copying anything
+            if( lidx == 0 )     // If we removed the last use, the old def is now dead
+                old_def.kill(); // Kill old def
+        }
+        // Set the new_def over the old (killed) edge
+        _inputs.set(idx,new_def);
+        // If new def is not null, add the corresponding use->def edge
+        if( new_def != null )
+            new_def._outputs.add(this);
+    }
+    
+  
+    /**
+     * Current computed type for this Node.  This value changes as the graph
+     * changes and more knowledge is gained about the program.
+     */
+    public Type _type;
+    
+    /**
+     * This function needs to be
+     * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a>
+     * as it is part of a Monotone Analysis Framework.
+     * <a href="https://www.cse.psu.edu/~gxt29/teaching/cse597s21/slides/08monotoneFramework.pdf">See for example this set of slides</a>.
+     * <p>
+     * For Chapter 2, all our Types are really integer constants, and so all
+     * the needed properties are trivially true, and we can ignore the high
+     * theory.  Much later on, this will become important and allow us to do
+     * many fancy complex optimizations trivially... because theory.
+     * <p>
+     * compute() needs to be stand-alone, and cannot recursively call compute
+     * on its inputs programs are cyclic (have loops!) and this will just
+     * infinitely recurse until stack overflow.  Instead, compute typically
+     * computes a new type from the {@link #_type} field of its inputs.
+     */
+    public abstract Type compute();
+
+    public abstract Node idealize();
+
+    /**
+     * Used to allow repeating tests in the same JVM.  This just resets the
+     * Node unique id generator, and is done as part of making a new Parser.
+     */
+    public static void reset() { UNIQUE_ID = 1; }
+  
+    /*
+     * hashCode and equals implementation to be added in later chapter.
+     */
+  
+}
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
new file mode 100644
index 00000000..c188ca79
--- /dev/null
+++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -0,0 +1,39 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.TypeBot;
+
+/**
+ * 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);
+    }
+
+    public Node ctrl() { return in(0); }
+    public Node expr() { return in(1); }
+  
+    @Override
+    public String label() { return "Return"; }
+
+    @Override
+    StringBuilder _print(StringBuilder sb) {
+        return expr()._print(sb.append("return ")).append(";");
+    }
+
+  
+    @Override
+    public TypeBot compute() {
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java
new file mode 100644
index 00000000..8d8031bb
--- /dev/null
+++ b/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -0,0 +1,31 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.TypeBot;
+
+/**
+ * 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();
+    }
+
+    @Override
+    public String label() { return "Start"; }
+
+    @Override
+    StringBuilder _print(StringBuilder sb) {
+      return sb.append(label());
+    }
+  
+    @Override
+    public TypeBot compute() {
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java
new file mode 100644
index 00000000..2d7db8d3
--- /dev/null
+++ b/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -0,0 +1,33 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeBot;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class SubNode extends Node {
+    public SubNode(Node lhs, Node rhs) {
+        super(null, lhs, rhs);
+    }
+
+    @Override
+    public String label() { return "Sub"; }
+
+    @Override
+    StringBuilder _print(StringBuilder sb) {
+        in(1)._print(sb.append("("));
+        in(2)._print(sb.append("-"));
+        return sb.append(")");
+    }
+  
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0 &&
+                in(2)._type instanceof TypeInteger i1)
+            return new TypeInteger(i0._con - i1._con);
+        return TypeBot.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+
+}
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java
new file mode 100644
index 00000000..872e453d
--- /dev/null
+++ b/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -0,0 +1,25 @@
+package com.seaofnodes.simple.type;
+
+
+/**
+ * These types are part of a Monotone Analysis Framework,
+ * @see <a href="https://www.cse.psu.edu/~gxt29/teaching/cse597s21/slides/08monotoneFramework.pdf">see for example this set of slides</a>.
+ * <p> 
+ * The types form a lattice; @see <a href="https://en.wikipedia.org/wiki/Lattice_(order)">a symmetric complete bounded (ranked) lattice.</a>
+ * <p>
+ * This wild lattice theory will be needed later to allow us to easily beef up
+ * the analysis and optimization of the Simple compiler... but we don't need it
+ * now, just know that it is coming along in a later Chapter.
+ * <p>g
+ * One of the fun things here is that while the theory is deep and subtle, the
+ * actual implementation is darn near trivial and is generally really obvious
+ * what we're doing with it.  Right now, it's just simple integer math to do
+ * simple constant folding e.g. 1+2 == 3 stuff.
+ */    
+
+public abstract class Type {
+
+    public boolean isConstant() { return false; }
+
+    public abstract StringBuilder _print(StringBuilder sb);
+}
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java
new file mode 100644
index 00000000..5284884a
--- /dev/null
+++ b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java
@@ -0,0 +1,14 @@
+package com.seaofnodes.simple.type;
+
+import java.lang.StringBuilder;
+
+public class TypeBot extends Type {
+
+    public static final TypeBot BOTTOM = new TypeBot();
+  
+    @Override
+    public String toString() { return "Bottom"; }
+  
+    @Override 
+    public StringBuilder _print(StringBuilder sb) { return sb.append(toString()); }
+}
diff --git a/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
new file mode 100644
index 00000000..db3d4c46
--- /dev/null
+++ b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -0,0 +1,34 @@
+package com.seaofnodes.simple.type;
+
+/**
+ * Integer Type
+ */
+public class TypeInteger extends Type {
+
+    /**
+     * The constant value observed for this type
+     */
+    public final long _con;
+
+    public TypeInteger(long con) { _con = con; }
+
+    @Override
+    public String toString() {
+      return _print(new StringBuilder()).toString();
+    }
+
+    @Override 
+    public StringBuilder _print(StringBuilder sb) { return sb.append(_con); }
+
+    @Override
+    public boolean isConstant() { return true; }
+
+    public long getConstant() { return _con; }
+
+    @Override
+    public boolean equals( Object o ) {
+        if( o==this ) return true;
+        if( !(o instanceof TypeInteger i) ) return false;
+        return _con==i._con;
+    }
+}
diff --git a/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java
new file mode 100644
index 00000000..5af07ec3
--- /dev/null
+++ b/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java
@@ -0,0 +1,171 @@
+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;
+import com.seaofnodes.simple.type.TypeInteger;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.rules.ExpectedException;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.fail;
+
+public class Chapter03Test {
+
+    @Rule
+    public ExpectedException exceptionRule = ExpectedException.none();
+
+    @Test
+    public void testVarDecl() {
+        Parser parser = new Parser("int a=1; return a;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 1;", ret.print());
+    }
+
+    @Test
+    public void testVarAdd() {
+        Parser parser = new Parser("int a=1; int b=2; return a+b;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 3;", ret.print());
+    }
+
+    @Test
+    public void testVarScope() {
+        Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 4;", ret.print());
+    }
+
+    @Test
+    public void testVarScopeNoPeephole() {
+        Node._disablePeephole = true;
+        Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;");
+        ReturnNode ret = parser.parse();
+        Node._disablePeephole = false;
+        assertEquals("return (1+3);", ret.print());
+    }
+
+    @Test
+    public void testVarDist() {
+        Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 8;", ret.print());
+    }
+
+
+    @Test
+    public void testChapter2ParseGrammar() {
+        Node._disablePeephole = true; // disable peephole so we can observe full graph
+        Parser parser = new Parser("return 1+2*3+-5;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return (1+((2*3)+(-5)));", ret.print());
+        GraphVisualizer gv = new GraphVisualizer();
+        System.out.println(gv.generateDotOutput(parser));
+        Node._disablePeephole = false;
+    }
+
+    @Test
+    public void testChapter2AddPeephole() {
+        Parser parser = new Parser("return 1+2;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 3;", ret.print());
+    }
+
+    @Test
+    public void testChapter2SubPeephole() {
+        Parser parser = new Parser("return 1-2;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return -1;", ret.print());
+    }
+
+    @Test
+    public void testChapter2MulPeephole() {
+        Parser parser = new Parser("return 2*3;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 6;", ret.print());
+    }
+
+    @Test
+    public void testChapter2DivPeephole() {
+        Parser parser = new Parser("return 6/3;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 2;", ret.print());
+    }
+
+    @Test
+    public void testChapter2MinusPeephole() {
+        Parser parser = new Parser("return 6/-3;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return -2;", ret.print());
+    }
+
+    @Test
+    public void testChapter2Example() {
+        Parser parser = new Parser("return 1+2*3+-5;");
+        ReturnNode ret = parser.parse();
+        assertEquals("return 2;", ret.print());
+        GraphVisualizer gv = new GraphVisualizer();
+        System.out.println(gv.generateDotOutput(parser));
+    }
+
+    @Test
+    public void testSimpleProgram() {
+        Parser parser = new Parser("return 1;");
+        ReturnNode ret = parser.parse();
+        StartNode start = Parser.START;
+        
+        assertEquals(start, ret.ctrl());
+        Node expr = ret.expr();
+        if( expr instanceof ConstantNode con ) {
+            assertEquals(start,con.in(0));
+            assertEquals(new TypeInteger(1), con._type);
+        } else {
+            fail();
+        }
+    }
+
+    @Test
+    public void testZero() {
+        Parser parser = new Parser("return 0;");
+        parser.parse();
+        StartNode start = Parser.START;
+        for( Node use : start._outputs )
+            if( use instanceof ConstantNode con )
+                assertEquals(new TypeInteger(0),con._type);
+    }
+
+    @Test
+    public void testBad1() {
+        exceptionRule.expect(RuntimeException.class);
+        exceptionRule.expectMessage("Syntax error, expected =: ");
+        new Parser("ret").parse();
+    }
+
+    @Test
+    public void testBad2() {
+        exceptionRule.expect(RuntimeException.class);
+        exceptionRule.expectMessage("Syntax error: integer values cannot start with '0'");
+        new Parser("return 0123;").parse();
+    }
+
+    @Test
+    public void testNotBad3() {
+        // this test used to fail in chapter 1
+        assertEquals("return 12;", new Parser("return --12;").parse().print());
+    }
+
+    @Test
+    public void testBad4() {
+        exceptionRule.expect(RuntimeException.class);
+        exceptionRule.expectMessage("Syntax error, expected ;:");
+        new Parser("return 100").parse();
+    }
+
+    @Test
+    public void testNotBad5() {
+        // this test used to fail in chapter 1
+        assertEquals("return -100;", new Parser("return -100;").parse().print());
+    }
+}