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 --- 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 ++++++++++++++++++++++++++++++++++++++++++ 16 files changed, 893 insertions(+) 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 (limited to 'docs') 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. -- cgit v1.2.3