From 47ad4a9f955fde76c6cf4022fc308f1d0723926d Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Sat, 19 Aug 2023 08:52:57 -0700 Subject: Chapter 1: Introduction Co-authored-by: Thalia Archibald Co-authored-by: Cliff Click Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> --- src/main/java/com/seaofnodes/simple/Parser.java | 250 +++++++++++++++++++++ .../com/seaofnodes/simple/node/ConstantNode.java | 25 +++ src/main/java/com/seaofnodes/simple/node/Node.java | 77 +++++++ .../com/seaofnodes/simple/node/ReturnNode.java | 23 ++ .../java/com/seaofnodes/simple/node/StartNode.java | 16 ++ .../java/com/seaofnodes/simple/Chapter01Test.java | 107 +++++++++ 6 files changed, 498 insertions(+) create mode 100644 src/main/java/com/seaofnodes/simple/Parser.java create mode 100644 src/main/java/com/seaofnodes/simple/node/ConstantNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/Node.java create mode 100644 src/main/java/com/seaofnodes/simple/node/ReturnNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/StartNode.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter01Test.java (limited to 'src') diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java new file mode 100644 index 00000000..806c985d --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -0,0 +1,250 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; + +/** + * The Parser converts a Simple source program to the Sea of Nodes intermediate + * representation directly in one pass. There is no intermediate Abstract + * Syntax Tree structure. + *

+ * This is a simple recursive descent parser. All lexical analysis is done here as well. + */ +public class Parser { + + /** + * A Global Static, unique to each compilation. This is a public, so we + * can make constants everywhere without having to thread the StartNode + * through the entire parser and optimizer. + *

+ * To make the compiler multithreaded, this field will have to move into a TLS. + */ + public static StartNode START; + + // The Lexer. Thin wrapper over a byte[] buffer with a cursor. + private final Lexer _lexer; + + + public Parser(String source) { + _lexer = new Lexer(source); + Node.reset(); + START = new StartNode(); + } + + public ReturnNode parse() { + var ret = (ReturnNode) parseStatement(); + if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); + return ret; + } + + /** + * Parses a statement + * + * 

+     *     returnStatement
+     *
+ * @return a {@link Node} or {@code null} + */ + private Node parseStatement() { + if (matchx("return")) return parseReturn(); + throw errorSyntax("a statement"); + } + + /** + * Parses a return statement; "return" already parsed. + * + * 
+     *     'return' expr ;
+     *
+ * @return an expression {@link Node}, never {@code null} + */ + private ReturnNode parseReturn() { + var expr = require(parseExpression(), ";"); + return new ReturnNode(START, expr); + } + + /** + * Parse an expression of the form: + * + * 
+     *     expr : primaryExpr
+     *
+ * @return an expression {@link Node}, never {@code null} + */ + private Node parseExpression() { + return parsePrimary(); + } + + /** + * Parse a primary expression: + * + * 
+     *     primaryExpr : integerLiteral
+     *
+ */ + private Node parsePrimary() { + _lexer.skipWhiteSpace(); + if (_lexer.isNumber()) + return parseIntegerLiteral(); + throw error("Syntax error, expected integer literal"); + } + + /** + * Parse integer literal + * + * 
+     *     integerLiteral: [1-9][0-9]* | [0]
+     *
+ */ + private ConstantNode parseIntegerLiteral() { + return new ConstantNode(_lexer.parseNumber()); + } + + ////////////////////////////////// + // Utilities for lexical analysis + + // Return true and skip if "syntax" is next in the stream. + private boolean match (String syntax) { return _lexer.match (syntax); } + // Match must be "exact", not be followed by more id letters + private boolean matchx(String syntax) { return _lexer.matchx(syntax); } + + // Require an exact match + private void require(String syntax) { require(null, syntax); } + private Node require(Node n, String syntax) { + if (match(syntax)) return n; + throw errorSyntax(syntax); + } + + RuntimeException errorSyntax(String syntax) { + return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken()); + } + + static RuntimeException error(String errorMessage) { + return new RuntimeException(errorMessage); + } + + //////////////////////////////////// + // Lexer components + + private static class Lexer { + + // Input buffer; an array of text bytes read from a file or a string + private final byte[] _input; + // Tracks current position in input buffer + private int _position = 0; + + /** + * Record the source text for lexing + */ + public Lexer(String source) { + this(source.getBytes()); + } + + /** + * Direct from disk file source + */ + public Lexer(byte[] buf) { + _input = buf; + } + + // True if at EOF + private boolean isEOF() { + return _position >= _input.length; + } + + // Peek next character, or report EOF + private char peek() { + return isEOF() ? Character.MAX_VALUE // Special value that causes parsing to terminate + : (char) _input[_position]; + } + + private char nextChar() { + char ch = peek(); + _position++; + return ch; + } + + // True if a white space + private boolean isWhiteSpace() { + return peek() <= ' '; // Includes all the use space, tab, newline, CR + } + + /** + * Return the next non-white-space character + */ + private void skipWhiteSpace() { + while (isWhiteSpace()) _position++; + } + + + // Return true, if we find "syntax" after skipping white space; also + // then advance the cursor past syntax. + // Return false otherwise, and do not advance the cursor. + boolean match(String syntax) { + skipWhiteSpace(); + int len = syntax.length(); + if (_position + len > _input.length) return false; + for (int i = 0; i < len; i++) + if ((char) _input[_position + i] != syntax.charAt(i)) + return false; + _position += len; + return true; + } + + boolean matchx(String syntax) { + if( !match(syntax) ) return false; + if( !isIdLetter(peek()) ) return true; + _position -= syntax.length(); + return false; + } + + // Used for errors + String getAnyNextToken() { + if (isEOF()) return ""; + if (isIdStart(peek())) return parseId(); + if (isNumber(peek())) return parseNumberString(); + if (isPunctuation(peek())) return parsePunctuation(); + return String.valueOf(peek()); + } + + boolean isNumber() {return isNumber(peek());} + boolean isNumber(char ch) {return Character.isDigit(ch);} + + private long parseNumber() { + String snum = parseNumberString(); + if (snum.length() > 1 && snum.charAt(0) == '0') + throw error("Syntax error: integer values cannot start with '0'"); + return Long.parseLong(snum); + } + private String parseNumberString() { + int start = _position; + while (isNumber(nextChar())) ; + return new String(_input, start, --_position - start); + } + + // First letter of an identifier + private boolean isIdStart(char ch) { + return Character.isAlphabetic(ch) || ch == '_'; + } + + // All characters of an identifier, e.g. "_x123" + private boolean isIdLetter(char ch) { + return Character.isLetterOrDigit(ch) || ch == '_'; + } + + private String parseId() { + int start = _position; + while (isIdLetter(nextChar())) ; + return new String(_input, start, --_position - start); + } + + private boolean isPunctuation(char ch) { + return "=;[]<>(){}+-/*!".indexOf(ch) != -1; + } + + private String parsePunctuation() { + int start = _position; + return new String(_input, start, 1); + } + } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java new file mode 100644 index 00000000..21f65084 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -0,0 +1,25 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; + +/** + * A Constant node represents a constant value. At present, the only constants + * that we allow are integer literals; therefore Constants contain an integer + * value. As we add other types of constants, we will refactor how we represent + * Constants. + *

+ * Constants have no semantic inputs. However, we set Start as an input to + * Constants to enable a forward graph walk. This edge carries no semantic + * meaning, and it is present solely to allow visitation. + *

+ * The Constant's value is the value stored in it. + */ +public class ConstantNode extends Node { + + public final long _value; + + public ConstantNode(long value) { + super(Parser.START); + _value = value; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java new file mode 100644 index 00000000..5d74e206 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -0,0 +1,77 @@ +package com.seaofnodes.simple.node; + +import java.util.*; + +/** + * All Nodes in the Sea of Nodes IR inherit from the Node class. + * The Node class provides common functionality used by all subtypes. + * Subtypes of Node specialize by overriding methods. + */ +public abstract class Node { + + /** + * Each node has a unique dense Node ID within a compilation context + * The ID is useful for debugging, for using as an offset in a bitvector, + * as well as for computing equality of nodes (to be implemented later). + */ + public final int _nid; + + /** + * Inputs to the node. These are use-def references to Nodes. + *

+ * Generally fixed length, ordered, nulls allowed, no unused trailing space. + * Ordering is required because e.g. "a/b" is different from "b/a". + * The first input (offset 0) is often a {@link #isCFG} node. + */ + 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 directly match inputs, making a directed graph that can be + * walked in either direction. These outputs are typically used for + * efficient optimizations but otherwise have no semantics meaning. + */ + public final ArrayList _outputs; + + /** + * A private Global Static mutable counter, for unique node id generation. + * To make the compiler multi-threaded, this field will have to move into a TLS. + * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values. + * */ + private static int UNIQUE_ID = 1; + + protected Node(Node... inputs) { + _nid = UNIQUE_ID++; // allocate unique dense ID + _inputs = new ArrayList<>(); + Collections.addAll(_inputs,inputs); + _outputs = new ArrayList<>(); + for( Node n : _inputs ) + if( n != null ) + n._outputs.add( this ); + } + + /** + * Gets the ith input node + * @param i Offset of the input node + * @return Input node or null + */ + public Node in(int i) { return _inputs.get(i); } + + public int nIns() { return _inputs.size(); } + + public int nOuts() { return _outputs.size(); } + + public boolean isUnused() { return nOuts() == 0; } + + public boolean isCFG() { return false; } + + + /** + * Used to allow repeating tests in the same JVM. This just resets the + * Node unique id generator, and is done as part of making a new Parser. + */ + public static void reset() { UNIQUE_ID = 1; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java new file mode 100644 index 00000000..85bbc83f --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -0,0 +1,23 @@ +package com.seaofnodes.simple.node; + +/** + * The Return node has two inputs. The first input is a control node and the + * second is the data node that supplies the return value. + *

+ * 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. + */ +public class ReturnNode extends Node { + + public ReturnNode(Node ctrl, Node data) { + super(ctrl, data); + } + + public Node ctrl() { return in(0); } + public Node expr() { return in(1); } + + @Override public boolean isCFG() { return true; } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java new file mode 100644 index 00000000..04bd6bb4 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -0,0 +1,16 @@ +package com.seaofnodes.simple.node; + +/** + * The Start node represents the start of the function. For now, we do not have any inputs to Start because our function does not + * yet accept parameters. When we add parameters the value of Start will be a tuple, and will require Projections to extract the values. + * We discuss this in detail in Chapter 9: Functions and Calls. + */ +public class StartNode extends Node { + + public StartNode(/*arguments go here*/) { + super(); + } + + @Override public boolean isCFG() { return true; } + +} diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java new file mode 100644 index 00000000..a91aabb1 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -0,0 +1,107 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter01Test { + + @Test + public void testSimpleProgram() { + Parser parser = new Parser("return 1;"); + ReturnNode ret = parser.parse(); + StartNode start = Parser.START; + + assertEquals(start, ret.ctrl()); + Node expr = ret.expr(); + if( expr instanceof ConstantNode con ) { + assertEquals(start,con.in(0)); + assertEquals(1, con._value); + } else { + fail(); + } + } + + @Test + public void testZero() { + Parser parser = new Parser("return 0;"); + parser.parse(); + StartNode start = Parser.START; + for( Node use : start._outputs ) + if( use instanceof ConstantNode con ) + assertEquals(0,con._value); + } + + @Test + public void testBad1() { + try { + new Parser("ret").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected a statement: ret",e.getMessage()); + } + } + + @Test + public void testBad2() { + try { + new Parser("return 0123;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); + } + } + + @Test + public void testBad3() { + try { + new Parser("return --12;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected integer literal",e.getMessage()); + } + } + + @Test + public void testBad4() { + try { + new Parser("return 100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected ;: ",e.getMessage()); + } + } + + // Negative numbers require unary operator support that is not in scope + @Test + public void testBad5() { + try { + new Parser("return -100;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected integer literal",e.getMessage()); + } + } + + @Test + public void testBad6() { + try { + new Parser("return100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected a statement: return100",e.getMessage()); + } + } + + @Test + public void testBad7() { + try { + new Parser("return 1;}").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, unexpected }",e.getMessage()); + } + } + +} -- cgit v1.2.3