1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
# 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
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 |
In this chapter we introduce:
| Node Name | Type | Description | Inputs | Value |
|-----------|------|--------------------------------|---------------------------------|-------|
| Scope | ? | Represents scopes in the graph | All nodes that define variables | None |
## Symbol Tables
To support variable declarations and lexical scopes, we introduce symbol tables in the parser.
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.
## ScopeNode
We wrap the stack of symbol tables in a `ScopeNode`. When a name binding is added to a symbol table,
we also make the newly added node an input in the `ScopeNode`. This means that the `ScopeNode` is a user of
all nodes that define new names.
From an implementation point of view, the symbol table maps names to offsets in the ScopeNode's inputs.
When a scope is exited, we not only pop the symbol table representing the scope, but also remove the relevant input nodes.
In the visualization, we show the ScopeNode in a separate box; the stack of symbol tables is shown inside
the box. We show the edge from each variable in the symbol table to the defining Node in the graph.
## Demonstration
We show the output from following code.
```
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 ScopeNode and the symbol tables in the bottom cluster.
Each table is annotated by its scope level, and shows the variables defined in that scope.
* When we exit the nested scope on line 8, the symbol table at level 1 is popped.
* 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!
|
