diff options
Diffstat (limited to 'chapter03')
25 files changed, 1932 insertions, 0 deletions
diff --git a/chapter03/README.md b/chapter03/README.md new file mode 100644 index 00000000..31f3d46a --- /dev/null +++ b/chapter03/README.md @@ -0,0 +1,98 @@ +# Chapter 3 + +In this chapter we extend the language grammar to allow variable declarations. This allows us to write: + +``` +int a=1; +int b=2; +int c=0; +{ + int b=3; + c=a+b; +} +return c; +``` + +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: + +| Node Name | Type | Description | Inputs | Value | +|------------|---------|------------------------------------|------------------------------------------------------------------|-------------------------------------------------------| +| Start | Control | Start of function | None | None for now as we do not have function arguments yet | +| Return | Control | End of function | Predecessor control node, Data node value | Return value of the function | +| Constant | Data | Constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant | +| Add | Data | Add two values | Two data nodes, values are added, order not important | Result of the add operation | +| Sub | Data | Subtract a value from another | Two data nodes, values are subtracted, order matters | Result of the subtract | +| 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 | + +## Symbol Tables + +To support variable declarations and lexical scopes, we introduce symbol tables in the parser. +A symbol table maps names to nodes. +We maintain a stack of symbol tables. +When a new scope is created, we push a new symbol table to the stack, when scope exits, the topmost symbol table is popped +from the stack. + +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. + +## Demonstration + +We show the output from following code. + +``` +01 int a=1; +02 int b=2; +03 int c=0; +04 { +05 int b=3; +07 c=a+b; +08 } +09 return c; +``` + +* When we start parsing above, we start with a symbol table (level 0). +The variables `a`, `b`, and `c` are registered in this table. +* On line 4, we start a nested scope. At this point, a new symbol table is pushed (level 1). +* On line 5, a variable `b` is declared. `b` is registered in the symbol table at level 1. This then +hides the variable with the same name on line 2. +* On line 7, we update the variable `c`. Variable lookup will find it in the symbol table at level 0. +The node graph is shown below (note that peephole opts are switched off here so that we can +see the graph as its initially constructed). + + + +The diagram shows 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. +* At line 9, our graph looks like this: + + + +As we see, only 1 symbol table is present at this point. + +## Enabling peephole optimizations + +Once we enable peephole optimizations, the parser is able to reduce all the expressions down to a +constant. This is illustrated nicely below. + +``` +01 int x0=1; +02 int y0=2; +03 int x1=3; +04 int y1=4; +05 return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); +``` + +The graph for above, is displayed below. + + + +The return node has the constant `8` as its data value!
\ No newline at end of file diff --git a/chapter03/docs/03-grammar.md b/chapter03/docs/03-grammar.md new file mode 100644 index 00000000..2a6d4c1b --- /dev/null +++ b/chapter03/docs/03-grammar.md @@ -0,0 +1,72 @@ +# Grammar for Chapter 1 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | metaStatement + ; + +metaStatement + : '#showGraph' ';' + ; + +expressionStatement + : IDENTIFIER '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : additiveExpression + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | '(' expression ')' + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +```
\ No newline at end of file diff --git a/chapter03/docs/03-graph1.gv b/chapter03/docs/03-graph1.gv new file mode 100644 index 00000000..5983f622 --- /dev/null +++ b/chapter03/docs/03-graph1.gv @@ -0,0 +1,33 @@ +digraph chapter03 { + rankdir=BT; + subgraph cluster_Nodes { + Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_2 [ label="#1" ]; + Con_3 [ label="#2" ]; + Con_5 [ label="#3" ]; + Add6 [ label="Add" ]; + } + node [shape=plaintext]; + subgraph cluster_0 { + scope0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="aqua">0</TD><TD PORT="scope0_a">a</TD><TD PORT="scope0_b">b</TD><TD PORT="scope0_c">c</TD></TR> + </TABLE>>]; + subgraph cluster_1 { + scope1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="aqua">1</TD><TD PORT="scope1_b">b</TD></TR> + </TABLE>>]; + } + } + Con_2 -> Start1 [style=dotted]; + Con_3 -> Start1 [style=dotted]; + Con_5 -> Start1 [style=dotted]; + Add6 -> Con_2; + Add6 -> Con_5; + edge [style=dashed color=cornflowerblue]; + scope0:scope0_a -> Con_2; + scope0:scope0_b -> Con_3; + scope0:scope0_c -> Add6; + scope1:scope1_b -> Con_5; +} diff --git a/chapter03/docs/03-graph1.svg b/chapter03/docs/03-graph1.svg new file mode 100644 index 00000000..364cd42c --- /dev/null +++ b/chapter03/docs/03-graph1.svg @@ -0,0 +1,131 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.43.0 (0) + --> +<!-- Title: chapter03 Pages: 1 --> +<svg width="238pt" height="300pt" + viewBox="0.00 0.00 238.00 300.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 296)"> +<title>chapter03</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-296 234,-296 234,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-88 8,-284 222,-284 222,-88 8,-88"/> +</g> +<g id="clust2" class="cluster"> +<title>cluster_0</title> +<polygon fill="none" stroke="black" points="36,-8 36,-76 210,-76 210,-8 36,-8"/> +</g> +<g id="clust3" class="cluster"> +<title>cluster_1</title> +<polygon fill="none" stroke="black" points="132,-16 132,-68 202,-68 202,-16 132,-16"/> +</g> +<!-- Start1 --> +<g id="node1" class="node"> +<title>Start1</title> +<polygon fill="yellow" stroke="black" points="142,-276 88,-276 88,-240 142,-240 142,-276"/> +<text text-anchor="middle" x="115" y="-254.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="43" cy="-186" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-182.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- Con_2->Start1 --> +<g id="edge1" class="edge"> +<title>Con_2->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M57.57,-201.17C66.92,-210.25 79.3,-222.29 90.17,-232.86"/> +<polygon fill="black" stroke="black" points="87.79,-235.43 97.4,-239.89 92.67,-230.41 87.79,-235.43"/> +</g> +<!-- Con_3 --> +<g id="node3" class="node"> +<title>Con_3</title> +<ellipse fill="none" stroke="black" cx="115" cy="-186" rx="27" ry="18"/> +<text text-anchor="middle" x="115" y="-182.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="M115,-204.3C115,-212.02 115,-221.29 115,-229.89"/> +<polygon fill="black" stroke="black" points="111.5,-229.9 115,-239.9 118.5,-229.9 111.5,-229.9"/> +</g> +<!-- Con_5 --> +<g id="node4" class="node"> +<title>Con_5</title> +<ellipse fill="none" stroke="black" cx="187" cy="-186" rx="27" ry="18"/> +<text text-anchor="middle" x="187" y="-182.3" font-family="Times,serif" font-size="14.00">#3</text> +</g> +<!-- Con_5->Start1 --> +<g id="edge3" class="edge"> +<title>Con_5->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M172.43,-201.17C163.08,-210.25 150.7,-222.29 139.83,-232.86"/> +<polygon fill="black" stroke="black" points="137.33,-230.41 132.6,-239.89 142.21,-235.43 137.33,-230.41"/> +</g> +<!-- Add6 --> +<g id="node5" class="node"> +<title>Add6</title> +<ellipse fill="none" stroke="black" cx="138" cy="-114" rx="28.7" ry="18"/> +<text text-anchor="middle" x="138" y="-110.3" font-family="Times,serif" font-size="14.00">Add</text> +</g> +<!-- Add6->Con_2 --> +<g id="edge4" class="edge"> +<title>Add6->Con_2</title> +<path fill="none" stroke="black" d="M120.13,-128.17C105.58,-138.89 84.84,-154.17 68.53,-166.18"/> +<polygon fill="black" stroke="black" points="66.44,-163.38 60.47,-172.13 70.59,-169.01 66.44,-163.38"/> +</g> +<!-- Add6->Con_5 --> +<g id="edge5" class="edge"> +<title>Add6->Con_5</title> +<path fill="none" stroke="black" d="M149.12,-130.88C155.32,-139.74 163.17,-150.96 170.12,-160.88"/> +<polygon fill="black" stroke="black" points="167.32,-162.99 175.93,-169.18 173.06,-158.98 167.32,-162.99"/> +</g> +<!-- scope0 --> +<g id="node6" class="node"> +<title>scope0</title> +<polygon fill="aqua" stroke="transparent" points="53,-31 53,-52 69,-52 69,-31 53,-31"/> +<polygon fill="none" stroke="black" points="53,-31 53,-52 69,-52 69,-31 53,-31"/> +<text text-anchor="start" x="56" y="-37.8" font-family="Times,serif" font-size="14.00">0</text> +<polygon fill="none" stroke="black" points="69,-31 69,-52 84,-52 84,-31 69,-31"/> +<text text-anchor="start" x="72" y="-37.8" font-family="Times,serif" font-size="14.00">a</text> +<polygon fill="none" stroke="black" points="84,-31 84,-52 100,-52 100,-31 84,-31"/> +<text text-anchor="start" x="87" y="-37.8" font-family="Times,serif" font-size="14.00">b</text> +<polygon fill="none" stroke="black" points="100,-31 100,-52 114,-52 114,-31 100,-31"/> +<text text-anchor="start" x="103" y="-37.8" font-family="Times,serif" font-size="14.00">c</text> +</g> +<!-- scope0->Con_2 --> +<g id="edge6" class="edge"> +<title>scope0:scope0_a->Con_2</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M76,-53C76,-90.54 63.29,-132.33 53.64,-158.64"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="50.27,-157.66 50,-168.25 56.81,-160.14 50.27,-157.66"/> +</g> +<!-- scope0->Con_3 --> +<g id="edge7" class="edge"> +<title>scope0:scope0_b->Con_3</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M92,-53C92,-88.29 93.39,-97.33 100,-132 101.65,-140.68 104.07,-150 106.48,-158.37"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="103.14,-159.42 109.37,-168 109.85,-157.41 103.14,-159.42"/> +</g> +<!-- scope0->Add6 --> +<g id="edge8" class="edge"> +<title>scope0:scope0_c->Add6</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M107,-53C107,-65.88 112.71,-78.75 119.22,-89.25"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="116.52,-91.5 125.03,-97.81 122.31,-87.57 116.52,-91.5"/> +</g> +<!-- scope1 --> +<g id="node7" class="node"> +<title>scope1</title> +<polygon fill="aqua" stroke="transparent" points="151,-31 151,-52 167,-52 167,-31 151,-31"/> +<polygon fill="none" stroke="black" points="151,-31 151,-52 167,-52 167,-31 151,-31"/> +<text text-anchor="start" x="154" y="-37.8" font-family="Times,serif" font-size="14.00">1</text> +<polygon fill="none" stroke="black" points="167,-31 167,-52 183,-52 183,-31 167,-31"/> +<text text-anchor="start" x="170" y="-37.8" font-family="Times,serif" font-size="14.00">b</text> +</g> +<!-- scope1->Con_5 --> +<g id="edge9" class="edge"> +<title>scope1:scope1_b->Con_5</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M175,-53C175,-89.4 179.58,-131.23 183.08,-157.87"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="179.64,-158.52 184.46,-167.96 186.58,-157.58 179.64,-158.52"/> +</g> +</g> +</svg> diff --git a/chapter03/docs/03-graph2.gv b/chapter03/docs/03-graph2.gv new file mode 100644 index 00000000..c6c55028 --- /dev/null +++ b/chapter03/docs/03-graph2.gv @@ -0,0 +1,29 @@ +digraph chapter03 { + rankdir=BT; + subgraph cluster_Nodes { + Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_2 [ label="#1" ]; + Con_3 [ label="#2" ]; + Con_5 [ label="#3" ]; + Add6 [ label="Add" ]; + Return7 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + node [shape=plaintext]; + subgraph cluster_0 { + scope0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="aqua">0</TD><TD PORT="scope0_a">a</TD><TD PORT="scope0_b">b</TD><TD PORT="scope0_c">c</TD></TR> + </TABLE>>]; + } + Con_2 -> Start1 [style=dotted]; + Con_3 -> Start1 [style=dotted]; + Con_5 -> Start1 [style=dotted]; + Add6 -> Con_2; + Add6 -> Con_5; + Return7 -> Start1 [color=red]; + Return7 -> Add6; + edge [style=dashed color=cornflowerblue]; + scope0:scope0_a -> Con_2; + scope0:scope0_b -> Con_3; + scope0:scope0_c -> Add6; +} diff --git a/chapter03/docs/03-graph2.svg b/chapter03/docs/03-graph2.svg new file mode 100644 index 00000000..4ab5a8b6 --- /dev/null +++ b/chapter03/docs/03-graph2.svg @@ -0,0 +1,130 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.43.0 (0) + --> +<!-- Title: chapter03 Pages: 1 --> +<svg width="360pt" height="292pt" + viewBox="0.00 0.00 360.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)"> +<title>chapter03</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-288 356,-288 356,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-276 242,-276 242,-8 8,-8"/> +</g> +<g id="clust2" class="cluster"> +<title>cluster_0</title> +<polygon fill="none" stroke="black" points="250,-8 250,-60 344,-60 344,-8 250,-8"/> +</g> +<!-- Start1 --> +<g id="node1" class="node"> +<title>Start1</title> +<polygon fill="yellow" stroke="black" points="126,-268 72,-268 72,-232 126,-232 126,-268"/> +<text text-anchor="middle" x="99" y="-246.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="135" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="135" y="-174.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- Con_2->Start1 --> +<g id="edge1" class="edge"> +<title>Con_2->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M126.65,-195.24C122.46,-203.39 117.27,-213.47 112.53,-222.69"/> +<polygon fill="black" stroke="black" points="109.27,-221.38 107.81,-231.88 115.49,-224.58 109.27,-221.38"/> +</g> +<!-- Con_3 --> +<g id="node3" class="node"> +<title>Con_3</title> +<ellipse fill="none" stroke="black" cx="207" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="207" y="-174.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="M188.19,-191.19C173.23,-200.89 151.89,-214.72 133.84,-226.42"/> +<polygon fill="black" stroke="black" points="131.77,-223.59 125.28,-231.97 135.58,-229.46 131.77,-223.59"/> +</g> +<!-- Con_5 --> +<g id="node4" class="node"> +<title>Con_5</title> +<ellipse fill="none" stroke="black" cx="63" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="63" y="-174.3" font-family="Times,serif" font-size="14.00">#3</text> +</g> +<!-- Con_5->Start1 --> +<g id="edge3" class="edge"> +<title>Con_5->Start1</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M71.35,-195.24C75.54,-203.39 80.73,-213.47 85.47,-222.69"/> +<polygon fill="black" stroke="black" points="82.51,-224.58 90.19,-231.88 88.73,-221.38 82.51,-224.58"/> +</g> +<!-- Add6 --> +<g id="node5" class="node"> +<title>Add6</title> +<ellipse fill="none" stroke="black" cx="89" cy="-106" rx="28.7" ry="18"/> +<text text-anchor="middle" x="89" y="-102.3" font-family="Times,serif" font-size="14.00">Add</text> +</g> +<!-- Add6->Con_2 --> +<g id="edge4" class="edge"> +<title>Add6->Con_2</title> +<path fill="none" stroke="black" d="M99.44,-122.88C105.2,-131.66 112.48,-142.74 118.96,-152.58"/> +<polygon fill="black" stroke="black" points="116.19,-154.74 124.6,-161.18 122.04,-150.9 116.19,-154.74"/> +</g> +<!-- Add6->Con_5 --> +<g id="edge5" class="edge"> +<title>Add6->Con_5</title> +<path fill="none" stroke="black" d="M82.84,-123.59C79.84,-131.66 76.16,-141.57 72.79,-150.65"/> +<polygon fill="black" stroke="black" points="69.5,-149.45 69.3,-160.04 76.06,-151.89 69.5,-149.45"/> +</g> +<!-- Return7 --> +<g id="node6" class="node"> +<title>Return7</title> +<polygon fill="yellow" stroke="black" points="96,-52 30,-52 30,-16 96,-16 96,-52"/> +<text text-anchor="middle" x="63" y="-30.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Return7->Start1 --> +<g id="edge6" class="edge"> +<title>Return7->Start1</title> +<path fill="none" stroke="red" d="M51.87,-52.38C33.84,-82.96 2.57,-147.69 27,-196 34.7,-211.23 49.06,-223.15 62.94,-231.8"/> +<polygon fill="red" stroke="red" points="61.52,-235.02 71.92,-237.01 65.03,-228.96 61.52,-235.02"/> +</g> +<!-- Return7->Add6 --> +<g id="edge7" class="edge"> +<title>Return7->Add6</title> +<path fill="none" stroke="black" d="M69.43,-52.3C72.4,-60.3 75.99,-69.98 79.29,-78.85"/> +<polygon fill="black" stroke="black" points="76.06,-80.22 82.83,-88.38 82.63,-77.78 76.06,-80.22"/> +</g> +<!-- scope0 --> +<g id="node7" class="node"> +<title>scope0</title> +<polygon fill="aqua" stroke="transparent" points="267,-23 267,-44 283,-44 283,-23 267,-23"/> +<polygon fill="none" stroke="black" points="267,-23 267,-44 283,-44 283,-23 267,-23"/> +<text text-anchor="start" x="270" y="-29.8" font-family="Times,serif" font-size="14.00">0</text> +<polygon fill="none" stroke="black" points="283,-23 283,-44 298,-44 298,-23 283,-23"/> +<text text-anchor="start" x="286" y="-29.8" font-family="Times,serif" font-size="14.00">a</text> +<polygon fill="none" stroke="black" points="298,-23 298,-44 314,-44 314,-23 298,-23"/> +<text text-anchor="start" x="301" y="-29.8" font-family="Times,serif" font-size="14.00">b</text> +<polygon fill="none" stroke="black" points="314,-23 314,-44 328,-44 328,-23 314,-23"/> +<text text-anchor="start" x="317" y="-29.8" font-family="Times,serif" font-size="14.00">c</text> +</g> +<!-- scope0->Con_2 --> +<g id="edge8" class="edge"> +<title>scope0:scope0_a->Con_2</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M290,-45C290,-77.9 208.02,-132.76 163.3,-160.24"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="161.36,-157.33 154.63,-165.51 164.99,-163.31 161.36,-157.33"/> +</g> +<!-- scope0->Con_3 --> +<g id="edge9" class="edge"> +<title>scope0:scope0_b->Con_3</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M306,-45C306,-93.23 263.17,-135.12 233.85,-158.15"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="231.47,-155.56 225.62,-164.4 235.7,-161.14 231.47,-155.56"/> +</g> +<!-- scope0->Add6 --> +<g id="edge10" class="edge"> +<title>scope0:scope0_c->Add6</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M321,-45C321,-86.77 178.12,-76.36 138,-88 132.99,-89.45 127.75,-91.12 122.62,-92.82"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="121.34,-89.56 113.02,-96.11 123.61,-96.18 121.34,-89.56"/> +</g> +</g> +</svg> diff --git a/chapter03/docs/03-graph3.gv b/chapter03/docs/03-graph3.gv new file mode 100644 index 00000000..da30744b --- /dev/null +++ b/chapter03/docs/03-graph3.gv @@ -0,0 +1,28 @@ +digraph chapter03 { + rankdir=BT; + 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_4 [ label="#3" ]; + 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> + </TABLE>>]; + } + Con_19 -> Start1 [style=dotted]; + Return20 -> Start1 [color=red]; + Return20 -> Con_19; + edge [style=dashed color=cornflowerblue]; + scope0:scope0_y0 -> Con_3; + scope0:scope0_x0 -> Con_2; + scope0:scope0_y1 -> Con_5; + scope0:scope0_x1 -> Con_4; +} + diff --git a/chapter03/docs/03-graph3.svg b/chapter03/docs/03-graph3.svg new file mode 100644 index 00000000..3900b93d --- /dev/null +++ b/chapter03/docs/03-graph3.svg @@ -0,0 +1,120 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- 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)"> +<title>chapter03</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-288 390,-288 390,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"/> +</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"/> +</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> +</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> +</g> +<!-- Con_19 --> +<g id="node3" 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> +</g> +<!-- Con_19->Start1 --> +<g id="edge1" 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"/> +</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> +</g> +<!-- Return20 --> +<g id="node5" 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> +</g> +<!-- Return20->Start1 --> +<g id="edge2" 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"/> +</g> +<!-- Return20->Con_19 --> +<g id="edge3" 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> +</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> +</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> +</g> +<!-- scope0->Con_2 --> +<g id="edge5" 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"/> +</g> +<!-- scope0->Con_3 --> +<g id="edge4" 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"/> +</g> +<!-- scope0->Con_4 --> +<g id="edge7" 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"/> +</g> +<!-- scope0->Con_5 --> +<g id="edge6" 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"/> +</g> +</g> +</svg> diff --git a/chapter03/pom.xml b/chapter03/pom.xml new file mode 100644 index 00000000..a484d5bd --- /dev/null +++ b/chapter03/pom.xml @@ -0,0 +1,14 @@ +<?xml version="1.0" encoding="UTF-8"?> +<project xmlns="http://maven.apache.org/POM/4.0.0" + xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" + xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"> + <modelVersion>4.0.0</modelVersion> + <parent> + <groupId>com.seaofnodes</groupId> + <artifactId>simple</artifactId> + <version>1.0</version> + </parent> + <artifactId>chapter03</artifactId> + <packaging>jar</packaging> + <name>Chapter 3</name> +</project>
\ No newline at end of file diff --git a/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java new file mode 100644 index 00000000..5f3f52d0 --- /dev/null +++ b/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -0,0 +1,145 @@ +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 java.util.*; + +/** + * Simple visualizer that outputs GraphViz dot format. + * The dot output must be saved to a file and run manually via dot to generate the SVG output. + * Currently, this is done manually. + */ +public class GraphVisualizer { + + public String generateDotOutput(Parser parser) { + + // Since the graph has cycles, we need to create a flat list of all the + // nodes in the graph. + Collection<Node> all = findAll(parser); + StringBuilder sb = new StringBuilder(); + sb.append("digraph chapter03 {\n"); + + // To keep the Scopes below the graph and pointing up into the graph we + // need to group the Nodes in a subgraph cluster, and the scopes into a + // different subgraph cluster. THEN we can draw edges between the + // scopes and nodes. If we try to cross subgraph cluster borders while + // still making the subgraphs DOT gets confused. + sb.append("\trankdir=BT;\n"); // Force Nodes before Scopes + + // Just the Nodes first, in a cluster no edges + nodes(sb, all); + + // Now the scopes, in a cluster no edges + scopes(sb, parser._scopes); + + // Walk the Node edges + nodeEdges(sb, all); + + // Walk the Scope edges + scopeEdges(sb, parser._scopes); + + sb.append("}\n"); + return sb.toString(); + } + + + private void nodes(StringBuilder sb, Collection<Node> all) { + // Just the Nodes first, in a cluster no edges + sb.append("\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name + for( Node n : all ) { + sb.append("\t\t").append(n.uniqueName()).append(" [ "); + // control nodes have box shape + // other nodes are ellipses, i.e. default shape + if( n instanceof Control ) + sb.append("shape=box style=filled fillcolor=yellow "); + sb.append("label=\"").append(n.label()).append("\" "); + sb.append("];\n"); + } + sb.append("\t}\n"); // End Node cluster + } + + private void scopes( StringBuilder sb, Stack<HashMap<String,Node>> scopes) { + sb.append("\tnode [shape=plaintext];\n"); + int level=0; + for( HashMap<String,Node> scope : 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"); + sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n"); + // Add the scope level + sb.append("\t\t\t<TR><TD BGCOLOR=\"aqua\">").append(level).append("</TD>"); + for( String name : scope.keySet() ) + sb.append("<TD PORT=\"").append(makePortName(scopeName, name)).append("\">").append(name).append("</TD>"); + sb.append("</TR>\n"); + sb.append("\t\t\t</TABLE>>];\n"); + level++; + } + // Scope clusters nest, so the graphics shows the nested scopes, so + // they are not closed as they are printed; so they just keep nesting. + // We close them all at once here. + sb.append( "\t}\n".repeat( level ) ); // End all Scope clusters + } + + private String makeScopeName(int level) { return "scope" + level; } + private String makePortName(String scopeName, String varName) { return scopeName + "_" + varName; } + + // Walk the node edges + private void nodeEdges(StringBuilder sb, Collection<Node> all) { + for( Node n : all ) + for( Node out : n._inputs ) + if( out != null ) { + sb.append('\t').append(n.uniqueName()).append(" -> ").append(out.uniqueName()); + // Control edges are colored red + if( n instanceof ConstantNode && out instanceof StartNode ) + sb.append(" [style=dotted]"); + else if( n instanceof Control && out instanceof Control ) + sb.append(" [color=red]"); + sb.append(";\n"); + } + } + + // Walk the scope edges + private void scopeEdges( StringBuilder sb, Stack<HashMap<String,Node>> scopes) { + sb.append("\tedge [style=dashed color=cornflowerblue];\n"); + int level=0; + for( HashMap<String,Node> scope : 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"); + level++; + } + } + + /** + * Walks the whole graph, starting from Start. + * Since Start is the input to all constants - we look at the outputs for + * Start, but for then subsequently we look at the inputs of each node. + * During graph construction not all nodes are reachable this way, so we + * also scan the symbol tables. + */ + private Collection<Node> findAll(Parser parser) { + final StartNode start = Parser.START; + final HashMap<Integer, Node> all = new HashMap<>(); + 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); + return all.values(); + } + + /** + * Walk a subgraph and populate distinct nodes in the all list. + */ + private void walk(HashMap<Integer, Node> all, Node n) { + if (all.get(n._nid) != null) return; // Been there, done that + all.put(n._nid, n); + for (Node c : n._inputs) + if (c != null) + walk(all, c); + } +} diff --git a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java new file mode 100644 index 00000000..13b25e60 --- /dev/null +++ b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java @@ -0,0 +1,389 @@ +package com.seaofnodes.simple; + +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 + * Syntax Tree structure. + * <p> + * 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. + * <p> + * To make the compiler multithreaded, this field will have to move into a TLS. + */ + public static StartNode START; + + 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 Stack<HashMap<String, Node>> _scopes; + + public Parser(String source) { + _lexer = new Lexer(source); + _scopes = new Stack<>(); + Node.reset(); + START = new StartNode(); + } + + public ReturnNode parse() { + 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 + * + * <pre> + * '{' statements '}' + * </pre> + */ + private Node parseBlock() { + // Enter a new scope + _scopes.push(new HashMap<>()); + 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(); + return n; + } + + /** + * Parses a statement + * + * <pre> + * returnStatement | declStatement | blockStatement | expressionStatement + * </pre> + */ + private Node parseStatement() { + if (match("return")) return parseReturn(); + else if (match("int")) return parseDecl(); + else if (match("{")) return parseBlock(); + else if (match("#showGraph")) return showGraph(); + else return parseExpressionStatement(); + } + + /** + * Parses returnStatement; "return" already parsed + * + * <pre> + * 'return' expr ; + * </pre> + */ + private Node parseReturn() { + var expr = require(parseExpression(), ";"); + return new ReturnNode(START, expr); + } + + /** + * Dumps out the node graph + */ + private Node showGraph() { + require(";"); + System.out.println(new GraphVisualizer().generateDotOutput(this)); + return null; + } + + /** + * Parses an expression statement + * + * <pre> + * name '=' expression ';' + * </pre> + */ + private Node parseExpressionStatement() { + var name = requireId(); + require("="); + var expr = require(parseExpression(), ";"); + return update(name, expr); + } + + /** + * Parses a declStatement + * + * <pre> + * 'int' name = expression ';' + * </pre> + */ + private Node parseDecl() { + // Type is 'int' for now + var name = requireId(); + require("="); + var expr = require(parseExpression(), ";"); + return define(name, expr); + } + + /** + * Parse an expression of the form: + * + * <pre> + * expr : additiveExpr + * </pre> + */ + private Node parseExpression() {return parseAddition();} + + /** + * Parse an additive expression + * + * <pre> + * additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)* + * </pre> + */ + private Node parseAddition() { + var lhs = parseMultiplication(); + if (match("+")) return new AddNode(lhs, parseAddition()).peephole(); + if (match("-")) return new SubNode(lhs, parseAddition()).peephole(); + return lhs; + } + + /** + * Parse an multiplicativeExpr expression + * + * <pre> + * multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)* + * </pre> + */ + private Node parseMultiplication() { + var lhs = parseUnary(); + if (match("*")) return new MulNode(lhs, parseMultiplication()).peephole(); + if (match("/")) return new DivNode(lhs, parseMultiplication()).peephole(); + return lhs; + } + + /** + * Parse a unary minus expression. + * + * <pre> + * unaryExpr : ('-') unaryExpr | primaryExpr + * </pre> + */ + private Node parseUnary() { + if (match("-")) return new MinusNode(parseUnary()).peephole(); + return parsePrimary(); + } + + /** + * Parse a primary expression: + * + * <pre> + * primaryExpr : integerLiteral | Identifier | '(' expression ')' + * </pre> + */ + private Node parsePrimary() { + if (_lexer.isNumber()) return parseIntegerLiteral(); + if (match("(")) return require(parseExpression(), ")"); + return lookup(requireId()); + } + + /** + * Parse integer literal + * + * <pre> + * integerLiteral: [1-9][0-9]* | [0] + * </pre> + */ + private ConstantNode parseIntegerLiteral() { + return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole(); + } + + ////////////////////////////////// + // Utilities for lexical analysis + + // Return true and skip if "syntax" is next in the stream. + private boolean match(String syntax) {return _lexer.match(syntax);} + + // Require and return an identifier + private String requireId() { + String id = _lexer.matchId(); + if (id != null) return id; + throw error("identifier"); + } + + // 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; + } + + // Very handy in the debugger, shows the unparsed program + @Override + public String toString() { + return new String(_input, _position, _input.length - _position); + } + + // 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; + } + + // Return an identifier or null + String matchId() { + skipWhiteSpace(); + return isIdStart(peek()) ? parseId() : null; + } + + // Used for errors + String getAnyNextToken() { + if (isEOF()) return ""; + if (isIdStart(peek())) return parseId(); + if (isPunctuation(peek())) return parsePunctuation(); + return String.valueOf(peek()); + } + + boolean isNumber() {return isNumber(peek());} + boolean isNumber(char ch) {return Character.isDigit(ch);} + + private Type parseNumber() { + int start = _position; + while (isNumber(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 new TypeInteger(Long.parseLong(snum)); + } + + // 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; + if (isPunctuation(nextChar())) ; + return new String(_input, start, --_position - start); + } + } + +} diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java new file mode 100644 index 00000000..015779dc --- /dev/null +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -0,0 +1,35 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.*; + +public class AddNode extends Node { + public AddNode(Node lhs, Node rhs) { + super(null, lhs, rhs); + } + + @Override + public String label() { return "Add"; } + + @Override + StringBuilder _print(StringBuilder sb) { + in(1)._print(sb.append("(")); + in(2)._print(sb.append("+")); + return sb.append(")"); + } + + + @Override + public Type compute() { + if( in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1 ) + return new TypeInteger(i0._con + i1._con); + return TypeBot.BOTTOM; + } + + @Override + public Node idealize () { + // TODO: add of 0 + return null; + } + +} diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ConstantNode.java new file mode 100644 index 00000000..798d40d5 --- /dev/null +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -0,0 +1,42 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.Type; + +/** + * 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 ConstantNode( Type type ) { + super(Parser.START); + _type = type; + } + + @Override + public String label() { return "#"+_type; } + + @Override + public String uniqueName() { return "Con_" + _nid; } + + @Override + StringBuilder _print(StringBuilder sb) { + return _type._print(sb); + } + + @Override + public Type compute() { return _type; } + + @Override + public Node idealize() { return null; } + +} diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/Control.java b/chapter03/src/main/java/com/seaofnodes/simple/node/Control.java new file mode 100644 index 00000000..48cf2b7a --- /dev/null +++ b/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java new file mode 100644 index 00000000..bc129690 --- /dev/null +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -0,0 +1,35 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.TypeInteger; + +public class DivNode extends Node { + public DivNode(Node lhs, Node rhs) { + super(null, lhs, rhs); + } + + @Override + public String label() { return "Div"; } + + @Override + StringBuilder _print(StringBuilder sb) { + in(1)._print(sb.append("(")); + in(2)._print(sb.append("/")); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) { + if (i1._con == 0) + throw new IllegalArgumentException("Divide by zero"); + return new TypeInteger(i0._con / i1._con); + } + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java new file mode 100644 index 00000000..7fab83b0 --- /dev/null +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -0,0 +1,30 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.TypeInteger; + +public class MinusNode extends Node { + public MinusNode(Node in) { + super(null, in); + } + + @Override + public String label() { return "Minus"; } + + @Override + StringBuilder _print(StringBuilder sb) { + in(1)._print(sb.append("(-")); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0) + return new TypeInteger(-i0._con); + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java new file mode 100644 index 00000000..e1a26858 --- /dev/null +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -0,0 +1,32 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.TypeInteger; + +public class MulNode extends Node { + public MulNode(Node lhs, Node rhs) { + super(null, lhs, rhs); + } + + @Override + public String label() { return "Mul"; } + + @Override + StringBuilder _print(StringBuilder sb) { + in(1)._print(sb.append("(")); + in(2)._print(sb.append("*")); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) + return new TypeInteger(i0._con * i1._con); + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java new file mode 100644 index 00000000..5528f296 --- /dev/null +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java @@ -0,0 +1,213 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; + +import java.util.ArrayList; +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 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 Control node. + * @see Control + */ + 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 ); + // Do an initial type computation + _type = compute(); + } + + public abstract String label(); + + public String uniqueName() { return label() + _nid; } + + @Override + public final String toString() { + // TODO: This needs a lot of work + return uniqueName(); + } + + // This is a *deep* print. This version will fail on cycles, which we will + // correct later when we can parse programs with loops. + public final String print() { + return _print(new StringBuilder()).toString(); + } + abstract StringBuilder _print(StringBuilder sb); + + + /** + * 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(); } + + /** + * 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 nOuts() { return _outputs.size(); } + + /** + * We allow disabling peephole opt so that we can observe the + * full graph, vs the optimized graph. + */ + public static boolean _disablePeephole = false; + + + /** + * Try to peephole at this node and return a better replacement Node if + * possible. We check and replace: + * <ul> + * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li> + * <li>in a future chapter we will look for a + * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a> + * to eliminate.</li> + * <li>we ask the Node for a better replacement (again, none enabled in this chapter)</li> + * </ul> + */ + public final Node peephole( ) { + if (_disablePeephole) + return this; // Peephole optimizations turned off + + // Replace constant computations from non-constants with a constant node + Type type = compute(); + if (!(this instanceof ConstantNode) && type.isConstant()) { + kill(); // Kill `this` because replacing with a Constant + return new ConstantNode(type); + } + + // Future chapter: Global Value Numbering goes here + + // Ask each node for a replacement + Node n = idealize(); + if( n != null ) return n; + + return this; // No progress + } + + /** + * 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 #set_def}. + */ + public void kill( ) { + assert nOuts()==0; // Has no uses, so it is dead + for( int i=0; i<nIns(); i++ ) + set_def(i,null); // Set all inputs to null, recursively killing unused Nodes + } + + /** + * 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}. + * + * @param idx which def to set + * @param new_def the new definition + */ + void 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 + 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 != null ) + new_def._outputs.add(this); + } + + + /** + * Current computed type for this Node. This value changes as the graph + * changes and more knowledge is gained about the program. + */ + public Type _type; + + /** + * This function needs to be + * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a> + * as it is part of a Monotone Analysis Framework. + * <a href="https://www.cse.psu.edu/~gxt29/teaching/cse597s21/slides/08monotoneFramework.pdf">See for example this set of slides</a>. + * <p> + * For Chapter 2, all our Types are really integer constants, and so all + * the needed properties are trivially true, and we can ignore the high + * theory. Much later on, this will become important and allow us to do + * many fancy complex optimizations trivially... because theory. + * <p> + * compute() needs to be stand-alone, and cannot recursively call compute + * on its inputs programs are cyclic (have loops!) and this will just + * infinitely recurse until stack overflow. Instead, compute typically + * computes a new type from the {@link #_type} field of its inputs. + */ + public abstract Type compute(); + + public abstract Node idealize(); + + /** + * 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; } + + /* + * hashCode and equals implementation to be added in later chapter. + */ + +} diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java new file mode 100644 index 00000000..c188ca79 --- /dev/null +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -0,0 +1,39 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.TypeBot; + +/** + * 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 implements Control { + + public ReturnNode(Node ctrl, Node data) { + super(ctrl, data); + } + + public Node ctrl() { return in(0); } + public Node expr() { return in(1); } + + @Override + public String label() { return "Return"; } + + @Override + StringBuilder _print(StringBuilder sb) { + return expr()._print(sb.append("return ")).append(";"); + } + + + @Override + public TypeBot compute() { + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java new file mode 100644 index 00000000..8d8031bb --- /dev/null +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -0,0 +1,31 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.TypeBot; + +/** + * 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 { + + public StartNode(/*arguments go here*/) { + super(); + } + + @Override + public String label() { return "Start"; } + + @Override + StringBuilder _print(StringBuilder sb) { + return sb.append(label()); + } + + @Override + public TypeBot compute() { + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java new file mode 100644 index 00000000..2d7db8d3 --- /dev/null +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -0,0 +1,33 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.TypeInteger; + +public class SubNode extends Node { + public SubNode(Node lhs, Node rhs) { + super(null, lhs, rhs); + } + + @Override + public String label() { return "Sub"; } + + @Override + StringBuilder _print(StringBuilder sb) { + in(1)._print(sb.append("(")); + in(2)._print(sb.append("-")); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) + return new TypeInteger(i0._con - i1._con); + return TypeBot.BOTTOM; + } + + @Override + public Node idealize() { return null; } + +} diff --git a/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java new file mode 100644 index 00000000..872e453d --- /dev/null +++ b/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java @@ -0,0 +1,25 @@ +package com.seaofnodes.simple.type; + + +/** + * These types are part of a Monotone Analysis Framework, + * @see <a href="https://www.cse.psu.edu/~gxt29/teaching/cse597s21/slides/08monotoneFramework.pdf">see for example this set of slides</a>. + * <p> + * The types form a lattice; @see <a href="https://en.wikipedia.org/wiki/Lattice_(order)">a symmetric complete bounded (ranked) lattice.</a> + * <p> + * This wild lattice theory will be needed later to allow us to easily beef up + * the analysis and optimization of the Simple compiler... but we don't need it + * now, just know that it is coming along in a later Chapter. + * <p>g + * One of the fun things here is that while the theory is deep and subtle, the + * actual implementation is darn near trivial and is generally really obvious + * what we're doing with it. Right now, it's just simple integer math to do + * simple constant folding e.g. 1+2 == 3 stuff. + */ + +public abstract class Type { + + public boolean isConstant() { return false; } + + public abstract StringBuilder _print(StringBuilder sb); +} diff --git a/chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java new file mode 100644 index 00000000..5284884a --- /dev/null +++ b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java @@ -0,0 +1,14 @@ +package com.seaofnodes.simple.type; + +import java.lang.StringBuilder; + +public class TypeBot extends Type { + + public static final TypeBot BOTTOM = new TypeBot(); + + @Override + public String toString() { return "Bottom"; } + + @Override + public StringBuilder _print(StringBuilder sb) { return sb.append(toString()); } +} diff --git a/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java new file mode 100644 index 00000000..db3d4c46 --- /dev/null +++ b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -0,0 +1,34 @@ +package com.seaofnodes.simple.type; + +/** + * Integer Type + */ +public class TypeInteger extends Type { + + /** + * The constant value observed for this type + */ + public final long _con; + + public TypeInteger(long con) { _con = con; } + + @Override + public String toString() { + return _print(new StringBuilder()).toString(); + } + + @Override + public StringBuilder _print(StringBuilder sb) { return sb.append(_con); } + + @Override + public boolean isConstant() { return true; } + + public long getConstant() { return _con; } + + @Override + public boolean equals( Object o ) { + if( o==this ) return true; + if( !(o instanceof TypeInteger i) ) return false; + return _con==i._con; + } +} diff --git a/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java new file mode 100644 index 00000000..5af07ec3 --- /dev/null +++ b/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -0,0 +1,171 @@ +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.type.TypeInteger; +import org.junit.Rule; +import org.junit.Test; +import org.junit.rules.ExpectedException; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class Chapter03Test { + + @Rule + public ExpectedException exceptionRule = ExpectedException.none(); + + @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 testVarScopeNoPeephole() { + Node._disablePeephole = true; + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); + ReturnNode ret = parser.parse(); + Node._disablePeephole = false; + assertEquals("return (1+3);", 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); #showGraph;"); + ReturnNode ret = parser.parse(); + assertEquals("return 8;", ret.print()); + } + + + @Test + public void testChapter2ParseGrammar() { + Node._disablePeephole = true; // disable peephole so we can observe full graph + Parser parser = new Parser("return 1+2*3+-5;"); + ReturnNode ret = parser.parse(); + assertEquals("return (1+((2*3)+(-5)));", ret.print()); + GraphVisualizer gv = new GraphVisualizer(); + System.out.println(gv.generateDotOutput(parser)); + Node._disablePeephole = false; + } + + @Test + public void testChapter2AddPeephole() { + Parser parser = new Parser("return 1+2;"); + ReturnNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testChapter2SubPeephole() { + Parser parser = new Parser("return 1-2;"); + ReturnNode ret = parser.parse(); + assertEquals("return -1;", ret.print()); + } + + @Test + public void testChapter2MulPeephole() { + Parser parser = new Parser("return 2*3;"); + ReturnNode ret = parser.parse(); + assertEquals("return 6;", ret.print()); + } + + @Test + public void testChapter2DivPeephole() { + Parser parser = new Parser("return 6/3;"); + ReturnNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testChapter2MinusPeephole() { + Parser parser = new Parser("return 6/-3;"); + ReturnNode ret = parser.parse(); + assertEquals("return -2;", ret.print()); + } + + @Test + public void testChapter2Example() { + Parser parser = new Parser("return 1+2*3+-5;"); + ReturnNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + GraphVisualizer gv = new GraphVisualizer(); + System.out.println(gv.generateDotOutput(parser)); + } + + @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(new TypeInteger(1), con._type); + } 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(new TypeInteger(0),con._type); + } + + @Test + public void testBad1() { + exceptionRule.expect(RuntimeException.class); + exceptionRule.expectMessage("Syntax error, expected =: "); + new Parser("ret").parse(); + } + + @Test + public void testBad2() { + exceptionRule.expect(RuntimeException.class); + exceptionRule.expectMessage("Syntax error: integer values cannot start with '0'"); + new Parser("return 0123;").parse(); + } + + @Test + public void testNotBad3() { + // this test used to fail in chapter 1 + assertEquals("return 12;", new Parser("return --12;").parse().print()); + } + + @Test + public void testBad4() { + exceptionRule.expect(RuntimeException.class); + exceptionRule.expectMessage("Syntax error, expected ;:"); + new Parser("return 100").parse(); + } + + @Test + public void testNotBad5() { + // this test used to fail in chapter 1 + assertEquals("return -100;", new Parser("return -100;").parse().print()); + } +} |
