Merge pull request #3 from dibyendumajumdar/main

Chapter 1 implementation

16 files changed, 687 insertions, 223 deletions

diff --git a/.github/workflows/maven.yml b/.github/workflows/maven.yml
index 48ad1d91..7f25a193 100644
--- a/.github/workflows/maven.yml
+++ b/.github/workflows/maven.yml
@@ -9,10 +9,10 @@ jobs:
 
     steps:
       - uses: actions/checkout@v3
-      - name: Set up JDK 17
+      - name: Set up JDK 20
         uses: actions/setup-java@v3
         with:
-          java-version: '17'
+          java-version: '20'
           distribution: 'temurin'
       - name: Build with Maven
         run: mvn --batch-mode --update-snapshots verify
\ No newline at end of file
diff --git a/.gitignore b/.gitignore
index a8c78987..acbde437 100644
--- a/.gitignore
+++ b/.gitignore
@@ -5,197 +5,10 @@
 # Log file
 *.log
 
-# BlueJ files
-*.ctxt
-
-# Mobile Tools for Java (J2ME)
-.mtj.tmp/
-
-# Package Files #
-*.jar
-*.war
-*.nar
-*.ear
-*.zip
-*.tar.gz
-*.rar
-
-# virtual machine crash logs, see http://www.java.com/en/download/help/error_hotspot.xml
-hs_err_pid*
-replay_pid*
-
-# Gradle stuff
-.gradle
-**/build/
-!src/**/build/
-
-# Ignore Gradle GUI config
-gradle-app.setting
-
-# Avoid ignoring Gradle wrapper jar file (.jar files are usually ignored)
-!gradle-wrapper.jar
-
-# Avoid ignore Gradle wrappper properties
-!gradle-wrapper.properties
-
-# Cache of project
-.gradletasknamecache
-
-
-# Covers JetBrains IDEs: IntelliJ, RubyMine, PhpStorm, AppCode, PyCharm, CLion, Android Studio, WebStorm and Rider
-# Reference: https://intellij-support.jetbrains.com/hc/en-us/articles/206544839
-
-# User-specific stuff
-.idea/**/workspace.xml
-.idea/**/tasks.xml
-.idea/**/usage.statistics.xml
-.idea/**/dictionaries
-.idea/**/shelf
-
-# AWS User-specific
-.idea/**/aws.xml
-
-# Generated files
-.idea/**/contentModel.xml
-
-# Sensitive or high-churn files
-.idea/**/dataSources/
-.idea/**/dataSources.ids
-.idea/**/dataSources.local.xml
-.idea/**/sqlDataSources.xml
-.idea/**/dynamic.xml
-.idea/**/uiDesigner.xml
-.idea/**/dbnavigator.xml
-
-# Gradle
-.idea/**/gradle.xml
-.idea/**/libraries
-
-# Gradle and Maven with auto-import
-# When using Gradle or Maven with auto-import, you should exclude module files,
-# since they will be recreated, and may cause churn.  Uncomment if using
-# auto-import.
-# .idea/artifacts
-# .idea/compiler.xml
-# .idea/jarRepositories.xml
-# .idea/modules.xml
-# .idea/*.iml
-# .idea/modules
-# *.iml
-# *.ipr
-
-# CMake
-cmake-build-*/
-
-# Mongo Explorer plugin
-.idea/**/mongoSettings.xml
-
-# File-based project format
-*.iws
-
-# IntelliJ
-out/
-
-# mpeltonen/sbt-idea plugin
-.idea_modules/
-
-# JIRA plugin
-atlassian-ide-plugin.xml
-
-# Cursive Clojure plugin
-.idea/replstate.xml
-
-# SonarLint plugin
-.idea/sonarlint/
-
-# Crashlytics plugin (for Android Studio and IntelliJ)
-com_crashlytics_export_strings.xml
-crashlytics.properties
-crashlytics-build.properties
-fabric.properties
-
-# Editor-based Rest Client
-.idea/httpRequests
-
-# Android studio 3.1+ serialized cache file
-.idea/caches/build_file_checksums.ser
-
-
+# Idea
+.idea/
 target/
-pom.xml.tag
-pom.xml.releaseBackup
-pom.xml.versionsBackup
-pom.xml.next
-release.properties
-dependency-reduced-pom.xml
-buildNumber.properties
-.mvn/timing.properties
-# https://github.com/takari/maven-wrapper#usage-without-binary-jar
-.mvn/wrapper/maven-wrapper.jar
-
-# Eclipse stuff
-.metadata
-bin/
-tmp/
-*.tmp
-*.bak
-*.swp
-*~.nib
-local.properties
-.settings/
-.loadpath
-.recommenders
-
-# External tool builders
-.externalToolBuilders/
-
-# Locally stored "Eclipse launch configurations"
-*.launch
-
-# PyDev specific (Python IDE for Eclipse)
-*.pydevproject
-
-# CDT-specific (C/C++ Development Tooling)
-.cproject
-
-# CDT- autotools
-.autotools
-
-# Java annotation processor (APT)
-.factorypath
-
-# PDT-specific (PHP Development Tools)
-.buildpath
-
-# sbteclipse plugin
-.target
-
-# Tern plugin
-.tern-project
-
-# TeXlipse plugin
-.texlipse
-
-# STS (Spring Tool Suite)
-.springBeans
-
-# Code Recommenders
-.recommenders/
-
-# Annotation Processing
-.apt_generated/
-.apt_generated_test/
-
-# Scala IDE specific (Scala & Java development for Eclipse)
-.cache-main
-.scala_dependencies
-.worksheet
 
-# Eclipse Gradle plugin generated files
-# Eclipse Core
-.project
-# JDT-specific (Eclipse Java Development Tools)
-.classpath
+# Editors
+.#*
 
-.idea/*
-*.iml
\ No newline at end of file
diff --git a/README.md b/README.md
index 8acd8585..bec41b81 100644
--- a/README.md
+++ b/README.md
@@ -27,7 +27,7 @@ Sea Of Nodes intermediate representation.
 The simple language will be a small subset of C. 
 
 * [Language](language/README.md): Simple language grammar.
-* [Chapter 1](chapter01/README.md): Empty script - i.e. empty function that takes no args and returns nothing, and has empty body.
+* [Chapter 1](chapter01/README.md): Script that returns an integer literal, i.e., an empty function that takes no arguments and returns a single integer value. The `return` statement.
 * Chapter 2: Simple binary arithmetic such as addition, subtraction, multiplication, division with constants. Peephole optimization / simple constant folding.
 * Chapter 3: Graphical Visualization of Sea of Nodes IR.
 * Chapter 4: Local variables, and assignment statements. Read on RHS, SSA, more peephole optimization if local is a constant.
@@ -35,7 +35,7 @@ The simple language will be a small subset of C.
 * Chapter 6: `if` statement.  CFG construction, peephole optimization around dead control flow.
 * Chapter 7: `while` statement. 
 * Chapter 8: Global Value Numbering.
-* Chapter 9: Function calls.
+* Chapter 9: Functions and calls.
 * Chapter 10: Boolean operators `&&`, `||` and `!` including short circuit.
 * Chapter 11: `float` type.
 * Chapter 12: Memory effects: general memory edges in SSA. Peephole optimization around load-after-store/store-after-store.
diff --git a/chapter01/README.md b/chapter01/README.md
index a641c4ad..f3231d8c 100644
--- a/chapter01/README.md
+++ b/chapter01/README.md
@@ -1,5 +1,119 @@
 # Chapter 1
-Simple start and end node for basic empty script.
 
+In this chapter we aim to compile simple scripts such as:
 
-* [Grammar](docs/01-grammar.md)
\ No newline at end of file
+```
+return 1;
+```
+
+We implement the `return` statement.
+The `return` statement accepts an `expression` as an argument.
+The only `expression` type is an integer literal, as shown in the example above. 
+
+Here is the [complete language grammar](docs/01-grammar.md) for this chapter. 
+
+To implement this simple language, we introduce a few key components and data structures.
+
+## Implementation Language
+
+Our implementation language is Java. We chose Java as it is widely available and understood.
+
+## Assumptions
+
+We assume that the reader is familiar with traditional linear intermediate representations, and is familiar with terms such as Basic Block, Control Flow Graph, etc. No attempt is made to explain these topics.
+If necessary the reader can consult a standard compiler text book.
+
+## Architecture
+
+We design our parser and compiler to illustrate some key aspects of the Sea of Nodes
+Intermediate Representation: 
+
+* We construct the intermediate Sea of Nodes representation directly as we parse the language. There is no Abstract Syntax Tree representation.
+
+* The compiler will perform a few basic local optimizations as we build the IR; this is a key benefit of the Sea of Nodes IR. This aspect is more fully explored from Chapter 2 onwards.
+
+## Data Structures
+
+Our data structures are based upon the descriptions provided in following papers:
+
+* [From Quads to Graphs: An Intermediate Representation's Journey](http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR93366-S.pdf)
+* [Combining Analyses, Combining Optimzations](https://scholarship.rice.edu/bitstream/handle/1911/96451/TR95-252.pdf)
+* [A Simple Graph-Based Intermediate Representation](https://www.oracle.com/technetwork/java/javase/tech/c2-ir95-150110.pdf)
+* [Global Code Motion Global Value Numbering](https://courses.cs.washington.edu/courses/cse501/06wi/reading/click-pldi95.pdf)
+
+Following the lead from above, we represent our intermediate representation using an object oriented data model. Details of the
+representation follow.
+
+### Intermediate Representation as a Graph of Nodes
+
+The intermediate representation is a graph of Node objects. The `Node` class is the base type for objects in the IR graph.
+The `Node` class provides common capabilities that are inherited by all subtypes. 
+Each subtype implements semantics relevant to that subtype.
+
+There are two types of Nodes in the representation.
+
+* **Control Nodes** - these represent the control flow subgraph (CFG) of the compiled program
+* **Data Nodes** - these capture the data semantics
+
+The following control and data nodes appear in this chapter.
+
+| Node Name | Type    | Description                                   | Inputs                                                           | Value                                                 |
+|-----------|---------|-----------------------------------------------|------------------------------------------------------------------|-------------------------------------------------------|
+| Start     | Control | Start of function                             | None                                                             | None for now as we do not have function arguments yet |
+| Return    | Control | Represents the termination of a function      | Predecessor control node, Data node value                        | Return value of the function                          |
+| Constant  | Data    | Represents constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant                                 |
+
+All control nodes implement a marker interface named `Control`.
+
+Within a traditional basic block, instructions are executed in sequence. In the Sea of Nodes model, the correct sequence of instructions is determined by a scheduling 
+algorithm that depends only on dependencies between nodes (including control dependencies) that are explicit as edges in the graph. This enables a number of optimizations 
+at very little cost (nearly always small constant time) because all dependencies are always available.
+
+### Unique Node ID
+
+Each node is assigned a unique dense integer Node ID when created. This ID is
+useful for debugging, efficiently computing equality and e.g. as an index into
+a bit vector, which in turn is used to efficiently visit a (possibly cyclic)
+graph.  We discuss Node equality in Chapter 8 Global Value Numbering.
+
+### Start 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.
+
+### Constant 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.
+
+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 _solely_ to allow visitation.
+
+The Constant's value is the value stored in it.
+
+### Return 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.
+
+In this presentation, Return functions as a Stop node, since multiple `return` statements are not possible.
+The Stop node will be introduced in Chapter 6 when we implement `if` statements. 
+
+The Return's output is the value from the data node.
+
+### Representation
+
+Here is visualization of the program:
+
+```
+return 1;
+```
+
+![Sea of Nodes Visual](./docs/02-graph.svg)
+
+* Control nodes appear as square boxes
+* Control edges are in bold red
diff --git a/chapter01/docs/01-grammar.md b/chapter01/docs/01-grammar.md
index 92ed7357..cf947dfc 100644
--- a/chapter01/docs/01-grammar.md
+++ b/chapter01/docs/01-grammar.md
@@ -4,36 +4,22 @@
 grammar SimpleLanguage;
 
 program
-    : declaration* statement+ EOF
-    ;
-
-declaration
-    : type IDENTIFIER ';'
-    ;
-
-type
-    : 'int'
+    : statement EOF
     ;
 
 statement
-    : 'if' '(' expression ')' statement
-    | 'if' '(' expression ')' statement 'else' statement
-    | 'while' '(' expression ')' statement
-    | IDENTIFIER '=' expression ';'
-    | '{' declaration* statement+ '}'
-    | 'break' ';'
+    : 'return' expression ';'
     ;
 
 expression
-    : primaryExpression                                             # PrimaryExpression_
-    | expression ('*' | '/' ) expression                            # ArithmeticOrLogicalExpression
-    | expression ('+' | '-') expression                             # ArithmeticOrLogicalExpression
+    : primaryExpression
     ;
 
 primaryExpression
-    :
-    | INTEGER_LITERAL
-    | IDENTIFIER
-    | '(' expression ')'
+    : INTEGER_LITERAL
     ;
+
+INTEGER_LITERAL
+    : [1-9][0-9]*
+    ;    
 ```
\ No newline at end of file
diff --git a/chapter01/docs/02-graph.gv b/chapter01/docs/02-graph.gv
new file mode 100644
index 00000000..40181544
--- /dev/null
+++ b/chapter01/docs/02-graph.gv
@@ -0,0 +1,9 @@
+digraph chapter01 
+{
+    start [shape=box, label="Start"];
+    constant [label="Constant 1"];
+    return [shape=box, label="Return"];
+    constant -> return;
+    edge [color=red];
+    start -> return [style=bold];
+}
\ No newline at end of file
diff --git a/chapter01/docs/02-graph.svg b/chapter01/docs/02-graph.svg
new file mode 100644
index 00000000..fbf92d7d
--- /dev/null
+++ b/chapter01/docs/02-graph.svg
@@ -0,0 +1,43 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
+ "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 2.43.0 (0)
+ -->
+<!-- Title: chapter01 Pages: 1 -->
+<svg width="204pt" height="116pt"
+ viewBox="0.00 0.00 203.74 116.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 112)">
+<title>chapter01</title>
+<polygon fill="white" stroke="transparent" points="-4,4 -4,-112 199.74,-112 199.74,4 -4,4"/>
+<!-- start -->
+<g id="node1" class="node">
+<title>start</title>
+<polygon fill="none" stroke="black" points="54,-108 0,-108 0,-72 54,-72 54,-108"/>
+<text text-anchor="middle" x="27" y="-86.3" font-family="Times,serif" font-size="14.00">Start</text>
+</g>
+<!-- return -->
+<g id="node3" class="node">
+<title>return</title>
+<polygon fill="none" stroke="black" points="113,-36 47,-36 47,0 113,0 113,-36"/>
+<text text-anchor="middle" x="80" y="-14.3" font-family="Times,serif" font-size="14.00">Return</text>
+</g>
+<!-- start&#45;&gt;return -->
+<g id="edge2" class="edge">
+<title>start&#45;&gt;return</title>
+<path fill="none" stroke="red" stroke-width="2" d="M40.1,-71.7C46.39,-63.39 54.05,-53.28 60.96,-44.14"/>
+<polygon fill="red" stroke="red" stroke-width="2" points="63.8,-46.19 67.05,-36.1 58.22,-41.96 63.8,-46.19"/>
+</g>
+<!-- constant -->
+<g id="node2" class="node">
+<title>constant</title>
+<ellipse fill="none" stroke="black" cx="134" cy="-90" rx="61.99" ry="18"/>
+<text text-anchor="middle" x="134" y="-86.3" font-family="Times,serif" font-size="14.00">Constant 1</text>
+</g>
+<!-- constant&#45;&gt;return -->
+<g id="edge1" class="edge">
+<title>constant&#45;&gt;return</title>
+<path fill="none" stroke="black" d="M120.93,-72.05C114.52,-63.75 106.68,-53.58 99.58,-44.38"/>
+<polygon fill="black" stroke="black" points="102.21,-42.06 93.33,-36.28 96.66,-46.33 102.21,-42.06"/>
+</g>
+</g>
+</svg>
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();
+    }
+}
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..887f63b8
--- /dev/null
+++ b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java
@@ -0,0 +1,72 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+public class ParserTest {
+
+    @Test
+    public void testSimpleProgram() {
+        Parser parser = new Parser();
+        StartNode startNode = parser.parse("return 1;");
+        assertNotNull(startNode);
+        assertEquals(2, startNode.nOuts());
+        for (int i = 0; i < startNode.nOuts(); i++) {
+            switch( startNode.out(i) ) {
+            case ReturnNode ret:
+                assertEquals(2, ret.nIns());
+                assertEquals(startNode, ret.in(0));
+                assertTrue(ret.in(1) instanceof ConstantNode);
+                break;
+            case ConstantNode con:
+                assertEquals(1, con._value);
+                assertEquals(1, con.nIns());
+                assertEquals(startNode, con.in(0));
+                break;
+            default:
+                throw new IllegalStateException();
+            }
+        }
+    }
+
+    @Test
+    public void testZero() {
+        Parser parser = new Parser();
+        StartNode start = parser.parse("return 0;");
+        for( Node use : start._outputs )
+            if( use instanceof ConstantNode con )
+                assertEquals(0,con._value);
+    }
+
+    @Test
+    public void testBad1() {
+        try { new Parser().parse("ret"); }
+        catch( RuntimeException e ) { assertEquals("syntax error, expected return: ret",e.getMessage()); }
+    }
+
+    @Test
+    public void testBad2() {
+        try { new Parser().parse("return 0123;"); }
+        catch( RuntimeException e ) { assertEquals("syntax error: integer values cannot start with '0'",e.getMessage()); }
+    }
+
+    @Test
+    public void testBad3() {
+        try { new Parser().parse("return --12;"); }
+        catch( RuntimeException e ) { assertEquals("syntax error, expected integer literal: --",e.getMessage()); }
+    }
+
+    @Test
+    public void testBad4() {
+        try { new Parser().parse("return 100"); }
+        catch( RuntimeException e ) { assertTrue(e.getMessage().contains("syntax error, expected ; got :")); }
+    }
+
+    // Negative numbers require unary operator support that is not in scope
+    @Test
+    public void testBad5() {
+        try { new Parser().parse("return -100;"); }
+        catch( RuntimeException e ) { assertEquals("syntax error, expected integer literal: -", e.getMessage()); }
+    }
+}
diff --git a/language/pom.xml b/language/pom.xml
index 7d748aa1..9073598f 100644
--- a/language/pom.xml
+++ b/language/pom.xml
@@ -11,8 +11,8 @@
 	<name>SeaOfNodes Demo Simple Language Grammar</name>
 	<properties>
 		<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
-		<maven.compiler.target>17</maven.compiler.target>
-		<maven.compiler.source>17</maven.compiler.source>
+		<maven.compiler.target>20</maven.compiler.target>
+		<maven.compiler.source>20</maven.compiler.source>
 		<antlr4test-maven-plugin.version>1.22</antlr4test-maven-plugin.version>
 		<antlr.version>4.11.1</antlr.version>
 		<antlr4test-maven-plugin.version>1.21</antlr4test-maven-plugin.version>
diff --git a/pom.xml b/pom.xml
index 9f9601d9..7b0f25e4 100644
--- a/pom.xml
+++ b/pom.xml
@@ -24,8 +24,8 @@
     </modules>
 
     <properties>
-        <maven.compiler.source>17</maven.compiler.source>
-        <maven.compiler.target>17</maven.compiler.target>
+        <maven.compiler.source>20</maven.compiler.source>
+        <maven.compiler.target>20</maven.compiler.target>
         <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
         <junit.version>4.13.2</junit.version>
     </properties>
@@ -44,6 +44,17 @@
                 <groupId>org.apache.maven.plugins</groupId>
                 <artifactId>maven-surefire-plugin</artifactId>
                 <version>3.1.2</version>
+                <configuration>
+                    <argLine>--enable-preview</argLine>
+                </configuration>
+            </plugin>
+            <plugin>
+                <artifactId>maven-compiler-plugin</artifactId>
+                <version>3.10.1</version>
+                <configuration>
+                    <release>20</release>
+                    <compilerArgs>--enable-preview</compilerArgs>
+                </configuration>
             </plugin>
         </plugins>
     </build>