diff options
Diffstat (limited to 'src')
8 files changed, 581 insertions, 0 deletions
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..c2ea3734 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -0,0 +1,253 @@ +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. + * <p> + * This is a simple recursive descent parser. All lexical analysis is done here as well. + */ +public class Parser { + + public int pos() { return _lexer._position; } + + + /** + * A Global Static, unique to each compilation. This is a public, so we + * can make constants everywhere without having to thread the StartNode + * through the entire parser and optimizer. + * <p> + * To make the compiler multithreaded, this field will have to move into a TLS. + */ + public static StartNode START; + + // 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 + * + * <pre> + * returnStatement + * </pre> + * @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. + * + * <pre> + * 'return' expr ; + * </pre> + * @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: + * + * <pre> + * expr : primaryExpr + * </pre> + * @return an expression {@link Node}, never {@code null} + */ + private Node parseExpression() { + return parsePrimary(); + } + + /** + * Parse a primary expression: + * + * <pre> + * primaryExpr : integerLiteral + * </pre> + */ + private Node parsePrimary() { + _lexer.skipWhiteSpace(); + if (_lexer.isNumber()) + return parseIntegerLiteral(); + throw error("Syntax error, expected integer literal"); + } + + /** + * Parse integer literal + * + * <pre> + * integerLiteral: [1-9][0-9]* | [0] + * </pre> + */ + 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. + * <p> + * Constants have no semantic inputs. However, we set Start as an input to + * Constants to enable a forward graph walk. This edge carries no semantic + * meaning, and it is present <em>solely</em> to allow visitation. + * <p> + * The Constant's value is the value stored in it. + */ +public class ConstantNode extends Node { + + public final long _value; + + public ConstantNode(long value) { + 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. + * <p> + * Generally fixed length, ordered, nulls allowed, no unused trailing space. + * Ordering is required because e.g. "a/b" is different from "b/a". + * The first input (offset 0) is often a {@link #isCFG} node. + */ + public final ArrayList<Node> _inputs; + + /** + * Outputs reference Nodes that are not null and have this Node as an + * input. These nodes are users of this node, thus these are def-use + * references to Nodes. + * <p> + * Outputs directly match inputs, making a directed graph that can be + * walked in either direction. These outputs are typically used for + * efficient optimizations but otherwise have no semantics meaning. + */ + public final ArrayList<Node> _outputs; + + /** + * A private Global Static mutable counter, for unique node id generation. + * To make the compiler multi-threaded, this field will have to move into a TLS. + * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values. + * */ + private static int UNIQUE_ID = 1; + + protected Node(Node... inputs) { + _nid = UNIQUE_ID++; // allocate unique dense ID + _inputs = new ArrayList<>(); + Collections.addAll(_inputs,inputs); + _outputs = new ArrayList<>(); + for( Node n : _inputs ) + if( n != null ) + n._outputs.add( this ); + } + + /** + * Gets the ith input node + * @param i Offset of the input node + * @return Input node or null + */ + public Node in(int i) { return _inputs.get(i); } + + public int nIns() { return _inputs.size(); } + + 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. + * <p> + * In this presentation, Return functions as a Stop node, since multiple <code>return</code> statements are not possible. + * The Stop node will be introduced in Chapter 6 when we implement <code>if</code> statements. + * <p> + * The Return's output is the value from the data node. + */ +public class ReturnNode extends Node { + + 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/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java new file mode 100644 index 00000000..59275832 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -0,0 +1,45 @@ +package com.seaofnodes.simple.print; + +import com.seaofnodes.graph.GraphAdapter; +import com.seaofnodes.graph.GraphSnapshot; +import com.seaofnodes.graph.GraphSnapshot.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.Node; +import java.util.ArrayList; + +/** Chapter 1's view of the IR; browser, transport and layout are shared. */ +public class SimpleGraphAdapter extends GraphAdapter<Node> { + @Override protected boolean dead(Node n) { return false; } + @Override protected int id(Node n) { return n._nid; } + @Override protected int nIns(Node n) { return n.nIns(); } + @Override protected Node in(Node n, int idx) { return n.in(idx); } + @Override protected int nOuts(Node n) { return n.nOuts(); } + @Override protected Node out(Node n, int idx) { return n._outputs.get(idx); } + + private ArrayList<Edge> edges(Node n) { + var edges = new ArrayList<Edge>(); + for( int i = 0; i < n.nIns(); i++ ) { + String name = null; + edges.add(new Edge(i, ref(n.in(i)), role(n, i), name)); + } + return edges; + } + + @Override protected GraphSnapshot.Node desc(Node n) { + Projection proj = null; + String label = n instanceof ConstantNode c ? Long.toString(c._value) : n.getClass().getSimpleName(); + return new GraphSnapshot.Node(n._nid, label == null ? n.getClass().getSimpleName() : label, + null, kind(n), edges(n), proj); + } + + private Kind kind(Node n) { + if( n instanceof StartNode ) return Kind.CTRL; + return n.isCFG() ? Kind.CTRL : Kind.DATA; + } + + private Role role(Node n, int i) { + if( n instanceof ConstantNode ) return Role.ASSOC; + if( i == 0 ) return Role.CTRL; + return Role.DATA; + } +} diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java new file mode 100644 index 00000000..1c78e4dd --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -0,0 +1,35 @@ +package com.seaofnodes.simple.print; + +import com.seaofnodes.graph.GraphCapture; +import com.seaofnodes.graph.GraphViewer; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.Node; +import java.util.ArrayList; +import java.io.IOException; + +/** Chapter 1's compilation context; capture and event bookkeeping are shared. */ +public class SimpleGraphObserver extends GraphCapture<Node> { + private Parser _parser; + private Node _ret; + private String _phase; + public SimpleGraphObserver() { super(new SimpleGraphAdapter()); } + public static void main(String[] args) throws IOException { + GraphViewer.run(new SimpleGraphObserver()); + } + @Override protected void compile(String src) { + _parser = new Parser(src); + _phase = "Parse"; + _ret = _parser.parse(); + phase(_phase); + } + @Override protected String phase() { return _phase; } + @Override protected int pos() { return "Parse".equals(_phase) ? _parser.pos() : -1; } + @Override protected void detach() { + _parser = null; + _ret = null; + } + @Override protected void roots(ArrayList<Node> roots) { + roots.add(Parser.START); + roots.add(_ret); + } +} 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()); + } + } + +} |