diff options
Diffstat (limited to 'src')
7 files changed, 370 insertions, 16 deletions
diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index f59b0f25..e6cb84f8 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -5,6 +5,8 @@ import com.seaofnodes.graph.GraphObserver; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; +import java.util.*; + /** * The Parser converts a Simple source program to the Sea of Nodes intermediate * representation directly in one pass. There is no intermediate Abstract @@ -32,33 +34,73 @@ public class Parser { // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; + /** + * Stack of lexical scopes, each scope is a symbol table that binds + * variable names to Nodes. The top of this stack represents current scope. + */ + public ScopeNode _scope; + + /** + * List of keywords disallowed as identifiers + */ + private final HashSet<String> KEYWORDS = new HashSet<>(){{ + add("int"); + add("return"); + }}; + public Parser(String source) { _lexer = new Lexer(source); PARSER = this; Node.reset(); + _scope = new ScopeNode(); START = new StartNode(); } String src() { return new String( _lexer._input ); } public ReturnNode parse() { - var ret = (ReturnNode) parseStatement(); + var ret = (ReturnNode) parseBlock(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); return ret; } /** + * Parses a block + * + * <pre> + * '{' statements '}' + * </pre> + * Does not parse the opening or closing '{}' + * @return a {@link Node} or {@code null} + */ + private Node parseBlock() { + // Enter a new scope + _scope.push(); + Node n = null; + while (!peek('}') && !_lexer.isEOF()) { + Node n0 = parseStatement(); + if (n0 != null) n = n0; // Empty statements can return null + }; + // Exit scope + _scope.pop(); + return n; + } + + /** * Parses a statement * * <pre> - * returnStatement + * returnStatement | declStatement | blockStatement | expressionStatement * </pre> * @return a {@link Node} or {@code null} */ private Node parseStatement() { - if (matchx("return")) return parseReturn(); - throw errorSyntax("a statement"); + if (matchx("return") ) return parseReturn(); + else if (matchx("int")) return parseDecl(); + else if (match ("{" )) return require(parseBlock(),"}"); + else if (matchx(";")) return null; // Empty statement + else return parseExpressionStatement(); } /** @@ -74,6 +116,43 @@ public class Parser { return new ReturnNode(START, expr).peephole(); } + + + /** + * Parses an expression statement + * + * <pre> + * name '=' expression ';' + * </pre> + * @return an expression {@link Node}, never {@code null} + */ + private Node parseExpressionStatement() { + var name = requireId(); + require("="); + var expr = require(parseExpression(), ";"); + if( _scope.update(name, expr)==null ) + throw error("Undefined name '" + name + "'"); + return expr; + } + + /** + * Parses a declStatement + * + * <pre> + * 'int' name = expression ';' + * </pre> + * @return an expression {@link Node}, never {@code null} + */ + private Node parseDecl() { + // Type is 'int' for now + var name = requireId(); + require("="); + var expr = require(parseExpression(), ";"); + if( _scope.define(name,expr) == null ) + throw error("Redefining name '" + name + "'"); + return expr; + } + /** * Parse an expression of the form: * @@ -138,7 +217,11 @@ public class Parser { private Node parsePrimary() { if( _lexer.isNumber() ) return parseIntegerLiteral(); if( match("(") ) return require(parseExpression(), ")"); - throw errorSyntax("integer literal"); + String name = _lexer.matchId(); + if( name == null) throw errorSyntax("an identifier or expression"); + Node n = _scope.lookup(name); + if( n!=null ) return n; + throw error("Undefined name '" + name + "'"); } /** @@ -159,6 +242,15 @@ public class Parser { 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); } + // Return true and do NOT skip if 'ch' is next + private boolean peek(char ch) { return _lexer.peek(ch); } + + // Require and return an identifier + private String requireId() { + String id = _lexer.matchId(); + if (id != null && !KEYWORDS.contains(id) ) return id; + throw error("Expected an identifier, found '"+id+"'"); + } // Require an exact match private void require(String syntax) { require(null, syntax); } @@ -256,6 +348,17 @@ public class Parser { return false; } + private boolean peek(char ch) { + skipWhiteSpace(); + return peek()==ch; + } + + // Return an identifier or null + String matchId() { + skipWhiteSpace(); + return isIdStart(peek()) ? parseId() : null; + } + // Used for errors String getAnyNextToken() { if (isEOF()) return ""; diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index acf6b236..3fa0fd1e 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -124,10 +124,18 @@ public abstract class Node { public boolean isCFG() { return false; } + /** * Change a <em>def</em> into a Node. Keeps the edges correct, by removing * the corresponding <em>use->def</em> edge. This may make the original * <em>def</em> go dead. This function is co-recursive with {@link #kill}. + * <p> + + * This method is the normal path for altering a Node, because it does the + * proper default edge maintenance. It also <em>immediately</em> kills + * Nodes that lose their last use; at times care must be taken to avoid + * killing Nodes that are being used without having an output Node. This + * definitely happens in the middle of recursive {@link #peephole} calls. * * @param idx which def to set * @param new_def the new definition @@ -150,6 +158,22 @@ public abstract class Node { return new_def; } + /** + * Add a new def to an existing Node. Keep the edges correct by + * adding the corresponding <em>def->use</em> edge. + * + * @param new_def the new definition, appended to the end of existing definitions + * @return new_def for flow coding + */ + Node addDef(Node new_def) { + // Add use->def edge + _inputs.add(new_def); + // If new def is not null, add the corresponding def->use edge + if( new_def != null ) + new_def.addUse(this); + return new_def; + } + // Breaks the edge invariants, used temporarily protected <N extends Node> void addUse(N n) { _outputs.add(n); } @@ -161,16 +185,25 @@ public abstract class Node { return _outputs.size() == 0; } + // Shortcut for "popping" n nodes. A "pop" is basically a + // set_def(last,null) followed by lowering the nIns() count. + void popN(int n) { + for( int i=0; i<n; i++ ) { + Node old_def = _inputs.removeLast(); + if( old_def != null && // If it exists and + old_def.delUse(this) ) // If we removed the last use, the old def is now dead + old_def.kill(); // Kill old def + } + } + /** * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em> * to null. This may recursively kill more Nodes and is basically dead - * code elimination. This function is co-recursive with {@link #setDef}. + * code elimination. This function is co-recursive with {@link #popN}. */ public void kill( ) { assert isUnused(); // Has no uses, so it is dead - for( int i=0; i<nIns(); i++ ) - setDef(i,null); // Set all inputs to null, recursively killing unused Nodes - _inputs.clear(); + popN(nIns()); // Set all inputs to null, recursively killing unused Nodes _type=null; // Flag as dead assert isDead(); // Really dead now } @@ -217,7 +250,6 @@ public abstract class Node { return null; // No progress } - /** * This function needs to be * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a> @@ -243,4 +275,24 @@ public abstract class Node { * Node unique id generator, and is done as part of making a new Parser. */ public static void reset() { UNIQUE_ID = 1; } + + /** + * Debugging utility to find a Node by index + */ + public Node find(int nid) { return _find(new BitSet(),nid); } + private Node _find(BitSet visit, int nid) { + if( _nid==nid ) return this; + if( visit.get(_nid) ) return null; + visit.set(_nid); + for( Node def : _inputs ) + if( def!=null ) { + Node rez = def._find(visit,nid); + if( rez != null ) return rez; + } + for( Node use : _outputs ) { + Node rez = use._find(visit,nid); + if( rez != null ) return rez; + } + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java new file mode 100644 index 00000000..379ef033 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -0,0 +1,128 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; + +import java.util.*; + +/** + * The Scope node is purely a parser helper - it tracks names to nodes with a + * stack of scopes. + * @see <a href="file:../../../../../../../../chapter03/README.md">chapter03/README.md</a> + */ +public class ScopeNode extends Node { + + /** + * A Stack of symbol tables; a symbol table is a map from names to node indices. + */ + public final Stack<HashMap<String, Integer>> _scopes; + + + // A new ScopeNode + public ScopeNode() { + _scopes = new Stack<>(); + _type = Type.BOTTOM; + } + + + @Override public String label() { return "Scope"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + sb.append(label()); + for( HashMap<String,Integer> scope : _scopes ) { + sb.append("["); + boolean first=true; + for( String name : scope.keySet() ) { + if( !first ) sb.append(", "); + first=false; + sb.append(name).append(":"); + Node n = in(scope.get(name)); + if( n==null ) sb.append("null"); + else n._print0(sb); + } + sb.append("]"); + } + return sb; + } + + /** + * Recover the names for all variable bindings. + * The result is an array of names that is aligned with the + * inputs to the Node. + * <p> + * This is an expensive operation. + */ + public String[] reverseNames() { + String[] names = new String[nIns()]; + for( HashMap<String,Integer> syms : _scopes ) + for( String name : syms.keySet() ) + names[syms.get(name)] = name; + return names; + } + + @Override public Type compute() { return Type.BOTTOM; } + + @Override public Node idealize() { return null; } + + public void push() { _scopes.push(new HashMap<>()); } + public void pop() { popN(_scopes.pop().size()); } + + /** + * Create a new name in the current scope + */ + public Node define( String name, Node n ) { + HashMap<String,Integer> syms = _scopes.lastElement(); + if( syms.put(name,nIns()) != null ) + return null; // Double define + return addDef(n); + } + /** + * Lookup a name in all scopes starting from most deeply nested. + * <p> + * @param name Name to be looked up + * @see #update(String, Node, int) + */ + public Node lookup( String name ) { return update(name,null,_scopes.size()-1); } + /** + * If the name is present in any scope, then redefine else null + * <p> + * @param name Name being redefined + * @param n The node to bind to the name + */ + public Node update( String name, Node n ) { return update(name,n,_scopes.size()-1); } + /** + * Both recursive lookup and update. + * <p> + * A shared implementation allows us to create lazy phis both during + * lookups and updates; the lazy phi creation is part of chapter 8. + * + * @param name Name whose binding is being updated or looked up + * @param n If null, do a lookup, else update binding + * @param nestingLevel The starting nesting level + * @return node being looked up, or the one that was updated + */ + private Node update( String name, Node n, int nestingLevel ) { + if( nestingLevel<0 ) return null; // Missed in all scopes, not found + var syms = _scopes.get(nestingLevel); // Get the symbol table for nesting level + var idx = syms.get(name); + if( idx == null ) return update(name,n,nestingLevel-1); // Not found in this scope, recursively look in parent scope + Node old = in(idx); + // If n is null we are looking up rather than updating, hence return existing value + return n==null ? old : setDef(idx,n); + } + + public Node ctrl() { return in(0); } + + /** + * The ctrl of a ScopeNode is always bound to the currently active + * control node in the graph, via a special name '$ctrl' that is not + * a valid identifier in the language grammar and hence cannot be + * referenced in Simple code. + * + * @param n The node to be bound to '$ctrl' + * + * @return Node that was bound + */ + public Node ctrl(Node n) { return setDef(0,n); } + +} diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index 502a2a8e..a615741d 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; import java.util.ArrayList; -/** Chapter 2's view of the IR; browser, transport and layout are shared. */ +/** Chapter 3's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter<Node> { @Override protected boolean dead(Node n) { return n.isDead(); } @Override protected int id(Node n) { return n._nid; } @@ -18,8 +18,9 @@ public class SimpleGraphAdapter extends GraphAdapter<Node> { private ArrayList<Edge> edges(Node n) { var edges = new ArrayList<Edge>(); + String[] names = n instanceof ScopeNode scope && n.nIns() != 0 ? scope.reverseNames() : null; for( int i = 0; i < n.nIns(); i++ ) { - String name = null; + String name = names == null || i >= names.length ? null : names[i]; edges.add(new Edge(i, ref(n.in(i)), role(n, i), name)); } return edges; @@ -33,12 +34,13 @@ public class SimpleGraphAdapter extends GraphAdapter<Node> { } private Kind kind(Node n) { + if( n instanceof ScopeNode ) return Kind.SCOPE; 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( n instanceof ScopeNode || 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 index a17bf796..2dc5d844 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 2's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 3's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture<Node> { private Parser _parser; private Node _ret; @@ -30,6 +30,7 @@ public class SimpleGraphObserver extends GraphCapture<Node> { _parser = null; _ret = null; } + @Override protected Node scope() { return _parser._scope; } @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 index 49edfb5b..311ca23b 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -40,7 +40,7 @@ public class Chapter01Test { new Parser("ret").parse(); fail(); } catch( RuntimeException e ) { - assertEquals("Syntax error, expected a statement: ret",e.getMessage()); + assertEquals("Syntax error, expected =: ",e.getMessage()); } } @@ -82,7 +82,7 @@ public class Chapter01Test { new Parser("return100").parse(); fail(); } catch( RuntimeException e ) { - assertEquals("Syntax error, expected a statement: return100",e.getMessage()); + assertEquals("Syntax error, expected =: ",e.getMessage()); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java new file mode 100644 index 00000000..9a7dda5d --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -0,0 +1,68 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter03Test { + + @Test + public void testVarDecl() { + Parser parser = new Parser("int a=1; return a;"); + ReturnNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testVarAdd() { + Parser parser = new Parser("int a=1; int b=2; return a+b;"); + ReturnNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testVarScope() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); + ReturnNode ret = parser.parse(); + assertEquals("return 4;", ret.print()); + } + + @Test + public void testVarDist() { + Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1);"); + ReturnNode ret = parser.parse(); + assertEquals("return 8;", ret.print()); + } + + @Test + public void testSelfAssign() { + try { + new Parser("int a=a; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'a'",e.getMessage()); + } + } + + @Test + public void testRedeclareVar() { + try { + new Parser("int a=1; int b=2; int c=0; int b=3; c=a+b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Redefining name 'b'",e.getMessage()); + } + } + + @Test + public void testBad1() { + try { + new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected }: ",e.getMessage()); + } + } + +} |