From 8b8cdf8873b30fd21f9012a479a42809c079eb42 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 14:06:27 +0100 Subject: Revise grammar for chapter 1. Start writing up Chapter 1. --- chapter01/README.md | 44 ++++++++++++++++++++++++++++++++++++++++++-- chapter01/docs/01-grammar.md | 30 ++++++++---------------------- 2 files changed, 50 insertions(+), 24 deletions(-) (limited to 'chapter01') diff --git a/chapter01/README.md b/chapter01/README.md index a641c4ad..b6a3d823 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -1,5 +1,45 @@ # Chapter 1 -Simple start and end node for basic empty script. +In this chapter we aim to compile simple scripts such as: + +``` +return 1; +``` + +The first statement to be implemented in the language is the `return` statement. +The `return` statement shall accept an argument, which must be an `expression`. +For this chapter, the language shall only have one type of `expression` - an integer literal, as +shown in the example above. + +Here is the [complete grammar](docs/01-grammar.md) of the language for this chapter. + +To implement this simple language, we will need to introduce several components and data +structures. + +## Implementation Language + +Our implementation language is Java. We chose Java as it is widely available and understood. + +## Architecture + +We will design our parser and compiler to illustrate some key aspects of the Sea of Nodes +Intermediate Representation: + +* We will construct the intermediate representation directly as we +parse the language. There will not be an intermediate 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. + +## Data Structures + +Our data structures will be 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 will represent our intermediate representation using an object oriented data model. Details of the +representation follow. -* [Grammar](docs/01-grammar.md) \ No newline at end of file diff --git a/chapter01/docs/01-grammar.md b/chapter01/docs/01-grammar.md index 92ed7357..63816e2e 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 + : [0-9]+ + ; ``` \ No newline at end of file -- cgit v1.2.3 From adb2ae48c7e92e3a9024b043e476162a11ef9641 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 15:59:44 +0100 Subject: Initial definition of nodes that will be relevant for chapter 1. --- chapter01/README.md | 25 ++++++ .../com/seaofnodes/simple/node/ConstantNode.java | 16 ++++ .../java/com/seaofnodes/simple/node/Control.java | 9 +++ .../main/java/com/seaofnodes/simple/node/Node.java | 94 ++++++++++++++++++++++ .../seaofnodes/simple/node/NodeIDGenerator.java | 19 +++++ .../com/seaofnodes/simple/node/RegionNode.java | 11 +++ .../com/seaofnodes/simple/node/ReturnNode.java | 11 +++ .../java/com/seaofnodes/simple/node/StartNode.java | 11 +++ 8 files changed, 196 insertions(+) create mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java create mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/Control.java create mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/Node.java create mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java create mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/RegionNode.java create mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java create mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java (limited to 'chapter01') diff --git a/chapter01/README.md b/chapter01/README.md index b6a3d823..bb15e828 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -43,3 +43,28 @@ Our data structures will be based upon the descriptions provided in following pa Following the lead from above, we will 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 will be created 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 | +| Region | Control | Represent a Basic Block | Predecessor control nodes in the CFG | Each region represents one value | +| Return | Control | Represents the termination of a function | Predecessor control node, Data value node | Return value of the function | +| Constant | Data | Represents constants such as integer literals | None | Value of the constant | + +All control nodes will 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 instruction within a +region will be determined by a scheduling algorithm, to be discussed in later chapters. + 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..7f798301 --- /dev/null +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -0,0 +1,16 @@ +package com.seaofnodes.simple.node; + +public class ConstantNode extends Node { + + long _value; + + public ConstantNode(int nid, long value) { + super(nid, OP_CONSTANT); + _value = value; + } + + public ConstantNode(NodeIDGenerator idGenerator, long value) { + super(idGenerator, OP_CONSTANT); + _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..0c6cdd3f --- /dev/null +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java @@ -0,0 +1,94 @@ +package com.seaofnodes.simple.node; + +import java.util.Arrays; +import java.util.List; + +/** + * 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 class Node { + + static final byte OP_START = 1; + static final byte OP_REGION = 2; + static final byte OP_RETURN = 3; + static final byte OP_CONSTANT = 4; + + /** + * The opcode for this node + */ + public final byte _opCode; + + /** + * Each node has a unique ID within a compilation context + */ + public final int _nid; + + /** + * Inputs to the node. + * + * Generally fixed length, ordered, nulls allowed, no unused trailing space. + * The first input (offset 0) must be a Control node. + * @see Control + */ + public final List _inputs; + + protected Node(int nid, byte opCode, Node ...inputs) + { + _nid = nid; + _opCode = opCode; + _inputs = Arrays.asList(inputs); + } + + protected Node(NodeIDGenerator idGenerator, byte opCode, Node ...inputs) + { + _nid = idGenerator.newNodeID(); + _opCode = opCode; + _inputs = Arrays.asList(inputs); + } + + /** + * Gets the ith input node + * @param i Offset of the input node + * @return Input node or null + */ + public Node in(int i) { return _inputs != null ? _inputs.get(i) : null; } + + public int numInputs() { return _inputs != null ? _inputs.size() : 0; } + + /** + * Is this a control node, all control nodes are marked with + * the interface Control. + */ + public boolean isControl() { return this instanceof Control; } + + /** + * Hash is function of this nodes type, its _nid and + * inputs, or opcode + input_nids + */ + @Override + public int hashCode() { + int sum = _opCode; + for (int i = 0; i < numInputs(); i++) + if (in(i) != null) + sum ^= in(i)._nid; + return sum; + } + + /** + * Equals is opcode + input nids. + * Note that nodes are compared by reference. + */ + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (!(o instanceof Node n)) return false; + if (_opCode != n._opCode) return false; + if (numInputs() != n.numInputs()) return false; + for (int i = 0; i < numInputs(); i++) + if (in(i) != n.in(i)) + return false; + return true; + } +} diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java b/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java new file mode 100644 index 00000000..96a292df --- /dev/null +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java @@ -0,0 +1,19 @@ +package com.seaofnodes.simple.node; + +/** + * Nodes are given unique dense ids. + */ +public class NodeIDGenerator { + /** + * Counter for node IDs, do not hand out NID 0 + * (Presumably) because it is used for the control node? + */ + private int nodeIDCounter = 1; + + public int newNodeID() { + if (nodeIDCounter > 100000) { + throw new RuntimeException("infinite node create loop"); + } + return nodeIDCounter++; + } +} diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/RegionNode.java new file mode 100644 index 00000000..b740deff --- /dev/null +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -0,0 +1,11 @@ +package com.seaofnodes.simple.node; + +public class RegionNode extends Node implements Control { + public RegionNode(int nid, Node... inputs) { + super(nid, OP_REGION, inputs); + } + + public RegionNode(NodeIDGenerator idGenerator, Node... inputs) { + super(idGenerator, OP_REGION, inputs); + } +} diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java new file mode 100644 index 00000000..655fd11f --- /dev/null +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -0,0 +1,11 @@ +package com.seaofnodes.simple.node; + +public class ReturnNode extends Node implements Control { + public ReturnNode(int nid, Node... inputs) { + super(nid, OP_RETURN, inputs); + } + + public ReturnNode(NodeIDGenerator idGenerator, Node... inputs) { + super(idGenerator, OP_RETURN, inputs); + } +} diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java new file mode 100644 index 00000000..8117c4f6 --- /dev/null +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -0,0 +1,11 @@ +package com.seaofnodes.simple.node; + +public class StartNode extends Node implements Control { + public StartNode(int nid, Node... inputs) { + super(nid, OP_START, inputs); + } + + public StartNode(NodeIDGenerator idGenerator, Node... inputs) { + super(idGenerator, OP_START, inputs); + } +} -- cgit v1.2.3 From d4e6ddb5084c0ef295adad6172e10c664a275260 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 16:09:37 +0100 Subject: Initial definition of nodes that will be relevant for chapter 1. --- chapter01/README.md | 35 +++++++++++++++++++++++++++++------ 1 file changed, 29 insertions(+), 6 deletions(-) (limited to 'chapter01') diff --git a/chapter01/README.md b/chapter01/README.md index bb15e828..0dee71be 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -56,15 +56,38 @@ There are two types of Nodes in the representation. The following control and data nodes will be created 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 | -| Region | Control | Represent a Basic Block | Predecessor control nodes in the CFG | Each region represents one value | -| Return | Control | Represents the termination of a function | Predecessor control node, Data value node | Return value of the function | -| Constant | Data | Represents constants such as integer literals | None | Value of the constant | +| Node Name | Type | Description | Inputs | Value | +|-----------|---------|-----------------------------------------------|-------------------------------------------|-------------------------------------------------------| +| Start | Control | Start of function | None | None for now as we do not have function arguments yet | +| Region | Control | Represent a Basic Block | Predecessor control nodes in the CFG | Each region represents one value | +| 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 | Value of the constant | All control nodes will 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 instruction within a region will be determined by a scheduling algorithm, to be discussed in later chapters. +### Unique Node ID + +Each node will be assigned a unique Node ID upon creation. The Node ID will be allocated in a particular compilation context. + +### Node Comparisons + +Nodes will by default be compared such that two nodes are equal if they have the same class type, and if all input nodes have the same Node ID. + +### Start Node + +TODO + +### Region Node + +TODO + +### Return Node + +TODO + +### Constant Node + +TODO \ No newline at end of file -- cgit v1.2.3 From 00af1bb88668791e9da5d43c921e38348beec421 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 17:13:01 +0100 Subject: Revised based on feedback Added descriptions of the nodes. --- chapter01/README.md | 31 +++++++++++++++++-------------- chapter01/docs/01-grammar.md | 2 +- 2 files changed, 18 insertions(+), 15 deletions(-) (limited to 'chapter01') diff --git a/chapter01/README.md b/chapter01/README.md index 0dee71be..62fafcd0 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -6,14 +6,14 @@ In this chapter we aim to compile simple scripts such as: return 1; ``` -The first statement to be implemented in the language is the `return` statement. -The `return` statement shall accept an argument, which must be an `expression`. -For this chapter, the language shall only have one type of `expression` - an integer literal, as +We will be implementing the `return` statement first. +The `return` statement accepts an `expression` as an argument. +For this chapter, the language only has one type of `expression` - an integer literal, as shown in the example above. Here is the [complete grammar](docs/01-grammar.md) of the language for this chapter. -To implement this simple language, we will need to introduce several components and data +To implement this simple language, we will introduce several components and data structures. ## Implementation Language @@ -59,14 +59,14 @@ The following control and data nodes will be created 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 | -| Region | Control | Represent a Basic Block | Predecessor control nodes in the CFG | Each region represents one value | | 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 | Value of the constant | All control nodes will 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 instruction within a -region will be determined by a scheduling algorithm, to be discussed in later chapters. +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 @@ -78,16 +78,19 @@ Nodes will by default be compared such that two nodes are equal if they have the ### Start Node -TODO +The Start node represents the start of the function. For now, we do not have any values in the Start node, because in this chapter our function does not +accept any parameters. When we add parameters, the value of the Start node will be a tuple, and will require Projection nodes to extract the values. However, +this will be subject of a later chapter. -### Region Node +### Constant Node -TODO +The Constant node represents the constant value. At present the only constants we allow are integer literals, hence the Constant node contains +an integer value. As we add other types of constants, we will need to refactor how we represent Constant nodes. -### Return Node +The Constant node has no inputs. Its output is the value stored in it. -TODO +### Return Node -### Constant Node +The Return node has two inputs. The first input is a control node. The second input is the data node that will supply the return value. -TODO \ No newline at end of file +The output of the Return node is the value it obtained from the data node. diff --git a/chapter01/docs/01-grammar.md b/chapter01/docs/01-grammar.md index 63816e2e..7c5cb57a 100644 --- a/chapter01/docs/01-grammar.md +++ b/chapter01/docs/01-grammar.md @@ -20,6 +20,6 @@ primaryExpression ; INTEGER_LITERAL - : [0-9]+ + : [1-9][0-0]* ; ``` \ No newline at end of file -- cgit v1.2.3 From e1ca5e63053d5d67fb77b35c773bb81ac502a58c Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 17:21:39 +0100 Subject: Fix typos --- chapter01/README.md | 2 +- chapter01/docs/01-grammar.md | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) (limited to 'chapter01') diff --git a/chapter01/README.md b/chapter01/README.md index 62fafcd0..1d83c226 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -74,7 +74,7 @@ Each node will be assigned a unique Node ID upon creation. The Node ID will be a ### Node Comparisons -Nodes will by default be compared such that two nodes are equal if they have the same class type, and if all input nodes have the same Node ID. +Nodes will by default be compared such that two nodes are equal if they have the same class type, and all input nodes have the same Node ID. ### Start Node diff --git a/chapter01/docs/01-grammar.md b/chapter01/docs/01-grammar.md index 7c5cb57a..cf947dfc 100644 --- a/chapter01/docs/01-grammar.md +++ b/chapter01/docs/01-grammar.md @@ -20,6 +20,6 @@ primaryExpression ; INTEGER_LITERAL - : [1-9][0-0]* + : [1-9][0-9]* ; ``` \ No newline at end of file -- cgit v1.2.3 From e839f9b639e85d0383d3227f78118f55193518b3 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 17:26:08 +0100 Subject: Revised text --- chapter01/README.md | 11 +++++------ 1 file changed, 5 insertions(+), 6 deletions(-) (limited to 'chapter01') diff --git a/chapter01/README.md b/chapter01/README.md index 1d83c226..6b2aebd1 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -6,10 +6,9 @@ In this chapter we aim to compile simple scripts such as: return 1; ``` -We will be implementing the `return` statement first. +We will implement the `return` statement first. The `return` statement accepts an `expression` as an argument. -For this chapter, the language only has one type of `expression` - an integer literal, as -shown in the example above. +For this chapter, the only `expression` type is an integer literal, as shown in the example above. Here is the [complete grammar](docs/01-grammar.md) of the language for this chapter. @@ -78,13 +77,13 @@ Nodes will by default be compared such that two nodes are equal if they have the ### Start Node -The Start node represents the start of the function. For now, we do not have any values in the Start node, because in this chapter our function does not -accept any parameters. When we add parameters, the value of the Start node will be a tuple, and will require Projection nodes to extract the values. However, +The Start node represents the start of the function. For now, we do not have any values in the Start node, this is because our function does not +yet accept parameters. When we add parameters, the value of the Start node will be a tuple, and will require Projection nodes to extract the values. However, this will be subject of a later chapter. ### Constant Node -The Constant node represents the constant value. At present the only constants we allow are integer literals, hence the Constant node contains +The Constant node represents the constant value. At present, the only constants we allow are integer literals; therefore the Constant node contains an integer value. As we add other types of constants, we will need to refactor how we represent Constant nodes. The Constant node has no inputs. Its output is the value stored in it. -- cgit v1.2.3 From ab6746dddee6175a68df2b34c147751e267324da Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 19:21:12 +0100 Subject: Add diagram --- chapter01/docs/02-graph.gv | 29 ++++++++++++++++++++++++++ chapter01/docs/02-graph.svg | 51 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 80 insertions(+) create mode 100644 chapter01/docs/02-graph.gv create mode 100644 chapter01/docs/02-graph.svg (limited to 'chapter01') diff --git a/chapter01/docs/02-graph.gv b/chapter01/docs/02-graph.gv new file mode 100644 index 00000000..a47c23fe --- /dev/null +++ b/chapter01/docs/02-graph.gv @@ -0,0 +1,29 @@ +digraph chapter01 +{ + start [shape=none, label=< + + + + + + + +
Inputs
Start
+ >]; + constant [label="Constant 1"]; + return [shape=none, label=< + + + + + + + + + +
Inputs01
Return
+ >]; + constant -> return:input1; + edge [color=red]; + start -> return:input0 [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..1ced4870 --- /dev/null +++ b/chapter01/docs/02-graph.svg @@ -0,0 +1,51 @@ + + + + + + +chapter01 + + + +start + +Inputs + +Start + + + +return + +Inputs + +0 + +1 + +Return + + + +start->return:input0 + + + + + +constant + +Constant 1 + + + +constant->return:input1 + + + + + -- cgit v1.2.3 From 149c78c4921d5a653e3ff83ec3b1d02a90d0a42c Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 19:27:47 +0100 Subject: Add diagram --- chapter01/README.md | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'chapter01') diff --git a/chapter01/README.md b/chapter01/README.md index 6b2aebd1..4bd0c798 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -93,3 +93,13 @@ The Constant node has no inputs. Its output is the value stored in it. The Return node has two inputs. The first input is a control node. The second input is the data node that will supply the return value. The output of the Return node is the value it obtained from the data node. + +### Representation + +Here is visualization of the program: + +``` +return 1; +``` + +![Sea of Nodes Visual](./docs/02-graph.svg) -- cgit v1.2.3 From 7ec5a9425c7585a67dc834cfb762470e86695b41 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 20:53:53 +0100 Subject: Revise text and update diagram. Remove the detail re inputs to a node from the diagram. --- chapter01/README.md | 64 +++++++++++++++++++++++++-------------------- chapter01/docs/02-graph.gv | 28 +++----------------- chapter01/docs/02-graph.svg | 40 ++++++++++++---------------- 3 files changed, 55 insertions(+), 77 deletions(-) (limited to 'chapter01') diff --git a/chapter01/README.md b/chapter01/README.md index 4bd0c798..679a5d5e 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -6,40 +6,42 @@ In this chapter we aim to compile simple scripts such as: return 1; ``` -We will implement the `return` statement first. +We implement the `return` statement. The `return` statement accepts an `expression` as an argument. -For this chapter, the only `expression` type is an integer literal, as shown in the example above. +The only `expression` type is an integer literal, as shown in the example above. -Here is the [complete grammar](docs/01-grammar.md) of the language for this chapter. +Here is the [complete language grammar](docs/01-grammar.md) for this chapter. -To implement this simple language, we will introduce several components and data -structures. +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 will design our parser and compiler to illustrate some key aspects of the Sea of Nodes +We design our parser and compiler to illustrate some key aspects of the Sea of Nodes Intermediate Representation: -* We will construct the intermediate representation directly as we -parse the language. There will not be an intermediate Abstract Syntax Tree 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. +* 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 will be based upon the descriptions provided in following papers: +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 will represent our intermediate representation using an object oriented data model. Details of the +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 @@ -53,15 +55,15 @@ 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 will be created in this chapter. +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 | Value of the constant | +| 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 will implement a marker interface named `Control`. +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 @@ -69,28 +71,29 @@ at very little cost (nearly always small constant time) because all dependencies ### Unique Node ID -Each node will be assigned a unique Node ID upon creation. The Node ID will be allocated in a particular compilation context. - -### Node Comparisons - -Nodes will by default be compared such that two nodes are equal if they have the same class type, and all input nodes have the same Node ID. +Each node is assigned a unique dense integer Node ID when created. This ID is useful for debugging and e.g. as +an index into a bit vector, which in turn is used to efficiently visit a (possibly cyclic) graph. +The ID is also used to efficiently compute equality of nodes; a subject that we discuss in Chapter 8 Global Value Numbering. ### Start Node The Start node represents the start of the function. For now, we do not have any values in the Start node, this is because our function does not -yet accept parameters. When we add parameters, the value of the Start node will be a tuple, and will require Projection nodes to extract the values. However, -this will be subject of a later chapter. +yet accept parameters. When we add parameters, the value of the Start node will be a tuple, and will require Projection nodes to extract the values. +We discuss this in detail in Chapter 9: Functions and Calls. ### Constant Node -The Constant node represents the constant value. At present, the only constants we allow are integer literals; therefore the Constant node contains +The Constant node represents a constant value. At present, the only constants that we allow are integer literals; therefore the Constant node contains an integer value. As we add other types of constants, we will need to refactor how we represent Constant nodes. -The Constant node has no inputs. Its output is the value stored in it. +The Constant node has no inputs. However, we set the Start node as an input to the Constant node to enable forward graph walk. This edge carries no semantic meaning, +it is present _solely_ to allow visitation. + +The Constant node's output is the value stored in it. ### Return Node -The Return node has two inputs. The first input is a control node. The second input is the data node that will supply the return value. +The Return node has two inputs. The first input is a control node. The second input is the data node that supplies the return value. The output of the Return node is the value it obtained from the data node. @@ -103,3 +106,6 @@ return 1; ``` ![Sea of Nodes Visual](./docs/02-graph.svg) + +* Control nodes appear as square boxes +* Control edges are in bold red \ No newline at end of file diff --git a/chapter01/docs/02-graph.gv b/chapter01/docs/02-graph.gv index a47c23fe..40181544 100644 --- a/chapter01/docs/02-graph.gv +++ b/chapter01/docs/02-graph.gv @@ -1,29 +1,9 @@ digraph chapter01 { - start [shape=none, label=< - - - - - - - -
Inputs
Start
- >]; + start [shape=box, label="Start"]; constant [label="Constant 1"]; - return [shape=none, label=< - - - - - - - - - -
Inputs01
Return
- >]; - constant -> return:input1; + return [shape=box, label="Return"]; + constant -> return; edge [color=red]; - start -> return:input0 [style=bold]; + start -> return [style=bold]; } \ No newline at end of file diff --git a/chapter01/docs/02-graph.svg b/chapter01/docs/02-graph.svg index 1ced4870..fbf92d7d 100644 --- a/chapter01/docs/02-graph.svg +++ b/chapter01/docs/02-graph.svg @@ -4,48 +4,40 @@ - - + + chapter01 - + start - -Inputs - -Start + +Start return - -Inputs - -0 - -1 - -Return + +Return -start->return:input0 - - +start->return + + constant - -Constant 1 + +Constant 1 -constant->return:input1 - - +constant->return + + -- cgit v1.2.3 From a62c095bd2451a6c7341bcddd32c0073b9c78ac7 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 21:05:19 +0100 Subject: Revise description of Return node. --- chapter01/README.md | 3 +++ 1 file changed, 3 insertions(+) (limited to 'chapter01') diff --git a/chapter01/README.md b/chapter01/README.md index 679a5d5e..e5b79493 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -95,6 +95,9 @@ The Constant node's output is the value stored in it. The Return node has two inputs. The first input is a control node. The second input is the data node that supplies the return value. +In this presentation, the Return node functions as the Stop node, since we are compiling a single unnamed function. +A separate Stop node is not necessary. Compiling multiple functions is covered in Chapter 9: Functions and Calls. + The output of the Return node is the value it obtained from the data node. ### Representation -- cgit v1.2.3 From 5166e178bda699d574bd9dfbd1718e86bc9c95f9 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 22:46:22 +0100 Subject: Start on parser --- .../main/java/com/seaofnodes/simple/Parser.java | 254 +++++++++++++++++++++ .../com/seaofnodes/simple/node/ConstantNode.java | 9 +- .../main/java/com/seaofnodes/simple/node/Node.java | 13 +- .../com/seaofnodes/simple/node/RegionNode.java | 11 - .../com/seaofnodes/simple/node/ReturnNode.java | 3 - .../java/com/seaofnodes/simple/node/StartNode.java | 3 - .../java/com/seaofnodes/simple/ParserTest.java | 15 ++ 7 files changed, 278 insertions(+), 30 deletions(-) create mode 100644 chapter01/src/main/java/com/seaofnodes/simple/Parser.java delete mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/RegionNode.java create mode 100644 chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java (limited to 'chapter01') diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java new file mode 100644 index 00000000..bf9791a8 --- /dev/null +++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java @@ -0,0 +1,254 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; + +import java.text.NumberFormat; +import java.text.ParseException; + +/** + * The Parser converts a Simple source program to the Sea of Nodes intermediate representation + * directly in one pass. There is no intermediate Abstract Syntax Tree structure. The parser also + * does the lexical analysis of the input source. + */ +public class Parser { + + private Token currentToken; + private final NodeIDGenerator _idGenerator; + private StartNode _startNode; + + public Parser() { + _idGenerator = new NodeIDGenerator(); + } + + public Node parse(String source) { + Lexer lexer = new Lexer(source); + _startNode = new StartNode(_idGenerator, new Node[0]); + nextToken(lexer); + return parseProgram(lexer); + } + + private Node parseProgram(Lexer lexer) { + parseReturnStatement(lexer); + return _startNode; + } + + private void nextToken(Lexer lexer) { + currentToken = lexer.next(); + } + + private boolean isToken(Token token, String value) { + return token._str.equals(value); + } + + private void error(Token t, String errorMessage) { + throw new RuntimeException(errorMessage + ": " + t.toString()); + } + + private void matchPunctuation(Lexer lexer, String value) { + if (currentToken._kind == Token.Kind.PUNCT && isToken(currentToken, value)) { + nextToken(lexer); + } else { + error(currentToken, "syntax error, expected " + value + " got " + currentToken._str); + } + } + + private void matchIdentifier(Lexer lexer, String identifier) { + if (currentToken._kind == Token.Kind.IDENT && isToken(currentToken, identifier)) { + nextToken(lexer); + } else { + error(currentToken, "syntax error, expected " + identifier); + } + } + + private Node parsePrimary(Lexer lexer) { + switch (currentToken._kind) { + case PUNCT -> { + /* Nested expression */ + return parseNestedExpr(lexer); + } + case NUM -> { + return parseNumberConstant(lexer); + } + default -> { + error(currentToken, "syntax error, expected nested expr or integer literal"); + return null; + } + } + } + + private ConstantNode parseNumberConstant(Lexer lexer) { + var constantNode = new ConstantNode(_idGenerator, currentToken._num.longValue(), _startNode); + nextToken(lexer); + return constantNode; + } + + private Node parseNestedExpr(Lexer lexer) { + matchPunctuation(lexer, "("); + nextToken(lexer); + var node = parsePrimary(lexer); + matchPunctuation(lexer, ")"); + return node; + } + + private Node parseReturnStatement(Lexer lexer) { + matchIdentifier(lexer, "return"); + var returnExpr = parsePrimary(lexer); + matchPunctuation(lexer, ";"); + return new ReturnNode(_idGenerator, _startNode, returnExpr); + } + + static class Token { + + enum Kind { + IDENT, + NUM, + PUNCT, + EOZ // Special kind to signal end of file + } + + public final Kind _kind; + /** + * String representation of a token - always + * populated + */ + public final String _str; + /** + * The parsed number value, only populated for Kind.NUM + */ + public final Number _num; + + public Token(Kind kind, String str, Number num) { + _kind = kind; + _str = str; + _num = num; + } + + public static Token newIdent(String str) { + return new Token(Kind.IDENT, str.intern(), null); + } + public static Token newNum(Number num, String str) { + return new Token(Kind.NUM, str, num); + } + public static Token newPunct(String str) { + return new Token(Kind.PUNCT, str.intern(), null); + } + + /** + * Special token that indicates that source has been exhausted + */ + public static Token EOF = new Token(Kind.EOZ, "", null); + + public String toString() { + return _str; + } + } + + static class Lexer { + + private final char[] _input; + /** + * Tracks current position in input buffer + */ + private int _position = 0; + private char _curCh = ' '; + + private final NumberFormat numberFormat; + + public Lexer(String source) { + _input = source.toCharArray(); + numberFormat = NumberFormat.getInstance(); + numberFormat.setGroupingUsed(false); + } + + private boolean isEOF() { + return _position >= _input.length; + } + + private char advance() { + if (isEOF()) + return 0; // Special value that causes parsing to terminate + return _input[_position++]; + } + + private boolean nextToken() { + _curCh = advance(); + return true; + } + + /** + * Note that EOF is not whitespace! + */ + private boolean isWhiteSpace(char c) { + return c == ' ' || + c == '\t' || + c == '\n' || + c == '\r'; + } + + private void skipWhitespace() { + while (isWhiteSpace(_curCh)) + nextToken(); + } + + /** + * Parses number in format nnn[.nnn] + * where n is a digit + */ + private Token parseNumber() { + assert Character.isDigit(_curCh); + StringBuilder sb = new StringBuilder(); + sb.append(_curCh); + while (nextToken() && Character.isDigit(_curCh)) + sb.append(_curCh); + if (_curCh == '.') { + sb.append(_curCh); + while (nextToken() && Character.isDigit(_curCh)) + sb.append(_curCh); + } + String str = sb.toString(); + Number number = parseNumber(str); + return Token.newNum(number, str); + } + + private Number parseNumber(String str) { + try { + return numberFormat.parse(str); + } catch (ParseException e) { + throw new RuntimeException("Failed to parse number " + str, e); + } + } + + private boolean isIdentifierStart(char ch) { + return Character.isAlphabetic(ch) || ch == '_'; + } + + private boolean isIdentifierLetter(char ch) { + return Character.isLetterOrDigit(ch) || ch == '_'; + } + + private Token parseIdentifier() { + assert isIdentifierStart(_curCh); + StringBuilder sb = new StringBuilder(); + sb.append(_curCh); + while (nextToken() && isIdentifierLetter(_curCh)) + sb.append(_curCh); + return Token.newIdent(sb.toString()); + } + + /** + * Gets the next token + */ + public Token next() { + skipWhitespace(); + if (_curCh == 0) + return Token.EOF; + if (Character.isDigit(_curCh)) + return parseNumber(); + if (isIdentifierLetter(_curCh)) + return parseIdentifier(); + Token token = Token.newPunct(Character.toString(_curCh)); + _curCh = ' '; + return token; + } + } +} diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 7f798301..d2f51cd8 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -4,13 +4,8 @@ public class ConstantNode extends Node { long _value; - public ConstantNode(int nid, long value) { - super(nid, OP_CONSTANT); - _value = value; - } - - public ConstantNode(NodeIDGenerator idGenerator, long value) { - super(idGenerator, OP_CONSTANT); + public ConstantNode(NodeIDGenerator idGenerator, long value, StartNode startNode) { + super(idGenerator, OP_CONSTANT, startNode); _value = value; } } diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java index 0c6cdd3f..c3562b5d 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import java.util.ArrayList; import java.util.Arrays; import java.util.List; @@ -34,18 +35,18 @@ public class Node { */ public final List _inputs; - protected Node(int nid, byte opCode, Node ...inputs) - { - _nid = nid; - _opCode = opCode; - _inputs = Arrays.asList(inputs); - } + public final List _refs = new ArrayList<>(); protected Node(NodeIDGenerator idGenerator, byte opCode, Node ...inputs) { _nid = idGenerator.newNodeID(); _opCode = opCode; _inputs = Arrays.asList(inputs); + for (int i = 0; i < _inputs.size(); i++) { + Node n = _inputs.get(i); + if (n != null) + n._refs.add(this); + } } /** diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/RegionNode.java deleted file mode 100644 index b740deff..00000000 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ /dev/null @@ -1,11 +0,0 @@ -package com.seaofnodes.simple.node; - -public class RegionNode extends Node implements Control { - public RegionNode(int nid, Node... inputs) { - super(nid, OP_REGION, inputs); - } - - public RegionNode(NodeIDGenerator idGenerator, Node... inputs) { - super(idGenerator, OP_REGION, inputs); - } -} diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 655fd11f..9c017eef 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -1,9 +1,6 @@ package com.seaofnodes.simple.node; public class ReturnNode extends Node implements Control { - public ReturnNode(int nid, Node... inputs) { - super(nid, OP_RETURN, inputs); - } public ReturnNode(NodeIDGenerator idGenerator, Node... inputs) { super(idGenerator, OP_RETURN, inputs); diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java index 8117c4f6..4ae7f71a 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -1,9 +1,6 @@ package com.seaofnodes.simple.node; public class StartNode extends Node implements Control { - public StartNode(int nid, Node... inputs) { - super(nid, OP_START, inputs); - } public StartNode(NodeIDGenerator idGenerator, Node... inputs) { super(idGenerator, OP_START, inputs); diff --git a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java new file mode 100644 index 00000000..9f4a9a2e --- /dev/null +++ b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java @@ -0,0 +1,15 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.Node; +import org.junit.Assert; +import org.junit.Test; + +public class ParserTest { + + @Test + public void testSimpleProgram() { + Parser parser = new Parser(); + Node startNode = parser.parse("return 1;"); + Assert.assertNotNull(startNode); + } +} -- cgit v1.2.3 From 1372c413329221aca0837134747d7ba45ac0501b Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Mon, 18 Sep 2023 22:24:12 +0100 Subject: Chapter 01 implementation --- .../main/java/com/seaofnodes/simple/Parser.java | 185 ++++++++++++++------- .../com/seaofnodes/simple/node/ConstantNode.java | 11 +- .../main/java/com/seaofnodes/simple/node/Node.java | 78 ++++----- .../com/seaofnodes/simple/node/ReturnNode.java | 8 + .../java/com/seaofnodes/simple/node/StartNode.java | 5 + .../java/com/seaofnodes/simple/ParserTest.java | 24 ++- 6 files changed, 206 insertions(+), 105 deletions(-) (limited to 'chapter01') diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java index bf9791a8..2feeddf9 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java @@ -7,81 +7,92 @@ import java.text.ParseException; /** * The Parser converts a Simple source program to the Sea of Nodes intermediate representation - * directly in one pass. There is no intermediate Abstract Syntax Tree structure. The parser also - * does the lexical analysis of the input source. + * 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 { - private Token currentToken; + /** + * Current token from lexer + */ + private Token _curTok; + private final NodeIDGenerator _idGenerator; + private StartNode _startNode; public Parser() { _idGenerator = new NodeIDGenerator(); } - public Node parse(String source) { + public StartNode parse(String source) { Lexer lexer = new Lexer(source); - _startNode = new StartNode(_idGenerator, new Node[0]); nextToken(lexer); return parseProgram(lexer); } - private Node parseProgram(Lexer lexer) { + private StartNode parseProgram(Lexer lexer) { + _startNode = new StartNode(_idGenerator); parseReturnStatement(lexer); return _startNode; } - private void nextToken(Lexer lexer) { - currentToken = lexer.next(); - } - - private boolean isToken(Token token, String value) { - return token._str.equals(value); - } - - private void error(Token t, String errorMessage) { - throw new RuntimeException(errorMessage + ": " + t.toString()); - } - - private void matchPunctuation(Lexer lexer, String value) { - if (currentToken._kind == Token.Kind.PUNCT && isToken(currentToken, value)) { - nextToken(lexer); - } else { - error(currentToken, "syntax error, expected " + value + " got " + currentToken._str); - } + /** + * Parses return statement. + * + * 
+     *     return expr ;
+     *
+ */ + private ReturnNode parseReturnStatement(Lexer lexer) { + matchIdentifier(lexer, "return"); + var returnExpr = parseExpression(lexer); + matchPunctuation(lexer, ";"); + return new ReturnNode(_idGenerator, _startNode, returnExpr); } - private void matchIdentifier(Lexer lexer, String identifier) { - if (currentToken._kind == Token.Kind.IDENT && isToken(currentToken, identifier)) { - nextToken(lexer); - } else { - error(currentToken, "syntax error, expected " + identifier); - } + /** + * Parse an expression of the form: + * + * 
+     *     expr : primaryExpr
+     *
+ */ + private Node parseExpression(Lexer lexer) { + return parsePrimary(lexer); } + /** + * Parse a primary expression: + * + * 
+     *     primaryExpr : nestedExpr | integerLiteral
+     *
+ */ private Node parsePrimary(Lexer lexer) { - switch (currentToken._kind) { + switch (_curTok._kind) { case PUNCT -> { /* Nested expression */ return parseNestedExpr(lexer); } case NUM -> { - return parseNumberConstant(lexer); + return parseIntegerLiteral(lexer); } default -> { - error(currentToken, "syntax error, expected nested expr or integer literal"); + error(_curTok, "syntax error, expected nested expr or integer literal"); return null; } } } - private ConstantNode parseNumberConstant(Lexer lexer) { - var constantNode = new ConstantNode(_idGenerator, currentToken._num.longValue(), _startNode); - nextToken(lexer); - return constantNode; - } - + /** + * Parse nested expression: + * + * 
+     *     nestedExpr : ( expr )
+     *
+ */ private Node parseNestedExpr(Lexer lexer) { matchPunctuation(lexer, "("); nextToken(lexer); @@ -90,13 +101,53 @@ public class Parser { return node; } - private Node parseReturnStatement(Lexer lexer) { - matchIdentifier(lexer, "return"); - var returnExpr = parsePrimary(lexer); - matchPunctuation(lexer, ";"); - return new ReturnNode(_idGenerator, _startNode, returnExpr); + /** + * Parse integer literal + * + * 
+     *     integerLiteral: [1-9][0-9]*
+     *
+ */ + private ConstantNode parseIntegerLiteral(Lexer lexer) { + var constantNode = new ConstantNode(_idGenerator, _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 { @@ -145,12 +196,18 @@ public class Parser { static class Lexer { + /** + * Input buffer + */ private final char[] _input; /** * Tracks current position in input buffer */ private int _position = 0; - private char _curCh = ' '; + /** + * Current character + */ + private char _cur = ' '; private final NumberFormat numberFormat; @@ -171,7 +228,7 @@ public class Parser { } private boolean nextToken() { - _curCh = advance(); + _cur = advance(); return true; } @@ -186,7 +243,7 @@ public class Parser { } private void skipWhitespace() { - while (isWhiteSpace(_curCh)) + while (isWhiteSpace(_cur)) nextToken(); } @@ -195,15 +252,15 @@ public class Parser { * where n is a digit */ private Token parseNumber() { - assert Character.isDigit(_curCh); + assert Character.isDigit(_cur); StringBuilder sb = new StringBuilder(); - sb.append(_curCh); - while (nextToken() && Character.isDigit(_curCh)) - sb.append(_curCh); - if (_curCh == '.') { - sb.append(_curCh); - while (nextToken() && Character.isDigit(_curCh)) - sb.append(_curCh); + sb.append(_cur); + while (nextToken() && Character.isDigit(_cur)) + sb.append(_cur); + if (_cur == '.') { + sb.append(_cur); + while (nextToken() && Character.isDigit(_cur)) + sb.append(_cur); } String str = sb.toString(); Number number = parseNumber(str); @@ -227,11 +284,11 @@ public class Parser { } private Token parseIdentifier() { - assert isIdentifierStart(_curCh); + assert isIdentifierStart(_cur); StringBuilder sb = new StringBuilder(); - sb.append(_curCh); - while (nextToken() && isIdentifierLetter(_curCh)) - sb.append(_curCh); + sb.append(_cur); + while (nextToken() && isIdentifierLetter(_cur)) + sb.append(_cur); return Token.newIdent(sb.toString()); } @@ -240,14 +297,14 @@ public class Parser { */ public Token next() { skipWhitespace(); - if (_curCh == 0) + if (_cur == 0) return Token.EOF; - if (Character.isDigit(_curCh)) + if (Character.isDigit(_cur)) return parseNumber(); - if (isIdentifierLetter(_curCh)) + if (isIdentifierLetter(_cur)) return parseIdentifier(); - Token token = Token.newPunct(Character.toString(_curCh)); - _curCh = ' '; + Token token = Token.newPunct(Character.toString(_cur)); + _cur = ' '; return token; } } diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index d2f51cd8..31718a1d 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -1,8 +1,17 @@ package com.seaofnodes.simple.node; +/** + * The Constant node represents a constant value. At present, the only constants that we allow are integer literals; therefore the Constant node contains + * an integer value. As we add other types of constants, we will need to refactor how we represent Constant nodes. + *

+ * The Constant node has no inputs. However, we set the Start node as an input to the Constant node to enable forward graph walk. This edge carries no semantic meaning, + * it is present _solely_ to allow visitation. + *

+ * The Constant node's output is the value stored in it. + */ public class ConstantNode extends Node { - long _value; + public final long _value; public ConstantNode(NodeIDGenerator idGenerator, long value, StartNode startNode) { super(idGenerator, OP_CONSTANT, startNode); diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java index c3562b5d..e78ab19a 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java @@ -11,10 +11,18 @@ import java.util.List; */ public class Node { + /** + * @see StartNode + */ static final byte OP_START = 1; - static final byte OP_REGION = 2; - static final byte OP_RETURN = 3; - static final byte OP_CONSTANT = 4; + /** + * @see ReturnNode + */ + static final byte OP_RETURN = 2; + /** + * @see ConstantNode + */ + static final byte OP_CONSTANT = 3; /** * The opcode for this node @@ -22,30 +30,43 @@ public class Node { public final byte _opCode; /** - * Each node has a unique ID within a compilation context + * 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. - * + * Inputs to the node. These are use-def references to Nodes. + *

* Generally fixed length, ordered, nulls allowed, no unused trailing space. - * The first input (offset 0) must be a Control node. + * The first input (offset 0) must be a Control nodes. * @see Control */ public final List _inputs; - public final List _refs = new ArrayList<>(); + /** + * 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. + *

+ * Note that the outputs are derived from inputs, it appears that + * outputs are therefore a performance optimization to make it easier to + * traverse the graph. The Sea of Nodes documentation in chapter 1 does not + * mention these outputs list. + */ + public final List _outputs; protected Node(NodeIDGenerator idGenerator, byte opCode, Node ...inputs) { - _nid = idGenerator.newNodeID(); + _nid = idGenerator.newNodeID(); // allocate unique dense ID _opCode = opCode; _inputs = Arrays.asList(inputs); + _outputs = new ArrayList<>(); for (int i = 0; i < _inputs.size(); i++) { Node n = _inputs.get(i); if (n != null) - n._refs.add(this); + n._outputs.add(this); } } @@ -54,9 +75,13 @@ public class Node { * @param i Offset of the input node * @return Input node or null */ - public Node in(int i) { return _inputs != null ? _inputs.get(i) : null; } + public Node in(int i) { return _inputs.get(i); } - public int numInputs() { return _inputs != null ? _inputs.size() : 0; } + public int numInputs() { return _inputs.size(); } + + public Node out(int i) { return _outputs.get(i); } + + public int numOutputs() { return _outputs.size(); } /** * Is this a control node, all control nodes are marked with @@ -64,32 +89,7 @@ public class Node { */ public boolean isControl() { return this instanceof Control; } - /** - * Hash is function of this nodes type, its _nid and - * inputs, or opcode + input_nids - */ - @Override - public int hashCode() { - int sum = _opCode; - for (int i = 0; i < numInputs(); i++) - if (in(i) != null) - sum ^= in(i)._nid; - return sum; - } - - /** - * Equals is opcode + input nids. - * Note that nodes are compared by reference. + /* + * hashCode and equals implementation to be added in later chapter. */ - @Override - public boolean equals(Object o) { - if (this == o) return true; - if (!(o instanceof Node n)) return false; - if (_opCode != n._opCode) return false; - if (numInputs() != n.numInputs()) return false; - for (int i = 0; i < numInputs(); i++) - if (in(i) != n.in(i)) - return false; - return true; - } } diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 9c017eef..0b62cd4c 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -1,5 +1,13 @@ package com.seaofnodes.simple.node; +/** + * The Return node has two inputs. The first input is a control node. The second input is the data node that supplies the return value. + *

+ * In this presentation, the Return node functions as the Stop node, since we are compiling a single unnamed function. + * A separate Stop node is not necessary. Compiling multiple functions is covered in Chapter 9: Functions and Calls. + *

+ * The output of the Return node is the value it obtained from the data node. + */ public class ReturnNode extends Node implements Control { public ReturnNode(NodeIDGenerator idGenerator, Node... inputs) { diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java index 4ae7f71a..7a9233a8 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -1,5 +1,10 @@ package com.seaofnodes.simple.node; +/** + * The Start node represents the start of the function. For now, we do not have any values in the Start node, this is because our function does not + * yet accept parameters. When we add parameters, the value of the Start node will be a tuple, and will require Projection nodes to extract the values. + * We discuss this in detail in Chapter 9: Functions and Calls. + */ public class StartNode extends Node implements Control { public StartNode(NodeIDGenerator idGenerator, Node... inputs) { diff --git a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java index 9f4a9a2e..ad420ece 100644 --- a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java +++ b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java @@ -1,6 +1,9 @@ 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 org.junit.Assert; import org.junit.Test; @@ -9,7 +12,26 @@ public class ParserTest { @Test public void testSimpleProgram() { Parser parser = new Parser(); - Node startNode = parser.parse("return 1;"); + StartNode startNode = parser.parse("return 1;"); Assert.assertNotNull(startNode); + Assert.assertTrue(startNode.isControl()); + Assert.assertEquals(2, startNode.numOutputs()); + for (int i = 0; i < startNode.numOutputs(); i++) { + Node out = startNode.out(i); + if (out instanceof ReturnNode) { + Assert.assertEquals(2, out.numInputs()); + Assert.assertEquals(startNode, out.in(0)); + Assert.assertTrue(out.isControl()); + Assert.assertTrue(out.in(1) instanceof ConstantNode); + } + else if (out instanceof ConstantNode cn) { + Assert.assertEquals(1, cn._value); + Assert.assertEquals(1, cn.numInputs()); + Assert.assertEquals(startNode, cn.in(0)); + } + else { + throw new IllegalStateException(); + } + } } } -- cgit v1.2.3 From ab76b39f74776e8a0b09d4add10fcacb6668eb2e Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Mon, 18 Sep 2023 23:39:53 +0100 Subject: Remove opcodes Make the IdGenerator an input to the Parser --- .../main/java/com/seaofnodes/simple/Parser.java | 4 +-- .../com/seaofnodes/simple/node/ConstantNode.java | 2 +- .../main/java/com/seaofnodes/simple/node/Node.java | 36 ++++++++-------------- .../seaofnodes/simple/node/NodeIDGenerator.java | 6 +--- .../com/seaofnodes/simple/node/ReturnNode.java | 2 +- .../java/com/seaofnodes/simple/node/StartNode.java | 2 +- .../java/com/seaofnodes/simple/ParserTest.java | 7 ++--- 7 files changed, 20 insertions(+), 39 deletions(-) (limited to 'chapter01') diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java index 2feeddf9..abaedd05 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java @@ -22,8 +22,8 @@ public class Parser { private StartNode _startNode; - public Parser() { - _idGenerator = new NodeIDGenerator(); + public Parser(NodeIDGenerator idGenerator) { + _idGenerator = idGenerator; } public StartNode parse(String source) { diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 31718a1d..bdf3340d 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -14,7 +14,7 @@ public class ConstantNode extends Node { public final long _value; public ConstantNode(NodeIDGenerator idGenerator, long value, StartNode startNode) { - super(idGenerator, OP_CONSTANT, startNode); + super(idGenerator, startNode); _value = value; } } diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java index e78ab19a..22ff8e3e 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java @@ -9,25 +9,8 @@ import java.util.List; * The Node class provides common functionality used by all subtypes. * Subtypes of Node specialize by overriding methods. */ -public class Node { +public abstract class Node { - /** - * @see StartNode - */ - static final byte OP_START = 1; - /** - * @see ReturnNode - */ - static final byte OP_RETURN = 2; - /** - * @see ConstantNode - */ - static final byte OP_CONSTANT = 3; - - /** - * The opcode for this node - */ - public final byte _opCode; /** * Each node has a unique dense Node ID within a compilation context @@ -53,18 +36,18 @@ public class Node { * Note that the outputs are derived from inputs, it appears that * outputs are therefore a performance optimization to make it easier to * traverse the graph. The Sea of Nodes documentation in chapter 1 does not - * mention these outputs list. + * mention the outputs list. */ public final List _outputs; - protected Node(NodeIDGenerator idGenerator, byte opCode, Node ...inputs) + protected Node(NodeIDGenerator idGenerator, Node ...inputs) { _nid = idGenerator.newNodeID(); // allocate unique dense ID - _opCode = opCode; _inputs = Arrays.asList(inputs); - _outputs = new ArrayList<>(); - for (int i = 0; i < _inputs.size(); i++) { - Node n = _inputs.get(i); + _outputs = new ArrayList<>(); // The outputs will be populated by nodes that use this as input + + // Add this to as output on all nodes that are inputs + for (Node n : _inputs) { if (n != null) n._outputs.add(this); } @@ -79,6 +62,11 @@ public class Node { public int numInputs() { 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 numOutputs() { return _outputs.size(); } diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java b/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java index 96a292df..5c022160 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java @@ -5,15 +5,11 @@ package com.seaofnodes.simple.node; */ public class NodeIDGenerator { /** - * Counter for node IDs, do not hand out NID 0 - * (Presumably) because it is used for the control node? + * Counter for node IDs, do not hand out NID 0; this is just for safety */ private int nodeIDCounter = 1; public int newNodeID() { - if (nodeIDCounter > 100000) { - throw new RuntimeException("infinite node create loop"); - } return nodeIDCounter++; } } diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 0b62cd4c..3b539ead 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -11,6 +11,6 @@ package com.seaofnodes.simple.node; public class ReturnNode extends Node implements Control { public ReturnNode(NodeIDGenerator idGenerator, Node... inputs) { - super(idGenerator, OP_RETURN, inputs); + super(idGenerator, inputs); } } diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java index 7a9233a8..11043a79 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -8,6 +8,6 @@ package com.seaofnodes.simple.node; public class StartNode extends Node implements Control { public StartNode(NodeIDGenerator idGenerator, Node... inputs) { - super(idGenerator, OP_START, inputs); + super(idGenerator, inputs); } } diff --git a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java index ad420ece..f1a82ec1 100644 --- a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java +++ b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java @@ -1,9 +1,6 @@ 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.node.*; import org.junit.Assert; import org.junit.Test; @@ -11,7 +8,7 @@ public class ParserTest { @Test public void testSimpleProgram() { - Parser parser = new Parser(); + Parser parser = new Parser(new NodeIDGenerator()); StartNode startNode = parser.parse("return 1;"); Assert.assertNotNull(startNode); Assert.assertTrue(startNode.isControl()); -- cgit v1.2.3 From 7e0b33067d83348b87652261845c2f40823012c7 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Mon, 18 Sep 2023 23:45:16 +0100 Subject: Update based on feedback --- chapter01/README.md | 22 +++++++++++----------- 1 file changed, 11 insertions(+), 11 deletions(-) (limited to 'chapter01') diff --git a/chapter01/README.md b/chapter01/README.md index e5b79493..2c0febb8 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -77,28 +77,28 @@ The ID is also used to efficiently compute equality of nodes; a subject that we ### Start Node -The Start node represents the start of the function. For now, we do not have any values in the Start node, this is because our function does not -yet accept parameters. When we add parameters, the value of the Start node will be a tuple, and will require Projection nodes to extract the values. +The Start node represents the start of the function. For now, we do not have any values in to Start, this is because our function does not yet accept parameters. +When we add parameters, the value of the 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 -The Constant node represents a constant value. At present, the only constants that we allow are integer literals; therefore the Constant node contains -an integer value. As we add other types of constants, we will need to refactor how we represent Constant nodes. +The Constant node represents a constant value. At present, the only constants that we allow are integer literals; therefore Constant contains an integer value. +As we add other types of constants, we will refactor Constants. -The Constant node has no inputs. However, we set the Start node as an input to the Constant node to enable forward graph walk. This edge carries no semantic meaning, -it is present _solely_ to allow visitation. +Constant has no inputs. However, we add Start as an input to Constant to enable forward graph walk. This edge carries no semantic meaning, +it is present solely to allow visitation. -The Constant node's output is the value stored in it. +The Constant's output is the value stored in it. ### Return Node -The Return node has two inputs. The first input is a control node. The second input is the data node that supplies the return value. +Return has two inputs. The first input is a control node. The second input is the data node that supplies the return value. -In this presentation, the Return node functions as the Stop node, since we are compiling a single unnamed function. -A separate Stop node is not necessary. Compiling multiple functions is covered in Chapter 9: Functions and Calls. +In this presentation, the Return functions as the Stop, since we are compiling a single unnamed function. +A separate Stop is not necessary. Compiling multiple functions is covered in Chapter 9: Functions and Calls. -The output of the Return node is the value it obtained from the data node. +The output of the Return is the value it obtained from the data node. ### Representation -- cgit v1.2.3 From b1d28a7d1d7996aaaef67b7823725c47e97a7d88 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 18 Sep 2023 16:48:25 -0700 Subject: More edits to Chpt 1 Add the Evil static global var, with appriopriate comments. Drop the singleton class, and every place it had to be passed. Much smaller code now, and will be a LOT smaller as the project grows. Drop the opcode; minor usages in prior implementations for performance, not needed here. Use the preview pattern match in test code to simplify. --- chapter01/README.md | 35 +++++----- .../main/java/com/seaofnodes/simple/Parser.java | 28 +++----- .../com/seaofnodes/simple/node/ConstantNode.java | 4 +- .../main/java/com/seaofnodes/simple/node/Node.java | 78 +++++++++------------- .../seaofnodes/simple/node/NodeIDGenerator.java | 19 ------ .../com/seaofnodes/simple/node/ReturnNode.java | 4 +- .../java/com/seaofnodes/simple/node/StartNode.java | 4 +- .../java/com/seaofnodes/simple/ParserTest.java | 35 +++++----- 8 files changed, 82 insertions(+), 125 deletions(-) delete mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java (limited to 'chapter01') diff --git a/chapter01/README.md b/chapter01/README.md index e5b79493..69a09328 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -71,34 +71,39 @@ at very little cost (nearly always small constant time) because all dependencies ### Unique Node ID -Each node is assigned a unique dense integer Node ID when created. This ID is useful for debugging and e.g. as -an index into a bit vector, which in turn is used to efficiently visit a (possibly cyclic) graph. -The ID is also used to efficiently compute equality of nodes; a subject that we discuss in Chapter 8 Global Value Numbering. +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 values in the Start node, this is because our function does not -yet accept parameters. When we add parameters, the value of the Start node will be a tuple, and will require Projection nodes to extract the values. +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 -The Constant node represents a constant value. At present, the only constants that we allow are integer literals; therefore the Constant node contains -an integer value. As we add other types of constants, we will need to refactor how we represent Constant nodes. +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 refactor how we represent +Constants. -The Constant node has no inputs. However, we set the Start node as an input to the Constant node to enable forward graph walk. This edge carries no semantic meaning, -it is present _solely_ to allow visitation. +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 node's output is the value stored in it. +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. The second input is the data node that supplies the return value. +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, the Return node functions as the Stop node, since we are compiling a single unnamed function. -A separate Stop node is not necessary. Compiling multiple functions is covered in Chapter 9: Functions and Calls. +In this presentation, Return functions as a Stop node, since we are compiling a single unnamed function. +A separate Stop is not necessary. Compiling multiple functions is covered in Chapter 9: Functions and Calls. -The output of the Return node is the value it obtained from the data node. +The Return's output is the value from the data node. ### Representation @@ -111,4 +116,4 @@ return 1; ![Sea of Nodes Visual](./docs/02-graph.svg) * Control nodes appear as square boxes -* Control edges are in bold red \ No newline at end of file +* Control edges are in bold red diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java index 2feeddf9..4da758b2 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java @@ -18,14 +18,8 @@ public class Parser { */ private Token _curTok; - private final NodeIDGenerator _idGenerator; - private StartNode _startNode; - public Parser() { - _idGenerator = new NodeIDGenerator(); - } - public StartNode parse(String source) { Lexer lexer = new Lexer(source); nextToken(lexer); @@ -33,7 +27,7 @@ public class Parser { } private StartNode parseProgram(Lexer lexer) { - _startNode = new StartNode(_idGenerator); + _startNode = new StartNode(); parseReturnStatement(lexer); return _startNode; } @@ -49,7 +43,7 @@ public class Parser { matchIdentifier(lexer, "return"); var returnExpr = parseExpression(lexer); matchPunctuation(lexer, ";"); - return new ReturnNode(_idGenerator, _startNode, returnExpr); + return new ReturnNode(_startNode, returnExpr); } /** @@ -109,7 +103,7 @@ public class Parser { * */ private ConstantNode parseIntegerLiteral(Lexer lexer) { - var constantNode = new ConstantNode(_idGenerator, _curTok._num.longValue(), _startNode); + var constantNode = new ConstantNode(_curTok._num.longValue(), _startNode); nextToken(lexer); return constantNode; } @@ -159,8 +153,7 @@ public class Parser { public final Kind _kind; /** - * String representation of a token - always - * populated + * String representation of a token - always populated */ public final String _str; /** @@ -189,6 +182,7 @@ public class Parser { */ public static Token EOF = new Token(Kind.EOZ, "", null); + @Override public String toString() { return _str; } @@ -236,13 +230,13 @@ public class Parser { * Note that EOF is not whitespace! */ private boolean isWhiteSpace(char c) { - return c == ' ' || - c == '\t' || - c == '\n' || - c == '\r'; + return c == ' ' || + c == '\t' || + c == '\n' || + c == '\r'; } - private void skipWhitespace() { + private void skipWhiteSpace() { while (isWhiteSpace(_cur)) nextToken(); } @@ -296,7 +290,7 @@ public class Parser { * Gets the next token */ public Token next() { - skipWhitespace(); + skipWhiteSpace(); if (_cur == 0) return Token.EOF; if (Character.isDigit(_cur)) diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 31718a1d..e7a3b3f2 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -13,8 +13,8 @@ public class ConstantNode extends Node { public final long _value; - public ConstantNode(NodeIDGenerator idGenerator, long value, StartNode startNode) { - super(idGenerator, OP_CONSTANT, startNode); + public ConstantNode(long value, StartNode startNode) { + super(startNode); _value = value; } } diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java index e78ab19a..bafa58f4 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java @@ -2,32 +2,14 @@ package com.seaofnodes.simple.node; import java.util.ArrayList; import java.util.Arrays; -import java.util.List; +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 class Node { - - /** - * @see StartNode - */ - static final byte OP_START = 1; - /** - * @see ReturnNode - */ - static final byte OP_RETURN = 2; - /** - * @see ConstantNode - */ - static final byte OP_CONSTANT = 3; - - /** - * The opcode for this node - */ - public final byte _opCode; +public abstract class Node { /** * Each node has a unique dense Node ID within a compilation context @@ -40,34 +22,40 @@ public class Node { * Inputs to the node. These are use-def references to Nodes. *

* Generally fixed length, ordered, nulls allowed, no unused trailing space. - * The first input (offset 0) must be a Control nodes. + * 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 List _inputs; + public final ArrayList _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. + * 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. *

- * Note that the outputs are derived from inputs, it appears that - * outputs are therefore a performance optimization to make it easier to - * traverse the graph. The Sea of Nodes documentation in chapter 1 does not - * mention these outputs list. + + * 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 List _outputs; + public final ArrayList _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(NodeIDGenerator idGenerator, byte opCode, Node ...inputs) - { - _nid = idGenerator.newNodeID(); // allocate unique dense ID - _opCode = opCode; - _inputs = Arrays.asList(inputs); + protected Node(Node ...inputs) { + _nid = UNIQUE_ID++; // allocate unique dense ID + _inputs = new ArrayList<>(); + Collections.addAll(_inputs,inputs); _outputs = new ArrayList<>(); - for (int i = 0; i < _inputs.size(); i++) { - Node n = _inputs.get(i); - if (n != null) - n._outputs.add(this); - } + for( Node n : _inputs ) { + if( n != null ) + n._outputs.add( this ); + } } /** @@ -77,17 +65,11 @@ public class Node { */ public Node in(int i) { return _inputs.get(i); } - public int numInputs() { return _inputs.size(); } + public int nIns() { return _inputs.size(); } public Node out(int i) { return _outputs.get(i); } - public int numOutputs() { return _outputs.size(); } - - /** - * Is this a control node, all control nodes are marked with - * the interface Control. - */ - public boolean isControl() { return this instanceof Control; } + 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/NodeIDGenerator.java b/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java deleted file mode 100644 index 96a292df..00000000 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java +++ /dev/null @@ -1,19 +0,0 @@ -package com.seaofnodes.simple.node; - -/** - * Nodes are given unique dense ids. - */ -public class NodeIDGenerator { - /** - * Counter for node IDs, do not hand out NID 0 - * (Presumably) because it is used for the control node? - */ - private int nodeIDCounter = 1; - - public int newNodeID() { - if (nodeIDCounter > 100000) { - throw new RuntimeException("infinite node create loop"); - } - return nodeIDCounter++; - } -} diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 0b62cd4c..eafcab94 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -10,7 +10,7 @@ package com.seaofnodes.simple.node; */ public class ReturnNode extends Node implements Control { - public ReturnNode(NodeIDGenerator idGenerator, Node... inputs) { - super(idGenerator, OP_RETURN, inputs); + 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 index 7a9233a8..6944e8fc 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -7,7 +7,7 @@ package com.seaofnodes.simple.node; */ public class StartNode extends Node implements Control { - public StartNode(NodeIDGenerator idGenerator, Node... inputs) { - super(idGenerator, OP_START, inputs); + 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 index ad420ece..9bc2fc1c 100644 --- a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java +++ b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java @@ -1,9 +1,6 @@ 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.node.*; import org.junit.Assert; import org.junit.Test; @@ -14,22 +11,20 @@ public class ParserTest { Parser parser = new Parser(); StartNode startNode = parser.parse("return 1;"); Assert.assertNotNull(startNode); - Assert.assertTrue(startNode.isControl()); - Assert.assertEquals(2, startNode.numOutputs()); - for (int i = 0; i < startNode.numOutputs(); i++) { - Node out = startNode.out(i); - if (out instanceof ReturnNode) { - Assert.assertEquals(2, out.numInputs()); - Assert.assertEquals(startNode, out.in(0)); - Assert.assertTrue(out.isControl()); - Assert.assertTrue(out.in(1) instanceof ConstantNode); - } - else if (out instanceof ConstantNode cn) { - Assert.assertEquals(1, cn._value); - Assert.assertEquals(1, cn.numInputs()); - Assert.assertEquals(startNode, cn.in(0)); - } - else { + Assert.assertEquals(2, startNode.nOuts()); + for (int i = 0; i < startNode.nOuts(); i++) { + switch( startNode.out(i) ) { + case ReturnNode ret: + Assert.assertEquals(2, ret.nIns()); + Assert.assertEquals(startNode, ret.in(0)); + Assert.assertTrue(ret.in(1) instanceof ConstantNode); + break; + case ConstantNode con: + Assert.assertEquals(1, con._value); + Assert.assertEquals(1, con.nIns()); + Assert.assertEquals(startNode, con.in(0)); + break; + default: throw new IllegalStateException(); } } -- cgit v1.2.3 From cd4ac0ecebec7ac6eda30bdf1989318c14c64806 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 19 Sep 2023 08:02:29 -0700 Subject: Fix a comp error missed one in the merge --- chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'chapter01') diff --git a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java index 15ae7863..9bc2fc1c 100644 --- a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java +++ b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java @@ -8,7 +8,7 @@ public class ParserTest { @Test public void testSimpleProgram() { - Parser parser = new Parser(new NodeIDGenerator()); + Parser parser = new Parser(); StartNode startNode = parser.parse("return 1;"); Assert.assertNotNull(startNode); Assert.assertEquals(2, startNode.nOuts()); -- cgit v1.2.3 From 02f839e3eaab921aecd9c13b59047dd0551e132a Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 19 Sep 2023 09:19:37 -0700 Subject: Overhaul Lexer Switched to bytes from chars, since we'll be parsing files eventually and typically compilers parse bytes from files (and not Java chars). Added a 'peek' to handle bad leading `--123` numbers. Used simpler number parsing; doesn't do doubles (yet). Added a filter for punctuation. Prior setup didn't handle multi-char punctuation like relation tests "<=". Switched the "EOF" marker char from 0 to Char.MAX_VALUE; harder to make mistakes, and simplifies the WS test. Switch javadoc comments to plain comments on private functions. Added tests for broken keyword, broken numbers, negative numbers. --- .../main/java/com/seaofnodes/simple/Parser.java | 145 ++++++++++----------- .../java/com/seaofnodes/simple/ParserTest.java | 45 +++++-- 2 files changed, 103 insertions(+), 87 deletions(-) (limited to 'chapter01') diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java index 4da758b2..e9cae52f 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java @@ -183,123 +183,112 @@ public class Parser { public static Token EOF = new Token(Kind.EOZ, "", null); @Override - public String toString() { - return _str; - } + public String toString() { return _str; } } static class Lexer { - /** - * Input buffer - */ - private final char[] _input; - /** - * Tracks current position in input buffer - */ + // 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; + /** - * Current character + * Record the source text for lexing */ - private char _cur = ' '; + public Lexer(String source) { this(source.getBytes()); } + public Lexer(byte[] buf) { _input = buf; } - private final NumberFormat numberFormat; + // True if at EOF + private boolean isEOF() { return _position >= _input.length; } - public Lexer(String source) { - _input = source.toCharArray(); - numberFormat = NumberFormat.getInstance(); - numberFormat.setGroupingUsed(false); + private char nextChar() { + char ch = peek(); + _position++; + return ch; } - - private boolean isEOF() { - return _position >= _input.length; - } - - private char advance() { - if (isEOF()) - return 0; // Special value that causes parsing to terminate - return _input[_position++]; + // 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 boolean nextToken() { - _cur = advance(); - return true; + // True if a white space + private boolean isWhiteSpace(char c) { + return c <= ' '; // Includes all the use space, tab, newline, CR } /** - * Note that EOF is not whitespace! + * Return the next non-white-space character */ - private boolean isWhiteSpace(char c) { - return c == ' ' || - c == '\t' || - c == '\n' || - c == '\r'; + private char skipWhiteSpace() { + char c = nextChar(); + while( isWhiteSpace(c) ) + c = nextChar(); + return c; } - private void skipWhiteSpace() { - while (isWhiteSpace(_cur)) - nextToken(); + // First digit of a number. + // Allows [-][1-9] but not a leading 0 + private boolean isFirstNumber(char ch) { + char ch2 = peek(); + return ('1'<=ch && ch<='9') || + (ch=='-' && ('1'<=ch2 && ch2<='9')); } - - /** - * Parses number in format nnn[.nnn] - * where n is a digit - */ private Token parseNumber() { - assert Character.isDigit(_cur); - StringBuilder sb = new StringBuilder(); - sb.append(_cur); - while (nextToken() && Character.isDigit(_cur)) - sb.append(_cur); - if (_cur == '.') { - sb.append(_cur); - while (nextToken() && Character.isDigit(_cur)) - sb.append(_cur); - } - String str = sb.toString(); - Number number = parseNumber(str); - return Token.newNum(number, str); - } - - private Number parseNumber(String str) { - try { - return numberFormat.parse(str); - } catch (ParseException e) { - throw new RuntimeException("Failed to parse number " + str, e); - } + int start = _position-1; + while( Character.isDigit( nextChar() ) ) ; + String snum = new String(_input,start,--_position-start); + 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() { - assert isIdentifierStart(_cur); - StringBuilder sb = new StringBuilder(); - sb.append(_cur); - while (nextToken() && isIdentifierLetter(_cur)) - sb.append(_cur); - return Token.newIdent(sb.toString()); + 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 + * Gets the next Token */ public Token next() { - skipWhiteSpace(); - if (_cur == 0) + char ch = skipWhiteSpace(); + if (ch == Character.MAX_VALUE) return Token.EOF; - if (Character.isDigit(_cur)) + if (isFirstNumber(ch)) return parseNumber(); - if (isIdentifierLetter(_cur)) + if (isIdentifierLetter(ch)) return parseIdentifier(); - Token token = Token.newPunct(Character.toString(_cur)); - _cur = ' '; - return token; + if (isPunctuation(ch)) + return parsePuncuation(); + + throw error("Unknown token "+ch); + } + + private RuntimeException error(String msg) { + throw new RuntimeException(msg); } } + } diff --git a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java index 9bc2fc1c..586c53de 100644 --- a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java +++ b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java @@ -1,8 +1,8 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; -import org.junit.Assert; import org.junit.Test; +import static org.junit.Assert.*; public class ParserTest { @@ -10,23 +10,50 @@ public class ParserTest { public void testSimpleProgram() { Parser parser = new Parser(); StartNode startNode = parser.parse("return 1;"); - Assert.assertNotNull(startNode); - Assert.assertEquals(2, startNode.nOuts()); + assertNotNull(startNode); + assertEquals(2, startNode.nOuts()); for (int i = 0; i < startNode.nOuts(); i++) { switch( startNode.out(i) ) { case ReturnNode ret: - Assert.assertEquals(2, ret.nIns()); - Assert.assertEquals(startNode, ret.in(0)); - Assert.assertTrue(ret.in(1) instanceof ConstantNode); + assertEquals(2, ret.nIns()); + assertEquals(startNode, ret.in(0)); + assertTrue(ret.in(1) instanceof ConstantNode); break; case ConstantNode con: - Assert.assertEquals(1, con._value); - Assert.assertEquals(1, con.nIns()); - Assert.assertEquals(startNode, con.in(0)); + assertEquals(1, con._value); + assertEquals(1, con.nIns()); + assertEquals(startNode, con.in(0)); break; default: throw new IllegalStateException(); } } } + + @Test + public void testNegative() { + Parser parser = new Parser(); + StartNode start = parser.parse("return -123;"); + for( Node use : start._outputs ) + if( use instanceof ConstantNode con ) + assertEquals(-123,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, expected nested expr or integer literal: 0123",e.getMessage()); } + } + + @Test + public void testBad3() { + try { new Parser().parse("return --12;"); } + catch( RuntimeException e ) { assertEquals("syntax error, expected ( got --: --",e.getMessage()); } + } } -- cgit v1.2.3 From bf82e7a511cd1f2ab739f75b4dcf536478591f09 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Tue, 19 Sep 2023 19:25:12 +0100 Subject: Parse standalone 0 as integer --- .../main/java/com/seaofnodes/simple/Parser.java | 43 +++++++--------------- .../main/java/com/seaofnodes/simple/node/Node.java | 1 - .../java/com/seaofnodes/simple/ParserTest.java | 19 +++++++++- 3 files changed, 30 insertions(+), 33 deletions(-) (limited to 'chapter01') diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java index e9cae52f..a4c07217 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java @@ -1,9 +1,9 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.node.*; - -import java.text.NumberFormat; -import java.text.ParseException; +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 @@ -61,40 +61,21 @@ public class Parser { * Parse a primary expression: * * 

-     *     primaryExpr : nestedExpr | integerLiteral
+     *     primaryExpr : integerLiteral
      *
*/ private Node parsePrimary(Lexer lexer) { switch (_curTok._kind) { - case PUNCT -> { - /* Nested expression */ - return parseNestedExpr(lexer); - } case NUM -> { return parseIntegerLiteral(lexer); } default -> { - error(_curTok, "syntax error, expected nested expr or integer literal"); + error(_curTok, "syntax error, expected integer literal"); return null; } } } - /** - * Parse nested expression: - * - * 
-     *     nestedExpr : ( expr )
-     *
- */ - private Node parseNestedExpr(Lexer lexer) { - matchPunctuation(lexer, "("); - nextToken(lexer); - var node = parsePrimary(lexer); - matchPunctuation(lexer, ")"); - return node; - } - /** * Parse integer literal * @@ -229,11 +210,13 @@ public class Parser { } // First digit of a number. - // Allows [-][1-9] but not a leading 0 + // Allows 0 on its own or + // [-][1-9][0-9]* private boolean isFirstNumber(char ch) { char ch2 = peek(); - return ('1'<=ch && ch<='9') || - (ch=='-' && ('1'<=ch2 && ch2<='9')); + return (ch=='0' && (ch2 <'0' || ch2 > '9')) || // 0 followed by non-digit + ('1'<=ch && ch<='9') || // starts with [1-9] + (ch=='-' && ('1'<=ch2 && ch2<='9')); // starts with - and followed by [1-9] } private Token parseNumber() { int start = _position-1; @@ -278,12 +261,12 @@ public class Parser { return Token.EOF; if (isFirstNumber(ch)) return parseNumber(); - if (isIdentifierLetter(ch)) + if (isIdentifierStart(ch)) return parseIdentifier(); if (isPunctuation(ch)) return parsePuncuation(); - throw error("Unknown token "+ch); + throw error("syntax error: unexpected input '" + ch + "'"); } private RuntimeException error(String msg) { diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java index f817db52..6b2a19b8 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; import java.util.ArrayList; -import java.util.Arrays; import java.util.Collections; /** diff --git a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java index 586c53de..029f6121 100644 --- a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java +++ b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java @@ -39,6 +39,15 @@ public class ParserTest { assertEquals(-123,con._value); } + @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"); } @@ -48,12 +57,18 @@ public class ParserTest { @Test public void testBad2() { try { new Parser().parse("return 0123;"); } - catch( RuntimeException e ) { assertEquals("syntax error, expected nested expr or integer literal: 0123",e.getMessage()); } + catch( RuntimeException e ) { assertEquals("syntax error: unexpected input '0'",e.getMessage()); } } @Test public void testBad3() { try { new Parser().parse("return --12;"); } - catch( RuntimeException e ) { assertEquals("syntax error, expected ( got --: --",e.getMessage()); } + 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 :")); } } } -- cgit v1.2.3 From cecb62d847da7dc937b52857ae2fd4b41af98a7c Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Tue, 19 Sep 2023 21:30:41 +0100 Subject: Do not parse negative integers, - will be treated as unary operator. Update the comments for Return node. Sync comments with README. --- chapter01/README.md | 4 ++-- .../src/main/java/com/seaofnodes/simple/Parser.java | 15 ++++++--------- .../java/com/seaofnodes/simple/node/ConstantNode.java | 13 ++++++++----- .../java/com/seaofnodes/simple/node/ReturnNode.java | 11 ++++++----- .../java/com/seaofnodes/simple/node/StartNode.java | 4 ++-- .../test/java/com/seaofnodes/simple/ParserTest.java | 18 ++++++++---------- 6 files changed, 32 insertions(+), 33 deletions(-) (limited to 'chapter01') diff --git a/chapter01/README.md b/chapter01/README.md index 5a59ace8..f3231d8c 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -100,8 +100,8 @@ The Constant's value is the value stored in it. 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 we are compiling a single unnamed function. -A separate Stop is not necessary. Compiling multiple functions is covered in Chapter 9: Functions and Calls. +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. diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java index a4c07217..8fb1ebaf 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java @@ -209,19 +209,16 @@ public class Parser { return c; } - // First digit of a number. - // Allows 0 on its own or - // [-][1-9][0-9]* - private boolean isFirstNumber(char ch) { - char ch2 = peek(); - return (ch=='0' && (ch2 <'0' || ch2 > '9')) || // 0 followed by non-digit - ('1'<=ch && ch<='9') || // starts with [1-9] - (ch=='-' && ('1'<=ch2 && ch2<='9')); // starts with - and followed by [1-9] + 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); } @@ -259,7 +256,7 @@ public class Parser { char ch = skipWhiteSpace(); if (ch == Character.MAX_VALUE) return Token.EOF; - if (isFirstNumber(ch)) + if (isDigit(ch)) return parseNumber(); if (isIdentifierStart(ch)) return parseIdentifier(); diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index e7a3b3f2..7644daf2 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -1,13 +1,16 @@ package com.seaofnodes.simple.node; /** - * The Constant node represents a constant value. At present, the only constants that we allow are integer literals; therefore the Constant node contains - * an integer value. As we add other types of constants, we will need to refactor how we represent Constant nodes. + * 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. *

- * The Constant node has no inputs. However, we set the Start node as an input to the Constant node to enable forward graph walk. This edge carries no semantic meaning, - * it is present _solely_ to allow visitation. + * 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 node's output is the value stored in it. + * The Constant's value is the value stored in it. */ public class ConstantNode extends Node { diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index eafcab94..12a5b464 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -1,16 +1,17 @@ package com.seaofnodes.simple.node; /** - * The Return node has two inputs. The first input is a control node. The second input is the data node that supplies the return value. + * 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, the Return node functions as the Stop node, since we are compiling a single unnamed function. - * A separate Stop node is not necessary. Compiling multiple functions is covered in Chapter 9: Functions and Calls. + * 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 output of the Return node is the value it obtained from the data node. + * 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); + 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 index 6944e8fc..c29ba53c 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -1,8 +1,8 @@ package com.seaofnodes.simple.node; /** - * The Start node represents the start of the function. For now, we do not have any values in the Start node, this is because our function does not - * yet accept parameters. When we add parameters, the value of the Start node will be a tuple, and will require Projection nodes to extract the values. + * 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 { diff --git a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java index 029f6121..887f63b8 100644 --- a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java +++ b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java @@ -30,15 +30,6 @@ public class ParserTest { } } - @Test - public void testNegative() { - Parser parser = new Parser(); - StartNode start = parser.parse("return -123;"); - for( Node use : start._outputs ) - if( use instanceof ConstantNode con ) - assertEquals(-123,con._value); - } - @Test public void testZero() { Parser parser = new Parser(); @@ -57,7 +48,7 @@ public class ParserTest { @Test public void testBad2() { try { new Parser().parse("return 0123;"); } - catch( RuntimeException e ) { assertEquals("syntax error: unexpected input '0'",e.getMessage()); } + catch( RuntimeException e ) { assertEquals("syntax error: integer values cannot start with '0'",e.getMessage()); } } @Test @@ -71,4 +62,11 @@ public class ParserTest { 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()); } + } } -- cgit v1.2.3