Chapter 3 - add vars and lexical scope. (#7)

* Chapter 3 - add vars and lexical scope.

* Fix typo

* Overhaul graph viz

Makes the scopes pointing into the graph being build more visually appealing.
Constants are a printed with just the constant value.

* Fix control edge color

* Fix missing grouping operator parse

Add a parens test.
Shorten names 'Identifier' to 'Id'
_lexer.match -> match
require() passes a Node thru, so can be flow-coded.
Uniform syntax error messages.
Handy Lexer.toString for debugging.
Drop Optional for null returns; less total code; less objects; less confusion.
camelCase some fcns.

* All parser helpers return Node, not void.

Drop _ret.  parseBlock and parseStatement now the same.

* CLosely align chap2 and chap3 parsers

Mostly whitespace aligned; dragged a few functions around to make more sense.
I think the diff from Ch2 and Ch3 is down a few differences about what is a statement, plus all the symbol stuff for scopes and variables.

* Add examples illustrating the symbol table creation.

* Update docs and comments

---------

Co-authored-by: Cliff Click <cliffc@acm.org>

1 files changed, 98 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).
+
+![Graph1](./docs/03-graph1.svg)
+
+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:
+
+![Graph2](./docs/03-graph2.svg)
+
+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.
+
+![Graph2](./docs/03-graph3.svg)
+
+The return node has the constant `8` as its data value!
\ No newline at end of file