diff options
| -rw-r--r-- | chapter03/README.md | 24 | ||||
| -rw-r--r-- | chapter03/docs/03-graph3.gv | 10 | ||||
| -rw-r--r-- | chapter03/docs/03-graph3.svg | 146 | ||||
| -rw-r--r-- | chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java | 25 | ||||
| -rw-r--r-- | chapter03/src/main/java/com/seaofnodes/simple/Parser.java | 56 | ||||
| -rw-r--r-- | chapter03/src/main/java/com/seaofnodes/simple/node/Node.java | 66 | ||||
| -rw-r--r-- | chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java | 89 | ||||
| -rw-r--r-- | chapter04/README.md | 3 | ||||
| -rw-r--r-- | chapter04/src/main/java/com/seaofnodes/simple/Parser.java | 2 |
9 files changed, 287 insertions, 134 deletions
diff --git a/chapter03/README.md b/chapter03/README.md index 31f3d46a..3e6cebfe 100644 --- a/chapter03/README.md +++ b/chapter03/README.md @@ -17,7 +17,7 @@ Here is the [complete language grammar](docs/03-grammar.md) for this chapter. ## Extensions to Intermediate Representation -In this chapter we do not add new nodes. To recap, our list of Nodes are: +To recap, our list of Nodes are: | Node Name | Type | Description | Inputs | Value | |------------|---------|------------------------------------|------------------------------------------------------------------|-------------------------------------------------------| @@ -30,6 +30,13 @@ In this chapter we do not add new nodes. To recap, our list of Nodes are: | Div | Data | Divide a value by another | Two data nodes, values are divided, order matters | Result of the division | | UnaryMinus | Data | Negate a value | One data node, value is negated | Result of the unary minus | +In this chapter we introduce: + +| Node Name | Type | Description | Inputs | Value | +|-----------|------|--------------------------------|---------------------------------|-------| +| Scope | ? | Represents scopes in the graph | All nodes that define variables | None | + + ## Symbol Tables To support variable declarations and lexical scopes, we introduce symbol tables in the parser. @@ -42,6 +49,19 @@ Declaring a name adds it to the current symbol table. If a name is assigned to, then its mapping in the most recent symbol table is updated. If a name is accessed, its mapping is looked up in the symbol tables. The lookup goes up the stack of symbol tables. +## ScopeNode + +We wrap the stack of symbol tables in a `ScopeNode`. When a name binding is added to a symbol table, +we also make the newly added node an input in the `ScopeNode`. This means that the `ScopeNode` is a user of +all nodes that define new names. + +From an implementation point of view, the symbol table maps names to offsets in the ScopeNode's inputs. + +When a scope is exited, we not only pop the symbol table representing the scope, but also remove the relevant input nodes. + +In the visualization, we show the ScopeNode in a separate box; the stack of symbol tables is shown inside +the box. We show the edge from each variable in the symbol table to the defining Node in the graph. + ## Demonstration We show the output from following code. @@ -68,7 +88,7 @@ see the graph as its initially constructed).  -The diagram shows the symbol tables in the bottom cluster. +The diagram shows the ScopeNode and the symbol tables in the bottom cluster. Each table is annotated by its scope level, and shows the variables defined in that scope. * When we exit the nested scope on line 8, the symbol table at level 1 is popped. diff --git a/chapter03/docs/03-graph3.gv b/chapter03/docs/03-graph3.gv index da30744b..717024e3 100644 --- a/chapter03/docs/03-graph3.gv +++ b/chapter03/docs/03-graph3.gv @@ -3,22 +3,26 @@ digraph chapter03 { subgraph cluster_Nodes { Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; Con_2 [ label="#1" ]; - Con_19 [ label="#8" ]; Con_3 [ label="#2" ]; - Return20 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_19 [ label="#8" ]; Con_4 [ label="#3" ]; + Return20 [ shape=box style=filled fillcolor=yellow label="Return" ]; Con_5 [ label="#4" ]; } node [shape=plaintext]; subgraph cluster_0 { scope0 [label=< <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> - <TR><TD BGCOLOR="aqua">0</TD><TD PORT="scope0_y0">y0</TD><TD PORT="scope0_x0">x0</TD><TD PORT="scope0_y1">y1</TD><TD PORT="scope0_x1">x1</TD></TR> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="scope0_y0">y0</TD><TD PORT="scope0_x0">x0</TD><TD PORT="scope0_y1">y1</TD><TD PORT="scope0_x1">x1</TD></TR> </TABLE>>]; } + Con_2 -> Start1 [style=dotted]; + Con_3 -> Start1 [style=dotted]; Con_19 -> Start1 [style=dotted]; + Con_4 -> Start1 [style=dotted]; Return20 -> Start1 [color=red]; Return20 -> Con_19; + Con_5 -> Start1 [style=dotted]; edge [style=dashed color=cornflowerblue]; scope0:scope0_y0 -> Con_3; scope0:scope0_x0 -> Con_2; diff --git a/chapter03/docs/03-graph3.svg b/chapter03/docs/03-graph3.svg index 3900b93d..3b720323 100644 --- a/chapter03/docs/03-graph3.svg +++ b/chapter03/docs/03-graph3.svg @@ -4,117 +4,141 @@ <!-- Generated by graphviz version 2.43.0 (0) --> <!-- Title: chapter03 Pages: 1 --> -<svg width="394pt" height="292pt" - viewBox="0.00 0.00 394.00 292.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> -<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 288)"> +<svg width="554pt" height="220pt" + viewBox="0.00 0.00 554.00 220.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 216)"> <title>chapter03</title> -<polygon fill="white" stroke="transparent" points="-4,4 -4,-288 390,-288 390,4 -4,4"/> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-216 550,-216 550,4 -4,4"/> <g id="clust1" class="cluster"> <title>cluster_Nodes</title> -<polygon fill="none" stroke="black" points="8,-80 8,-276 378,-276 378,-80 8,-80"/> +<polygon fill="none" stroke="black" points="8,-8 8,-204 386,-204 386,-8 8,-8"/> </g> <g id="clust2" class="cluster"> <title>cluster_0</title> -<polygon fill="none" stroke="black" points="115,-8 115,-60 259,-60 259,-8 115,-8"/> +<polygon fill="none" stroke="black" points="394,-8 394,-60 538,-60 538,-8 394,-8"/> </g> <!-- Start1 --> <g id="node1" class="node"> <title>Start1</title> -<polygon fill="yellow" stroke="black" points="220,-268 166,-268 166,-232 220,-232 220,-268"/> -<text text-anchor="middle" x="193" y="-246.3" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="yellow" stroke="black" points="198,-196 144,-196 144,-160 198,-160 198,-196"/> +<text text-anchor="middle" x="171" y="-174.3" font-family="Times,serif" font-size="14.00">Start</text> </g> <!-- Con_2 --> <g id="node2" class="node"> <title>Con_2</title> -<ellipse fill="none" stroke="black" cx="343" cy="-106" rx="27" ry="18"/> -<text text-anchor="middle" x="343" y="-102.3" font-family="Times,serif" font-size="14.00">#1</text> +<ellipse fill="none" stroke="black" cx="207" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="207" y="-102.3" font-family="Times,serif" font-size="14.00">#1</text> </g> -<!-- Con_19 --> +<!-- Con_2->Start1 --> +<g id="edge1" class="edge"> +<title>Con_2->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M198.65,-123.24C194.46,-131.39 189.27,-141.47 184.53,-150.69"/> +<polygon fill="black" stroke="black" points="181.27,-149.38 179.81,-159.88 187.49,-152.58 181.27,-149.38"/> +</g> +<!-- Con_3 --> <g id="node3" class="node"> +<title>Con_3</title> +<ellipse fill="none" stroke="black" cx="135" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="135" y="-102.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- Con_3->Start1 --> +<g id="edge2" class="edge"> +<title>Con_3->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M143.35,-123.24C147.54,-131.39 152.73,-141.47 157.47,-150.69"/> +<polygon fill="black" stroke="black" points="154.51,-152.58 162.19,-159.88 160.73,-149.38 154.51,-152.58"/> +</g> +<!-- Con_19 --> +<g id="node4" class="node"> <title>Con_19</title> -<ellipse fill="none" stroke="black" cx="216" cy="-178" rx="27" ry="18"/> -<text text-anchor="middle" x="216" y="-174.3" font-family="Times,serif" font-size="14.00">#8</text> +<ellipse fill="none" stroke="black" cx="43" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-102.3" font-family="Times,serif" font-size="14.00">#8</text> </g> <!-- Con_19->Start1 --> -<g id="edge1" class="edge"> +<g id="edge3" class="edge"> <title>Con_19->Start1</title> -<path fill="none" stroke="black" stroke-dasharray="1,5" d="M210.43,-195.95C207.84,-203.82 204.7,-213.38 201.8,-222.21"/> -<polygon fill="black" stroke="black" points="198.47,-221.13 198.68,-231.72 205.12,-223.32 198.47,-221.13"/> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M63.28,-118.09C82.45,-128.57 111.64,-144.54 134.8,-157.2"/> +<polygon fill="black" stroke="black" points="133.21,-160.32 143.67,-162.05 136.57,-154.18 133.21,-160.32"/> </g> -<!-- Con_3 --> -<g id="node4" class="node"> -<title>Con_3</title> -<ellipse fill="none" stroke="black" cx="271" cy="-106" rx="27" ry="18"/> -<text text-anchor="middle" x="271" y="-102.3" font-family="Times,serif" font-size="14.00">#2</text> +<!-- Con_4 --> +<g id="node5" class="node"> +<title>Con_4</title> +<ellipse fill="none" stroke="black" cx="351" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="351" y="-102.3" font-family="Times,serif" font-size="14.00">#3</text> +</g> +<!-- Con_4->Start1 --> +<g id="edge4" class="edge"> +<title>Con_4->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M329.82,-117.38C324.99,-119.65 319.84,-121.97 315,-124 279.07,-139.06 237.19,-154.21 207.89,-164.43"/> +<polygon fill="black" stroke="black" points="206.38,-161.25 198.08,-167.84 208.68,-167.87 206.38,-161.25"/> </g> <!-- Return20 --> -<g id="node5" class="node"> +<g id="node6" class="node"> <title>Return20</title> -<polygon fill="yellow" stroke="black" points="226,-124 160,-124 160,-88 226,-88 226,-124"/> -<text text-anchor="middle" x="193" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +<polygon fill="yellow" stroke="black" points="102,-52 36,-52 36,-16 102,-16 102,-52"/> +<text text-anchor="middle" x="69" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text> </g> <!-- Return20->Start1 --> -<g id="edge2" class="edge"> +<g id="edge5" class="edge"> <title>Return20->Start1</title> -<path fill="none" stroke="red" d="M187.59,-124.47C184.7,-134.71 181.45,-147.96 180,-160 178.08,-175.88 178.08,-180.12 180,-196 181.02,-204.47 182.93,-213.53 184.98,-221.72"/> -<polygon fill="red" stroke="red" points="181.64,-222.77 187.59,-231.53 188.4,-220.97 181.64,-222.77"/> +<path fill="none" stroke="red" d="M71.6,-52.16C75.16,-71.21 83.04,-102.14 99,-124 108.52,-137.04 122.19,-148.23 135.06,-156.92"/> +<polygon fill="red" stroke="red" points="133.48,-160.07 143.79,-162.53 137.27,-154.18 133.48,-160.07"/> </g> <!-- Return20->Con_19 --> -<g id="edge3" class="edge"> +<g id="edge6" class="edge"> <title>Return20->Con_19</title> -<path fill="none" stroke="black" d="M198.69,-124.3C201.25,-132.1 204.33,-141.49 207.18,-150.17"/> -<polygon fill="black" stroke="black" points="203.93,-151.49 210.38,-159.9 210.58,-149.3 203.93,-151.49"/> -</g> -<!-- Con_4 --> -<g id="node6" class="node"> -<title>Con_4</title> -<ellipse fill="none" stroke="black" cx="115" cy="-106" rx="27" ry="18"/> -<text text-anchor="middle" x="115" y="-102.3" font-family="Times,serif" font-size="14.00">#3</text> +<path fill="none" stroke="black" d="M62.57,-52.3C59.6,-60.3 56.01,-69.98 52.71,-78.85"/> +<polygon fill="black" stroke="black" points="49.37,-77.78 49.17,-88.38 55.94,-80.22 49.37,-77.78"/> </g> <!-- Con_5 --> <g id="node7" class="node"> <title>Con_5</title> -<ellipse fill="none" stroke="black" cx="43" cy="-106" rx="27" ry="18"/> -<text text-anchor="middle" x="43" y="-102.3" font-family="Times,serif" font-size="14.00">#4</text> +<ellipse fill="none" stroke="black" cx="279" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="279" y="-102.3" font-family="Times,serif" font-size="14.00">#4</text> +</g> +<!-- Con_5->Start1 --> +<g id="edge7" class="edge"> +<title>Con_5->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M260.19,-119.19C245.23,-128.89 223.89,-142.72 205.84,-154.42"/> +<polygon fill="black" stroke="black" points="203.77,-151.59 197.28,-159.97 207.58,-157.46 203.77,-151.59"/> </g> <!-- scope0 --> <g id="node8" class="node"> <title>scope0</title> -<polygon fill="aqua" stroke="transparent" points="131,-23 131,-44 147,-44 147,-23 131,-23"/> -<polygon fill="none" stroke="black" points="131,-23 131,-44 147,-44 147,-23 131,-23"/> -<text text-anchor="start" x="134" y="-29.8" font-family="Times,serif" font-size="14.00">0</text> -<polygon fill="none" stroke="black" points="147,-23 147,-44 171,-44 171,-23 147,-23"/> -<text text-anchor="start" x="150" y="-29.8" font-family="Times,serif" font-size="14.00">y0</text> -<polygon fill="none" stroke="black" points="171,-23 171,-44 195,-44 195,-23 171,-23"/> -<text text-anchor="start" x="174" y="-29.8" font-family="Times,serif" font-size="14.00">x0</text> -<polygon fill="none" stroke="black" points="195,-23 195,-44 219,-44 219,-23 195,-23"/> -<text text-anchor="start" x="198" y="-29.8" font-family="Times,serif" font-size="14.00">y1</text> -<polygon fill="none" stroke="black" points="219,-23 219,-44 243,-44 243,-23 219,-23"/> -<text text-anchor="start" x="222" y="-29.8" font-family="Times,serif" font-size="14.00">x1</text> +<polygon fill="cyan" stroke="transparent" points="410,-23 410,-44 426,-44 426,-23 410,-23"/> +<polygon fill="none" stroke="black" points="410,-23 410,-44 426,-44 426,-23 410,-23"/> +<text text-anchor="start" x="413" y="-29.8" font-family="Times,serif" font-size="14.00">0</text> +<polygon fill="none" stroke="black" points="426,-23 426,-44 450,-44 450,-23 426,-23"/> +<text text-anchor="start" x="429" y="-29.8" font-family="Times,serif" font-size="14.00">y0</text> +<polygon fill="none" stroke="black" points="450,-23 450,-44 474,-44 474,-23 450,-23"/> +<text text-anchor="start" x="453" y="-29.8" font-family="Times,serif" font-size="14.00">x0</text> +<polygon fill="none" stroke="black" points="474,-23 474,-44 498,-44 498,-23 474,-23"/> +<text text-anchor="start" x="477" y="-29.8" font-family="Times,serif" font-size="14.00">y1</text> +<polygon fill="none" stroke="black" points="498,-23 498,-44 522,-44 522,-23 498,-23"/> +<text text-anchor="start" x="501" y="-29.8" font-family="Times,serif" font-size="14.00">x1</text> </g> <!-- scope0->Con_2 --> -<g id="edge5" class="edge"> +<g id="edge9" class="edge"> <title>scope0:scope0_x0->Con_2</title> -<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M183,-45C183,-102.26 255.22,-55.55 307,-80 310.61,-81.71 314.26,-83.76 317.77,-85.96"/> -<polygon fill="cornflowerblue" stroke="cornflowerblue" points="315.88,-88.9 326.13,-91.56 319.78,-83.09 315.88,-88.9"/> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M462,-45C462,-94.6 290.16,-72.65 243,-88 241.08,-88.63 239.12,-89.33 237.17,-90.09"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="235.39,-87.04 227.58,-94.19 238.15,-93.48 235.39,-87.04"/> </g> <!-- scope0->Con_3 --> -<g id="edge4" class="edge"> +<g id="edge8" class="edge"> <title>scope0:scope0_y0->Con_3</title> -<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M159,-45C159,-82.19 202.71,-61.55 235,-80 238.3,-81.89 241.68,-83.99 244.99,-86.15"/> -<polygon fill="cornflowerblue" stroke="cornflowerblue" points="243.22,-89.18 253.46,-91.9 247.15,-83.39 243.22,-89.18"/> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M438,-45C438,-67.35 411.84,-55.23 390,-60 294.13,-80.94 265.19,-60.49 171,-88 169.06,-88.57 167.09,-89.23 165.13,-89.95"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="163.39,-86.88 155.5,-93.97 166.08,-93.34 163.39,-86.88"/> </g> <!-- scope0->Con_4 --> -<g id="edge7" class="edge"> +<g id="edge11" class="edge"> <title>scope0:scope0_x1->Con_4</title> -<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M231,-45C231,-83.81 184.88,-61.06 151,-80 147.51,-81.95 143.94,-84.15 140.47,-86.42"/> -<polygon fill="cornflowerblue" stroke="cornflowerblue" points="138.44,-83.57 132.14,-92.09 142.37,-89.35 138.44,-83.57"/> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M510,-45C510,-71.13 433.9,-89.82 387,-98.86"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="386.09,-95.47 376.9,-100.75 387.37,-102.35 386.09,-95.47"/> </g> <!-- scope0->Con_5 --> -<g id="edge6" class="edge"> +<g id="edge10" class="edge"> <title>scope0:scope0_y1->Con_5</title> -<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M207,-45C207,-103.98 132.44,-55.04 79,-80 75.38,-81.69 71.73,-83.74 68.22,-85.93"/> -<polygon fill="cornflowerblue" stroke="cornflowerblue" points="66.21,-83.06 59.85,-91.53 70.11,-88.87 66.21,-83.06"/> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M486,-45C486,-123.37 388.78,-61.59 315,-88 313.15,-88.66 311.26,-89.39 309.37,-90.16"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="307.8,-87.02 300.03,-94.23 310.6,-93.44 307.8,-87.02"/> </g> </g> </svg> diff --git a/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index 5f3f52d0..dc5358f4 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -1,9 +1,6 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.node.ConstantNode; -import com.seaofnodes.simple.node.Control; -import com.seaofnodes.simple.node.Node; -import com.seaofnodes.simple.node.StartNode; +import com.seaofnodes.simple.node.*; import java.util.*; @@ -33,13 +30,13 @@ public class GraphVisualizer { nodes(sb, all); // Now the scopes, in a cluster no edges - scopes(sb, parser._scopes); + scopes(sb, parser._scope); // Walk the Node edges nodeEdges(sb, all); // Walk the Scope edges - scopeEdges(sb, parser._scopes); + scopeEdges(sb, parser._scope); sb.append("}\n"); return sb.toString(); @@ -61,10 +58,10 @@ public class GraphVisualizer { sb.append("\t}\n"); // End Node cluster } - private void scopes( StringBuilder sb, Stack<HashMap<String,Node>> scopes) { + private void scopes( StringBuilder sb, ScopeNode scopenode) { sb.append("\tnode [shape=plaintext];\n"); int level=0; - for( HashMap<String,Node> scope : scopes ) { + for( HashMap<String,Integer> scope : scopenode._scopes ) { sb.append("\tsubgraph cluster_").append(level).append(" {\n"); // Magic "cluster_" in the subgraph name String scopeName = makeScopeName(level); sb.append("\t\t").append(scopeName).append(" [label=<\n"); @@ -102,13 +99,13 @@ public class GraphVisualizer { } // Walk the scope edges - private void scopeEdges( StringBuilder sb, Stack<HashMap<String,Node>> scopes) { + private void scopeEdges( StringBuilder sb, ScopeNode scopenode ) { sb.append("\tedge [style=dashed color=cornflowerblue];\n"); int level=0; - for( HashMap<String,Node> scope : scopes ) { + for( HashMap<String,Integer> scope : scopenode._scopes ) { String scopeName = makeScopeName(level); for( String name : scope.keySet() ) - sb.append("\t").append(scopeName).append(":").append(makePortName(scopeName, name)).append(" -> ").append(scope.get(name).uniqueName()).append(";\n"); + sb.append("\t").append(scopeName).append(":").append(makePortName(scopeName, name)).append(" -> ").append(scopenode.in(scope.get(name)).uniqueName()).append(";\n"); level++; } } @@ -126,9 +123,9 @@ public class GraphVisualizer { for( Node n : start._outputs ) walk(all, n); // Scan symbol tables - for( HashMap<String,Node> scope : parser._scopes ) - for (Node n : scope.values()) - walk(all, n); + for( HashMap<String,Integer> scope : parser._scope._scopes ) + for (Integer i : scope.values()) + walk(all, parser._scope.in(i)); return all.values(); } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java index 13b25e60..12e156ed 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java @@ -26,15 +26,14 @@ public class Parser { 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. + * 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 Stack<HashMap<String, Node>> _scopes; + public ScopeNode _scope; public Parser(String source) { _lexer = new Lexer(source); - _scopes = new Stack<>(); + _scope = new ScopeNode(); Node.reset(); START = new StartNode(); } @@ -43,35 +42,6 @@ public class Parser { return (ReturnNode) parseBlock(); } - // Create a new name in current scope - private Node define(String name, Node n) { - // new name - _scopes.lastElement().put(name, n); - return n; - } - - // If the name is present in any scope, then redefine - private Node update(String name, Node n) { - for (int i = _scopes.size() - 1; i >= 0; i--) { - HashMap<String, Node> scope = _scopes.get(i); - Node old = scope.get(name); - if (old != null) { // Found prior def - if (old.nOuts() == 0) old.kill(); // Delete old ref - scope.put(name, n); // Update existing ref - return n; - } - } - throw error("Undefined name '" + name + "'"); - } - - // Lookup a name in all scopes - private Node lookup(String name) { - for (int i = _scopes.size() - 1; i >= 0; i--) { - var n = _scopes.get(i).get(name); - if (n != null) return n; - } - throw error("Undefined name '" + name + "'"); - } /** * Parses a block @@ -82,14 +52,14 @@ public class Parser { */ private Node parseBlock() { // Enter a new scope - _scopes.push(new HashMap<>()); + _scope.push(); Node n = null; while (!match("}") && !_lexer.isEOF()) { Node n0 = parseStatement(); if (n0 != null) n = n0; // Allow null returns from eg showGraph } // Exit scope - _scopes.pop(); + _scope.pop(); return n; } @@ -140,7 +110,9 @@ public class Parser { var name = requireId(); require("="); var expr = require(parseExpression(), ";"); - return update(name, expr); + if( _scope.update(name, expr)==null ) + throw error("Undefined name '" + name + "'"); + return expr; } /** @@ -155,7 +127,9 @@ public class Parser { var name = requireId(); require("="); var expr = require(parseExpression(), ";"); - return define(name, expr); + if( _scope.define(name,expr) == null ) + throw error("Redefining name '" + name + "'"); + return expr; } /** @@ -217,7 +191,11 @@ public class Parser { private Node parsePrimary() { if (_lexer.isNumber()) return parseIntegerLiteral(); if (match("(")) return require(parseExpression(), ")"); - return lookup(requireId()); + String name = requireId(); + Node id = _scope.lookup(name); + if( id==null ) + throw error("Undefined name '" + name + "'"); + return id; } /** diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java index 5528f296..6b7d673a 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java @@ -152,27 +152,65 @@ public abstract class Node { * @param idx which def to set * @param new_def the new definition */ - void set_def(int idx, Node new_def ) { + Node set_def(int idx, Node new_def ) { Node old_def = in(idx); - if( old_def != null ) { // If the old def exists, remove a use->def edge - ArrayList<Node> outs = old_def._outputs; - int lidx = outs.size()-1; // Last index - - // This 1-line hack compresses an element out of an ArrayList - // without having to copy the contents. The last element is - // stuffed over the deleted element, and then the size is reduced. - outs.set(outs.indexOf(this),outs.get(lidx)); - outs.remove(lidx); // Reduce ArrayList size without copying anything - if( lidx == 0 ) // If we removed the last use, the old def is now dead + if( old_def == new_def ) return this; // No change + if( old_def != null && // If the old def exists, remove a def->use edge + old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def - } // Set the new_def over the old (killed) edge _inputs.set(idx,new_def); - // If new def is not null, add the corresponding use->def edge + // If new def is not null, add the corresponding def->use edge if( new_def != null ) new_def._outputs.add(this); + // Return self for easy flow-coding + return this; + } + + /** + * 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 add_def(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._outputs.add(this); + return new_def; + } + + + // Breaks the edge invariants, used temporarily + private void addUse(Node n) { _outputs.add(n); } + + // Remove node 'use' from 'def's (i.e. our) output list, by compressing the list in-place. + // Return true if the output list is empty afterward. + // Error is 'use' does not exist; ok for 'use' to be null. + private boolean delUse( Node use ) { + ArrayList<Node> outs = _outputs; + int lidx = outs.size()-1; // Last index + // This 1-line hack compresses an element out of an ArrayList + // without having to copy the contents. The last element is + // stuffed over the deleted element, and then the size is reduced. + outs.set(outs.indexOf(use),outs.get(lidx)); + outs.remove(lidx); // Reduce ArrayList size without copying anything + return lidx==0; + } + + // Shortcut for "popping" n nodes. A "pop" is basically a + // set_def(last,null) followed by lowering the nIns() count. + void pop_n(int n) { + for( int i=0; i<n; i++ ) { + Node old_def = _inputs.remove(_inputs.size()-1); + 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 + } } - /** * Current computed type for this Node. This value changes as the graph diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java new file mode 100644 index 00000000..c7d6edb9 --- /dev/null +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -0,0 +1,89 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.TypeBot; + +import java.util.HashMap; +import java.util.Stack; + +/** + * The Scope node is a purely parser helper - it tracks names to nodes with a + * stack of scopes. + */ +public class ScopeNode extends Node { + + /** + * 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 final Stack<HashMap<String, Integer>> _scopes = new Stack<>(); + + @Override + public String label() { return "Scope"; } + + @Override + StringBuilder _print(StringBuilder sb) { + 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._print(sb); + } + sb.append("]"); + } + return sb; + } + + @Override + public TypeBot compute() { return TypeBot.BOTTOM; } + + @Override + public Node idealize() { return null; } + + // Add an empty lexical scope + public void push() { + _scopes.push(new HashMap<>()); + } + + // Remove the current lexical scope, killing all unused nodes. + public void pop() { + HashMap<String,Integer> scope = _scopes.pop(); + pop_n(scope.size()); + } + + // Create a new name in the current scope + public Node define( String name, Node n ) { + HashMap<String,Integer> scope = _scopes.lastElement(); + if( scope.put(name,nIns()) != null ) + return null; // Double define + return add_def(n); + } + + // Lookup a name in all scopes + public Node lookup(String name) { + for (int i = _scopes.size() - 1; i >= 0; i--) { + var idx = _scopes.get(i).get(name); + if (idx != null) return in(idx); + } + return null; + } + + + // If the name is present in any scope, then redefine + public Node update(String name, Node n) { + for (int i = _scopes.size() - 1; i >= 0; i--) { + HashMap<String, Integer> scope = _scopes.get(i); + Integer idx = scope.get(name); + if (idx != null) // Found prior def + return set_def(idx,n); // Update def in scope + } + return null; + } + + +} diff --git a/chapter04/README.md b/chapter04/README.md index 7e8a8eea..45d054de 100644 --- a/chapter04/README.md +++ b/chapter04/README.md @@ -33,6 +33,7 @@ Below is our list of Nodes from [Chapter 3](../chapter03/README.md): | Mul | Data | Multiply two values | Two data nodes, values are multiplied, order not important | Result of the multiply | | Div | Data | Divide a value by another | Two data nodes, values are divided, order matters | Result of the division | | UnaryMinus | Data | Negate a value | One data node, value is negated | Result of the unary minus | +| Scope | ? | Represents scopes in the graph | All nodes that define variables | None | ## Projection Nodes @@ -228,7 +229,7 @@ The peephole method does following: private Node deadCodeElim(Node m) { // If self is going dead and not being returned here (Nodes returned // from peephole commonly have no uses (yet)), then kill self. - if( m != this && isDead() ) { + if( m != this && isUnused() ) { // Killing self - and since self recursively kills self's inputs we // might end up killing 'm', which we are returning as a live Node. // So we add a bogus extra null output edge to stop kill(). diff --git a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java index a6872106..147515f6 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java @@ -45,6 +45,8 @@ public class Parser { String src() { return new String( _lexer._input ); } + + public ReturnNode parse() { _scope.push(); try { |
