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. --- .../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 +++ 7 files changed, 171 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/src') 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 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/src') 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/src') 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/src') 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 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. --- .../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 +++++----- 7 files changed, 62 insertions(+), 110 deletions(-) delete mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java (limited to 'chapter01/src') 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/src') 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/src') 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/src') 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. --- .../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 ++++++++---------- 5 files changed, 30 insertions(+), 31 deletions(-) (limited to 'chapter01/src') 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