From bafb37e0078950acdf0d0218a977beaf05e0b6ac Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 1 Oct 2023 18:01:54 +0100 Subject: Chapter 3: Variable Declarations MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Dibyendu Majumdar Co-authored-by: Yichen Yan Co-authored-by: Thalia Archibald Co-authored-by: Tamas Hadhazy Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: godalming123 <68993177+godalming123@users.noreply.github.com> Co-authored-by: RobertObkircher --- README.md | 2 +- docs/chapter03/03-grammar.md | 68 ++++++++ docs/chapter03/03-graph1.gv | 39 +++++ docs/chapter03/03-graph1.json | 17 ++ docs/chapter03/03-graph1.svg | 86 ++++++++++ docs/chapter03/03-graph2.gv | 35 ++++ docs/chapter03/03-graph2.json | 18 ++ docs/chapter03/03-graph2.svg | 89 ++++++++++ docs/chapter03/03-graph3.gv | 37 ++++ docs/chapter03/03-graph3.json | 19 ++ docs/chapter03/03-graph3.svg | 91 ++++++++++ docs/chapter03/03-graph4.json | 17 ++ docs/chapter03/03-graph4.svg | 84 +++++++++ docs/chapter03/03-graph5.json | 17 ++ docs/chapter03/03-graph5.svg | 84 +++++++++ docs/chapter03/Makefile | 1 + docs/chapter03/README.md | 191 +++++++++++++++++++++ src/main/java/com/seaofnodes/simple/Parser.java | 113 +++++++++++- src/main/java/com/seaofnodes/simple/node/Node.java | 60 ++++++- .../java/com/seaofnodes/simple/node/ScopeNode.java | 130 ++++++++++++++ .../simple/print/SimpleGraphAdapter.java | 9 +- .../simple/print/SimpleGraphObserver.java | 3 +- .../java/com/seaofnodes/simple/Chapter01Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter03Test.java | 68 ++++++++ 24 files changed, 1267 insertions(+), 15 deletions(-) create mode 100644 docs/chapter03/03-grammar.md create mode 100644 docs/chapter03/03-graph1.gv create mode 100644 docs/chapter03/03-graph1.json create mode 100644 docs/chapter03/03-graph1.svg create mode 100644 docs/chapter03/03-graph2.gv create mode 100644 docs/chapter03/03-graph2.json create mode 100644 docs/chapter03/03-graph2.svg create mode 100644 docs/chapter03/03-graph3.gv create mode 100644 docs/chapter03/03-graph3.json create mode 100644 docs/chapter03/03-graph3.svg create mode 100644 docs/chapter03/03-graph4.json create mode 100644 docs/chapter03/03-graph4.svg create mode 100644 docs/chapter03/03-graph5.json create mode 100644 docs/chapter03/03-graph5.svg create mode 100644 docs/chapter03/Makefile create mode 100644 docs/chapter03/README.md create mode 100644 src/main/java/com/seaofnodes/simple/node/ScopeNode.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter03Test.java diff --git a/README.md b/README.md index 2430222d..39c792e0 100644 --- a/README.md +++ b/README.md @@ -40,7 +40,7 @@ The Simple language is styled after a subset of C or Java. * [Chapter 1](docs/chapter01/README.md): Script that returns an integer literal, i.e., an empty function that takes no arguments and returns a single integer value. The `return` statement. * [Chapter 2](docs/chapter02/README.md): Simple binary arithmetic such as addition, subtraction, multiplication, division with constants. Peephole optimization / simple constant folding. -* Chapter 3: Local variables, and assignment statements. Read on RHS, SSA, more peephole optimization if local is a +* [Chapter 3](docs/chapter03/README.md): Local variables, and assignment statements. Read on RHS, SSA, more peephole optimization if local is a constant. * Chapter 4: A non-constant external variable input named `arg`. Binary and Comparison operators involving constants and `arg`. diff --git a/docs/chapter03/03-grammar.md b/docs/chapter03/03-grammar.md new file mode 100644 index 00000000..1d36b532 --- /dev/null +++ b/docs/chapter03/03-grammar.md @@ -0,0 +1,68 @@ +# Grammar for Chapter 1 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + ; + + +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]; +``` diff --git a/docs/chapter03/03-graph1.gv b/docs/chapter03/03-graph1.gv new file mode 100644 index 00000000..7008a44e --- /dev/null +++ b/docs/chapter03/03-graph1.gv @@ -0,0 +1,39 @@ +digraph chapter03 { +/* +int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_3 [ label="#1" ]; + Con_4 [ label="#2" ]; + Con_6 [ label="#3" ]; + Add7 [ label="+" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + + +
0abc
>]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + + +
1b
>]; + } + } + edge [ fontname=Helvetica, fontsize=8 ]; + Con_3 -> Start2[taillabel=0 style=dotted]; + Con_4 -> Start2[taillabel=0 style=dotted]; + Con_6 -> Start2[taillabel=0 style=dotted]; + Add7 -> Con_3[taillabel=1]; + Add7 -> Con_6[taillabel=2]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_a" -> Con_3; + Scope1_0:"Scope1_0_b" -> Con_4; + Scope1_0:"Scope1_0_c" -> Add7; + Scope1_1:"Scope1_1_b" -> Con_6; +} diff --git a/docs/chapter03/03-graph1.json b/docs/chapter03/03-graph1.json new file mode 100644 index 00000000..5dce5431 --- /dev/null +++ b/docs/chapter03/03-graph1.json @@ -0,0 +1,17 @@ +{ + "ver": 1, + "comp": "chapter03/docs/03-graph1.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 3, "role": "ASSOC", "label": "0: a"}, {"idx": 1, "def": 4, "role": "ASSOC", "label": "0: b"}, {"idx": 2, "def": 7, "role": "ASSOC", "label": "0: c"}, {"idx": 3, "def": 6, "role": "ASSOC", "label": "1: b"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 4, "label": "#2", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 6, "label": "#3", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 3, "role": "DATA", "label": null}, {"idx": 2, "def": 6, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter03/03-graph1.svg b/docs/chapter03/03-graph1.svg new file mode 100644 index 00000000..0ecaffac --- /dev/null +++ b/docs/chapter03/03-graph1.svg @@ -0,0 +1,86 @@ +#1[0] → #3 · ASSOC · 0: a#1[1] → #4 · ASSOC · 0: b#1[2] → #7 · ASSOC · 0: c#1[3] → #6 · ASSOC · 1: b#3[0] → #2 · ASSOC#4[0] → #2 · ASSOC#6[0] → #2 · ASSOC#7[1] → #3 · DATA#7[2] → #6 · DATAScope  #1#1 Scope +Type not computed + +[0] → #3 ASSOC 0: a +[1] → #4 ASSOC 0: b +[2] → #7 ASSOC 0: c +[3] → #6 ASSOC 1: b0: a0: b0: c1: b0123Start  #2#2 Start +Type not computed + +#1  #3#3 #1 +Type not computed + +[0] → #2 ASSOC0#2  #4#4 #2 +Type not computed + +[0] → #2 ASSOC0#3  #6#6 #3 +Type not computed + +[0] → #2 ASSOC0+  #7#7 + +Type not computed + +[0] → — DATA +[1] → #3 DATA +[2] → #6 DATA012 diff --git a/docs/chapter03/03-graph2.gv b/docs/chapter03/03-graph2.gv new file mode 100644 index 00000000..cafa7f25 --- /dev/null +++ b/docs/chapter03/03-graph2.gv @@ -0,0 +1,35 @@ +digraph chapter03 { +/* +int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_3 [ label="#1" ]; + Con_4 [ label="#2" ]; + Con_6 [ label="#3" ]; + Add7 [ label="+" ]; + Return8 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + + +
0abc
>]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Con_3 -> Start2[taillabel=0 style=dotted]; + Con_4 -> Start2[taillabel=0 style=dotted]; + Con_6 -> Start2[taillabel=0 style=dotted]; + Add7 -> Con_3[taillabel=1]; + Add7 -> Con_6[taillabel=2]; + Return8 -> Start2[taillabel=0 color=red]; + Return8 -> Add7[taillabel=1]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_a" -> Con_3; + Scope1_0:"Scope1_0_b" -> Con_4; + Scope1_0:"Scope1_0_c" -> Add7; +} diff --git a/docs/chapter03/03-graph2.json b/docs/chapter03/03-graph2.json new file mode 100644 index 00000000..80397161 --- /dev/null +++ b/docs/chapter03/03-graph2.json @@ -0,0 +1,18 @@ +{ + "ver": 1, + "comp": "chapter03/docs/03-graph2.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 3, "role": "ASSOC", "label": "0: a"}, {"idx": 1, "def": 4, "role": "ASSOC", "label": "0: b"}, {"idx": 2, "def": 7, "role": "ASSOC", "label": "0: c"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 4, "label": "#2", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 6, "label": "#3", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 3, "role": "DATA", "label": null}, {"idx": 2, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter03/03-graph2.svg b/docs/chapter03/03-graph2.svg new file mode 100644 index 00000000..3904d87e --- /dev/null +++ b/docs/chapter03/03-graph2.svg @@ -0,0 +1,89 @@ +#1[0] → #3 · ASSOC · 0: a#1[1] → #4 · ASSOC · 0: b#1[2] → #7 · ASSOC · 0: c#3[0] → #2 · ASSOC#4[0] → #2 · ASSOC#6[0] → #2 · ASSOC#7[1] → #3 · DATA#7[2] → #6 · DATA#8[0] → #2 · CTRL#8[1] → #7 · DATAScope  #1#1 Scope +Type not computed + +[0] → #3 ASSOC 0: a +[1] → #4 ASSOC 0: b +[2] → #7 ASSOC 0: c0: a0: b0: c012Start  #2#2 Start +Type not computed + +#1  #3#3 #1 +Type not computed + +[0] → #2 ASSOC0#2  #4#4 #2 +Type not computed + +[0] → #2 ASSOC0#3  #6#6 #3 +Type not computed + +[0] → #2 ASSOC0+  #7#7 + +Type not computed + +[0] → — DATA +[1] → #3 DATA +[2] → #6 DATA012Return  #8#8 Return +Type not computed + +[0] → #2 CTRL +[1] → #7 DATA01 diff --git a/docs/chapter03/03-graph3.gv b/docs/chapter03/03-graph3.gv new file mode 100644 index 00000000..791a7dc1 --- /dev/null +++ b/docs/chapter03/03-graph3.gv @@ -0,0 +1,37 @@ +digraph chapter03 { +/* +int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_3 [ label="#1" ]; + Con_4 [ label="#2" ]; + Con_20 [ label="#8" ]; + Con_5 [ label="#3" ]; + Return21 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_6 [ label="#4" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + + +
0y0x0y1x1
>]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Con_3 -> Start2[taillabel=0 style=dotted]; + Con_4 -> Start2[taillabel=0 style=dotted]; + Con_20 -> Start2[taillabel=0 style=dotted]; + Con_5 -> Start2[taillabel=0 style=dotted]; + Return21 -> Start2[taillabel=0 color=red]; + Return21 -> Con_20[taillabel=1]; + Con_6 -> Start2[taillabel=0 style=dotted]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_y0" -> Con_4; + Scope1_0:"Scope1_0_x0" -> Con_3; + Scope1_0:"Scope1_0_y1" -> Con_6; + Scope1_0:"Scope1_0_x1" -> Con_5; +} diff --git a/docs/chapter03/03-graph3.json b/docs/chapter03/03-graph3.json new file mode 100644 index 00000000..a6d6175a --- /dev/null +++ b/docs/chapter03/03-graph3.json @@ -0,0 +1,19 @@ +{ + "ver": 1, + "comp": "chapter03/docs/03-graph3.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 4, "role": "ASSOC", "label": "0: y0"}, {"idx": 1, "def": 3, "role": "ASSOC", "label": "0: x0"}, {"idx": 2, "def": 6, "role": "ASSOC", "label": "0: y1"}, {"idx": 3, "def": 5, "role": "ASSOC", "label": "0: x1"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 4, "label": "#2", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 5, "label": "#3", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 6, "label": "#4", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 20, "label": "#8", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 21, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}, {"idx": 1, "def": 20, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter03/03-graph3.svg b/docs/chapter03/03-graph3.svg new file mode 100644 index 00000000..4c5db5e0 --- /dev/null +++ b/docs/chapter03/03-graph3.svg @@ -0,0 +1,91 @@ +#1[0] → #4 · ASSOC · 0: y0#1[1] → #3 · ASSOC · 0: x0#1[2] → #6 · ASSOC · 0: y1#1[3] → #5 · ASSOC · 0: x1#3[0] → #2 · ASSOC#4[0] → #2 · ASSOC#5[0] → #2 · ASSOC#6[0] → #2 · ASSOC#20[0] → #2 · ASSOC#21[0] → #2 · CTRL#21[1] → #20 · DATAScope  #1#1 Scope +Type not computed + +[0] → #4 ASSOC 0: y0 +[1] → #3 ASSOC 0: x0 +[2] → #6 ASSOC 0: y1 +[3] → #5 ASSOC 0: x10: y00: x00: y10: x10123Start  #2#2 Start +Type not computed + +#1  #3#3 #1 +Type not computed + +[0] → #2 ASSOC0#2  #4#4 #2 +Type not computed + +[0] → #2 ASSOC0#3  #5#5 #3 +Type not computed + +[0] → #2 ASSOC0#4  #6#6 #4 +Type not computed + +[0] → #2 ASSOC0#8  #20#20 #8 +Type not computed + +[0] → #2 ASSOC0Return  #21#21 Return +Type not computed + +[0] → #2 CTRL +[1] → #20 DATA01 diff --git a/docs/chapter03/03-graph4.json b/docs/chapter03/03-graph4.json new file mode 100644 index 00000000..b594eee2 --- /dev/null +++ b/docs/chapter03/03-graph4.json @@ -0,0 +1,17 @@ +{ + "ver": 1, + "comp": "chapter03/docs/03-graph4.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 3, "role": "ASSOC", "label": "0: a"}, {"idx": 1, "def": 4, "role": "ASSOC", "label": "0: b"}, {"idx": 2, "def": 8, "role": "ASSOC", "label": "0: c"}, {"idx": 3, "def": 6, "role": "ASSOC", "label": "1: b"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 4, "label": "#2", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 6, "label": "#5", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 8, "label": "#6", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter03/03-graph4.svg b/docs/chapter03/03-graph4.svg new file mode 100644 index 00000000..c773ef9b --- /dev/null +++ b/docs/chapter03/03-graph4.svg @@ -0,0 +1,84 @@ +#1[0] → #3 · ASSOC · 0: a#1[1] → #4 · ASSOC · 0: b#1[2] → #8 · ASSOC · 0: c#1[3] → #6 · ASSOC · 1: b#3[0] → #2 · ASSOC#4[0] → #2 · ASSOC#6[0] → #2 · ASSOC#8[0] → #2 · ASSOCScope  #1#1 Scope +Type not computed + +[0] → #3 ASSOC 0: a +[1] → #4 ASSOC 0: b +[2] → #8 ASSOC 0: c +[3] → #6 ASSOC 1: b0: a0: b0: c1: b0123Start  #2#2 Start +Type not computed + +#1  #3#3 #1 +Type not computed + +[0] → #2 ASSOC0#2  #4#4 #2 +Type not computed + +[0] → #2 ASSOC0#5  #6#6 #5 +Type not computed + +[0] → #2 ASSOC0#6  #8#8 #6 +Type not computed + +[0] → #2 ASSOC0 diff --git a/docs/chapter03/03-graph5.json b/docs/chapter03/03-graph5.json new file mode 100644 index 00000000..476ad586 --- /dev/null +++ b/docs/chapter03/03-graph5.json @@ -0,0 +1,17 @@ +{ + "ver": 1, + "comp": "chapter03/docs/03-graph5.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 3, "role": "ASSOC", "label": "0: a"}, {"idx": 1, "def": 4, "role": "ASSOC", "label": "0: b"}, {"idx": 2, "def": 11, "role": "ASSOC", "label": "0: c"}, {"idx": 3, "def": 9, "role": "ASSOC", "label": "1: e"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 4, "label": "#2", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 9, "label": "#6", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 11, "label": "#7", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter03/03-graph5.svg b/docs/chapter03/03-graph5.svg new file mode 100644 index 00000000..a62d03bb --- /dev/null +++ b/docs/chapter03/03-graph5.svg @@ -0,0 +1,84 @@ +#1[0] → #3 · ASSOC · 0: a#1[1] → #4 · ASSOC · 0: b#1[2] → #11 · ASSOC · 0: c#1[3] → #9 · ASSOC · 1: e#3[0] → #2 · ASSOC#4[0] → #2 · ASSOC#9[0] → #2 · ASSOC#11[0] → #2 · ASSOCScope  #1#1 Scope +Type not computed + +[0] → #3 ASSOC 0: a +[1] → #4 ASSOC 0: b +[2] → #11 ASSOC 0: c +[3] → #9 ASSOC 1: e0: a0: b0: c1: e0123Start  #2#2 Start +Type not computed + +#1  #3#3 #1 +Type not computed + +[0] → #2 ASSOC0#2  #4#4 #2 +Type not computed + +[0] → #2 ASSOC0#6  #9#9 #6 +Type not computed + +[0] → #2 ASSOC0#7  #11#11 #7 +Type not computed + +[0] → #2 ASSOC0 diff --git a/docs/chapter03/Makefile b/docs/chapter03/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter03/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter03/README.md b/docs/chapter03/README.md new file mode 100644 index 00000000..29ff8ee4 --- /dev/null +++ b/docs/chapter03/README.md @@ -0,0 +1,191 @@ +# Chapter 3: Variable Declarations + +[Previous: Chapter 2](../chapter02/README.md) | +[Next: Chapter 4](../chapter04/README.md) + +# Table of Contents + +1. [Extensions to Intermediate Representation](#extensions-to-intermediate-representation) +2. [Symbol Tables](#symbol-tables) +3. [ScopeNode](#scopenode) +4. [Demonstration](#demonstration) +5. [Enabling peephole optimizations](#enabling-peephole-optimizations) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter03) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter02...linear-chapter03) it to the previous chapter. + +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](03-grammar.md) for this chapter. + + +## Extensions to Intermediate Representation + +In this chapter we introduce: + +| Node Name | Type | Description | Inputs | Value | +|-----------|--------------|--------------------------------|---------------------------------|-------| +| Scope | Symbol Table | Represents scopes in the graph | All nodes that define variables | None | + +and keep all nodes from prior chapters. + +## 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 lexical 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, in lexical order. + +## ScopeNode + +A ScopeNode encapsulates the stack of symbol tables that are used to implement lexical scopes. + +* The nodes referenced by the names in a lexical scope become inputs to the + ScopeNode; this makes ScopeNode a user of these values, thus keeping them + alive while a particular lexical scope is alive. When the lexical scope + ends, those inputs are removed. This is crucial because peepholes will remove + dead Nodes and every new Node is effectively dead at the instant of creation. +* In [Chapter 5](../chapter05/README.md) when we implement branches, the ScopeNode gets duplicated at a branch point and then gets merged when the branch joins. This allows + the names to evolve in each branch independently. At the merge point, names that have diverged require a Phi node. +* In [Chapter 7](../chapter07/README.md) additional logic is deployed for handling Phis from back edges. +* The ScopeNode is used to track some other values such as the Control token starting from [Chapter 4](../chapter04/README.md), and whole memory starting from [Chapter 10](../chapter10/README.md). Special name bindings are used + for these, and each name is tracked across branches and then merged at merge points. +* In [Chapter 10](../chapter10/README.md) the ScopeNode is enhanced to also maintain the declared type for each name. + +From an implementation standpoint, each symbol table is represented as a `HashMap`, where the `String` is the variable name, and the `Integer` is an index into the inputs of the +ScopeNode. To access the Node associated with a name, first the symbol table is consulted, and then the ScopeNode's inputs to find the required Node. +The stack of symbol tables is represented as `Stack>`. + +When a lexical scope is exited, we not only pop the symbol table representing the +scope from the stack, but also remove the relevant input nodes. If the variable's expression +only exists for the Scope mapping (e.g., "just in case" the Parser parses code +that uses the variable) this is when the expression dies: +``` + int a=1; + { + int b=a*a*a; + } // When this scope closes and ends, b (and the cube of a) dies + return a; +``` + + +In the visualization, we show the ScopeNode in a separate purple box. Each +binding is labelled with its lexical scope level. We show the edge from each +variable in the symbol table to the defining +Node in the graph. + +The ScopeNode is neither a Data Node nor a Control Node; it really is a utility for maintaining symbol tables, name lookups, plays a crucial role in deciding where Phi nodes are required. +Representing it as a Node allows us to leverage the Sea of Nodes def-use architecture to maintain liveness of values in scope. + +A ScopeNode has no outputs. + +## Demonstration + +We show the output from the 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 the example above, we start with a symbol table (at 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 (at 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 schematic below shows the variable bindings and arithmetic before constant +folding. The compiler applies peepholes as it builds the graph, so the actual +result of this example is `return 4;`. + +![Graph1](./03-graph1.svg) + +The diagram shows the ScopeNode's bindings with their scope levels. The two +bindings for `b` belong to different lexical scopes. + +* 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: + +![Graph2](./03-graph2.svg) + +As we see, only 1 symbol table is present at this point. + +We can also have multiple scopes at the same level during the execution of the program, +but only one will be active at a time because the symbol table can only hold one symbol table +for each scope level. + +For example: +``` +01 int a=1; +02 int b=2; +03 int c=0; +04 { +05 int b=5; +06 c=a+b; +08 } +09 { +10 int e=6; +11 c = a+e; +13 } +14 return c; +``` +Here both scopes starting from `(04-08)` and `(09-13)` are at the same level: +```java +public final Stack> _scopes; +``` +The `_scopes` stack holds nested scopes, with index 0 representing the highest (global) +scope and deeper indices representing more nested scopes. +Popping returns the current scope and moves to the outer one. +There is a direct one-to-one mapping between each index and its corresponding scope. + +The first nested scope (04-08): + +![Graph4](./03-graph4.svg) + +The second nested scope (09-13): + +![Graph5](./03-graph5.svg) + + - In both cases the index which represents the depth of the scope is 1. +## 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 the example above is displayed below. + +![Graph2](./03-graph3.svg) + +The return node has the constant `8` as its data value! When the parsing ends +and the scope at level 0 is removed, only the `return 8` remains. diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index f59b0f25..e6cb84f8 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -5,6 +5,8 @@ import com.seaofnodes.graph.GraphObserver; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; +import java.util.*; + /** * The Parser converts a Simple source program to the Sea of Nodes intermediate * representation directly in one pass. There is no intermediate Abstract @@ -32,33 +34,73 @@ public class Parser { // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; + /** + * Stack of lexical scopes, each scope is a symbol table that binds + * variable names to Nodes. The top of this stack represents current scope. + */ + public ScopeNode _scope; + + /** + * List of keywords disallowed as identifiers + */ + private final HashSet KEYWORDS = new HashSet<>(){{ + add("int"); + add("return"); + }}; + public Parser(String source) { _lexer = new Lexer(source); PARSER = this; Node.reset(); + _scope = new ScopeNode(); START = new StartNode(); } String src() { return new String( _lexer._input ); } public ReturnNode parse() { - var ret = (ReturnNode) parseStatement(); + var ret = (ReturnNode) parseBlock(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); return ret; } + /** + * Parses a block + * + * 
+     *     '{' statements '}'
+     *
+ * Does not parse the opening or closing '{}' + * @return a {@link Node} or {@code null} + */ + private Node parseBlock() { + // Enter a new scope + _scope.push(); + Node n = null; + while (!peek('}') && !_lexer.isEOF()) { + Node n0 = parseStatement(); + if (n0 != null) n = n0; // Empty statements can return null + }; + // Exit scope + _scope.pop(); + return n; + } + /** * Parses a statement * * 
-     *     returnStatement
+     *     returnStatement | declStatement | blockStatement | expressionStatement
      *
* @return a {@link Node} or {@code null} */ private Node parseStatement() { - if (matchx("return")) return parseReturn(); - throw errorSyntax("a statement"); + if (matchx("return") ) return parseReturn(); + else if (matchx("int")) return parseDecl(); + else if (match ("{" )) return require(parseBlock(),"}"); + else if (matchx(";")) return null; // Empty statement + else return parseExpressionStatement(); } /** @@ -74,6 +116,43 @@ public class Parser { return new ReturnNode(START, expr).peephole(); } + + + /** + * Parses an expression statement + * + * 
+     *     name '=' expression ';'
+     *
+ * @return an expression {@link Node}, never {@code null} + */ + private Node parseExpressionStatement() { + var name = requireId(); + require("="); + var expr = require(parseExpression(), ";"); + if( _scope.update(name, expr)==null ) + throw error("Undefined name '" + name + "'"); + return expr; + } + + /** + * Parses a declStatement + * + * 
+     *     'int' name = expression ';'
+     *
+ * @return an expression {@link Node}, never {@code null} + */ + private Node parseDecl() { + // Type is 'int' for now + var name = requireId(); + require("="); + var expr = require(parseExpression(), ";"); + if( _scope.define(name,expr) == null ) + throw error("Redefining name '" + name + "'"); + return expr; + } + /** * Parse an expression of the form: * @@ -138,7 +217,11 @@ public class Parser { private Node parsePrimary() { if( _lexer.isNumber() ) return parseIntegerLiteral(); if( match("(") ) return require(parseExpression(), ")"); - throw errorSyntax("integer literal"); + String name = _lexer.matchId(); + if( name == null) throw errorSyntax("an identifier or expression"); + Node n = _scope.lookup(name); + if( n!=null ) return n; + throw error("Undefined name '" + name + "'"); } /** @@ -159,6 +242,15 @@ public class Parser { private boolean match (String syntax) { return _lexer.match (syntax); } // Match must be "exact", not be followed by more id letters private boolean matchx(String syntax) { return _lexer.matchx(syntax); } + // Return true and do NOT skip if 'ch' is next + private boolean peek(char ch) { return _lexer.peek(ch); } + + // Require and return an identifier + private String requireId() { + String id = _lexer.matchId(); + if (id != null && !KEYWORDS.contains(id) ) return id; + throw error("Expected an identifier, found '"+id+"'"); + } // Require an exact match private void require(String syntax) { require(null, syntax); } @@ -256,6 +348,17 @@ public class Parser { return false; } + private boolean peek(char ch) { + skipWhiteSpace(); + return peek()==ch; + } + + // Return an identifier or null + String matchId() { + skipWhiteSpace(); + return isIdStart(peek()) ? parseId() : null; + } + // Used for errors String getAnyNextToken() { if (isEOF()) return ""; diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 3c0c3905..54687b2e 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -83,6 +83,13 @@ public abstract class Node extends BaseNode { * Change a def into a Node. Keeps the edges correct, by removing * the corresponding use->def edge. This may make the original * def go dead. This function is co-recursive with {@link #kill}. + *

+ + * This method is the normal path for altering a Node, because it does the + * proper default edge maintenance. It also immediately kills + * Nodes that lose their last use; at times care must be taken to avoid + * killing Nodes that are being used without having an output Node. This + * definitely happens in the middle of recursive {@link #peephole} calls. * * @param idx which def to set * @param new_def the new definition @@ -105,6 +112,22 @@ public abstract class Node extends BaseNode { return new_def; } + /** + * Add a new def to an existing Node. Keep the edges correct by + * adding the corresponding def->use edge. + * + * @param new_def the new definition, appended to the end of existing definitions + * @return new_def for flow coding + */ + Node addDef(Node new_def) { + // Add use->def edge + _inputs.add(new_def); + // If new def is not null, add the corresponding def->use edge + if( new_def != null ) + new_def.addUse(this); + return new_def; + } + // Breaks the edge invariants, used temporarily protected void addUse(N n) { _outputs.add(n); } @@ -116,16 +139,25 @@ public abstract class Node extends BaseNode { return _outputs.size() == 0; } + // Shortcut for "popping" n nodes. A "pop" is basically a + // set_def(last,null) followed by lowering the nIns() count. + void popN(int n) { + for( int i=0; iuses, by setting all of its defs * to null. This may recursively kill more Nodes and is basically dead - * code elimination. This function is co-recursive with {@link #setDef}. + * code elimination. This function is co-recursive with {@link #popN}. */ public void kill( ) { assert isUnused(); // Has no uses, so it is dead - for( int i=0; i { * Node unique id generator, and is done as part of making a new Parser. */ public static void reset() { UNIQUE_ID = 1; } + + /** + * Debugging utility to find a Node by index + */ + public Node find(int nid) { return _find(new BitSet(),nid); } + private Node _find(BitSet visit, int nid) { + if( _nid==nid ) return this; + if( visit.get(_nid) ) return null; + visit.set(_nid); + for( Node def : _inputs ) + if( def!=null ) { + Node rez = def._find(visit,nid); + if( rez != null ) return rez; + } + for( Node use : _outputs ) { + Node rez = use._find(visit,nid); + if( rez != null ) return rez; + } + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java new file mode 100644 index 00000000..95c25391 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -0,0 +1,130 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; + +import com.seaofnodes.simple.type.Type; + +import java.util.*; + +/** + * The Scope node is purely a parser helper - it tracks names to nodes with a + * stack of scopes. + * @see chapter03/README.md + */ +public class ScopeNode extends Node { + + /** + * A Stack of symbol tables; a symbol table is a map from names to node indices. + */ + public final Stack> _scopes; + + + // A new ScopeNode + public ScopeNode() { + _scopes = new Stack<>(); + _type = Type.BOTTOM; + } + + + @Override public String label() { return "Scope"; } + + @Override + protected ExprPrinter _print1(ExprPrinter p) { + p.p(label()); + for( HashMap scope : _scopes ) { + p.p("["); + boolean first=true; + for( String name : scope.keySet() ) { + if( !first ) p.p(", "); + first=false; + p.p(name).p(":"); + Node n = in(scope.get(name)); + if( n==null ) p.p("null"); + else p.n(n); + } + p.p("]"); + } + return p; + } + + /** + * Recover the names for all variable bindings. + * The result is an array of names that is aligned with the + * inputs to the Node. + *

+ * This is an expensive operation. + */ + public String[] reverseNames() { + String[] names = new String[nIns()]; + for( HashMap syms : _scopes ) + for( String name : syms.keySet() ) + names[syms.get(name)] = name; + return names; + } + + @Override public Type compute() { return Type.BOTTOM; } + + @Override public Node idealize() { return null; } + + public void push() { _scopes.push(new HashMap<>()); } + public void pop() { popN(_scopes.pop().size()); } + + /** + * Create a new name in the current scope + */ + public Node define( String name, Node n ) { + HashMap syms = _scopes.lastElement(); + if( syms.put(name,nIns()) != null ) + return null; // Double define + return addDef(n); + } + /** + * Lookup a name in all scopes starting from most deeply nested. + *

+ * @param name Name to be looked up + * @see #update(String, Node, int) + */ + public Node lookup( String name ) { return update(name,null,_scopes.size()-1); } + /** + * If the name is present in any scope, then redefine else null + *

+ * @param name Name being redefined + * @param n The node to bind to the name + */ + public Node update( String name, Node n ) { return update(name,n,_scopes.size()-1); } + /** + * Both recursive lookup and update. + *

+ * A shared implementation allows us to create lazy phis both during + * lookups and updates; the lazy phi creation is part of chapter 8. + * + * @param name Name whose binding is being updated or looked up + * @param n If null, do a lookup, else update binding + * @param nestingLevel The starting nesting level + * @return node being looked up, or the one that was updated + */ + private Node update( String name, Node n, int nestingLevel ) { + if( nestingLevel<0 ) return null; // Missed in all scopes, not found + var syms = _scopes.get(nestingLevel); // Get the symbol table for nesting level + var idx = syms.get(name); + if( idx == null ) return update(name,n,nestingLevel-1); // Not found in this scope, recursively look in parent scope + Node old = in(idx); + // If n is null we are looking up rather than updating, hence return existing value + return n==null ? old : setDef(idx,n); + } + + public Node ctrl() { return in(0); } + + /** + * The ctrl of a ScopeNode is always bound to the currently active + * control node in the graph, via a special name '$ctrl' that is not + * a valid identifier in the language grammar and hence cannot be + * referenced in Simple code. + * + * @param n The node to be bound to '$ctrl' + * + * @return Node that was bound + */ + public Node ctrl(Node n) { return setDef(0,n); } + +} diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index 8f2f31ec..c97aaf55 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -5,16 +5,21 @@ import com.seaofnodes.graph.GraphSnapshot.*; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; -/** Chapter 2's view of the IR; browser, transport and layout are shared. */ +/** Chapter 3's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter { + @Override protected String[] edgeNames(Node n) { + return n instanceof ScopeNode scope && n.nIns()!=0 ? scope.reverseNames() : null; + } + @Override protected Kind kind(Node n) { + if( n instanceof ScopeNode ) return Kind.SCOPE; if( n instanceof StartNode ) return Kind.CTRL; return n.isCFG() ? Kind.CTRL : Kind.DATA; } @Override protected Role role(Node n, int i) { - if( n instanceof ConstantNode ) return Role.ASSOC; + if( n instanceof ScopeNode || n instanceof ConstantNode ) return Role.ASSOC; if( i == 0 ) return Role.CTRL; return Role.DATA; } diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index a17bf796..2dc5d844 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 2's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 3's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture { private Parser _parser; private Node _ret; @@ -30,6 +30,7 @@ public class SimpleGraphObserver extends GraphCapture { _parser = null; _ret = null; } + @Override protected Node scope() { return _parser._scope; } @Override protected void roots(ArrayList roots) { roots.add(Parser.START); roots.add(_ret); diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 49edfb5b..311ca23b 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -40,7 +40,7 @@ public class Chapter01Test { new Parser("ret").parse(); fail(); } catch( RuntimeException e ) { - assertEquals("Syntax error, expected a statement: ret",e.getMessage()); + assertEquals("Syntax error, expected =: ",e.getMessage()); } } @@ -82,7 +82,7 @@ public class Chapter01Test { new Parser("return100").parse(); fail(); } catch( RuntimeException e ) { - assertEquals("Syntax error, expected a statement: return100",e.getMessage()); + assertEquals("Syntax error, expected =: ",e.getMessage()); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java new file mode 100644 index 00000000..9a7dda5d --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -0,0 +1,68 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter03Test { + + @Test + public void testVarDecl() { + Parser parser = new Parser("int a=1; return a;"); + ReturnNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testVarAdd() { + Parser parser = new Parser("int a=1; int b=2; return a+b;"); + ReturnNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testVarScope() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); + ReturnNode ret = parser.parse(); + assertEquals("return 4;", ret.print()); + } + + @Test + public void testVarDist() { + Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1);"); + ReturnNode ret = parser.parse(); + assertEquals("return 8;", ret.print()); + } + + @Test + public void testSelfAssign() { + try { + new Parser("int a=a; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'a'",e.getMessage()); + } + } + + @Test + public void testRedeclareVar() { + try { + new Parser("int a=1; int b=2; int c=0; int b=3; c=a+b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Redefining name 'b'",e.getMessage()); + } + } + + @Test + public void testBad1() { + try { + new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected }: ",e.getMessage()); + } + } + +} -- cgit v1.2.3