From df5294e88cc409d7adf3e10666bfcb40e34472b9 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Sun, 1 Oct 2023 18:01:54 +0100 Subject: 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 --- chapter03/README.md | 98 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 98 insertions(+) create mode 100644 chapter03/README.md (limited to 'chapter03/README.md') 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 -- cgit v1.2.3