PageSourceSearch

https://silcnitc.github.io/roadmap.html

html silcnitc.github.io collected 2026-10-03 09:57:08 UTC 195,455 bytes, 2,421 lines download raw bytes

1<!Doctype html>
2<html lang="en">
3    <head>
4        <title>Roadmap</title>
5        <meta charset="UTF-8">
6        <!--<link rel="stylesheet" href="css/bootstrap.min.css">-->
7        <link rel="stylesheet" href="css/style_new.css">
8        
8<script src="js/jquery-1.12.1.min.js" charset="utf-8"></script>
8
9        <link rel="stylesheet" href="js/embed-2cd369fa1c0830bd3aa06c21d4f14a13e060d2d31bbaae740f4af4.css"><div id="gist28627206" class="gist"></div>
10        <link rel="stylesheet" href="js/embed-cbe5b40fa72b0964f90d4919c2da8f8f94d7c9f6c2aa49c07f6fa3.css"><div id="gist28627206" class="gist"></div>
11    </head>
12
13    <div class="container">
14        <header id="navtop">
15            <a href="index.html" class="logo fleft"><img src="img/logo.png" alt=""></a>
16            <nav class="fright">
17                <ul>
18                    <li><a href="index.html">Home</a></li>
19                    <li><a href="about.html">About</a></li>
20
21                        <li><a href="roadmap.html" class="navactive">Roadmap</a></li>
22                        <li><a href="documentation.html">Documentation</a></li>
23                </ul>
24            </nav>
25        </header>
26        <div class="Services-page main grid-wrap">
27            <header class="grid col-full">
28                <hr/>
29                <p class="fleft">ROADMAP</p>
30                <div style="background-color: #dff0d8;padding:4px 8px;border-radius: 4px;" class="grid col-full">
31                    <h4 style="font-size: 16px">
32                      mkDocs version of the roadmap is available at <a href="https://silcnitc.github.io/expl-docs/roadmap" target="_blank">silcnitc.github.io/expl-docs/roadmap</a>
33                    </h4>
34                </div>
35                <!--<a class="button" href="">Download as PDF</a>-->
36            </header>
37            <aside class="grid col-one-quarter mq2-col-full">
38                <menu>
39                    <ul>
40                        <li class="sec"><a href="#nav-stage0">0. Installation</a> </li>
41                        <li class="sec"><a href="#nav-stage1">1. CodeGeneration for Arithmetic Expressions</a></li>
42                        <li class="sec"><a href="#nav-stage2">2. Introduction to static storage allocation</a></li>
43                        <li class="sec"><a href="#nav-stage3">3. Adding Flow Control Statements</a></li>
44                        <li class="sec"><a href="#nav-stage4">4. User Defined Variables and arrays</a></li>
45                        <li class="sec"><a href="#nav-stage5">5. Adding Functions</a></li>
46                        <li class="sec"><a href="#nav-stage6">6. User defined types and Dynamic Memory Allocation</a></li>
47                    <!--    <li class="sec"><a href="#nav-stage7">7. Register Allocation</a></li> -->
48                        <li class="sec"><a href="#nav-stage7">7. Adding Objects – Data encapsulation</a></li>
49                        <li class="sec"><a href="#nav-stage8">8. Inheritance and Sub-type Polymorphism</a></li>
50
51
52                    </ul>
53                </menu>
54            </aside>
55            <body>
56            <section class="grid col-three-quarters mq2-col-full">
57                <div class="grid-wrap">
58                    <article class="grid col-full">
59                        <h2>Using the Roadmap</h2>
60                        <p>
61                            This roadmap is divided into several stages, to be done in sequential order. Incrementally you will build a compiler for the ExpL language according to its specification. Links are provided for background reading material wherever appropriate. It will be assumed that you have background in C programming, Data Structures and Principles of Computer Organization.
62                        </p>
63                    </article>
64                    <article class="grid col-full" id="nav-stage0">
65                        <h2>Stage 0 : Installation and Preparation</h2>
66                         <b>Time Estimate :</b> 2 weeks, 5-10 hours/week
67                        <p>
68                            <b>Pre-requisites</b>: NIL<br>
69                            In this stage, you will download and familiarize yourself with the simulation package and learn the compiler design software tools LEX and YACC.  Follow the instructions below.
70                        </p>
71                        <p>
72                            <ul>
73                                <li id="otis">1.  Install the LEX, YACC and the XSM simulator package.  Follow the instructions <a href="install.html" target="_blank">here</a></li>.
74                            </ul>
75                        </p>
76                        <p>
77                            You need to learn two software tools - YACC and LEX which you will use in the project. These tools are somewhat
78                            sophisticated. Fortunately, understanding what is enough for the purpose of our compiler project is not very difficult. The following tutorials will help you through this process.
79                        </p>
80                        <p>
81                            If you are not already familiar with the tools LEX and YACC do the following:<br>
82                            <ul>
83                                <li id="otis">2.  Complete the <a href="lex.html" target="_blank">LEX tutorial</a>.</li>
84                                <li id="otis">3.  Complete the <a href="yacc.html" target="_blank">YACC tutorial</a>.</li>
85                                <li id="otis">4.  Complete the <a href="ywl.html" target="_blank">Using YACC with LEX tutorial</a>.</li>
86                            </ul>
87                        </p>
88                        <p>
89                            If you are not already familiar with using the GNU debugger, do the following:
90                            <ul>
91                                <li id="otis">5.  Complete the <a href="gdb.html" target="_blank">GDB tutorial</a>.</li>
92                            </ul>
93                        </p>
94
95                        <p>
96                            The next step is to understand the target machine envionment. You must carefully go through the following tutorial
97                            before proceeding to the next stage of this roadmap.
98                        </p>
99                        <p>
100                            <ul>
101                                <li id="otis">6.  Complete the <a href="xsm-environment-tut.html">XSM execution environment tutorial</a>.</li>
102                            </ul>
103                        </p>
104                        <p>
105                            With this, you are ready with all the required pre-requisites to proceed further in this roadmap.
106                        </p>
107                            <div class="up column3 mright"> <a href="#navtop" class="ir">Go up</a> </div>
108                    </article>
109                    <article class="grid col-full" id="nav-stage1">
110                        <h2>Stage 1 : Code generation for Arithmetic Expressions</h2>
111                           <b>Time Estimate :</b> 0.5 week, 5-10 hours/week
112                        <p>
113                            <b>Prerequisites</b>:<br/>
114                            <ul>
115                                <li id="otis">1.  You must be comfortable with LEX and YACC.  ( If you are not, you must first do <a href="lex.html" target="_blank">LEX</a> tutorial, <a href="yacc.html" target="_blank">YACC</a> Tutorial and <a href="ywl.html" target="_blank">Using Lex with Yacc</a> tutorials.)</li>
116                                <li id="otis">2.  You must have completed the <a href="xsm-environment-tut.html" target="_blank">XSM environment tutorial</a> <b>including all the exercises</b> before staring this stage.</li>
117                            </ul>
118                        </p>
119                        <p>
120                            <b>Learning Objectives</b>:<br/>
121                            <p>In this stage, you will:</p>
122                            <ul>
123                                <li id="otis">1.  Parse an input  arithmetic expression and create an expression tree using YACC and LEX.</li>
124                                <li id="otis">2.  Recursively traverse the tree and generate assembly language code.  The allocation of registers for storing results of intermediate computations will be handled enroute.</li>
125                            </ul>
126                            <hr>
127                        </p>
128                        <p>
129                            A compiler is a software that takes as input a high level program and produces a machine
130                            recognizible target program as output.  The high level program typically allows variables,
131                            expressions, conditionals, iterative constructs, user defined types, functions etc.
132                            The low level target program on the other hand will be a sequence of assembly level
133                            instructions that can be run on a target machine (which is the XSM simulator in this
134                            project).
135                          </p>
136                        <p>
137                            The strategy of the roadmap is to help you build the compiler in stages.
138                            We start here by building a very simple c
138ompiler whose input (high level) program
139                            contains only simple arithmetic expressions.
140                            In subsequent stages, we will add more and more constructs to the
141                            input language one by one, learning the relevant theoretical concepts along the way.
142                        </p>
143
144                      <!--  <p>
145                            In this stage, you will implement a very simple compiler that can take an arithmetic expression as input (from some input file)  and generate a target executable file containing XSM instructions to evaluate the expression and output the result.
146                        </p> -->
147                        <p>
148                            We assume that you have implemented the library routine for handling console output,
149                            which you were asked to do in the <a href="xsm-environment-tut.html" target="_blank">XSM execution environment tutorial</a>.
150                        </p>
151
152                        <p>
153                            Consider arithmetic expressions with the following syntax.
154                            <div class="syntax">
155                                E :  E + E | (E) | NUM
156                            </div>
157                            Where the <a href="lex.html#navyytext" target="_blank">lexeme</a> <b>NUM</b> correspond to integers.  Assume left <a href="yacc.html#associativity" target="_blank">associativity</a>  for '+'. Thus, the <a href="lex.html#token" target="_blank">tokens</a> relevant are NUM and +. The attribute value associated with a number is the number read.  Assume that the input file is passed as argument to the main() function in YACC.
158                        </p>
159                        <p>
160                            The lexer must pack the attribute into a tree node of the following structure:
161                           <div class="syntax">
162                            typedef struct tnode{<br>
163                            &emsp;int val;
164                            &emsp;char *op;           //indicates the name of the operator for a non leaf node<br>
165                            &emsp;struct tnode *left,*right;      //left and right branches<br>
166                            }tnode;<br>
167                            <br>
168                            #define YYSTYPE tnode*
169                            </div>
170                            Since the semantics actions in the parser must build the tree, the following function must be written:
171                            <div class="syntax">
172                            /*Make a leaf tnode and set the value of val field*/<br/>
173                            struct tnode* makeLeafNode(int n);<br/>
174                            <br/>
175                            /*Make a tnode with operator, left and right branches set*/<br/>
176                            struct tnode* makeOperatorNode(char op,struct tnode *l,struct tnode *r);
177                            </div>
178                        </p>
179                        <p>
180                            <b>Task 1</b>:  Build the expression tree for the given input.<br>
181                            <b>Exercise 1</b>:  Output the prefix and postfix forms of the expression from the tree.<br>
182                        </p>
183
184                        <p>
185                            (Note:  You would have already completed this task if you have done the <a href="ywl.html" target="_blank"> Using Yacc With Lex tutorial </a>).
186                        </p>
187                        <p>
188                            Now, comes the next task - to generate assembly language program equivalent for the expression and write it out into an executable file in the XEXE format.  Once this is done, you can use the simulator to load the XEXE file into the memory of the XSM machine and execute it as outlined in the <a href="xsm-environment-tut.html" target="_blank"> XSM run time environment tutorial</a>.
189                        </p>
190
191                        <p>
192                            To do this, one needs to know the following:<br>
193                            <ul>
194                                <li id="otis">
1941. The <a href="abi.html#nav-XSM-instruction-set" target="_blank">machine model and the instruction set</a> of the target machine.</li>
195
196                                <li id="otis">2. Format of the <a href="abi.html#nav-XEXE-executable-file-format" target="_blank"> executable file</a>.</li>
197
198                                <li id="otis">3. You need to know the address in the memory (in the target machine) where each instruction you generate will be loaded (by the OS loader). This is because program control instructions like JMP, CALL etc.,  requires specification of the jump address.
199                            </p>
200                            <p>
201                                As already outlined in the <a href="xsm-environment-tut.html" target="_blank"> XSM run time environment tutorial</a>, the header will be loaded into addresses 2048-2055. The first instruction generated by you will be loaded to the address 2056. Each XSM instruction occupies 2 memory words. Hence, the next instruction will be loaded at address 2058 and so on. The entry point field of the header must contain the address of the first instruction to be fetched and executed.</li>
202
203                                <li id="otis">4. You need to fix the memory addresses where variables and other data is stored. For example, for each variable in the program, the compiler will have to allocate storage space in memory. The ABI stipulates that the region for this is the <a href="abi.html#nav-virtual-address-space-model" target="_blank"> stack region</a>. Thus each variable must be stored in some address between 4096 and 5119.</li>
204
205                                <li id="otis">5. Since XSM machine stipulates that arithmetic and logic instructions can be done only when operands are loaded into machine registers, we need to load the contents of variables/constants in the program into the machine registers before processing them. This brings in the problem of register allocation. The XSM machine makes available 20 registers (R0-R19) for the compiler.</li>
206                            </ul>
207                        </p>
208                        <p>
209                            Of the above, the XSM execution environment tutorial has already explained (1) and (2). Evaluation of expressions do not involve either storage allocation or program control transfer (JMP). Hence, we will not take up (3) and (4) at this stage. However, we need to solve (5) now.
210                        </p>
211                        <p><h3>What must be the evaluation strategy?</h3></p>
212                        <p>
213                            Let us take an example:<br>
214                            If you are given a two node expression tree as shown below corresponding to the expression (3+2):<br>
215                        </p>
216                        <p>
217                            <img src="img/tree1.png">
218                        </p>
219                        <p>
220                            The evaluation strategy will be:
221                            <ul>
222                                <li id="otis">1.  Store 3 in a register – say R0.</li>
223                                <li id="otis">2.  Store 2 in a register – say R1.</li>
224                                <li id="otis">3.  ADD R0, R1.</li>
225                            </ul>
226                        </p>
227                        <p>
228                            The result will be stored in R0 and is sufficient for us. To generate code for the above tasks and write it into a target_file, you must write code as:
229
230                        <div class="syntax">
231                            fprintf(target_file, "MOV R0, 3");<br>
232                            fprintf(target_file, "MOV R1, 2");<br>
233                            fprintf(target_file, "ADD R0, R1");<br>
234                        </div>
235
236                            However, life becomes complicated if we have an expression like (3+2)+(5+6) resulting in the following tree.
237                        </p>
238                        <p>
239                            <img src="img/tree2.png">
240                        </p>
241                        <p>
242                            Of course, we can “hand craft” this case also.  But the strategy will not generalize. The basic 
242issue is that your compiler does not know the input expression before-hand.  Technically speaking, the issue is that the “expression is not available at <b>compile time</b>, but only known at <b>run time</b>”. Your code generation module must be more <i>"intelligent"</i> to handle <i>arbitrary expressions</i>.
243                        </p>
244                        <p>
245                            The root of the problem with the above code is that R0 and R1 were picked by you and not by your compiler. Thus, we must have a <b>register assignment policy</b> (basically a function) that returns a free register whenever we require one. That is, you must design the following functions:
246                        </p>
247                        <div class="syntax">
248                            int getReg()   //  Allocate a free register
249                        </div>
250
251                        <p>
252                            That returns the register number of an unallocated register, so that your code for adding 3 and 2 would look like:
253                        </p>
254
255                        <div class="syntax">
256                            int p = getReg();<br>
257                            int q = getReg();<br>
258                            fprintf(target_file, “MOV R%d, 3”, p);<br>
259                            fprintf(target_ file, “MOV R%d, 2”, q);<br>
260                            fprintf(target_file, “ADD R%d, R%d,”, p,q);<br>
261                        </div>
262
263                        <p>
264                            In addition to allocating registers, you must also have mechanism to <b>release a register</b> back into the register pool. In the above example, after the ADD instruction is generated R1 can be released and send back to the register pool.
265                        </p>
266
267                        <p>
268                            For this purpose, you will write a function
269                        </p>
270
271                        <div class="syntax">
272                            freeReg() //  Releases a register.
273                        </div>
274
275                        <p>
276                            To make the allocation  strategy simple,  we suggest that you  generate target code in such a way that  <i>the result of a CPU instruction involving two registers will be always stored in the register with lower index</i>. In the code above the result of the computation is kept in R0 and not R1 so that the register with the higher index value can be released. As a consequence, the freeReg() function does not require any arguments. Instead, freeReg() and getReg() can be designed to keep track of the highest numbered register allocated so far and hence can keep track of the correct register that must be allocated or freed.
277                        </p>
278                        <p>
279                            The following summarizes the register allocation strategy:
280                        </p>
281                        <div class="syntax">
282                            1. Whenever a register is needed, allocate the lowest numbered register that is free. (Thus, give R0 if possible, otherwise R1 etc.)<br>
283
284                            2.  Whenever we free a register, always release the highest used register that was allocated previously. (Thus, if R0, R1 and R2 were allocated, freeReg() must release R2).
285                        </div>
286
287                        <p>
288                            Finally, we must design a code generation module.  The strategy here is to start with an expression tree and do the following:
289                        </p>
290
291                        <div class="syntax">
292                            1.  At the leaf nodes of the tree (corresponding to a NUM),  Allocate a new register and store the number &emsp;to the register.<br>
293                            2.  At the intermediete nodes :<br>
294                            &emsp;a.  Generate code for the left subtree (recursively). Find out the register holding the result.<br>
295                            &emsp;b.  Evaluate the right subtree (recursively). Find out the register holding the result.<br>
296                            &emsp;c.  ADD the contents of the two registers and store the result in the lower numbered register.<br>
297                            &emsp;d.  Release the higher numbered register and return.<br>
298                        </div>
299
300                        <p>
301                            In the above box, as step 2.a and 2.b requires finding the index of the register which stores the result of expression evaluation. The simplest strategy is to <b>design a codeGen() function that can take as input an expression tree and generates code for the expression, returning the index of the register storing the result</b>:
302                        </p>
303                        <div class="syntax">
304                            #define reg_index int;<br>
305                            reg_index codeGen( struct node *t) {<br>
306                            &emsp;..<br>
307                            &emsp;..<br>
308                            &emsp;return register number storing result<br>
309                            }
310                        </div>
311                        <p>
312                            The codeGen() function takes as input a pointer to the root of an expression tree and generates code for the subtree rooted at that node. After generating code, the function must return the index of the register storing the result. See this <a href="codegen.html" target="_blank">link</a> for furthur details.
313                        </p>
314                        <p>
315                            <b>Task 2</b>
315: Complete the simple compiler for expression evaluation and generate the executable file. The result of expression evaluation may be stored in the first location of the stack region – memory address 4096. This value may be printed out using the write system call. Note that the XEXE executable format must be adhered so that the XSM simulator can load and execute the file.
316                        </p>
317                        <p>
318                            <b>Note</b>:  To run the simulator, you must prepare the library.lib together with the XEXE executable file.  Please follow instructions in the <a href="xsm-environment-tut.html" target="_blank">XSM environment tutorial</a>.
319                        </p>
320                        <p>
321                            <b>Exercise 2</b>:  Modify the grammar to
322                            <div class="syntax">E :  E + E | E*E | E-E| E/E | (E) | NUM</div>  Assume standard rules of precedence and associativity.
323                        </p>
324                        <p>
325                            <b>Exercise 3</b>:  Redo Exercise 2 assuming that the input expression is given in prefix from.
326                        </p>
327                        <p>
328                            <b>Note:</b> Here we assumed that machine registers never get exhausted. XSM provides 20 general purpose registers and these registers are sufficient for all practial purposes.  However, if all registers are exhausted, then space will have to be allocated in memory.  We will not address this contingency in this roadmap. If register pool is exhausted, your compiler may stop compilation and flag "Out of registers"  error.
329                        </p>
330                        <div class="up column3 mright">
331                            <a href="#navtop">  &#x2191; </a>
332                        </div>
333                    </article>
334
335                    <article class="grid col-full" id="nav-stage2">
336                        <h2>Stage 2. Introduction to static storage allocation</h2>
337                           <b>Time Estimate :</b> 0.5 week, 5-10 hours/week
338                        <p>
339                            <b>Prerequisites</b> :
340                            <ul>
341                                <li id="otis">1.  You must be comfortable with LEX and YACC.  (If you are not, you must first do <a href="lex.html" target="_blank"> LEX tutorial</a>, <a href="yacc.html" target="_blank">
341YACC Tutorial</a> and <a href="ywl.html" target="_blank"> YACC+LEX tutorial</a>.)</li>
342                                <li id="otis">2.  You must have completed the <a href="xsm-environment-tut.html" target="_blank">XSM environment tutorial</a> before starting this stage.</li>
343                            </ul>
344                        </p>
345                        <p>
346                            <b>Learning Objectives</b> :
347                            <ul>
348                                <li id="otis">In this stage, you will extend the expression evaluator of the previous stage to support a set of pre-defined variables with Input/Output and assignment statements. You will get introduced to the notion of <b>static storage allocation</b> enroute. You will also learn to differentiate between statements and expressions and also construct an <i>abstract syntax tree representation</i> for a program.</li>
349                            </ul>
350                            <hr>
351                         </p>
352                         <p>
353                            Consider a simple programming language with the following syntax:
354                            <div class="syntax">
355                                Program ::= BEGIN Slist END | BEGIN END<br>
356                                <br>
357                                Slist ::=  Slist Stmt | Stmt<br>
358                                <br>
359                                Stmt ::= InputStmt |  OuptputStmt | AsgStmt<br>
360                                <br>
361                                InputStmt ::= READ(ID);<br>
362                                <br>
363                                OutputStmt ::== WRITE(E);<br>
364                                <br>
365                                AsgStmt ::==  ID = E;<br>
366                            </div>
367                            Apart from the <a href="lex.html" target="_blank">literal tokens</a>, BEGIN, END, READ, and WRITE are tokens corresponding to keywords "begin", "end", "read" and "write".  ID is a token for variables.  We will permit only variables [a-z] in this stage.
368                         </p>
369                         <p>
370                            To support variables to appear in expressions, you must add the rule <b>E := ID</b> to the expression syntax used in Stage 1. The above syntax defines a small programming language that permits just straight line programs (programs without conditionals, loops, jumps or such control transfer constructs). There are only 26 pre-defined variables that are supported – a, b,c,..,z. A typical program would look like:
371                            <div class="syntax">
372                                begin<br>
373                                &emsp;read (a);<br>
374                                &emsp;read (b);<br>
375                                &emsp;d = a + 2 * b;<br>
376                                &emsp;write (a+d);<br>
377                                end;
378                            </div>
379                         </p>
380                         <p>
381                            We will assume that variables can store only integers. Handling variables of multiple types will be taken up in subsequent stages.
382                        </p>
383                        <p>
384                            A conceptual point to note here is that apart from the addition of variables, the extended language now has two kinds of constructs – expressions and <b>statements</b>. While an expression evaluates to a value (in this case, we limit ourselves to integer expressions), a statement commands the execution of some action by the machine. For example, the statement <i>read(a);</i> instructs the action of reading a variable from the console into a variable a. <i>write(a+d);</i> instructs evaluation of the expression (a+d) and printing the result into the console output.
385                        </p>
386                        <p>
387                            Another important conceptual point to note is that the introduction of variables also demand binding them to storage (memory) locations. The storage location associated with a variable must hold the value of the variable at each point of program execution. A statement (like the assignment statement or a read statement) that alters the value of a variable must result in a change the value stored in the corresponding storage location.
388                        </p>
389                        <p>
390                            In the present case, the compiler can fix the address for each variable in memory right at the time of program compilation. Since the ABI stipulate that storage allocation must be done in the stack regi
390on, we can pre-allocate the first 26 memory locations in the stack region of <a href="abi.html#nav-virtual-address-space-model" target="_blank">memory</a> for the variables a-z. Thus, variable <i>a</i> will refer to contents of address 4096, <i>b</i> to contents of address 4097 and so on. Any time the compiler encounters the variable – say <i>a</i>, the address to be looked at is fixed – in this case 4096. Such allocation policy is called <b>static allocation</b>. In later stages you will encounter situations where it will not be possible for the compiler to fix memory address of a variable at compile time. This leads to <b>run time</b> and <b>dynamic memory allocation</b> policies. For now, we will be content with static allocation.
391                        </p>
392                        <p>
393                            To implement the above, your compiler must:
394                            <ul>
395                                <li id="otis">1. Fix the storage location for each variable. As noted above, the first 26 locations of the stack region starting at address 4096 may be assigned for a to z. Note that the XSM machine can store an integer in a single memory location. Hence, for each variable we need to allocate only 1 memory word. Note that "allocation" here means that while generating code, the compiler assumes that the variable a is stored in location 4096, b in location 4097 and so forth.</li>
396
397                                <li id="otis"><b>Note</b> : Some programming languages stipulate that variables must be initialized to zero.  In that case, the compiler must generate code to MOV 0 to each of these locations before generating code for statements in the program. Some machines provide machine instructions that support initializing memory to zero.  Certain operating systems would have initialized all memory regions (except those to which code is loaded into) to zero at load time.  We will not pursue these issues here.</li>
398
399                                <li id="otis">2. To translate an assignment statement, the compiler must generate code to evaluate the expression and then MOV the contents of the register storing the result to the memory location allocated for the variable.</li>
400
401                                <li id="otis">3. To translate a Read statement, the compiler must generate code to invoke the <a href="abi.html#nav-eXpOS-system-library-interface" target="_blank">library</a> function for read, passing the address of the variable as argument. Write is implemented similarly.</li>
402                            </ul>
403                        </p>
404                        <p>
405                            But before getting into code generation, we must create an <b>abstract syntax tree (AST)</b> for the program.  An abstract syntax tree is a tree representation of the program, just like an expression tree for expressions. An abstract syntax tree for the above program would look like the following:
406                        </p>
407                        <p>
408                            <img src="img/ast_stage2.png">
409                        </p>
410                        <p>
411                            Observe that each node now needs to store distinguishing information like:
412                            <ul>
413                                <li id="otis">1. Whether it corresponds to a variable, constant, operator, assignment statement, write statement or read statement. </li>
414                                <li id="otis">2. In case of operators, the information on the operator must be present. In the case of constants, the value must be stored in the node. In the case of variables, the node must contain the variable name.</li>
415                                <li id="otis">3. There are also connector nodes which simply join two subtrees of statements together.</li>
416                            </ul>
417                        </p>
418                        <p>
419                            This leads to the definition of the following node structure:
420                            
420<script src="js/dd1979bba5d35250a0c9419520a6b5b8.js"></script>
420
421                        </p>
422                        <p>
423                            <b>Task 1</b> : Use Yacc and Lex to generate abstract syntax tree representation of a program. A file containing the source program will be input to your program.
424                        </p>
425                        <p>
426                            Thus, after parsing, we use the syntax directed translation scheme of YACC to construct an intermediate representation – namely, the abstract syntax tree. This phase of compilation is sometimes called the <b>front end</b> of the compiler. The next step is to recursively traverse the expression tree to generate executable code.  This is typically called the <b>back end</b>. The output of the front end is generally a <b>machine independent intermediate representation</b> like the AST. The back end of course will be dependent on the target platform.
427                        </p>
428                        <p>
429                            <b>Task 2</b> : Modify CodeGen() function of Stage 1 to generate code for the abstract syntax tree generated as Task 1 above.
430                        </p>
431                        <p>
432                            In the next stage, we will see how program control instructions like if-then-else can be incorporated into the language.
433                        </p>
434                        <p>
435                            <b>Note</b> : An abstract syntax tree is an <a href="https://en.wikipedia.org/wiki/Intermediate_representation" target="_blank">intermediate representation</a> of the source program in a tree form suitable for code generation. There are several other forms of intermediate representations like the three address code form, the static single assignment form etc. This roadmap will be based on the abstract syntax tree representation.
436                        </p>
437                        <p>
438                            In commercial strength compilers, the source is first translated to intermediate forms like the three address form which is a <b>lower level representation</b> (that is the intermediate form is closer to machine code) than the AST. Typically machine independent <a href="https://en.wikipedia.org/wiki/Optimizing_compiler" target="_blank">code optimizations</a> are performed on the intermediate code and only then the back-end code generation is run. This step is followed by another set of machine dependent code optimizations before the target file is finally generated. As these issues are beyond the scope of our project, we will not dwell into these matters further in this roadmap.
439                        </p>
440                        <p>
441                            <b>Exercise 1</b> : Build an <b>evaluator</b> for the program. (Hint: Your front end does not change. But, instead of generating code from the AST, you can recursively "evaluate" it. For storage allocation of variables, you can simply declare an array that can store 26 integers and allocate one entry for each variable).
442                        </p>
443                        <p>
444                            <b>Note</b> : The compiler generates target code which must be executed by the target machine. In our case, the compiler you wrote as Task 2 actually is a <b>cross compiler</b>. This means that your compiler generated target code that is not for your host system, but on some other target platform – which in our case the simulated XSM machine. The evaluator done in Exercise 1 actually does not generate "code" for any machine. Instead, it executes the program in "then and there". Such a program could be classified as an <b>interpreter</b>. (Unfortunately, the standard terminology in literature associated with the term "interpreter" seems to be contradictory to this classification).
445                        </p>
446                        <div class="up column3 mright">
447                            <a href="#navtop">  &#x2191; </a>
448                        </div>
449                    </article>
450                    <article class="grid col-full" id="nav-stage3">
451                        <h2>Stage 3:  Adding Flow Control Statements</h2>
452                           <b>Time Estimate :</b> 1 week, 5-10 hours/week
453                        <p>
454                            <b>Prerequisite</b>:  You must read the  <a href="label-translation.html" target="_blank">
454label translation tutorial</a> before proceeding with this stage.
455                        </p>
456                        <p>
457                            <b>Learning Objectives</b>:
458                            <ul>
459                                 <li id="otis">In this stage, you will extend the straight-line-program compiler of Stage 2 to support control flow constructs like if-then-else, while-do, break and continue. You will encounter integer and boolean expressions and the notion of <i>type</i> enroute. You will also learn the use of <i>labels</i> for handling control flow constructs.</li>
460                            </ul>
461                            <hr>
462                        </p>
463                        <p>
464                            The if-then-else and the while-do constructs can be added to the source language of Stage 2 by adding the grammar rule:
465                            <div class="syntax">
466                                Ifstmt ::=  IF (E) then Slist Else Slist ENDIF<br>
467                                &emsp;&emsp;&emsp;&emsp;&emsp;| IF (E) then Slist ENDIF;
468                                <br>
469                                Whilestmt ::= WHILE (E) DO Slist ENDWHILE;<br>
470                            </div>
471                            To permit logical expressions, we need to add to the grammar the following productions:
472                            <div class="syntax">
473                                E ::= E &lt; E  |  E &gt; E  |  E &lt; =E  |  E &gt;= E  |  E != E  |  E == E;<br>
474                            </div>
475                            A simple program in this language to find the largest among three numbers would look like the following:
476                            <div class="syntax">
477                                &emsp;read(a);<br>
478                                &emsp;read(b);<br>
479                                &emsp;read(c);<br>
480                                &emsp;if (a &lt; b) then<br>
481                                &emsp;&emsp;if (b &lt; c) then Write(c);  else Write(b); endif; <br>
482                                &emsp;else<br>
483                                &emsp;&emsp;if (a &lt; c) then Write(c); else Write(a); endif; <br>
484                                &emsp;endif; <br>
485                            </div>
486                            Note that we continue to assume that variables hold only integer values. The first task in translation is to complete the front end.
487                        </p>
488                        <p>
489                            There is one important conceptual point to understand here before proceeding to the front end implementation.  With the introduction of logical expressions, there are two <b>types</b> of expressions in the language – <b>arithmetic expressions</b> and <b>logical expressions</b>. An arithmetic expression evaluates to an integer value whereas a logical expression evaluates to a <b>boolean value</b> – that is true/false.
490                        </p>
491                        <p>
492                            The guard of an if-else statement or a while-do statement must be a boolean expression.  On the other hand, the expression on the right side of an assignment statement must be of integer type as variables are assumed to hold integer values only. In other words, the statements given below are <b>invalid</b>.
493                            <div class="syntax">
494                                if (a+b) then Write(c);<br>
495                                &emsp;&emsp;OR<br>
496                                a = b &lt; c;<br>
497                            </div>
498                        </p>
499                        <p>
500                            Your compiler must flag a "<i>type mismatch</i>" error if such constructs are encountered during the AST construction process. A program with type errors must not pass the compiler's type check scrutiny and the compiler must report error without generating code. Type analysis is a part of the responsibilities of a compiler (normally classified under <a href="https://en.wikipedia.org/wiki/Semantic_analysis_(compilers)" target="_blank">semantic analysis</a>).
501                        </p>
502                        <p>
503                            A simple way to handle this issue is to <i>annotate each node in the AST with a <b>type attribute</b></i> that indicates what is the type of the expression (or subexpression) with this node as the root.
504                        </p>
505                        <p>
506                            For example, consider the AST for the following erratic expression.
507                            <div class="syntax">
508                                d = ( a + b ) + ( c &lt; 3 )
509                            </div>
510                            <p>
511                               <img src="img/ast3.png">
512                            </p>
513                        </p>
514                        <p>
515                            Here, the root of the AST is an assignment node which is <b>typeless</b>. (statements have no type, only expressions have a type associated with them). The left subtree of the root is a variable, and hence has type integer. The right subtree is a  <b>+</b>  node of type integer. Hence, at the root, there is no type mismatch. However, the right child of the right subtree has type boolean and does not match the operand type for the + operator. Hence the compiler must terminate compilation flagging error "type mismatch". Note that the compiler can stop processing when the first error is encountered without proceeding further with the tree construction.
516                        </p>
517                        <p>
518                            To implement type checking, add a type field in the AST node structure.
519                            
519<script src="js/09129e56138b0207d595eaefbf2873cd.js"></script>
519
520                            At the leaf nodes of the tree, since you have either constants or variables, the type must be set to integer. Next, while constructing the tree for intermediate nodes, check whether the types of the children are compatible with the operator at the root. For instance, for the addition operation, the check could be as the following:
521                            <div class="syntax">
522                            E :== E+E {<br>
523                            &emsp;&emsp;&emsp;&emsp;&emsp;&emsp;if (($1->type != inttype) || ($2->type != inttype)) {<br>
524                            &emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;error("type mismatch"); <br>
525                            &emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;exit();<br>
526                            &emsp;&emsp;&emsp;&emsp;&emsp;&emsp;} else {<br>
527                            &emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;$$->type = inttype); <br>
528                            &emsp;&emsp;&emsp;&emsp;}<br>
529                            </div>
530                        </p>
531                        <p>
532                            If there is no mismatch, you must annotate root node ($$->type) with the proper type (integer in the above case).
533                        </p>
534                        <p>
535                            <li id="otis">
536                                <b>Note</b>:  The above check is better done inside the TreeCreate() function so that the YACC file is not cluttered with C statements.
537                            </li>
538                        </p>
539                        <p>
540                            The essential idea is that the type of each node can by synthesized from the types of the subtrees. At any stage, the compiler may terminate flagging error if a type error is found.
541                        </p>
542                        <p>
543                            <b>Task 1</b>:  Complete the front-end module (AST construction) for the programming language. You need to
544                            <ul>
545                                <li id="otis">(1) add additional lexical tokens for the new constructs</li>
546                                <li id="otis">(2) make appropriate modifications in the tree node structure including provision for storing type attribute</li>
547                                <li id="otis">(3) modify the TreeCreate() function to have three subtrees passed (for if-then-else) etc.</li>
548                            </ul>
549                        </p>
550                        <p>
551                            <b>Exercise 1</b>:  To test the implementation of Task 1, implement an <b>evaluator</b> for the expression tree.  Test with simple programs like those for finding the largest of 3 numbers, sum of n numbers (n read from input) etc.
552                        </p>
553                        <p>
554                            The next task is to complete the back-end code generation phase.  For better clarity, we will split the task into two steps.
555                        </p>
556                        <p>
557                            <ul>
558                                <li id="otis"><b>Step 1</b>:  Generate code with <b>labels</b>.  At this stage labels will be placed at various control flow points of the target assembly code so that a JMP instruction will only indicate the label corresponding to the instruction to which transfer of program flow must happen.</li>
559                                <li id="otis"><b>Step 2</b>:  Replace the labels with addresses.</li>
560                            </ul>
561                        </p>
562                        <p>
563                            <b>Important note</b>: You must have read the <a href="label-translation.html" target="_blank">label translation tutorial</a> before proceeding any further.
564                        </p>
565                        <p>
566                            We will now look at Subtask 1. Consider the following statement:
567                            <div class="syntax">
568                                while (a < b) {<br>
569                                &emsp;&emsp;a = a+1 ;<br>
570                                }<br>
571                            </div>
572                        </p>
573                        <p>
574                            The expression tree for the above statement would look like:
575                        </p>
576                        <p>
577                            <img src="img/ast31.png">
578                        </p>
579                        <p>
580                            Suppose variable a is bound to address 4096, b to address 4097, then our plan is to generate code that would look like the following:
581                            <div class="syntax">
582                            L1:  <br>
583                            MOV R0, [4096]&nbsp;&nbsp;// transfer a to R0<br>
584                            MOV R1, [4097]&nbsp;&nbsp;//  transfer b to R1<br>
585                            LT R0, R1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//  a&lt;b<br>
586                            JZ R0,L2&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//  if (a&lt;b) is false goto L2  <br>
587                            MOV R0, [4096]&nbsp;&nbsp;//  transfer a to R0<br>
588                            ADD R0, 1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//  add 1  <br>
589                            MOV [4096], R0&nbsp;&nbsp;// transfer sum back to a<br>
590                            JMP L1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;// goto next iteration. <br>
591                            L2: <br>
592                            ... Next Instruction ..  <br>
593                            </div>
594                        </p>
595                        <p>
596                            Note the use of labels L1 and L2 indicating control flow points in the above code. A while statement involves two jumps and two labels. The labels are just symbols that are placed at the start of instructions to which jump instructions must branch to. Placing labels in the code relieves us from bothering about the exact memory address to which jump must be made. Of course, this is only a temporary measure. The final target code must not contain labels.
597                        </p>
598                        <p>
599                            Our strategy here is to first generate code with labels and then replace the labels with addresses. To implement the plan, we may 
599name labels in the program L0, L1,.... We must design an <i>int GetLabel()</i> function that returns the index of the next unused label.  Thus the first call to <i>GetLabel()</i> returns 0, next call returns 1 and so forth.
600                        </p>
601                        <p>
602                            The code generation strategy for the while-do statement is illustrated by the following pseudo-code.
603                            <div class="syntax">
604                                int label_1 = getLabel();<br>
605                                int label_2 = getLabel();<br>
606                                fprintf (target_file "L%d", Label_1)  //  Place the first label here.  <br>
607                                Generate code for the guard expression.    <br>
608                                Generate code to compare the result to zero and if so jump to label_2 // loop exit   <br>
609                                Generate code for the body of the while loop.<br>
610                                fprintf(target_file, "JMP L%d", label_1);   // return to the beginning of the loop.  <br>
611                                fprintf(target_file, "L%d", label_2);    // Place the second label here<br>
612                            </div>
613                        </p>
614                        <p>
615                            <b>Task 2</b>:  Complete the code generation with labels for while-do, if-then and if-then-else constructs.
616                        </p>
617                        <p>
618                            Now, we must complete Step 2 of replacing the labels with the correct addresses. This is explained in the <a href="label-translation.html" target="_blank">label translation documentation</a>.
619                        </p>
620                        <p>
621                            <b>Task 3</b>: Read the link specified above and complete the label translation for  if-then, if-then-else and the while-do statement.
622                        </p>
623                        <p>
624                            <b>Exercise 2</b>: Test your Task 3 code with the following programs:
625                            <ul>
626                                <li id="otis">(a) program to find the largest for a, b, c (values read from input)</li>
627                                <li id="otis">(b) program to read numbers till 0 is input and output the sum. </li>
628                            </ul>
629                        </p>
630                        <p>
631                            <b>Task 4</b>: Add <b>break</b> and <b>continue</b> statements.  Code for these statements need be generated only if they appear inside some while loop.  Otherwise, the compiler may simply ignore these statements, generating no code.  (The primary task is to keep track of which label to jump to when one of these statements is encountered).
632                        </p>
633                        <p>
634                            <b>Exercise</b> : Add <i>repeat-until</i> and <i>do-while</i> statements to the language with standard semantics.
635                        </p>
636                        <p>
637                            <b>Reading Exercise</b> : Please read the <a href="gdb.html" target="_blank">GNU Debugger (GDB) tutorial</a> ,before proceeding to the next stage for learning the GDB debugger.
638                        </p>
639                        <p>
640                            <b>Note</b>:  Often in practice, programming languages allow a program to be split into different functions, written in different source files. In such cases, each file is separately compiled and the compiler generates target code with labels without translating them into addresses.  Even variable references will be symbolic and the actual addresses may not be determined.  Such target files are called <a href="https://en.wikipedia.org/wiki/Object_file" target="_blank">object files</a>.  The compiler will include symbol table information in the object file for translation later.  A separate software called the <a href="https://en.wikipedia.org/wiki/Linker_(computing)" target="_blank">linker</a> will collect the information in all the symbol tables and combine the object files into a single executable file replacing labels and symbolic variable references with actual addresses.
641                        </p>
642                        <div class="up column3 mright">
643                            <a href="#navtop">  &#x2191; </a>
644                        </div>
645                    </article>
646                    <article class="grid col-full" id="nav-stage4">
647                        <h2>Stage 4:  User Defined Variables and arrays</h2>
648                           <b>Time Estimate :</b> 1 week, 5-10 hours/week
649                           <br>
650                        <p>
651                            <b>Prerequisites</b>:<br/>
652                            <ul>
653                                <li id="otis">1.  You must have completed the <a href="gdb.html" target="_blank">GNU Debugger (GDB) tutorial</a> before starting this stage.</li>
654                            </ul>
655                        </p>
656                        <p>
657                            <b>Learning Objectives</b>:<br>
658                            You will extend the language of Stage 3 to permit users to declare and use variables of <i>integer</i> and <i>string</i> types. You will learn <b>symbol table</b> management enroute.
659                            <hr>
660                        </p>
661                        <p>
662                            In this stage, we allow the program to contain variable declarations of the following syntax:
663                            <div class="syntax">
664                                Declarations ::=  DECL  DeclList ENDDECL | DECL ENDDECL<br>
665                                <br>
666                                DeclList ::=  DeclList Decl | Decl<br>
667                                <br>
668                                Decl  ::= Type VarList ;<br>
669                                <br>
670                                Type ::=  INT | STR<br>
671                                <br>
672                                VarList ::= Varlist , ID | ID<br>
673                            </div>
674                        </p>
675                        <p>
676                            We will assume hereafter that all variables used in a program must be <b>declared</b> in the declaration section of the program (between the <i>decl</i> and <i>enddecl</i> keywords). Since string type variables are allowed, we will allow string constants as well.  (See <a href="expl.html#nav-constant">ExpL specification</a> for details).
677                        </p>
678                        <p>
679                            A simple program in this language to find the sum of numbers entered from the console (until a zero is entered) would look like the following:
680                            <div class="syntax">
681                            decl<br>
682                            &emsp;&emsp;int num, sum;<br>
683                            &emsp;&emsp;str mesg;<br>
684                            enddecl<br><br>
685                            read(num);<br>
686                            sum = 0;<br>
687                            while (num != 0) do<br>
688                            &emsp;&emsp;sum = sum + num;<br>
689                            &emsp;&emsp;read(num);<br>
690                            endwhile;<br>
691                            write("sum is:");<br>
692                            write(sum);<br>
693                            mesg = "good bye";<br>
694                            write(mesg);<br>
695                            </div>
696                        </p>
697                        <p>
698                            It is the responsibility of the compiler to track for various <b>semantic errors</b> as:
699                            <ul>
700                                <li id="otis">1.  Flag error if any variable not declared is used.</li>
701                                <li id="otis">2.  Flag error if a type mismatch involving any variable is found.</li>
702                            </ul>
703                        </p>
704                        <p>
705                            To this end, while parsing declarations, the compiler transfers the information about variables in a compile time data structure called the <b>symbol table</b>. The symbol table stores the following information about each variable:
706                            <ul>
707                                <li id="otis">1.  Name of the variable (known at the time of declaration).</li>
708                                <li id="otis">2.  Type (For the present stage, only integer/string).</li>
709                                <li id="otis">3.  Size (For the time being, we will assume that all variables have size one).</li>
710                                <li id="otis">4.  The memory <b>binding</b> of each variable – that is, static memory address determined by the compiler for the variable.</li>
711                            </ul>
712                        </p>
713                        <p>
714                            The first three entries are determined by the declaration of the variable. For the fourth, a simple strategy would be to allocate the first address (4096) for the variable declared first, 4097 for the next variable and so on. Note that here too we are fixing the address of each variable at compile time (<b>static allocation</b>).
715                        </p>
716                        <p>
717                            The following structure may be used for a symbol table entry:
718                            <div class="syntax">
719                                struct Gsymbol {<br>
720                                &emsp;&emsp;char* name;&emsp;&emsp;// name of the variable<br>
721                                &emsp;&emsp;int type;&emsp;&emsp;&emsp;// type of the variable<br>
722                                &emsp;&emsp;int size;&emsp;&emsp;&emsp;// size of the type of the variable<br>
723                                &emsp;&emsp;int binding;&emsp;// stores the static memory address allocated to the variable<br>
724                                &emsp;&emsp;struct Gsymbol *next;<br>
725                                  <!-- ...  any other field for data structure maintainance .. -->
726                                }
727                            </div>
728                        </p>
729                        <p>
730                            The symbol table entries for the program above would look as below:
731                            <img src="img/gsymboltable1.png">
732                        </p>
733                        <p>
734                            To implement the symbol table, you must write two functions.  For a simple implementation, a linear linked list suffices.  In modern compilers, hash tables are maintained to make search efficient.
735                        </p>
736                        <p>
737                            <div class="syntax">
738                                struct Gsymbol *<i>Lookup</i>(char * name);  //  Returns a pointer to the symbol table entry for the variable, returns NULL otherwise.<br>
739                                <br>
740                                void <i>Install</i>(char *name, int type, int size);  // Creates a symbol table entry.
741                            </div>
742                        </p>
743                        <p>
744                            <b>Note</b>:  You must check before installing a variable whether the variable is already present.  If a variable is declared multiple times, the compiler must stop the compilation and flag error.
745                        </p>
746                        <p>
747                            <b>Task 1</b>: Complete the program to parse declarations and set up the symbol table entries and print out the contents of the symbol table.
748                        </p>
749                        <p>
750                            The next task is to make necessary modifications to the AST construction and code generation. These are straightforward. Add a an additional field to the tree node structure
751                            <div class="syntax">
752                                typedef struct tnode{<br>
753                                &emsp;&emsp;int val;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;//value of the constant<br>
754                                &emsp;&emsp;char* varname;&emsp;&emsp;&emsp;//name of the variable<br>
755                                &emsp;&emsp;int type;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;//type of the variable<br>
756                                &emsp;&emsp;int nodetype;&emsp;&emsp;&emsp;&emsp;//node type information<br>
757                                &emsp;&emsp;struct Gsymbol *Gentry;&emsp;&emsp;//pointer to GST entry for global variables and functions<br>
758                                &emsp;&emsp;struct tnode *left,*right;&emsp;&emsp;//left and right branches<br>
759                                }tnode;
760                            </div>
761                        </p>
762                        <p>
763                            While constructing the tree, if a variable is encountered, keep a pointer to the corresponding symbol table entry. Set the type field as well to the correct type. The rest of the type checking steps are exactly as in the previous stage. The AST of while loop present in the above code is as follows (the relevant part of the code is shown below for easy reference):
764                            <div class="syntax">
765                            .<br>
766                            .<br>
767                            .<br>
768                            while (num != 0) do<br>
769                            &emsp;&emsp;sum = sum + num;<br>
770                            &emsp;&emsp;read(num);<br>
771                            endwhile;<br>
772                            .<br>
773                            .<br>
774                            .<br>
775                            </div>
776                        </p>
777                        <p>
778                            <img src="img/ast_stage4.png">
779                        </p>
780                        <p>
781                            There is no serious change to the code generation process, except that for variables, the binding address is obtained from the symbol table.<br><br>
782                            <b>Important Note</b>:  The XSM architecture is unrealistic in that allows a memory word to hold a string.  Normally, in a real system, a string would require storing the characters one after another in consecutive memory locations as in an array.   You will anyway learn array allocation immediately.
783                        </p>
784                        <p>
785                            <b>Task 2</b>:  Complete the AST construction and code generation steps.
786                        </p>
787                        <p>
788                            <h4>Adding arrays</h4>
789                            The next step is to allow declaration of arrays like:
790                            <div class="syntax">
791                                decl<br>
792                                &emsp;---<br>
793                                &emsp;int a[100];<br>
794                                &emsp;str names[20];<br>
795                                &emsp;---<br>
796                                enddecl
797                            </div>
798
799                            The declaration syntax must permit:
800                            <div class="syntax">
801                            Varlist ::= Varlist , ID[NUM] | ID[NUM]
802                            </div>
803                            To implement this, for each variable, you must reserve as much static space as specified by the declaration and set the size field in the symbol table to indicate the number of words allocated.  The next variable must be allocated space only below this space allocated.
804                        </p>
805                        <p>
806                            For instance, for the declaration,
807                            <div class="syntax">
808                                decl<br>
809                                &emsp;&emsp;int a[10], b;<br>
810                                enddecl
811                            </div>
812                            The binding field in the symbol table for the variable a  may be set to address 4096.
813                            The size entry set to 10.  This means that we are allocating locations 4096-4105 for the array.
814                            The next variable, b can be bound to the address 4106.
815                            <img src="img/gsymboltable2.png">
816                        </p>
817                        <p>
818                            <b>Task 2</b>:  Complete the implementation of single dimensional arrays.
819                            <br><br>
820                            <b>Exercise 1</b>:  Permit two dimensional arrays like:
821                            <div class="syntax"> int a[10][10]; </div>
822                            Test your implementation with a program for multiplying two nxn matrices.
823                            <br><br>
824                            <b id="stage4_ex2">Exercise 2</b>:  Permit <i>pointer type</i> variables as in the following declaration as in the C programming language.
825                            <div class="syntax">
826                                decl<br>
827                                &emsp;&emsp;int x, *p;<br>
828                                &emsp;&emsp;str p, *q;<br>
829                                enddecl
830                            </div>
831                            If you permit assignments like p=&amp;x; and q=&amp;p; , pointer variables may also be permitted in expressions like *p=*q+1; for referring to the data pointed to, as permitted in the C programming language. Semantic rules as in the C programming language may be assumed.
832                        </p>
833                        <p>
834                            <b>Note</b>:  Right now, you are not equipped to do dynamic memory
835                             allocation for pointer variables (as done by the malloc() function of C).
836                             Hence, a pointer type variable can be used as a pointer to another statically
837                             declared variable of the corresponding type.  Dynamic memory allocation will be discussed in later stages.
838                        </p>
839                        <h4> <b>Test Programs </b></h4>
840                        <p>
841                          Check your implementation with the following test cases : <br>
842
843                        <h4> 1. Bubblesort (iterative) </h4>
844                        <p>
845                        <p>
846                          This test program reads elements into an array and sorts them using the classic bubblesort algorithm. (iterative version)
847                        </p>
848                        <p>
849                          <b> Input </b> : 1. Number of elements to be sorted from standard input.
850                                           2. Elements to be sorted
851                        </p>
852                        <p>
853                          <b> Output </b> : A sorted array of elements.
854                        </p>
855                        To get the code for this test program <a href="testprograms/stage4/bubblesort.html" target="_blank">click here</a>.
856                      </p>
857                        </p>
858                        <h4> 2. Nth Fibonacci Number(iterative) </h4>
859                        <p>
860                        <p>
861                          This test program prints the nth fibonacci number
862                        </p>
863                        <p>
864                          <b> Input </b> : 1.An integer n
865                        </p>
866                        <p>
867                          <b> Output </b> : nth fibonacci number
868                        </p>
869                        To get the code for this test program <a href="testprograms/stage4/fibaofn.html" target="_blank">click here</a>.
870                      </p>
871                        </p>
872                        <h4> 3. Is Prime or Not </h4>
873                        <p>
874                        <p>
875                          This program tests if a given integer is prime or not.
876                        </p>
877                        <p>
878                          <b> Input </b> : 1.An integer n
879                        </p>
880                        <p>
881                          <b> Output </b> : Prime if n is prime else not a prime.
882                        </p>
883                        To get the code for this test program <a href="testprograms/stage4/prime.html" target="_blank">click here</a>.
884                      </p>
885                        </p>
886                        <h4> 4. Sum of n factorials (iterative) </h4>
887                        <p>
888                        <p>
889                          This program prints the sum to n factorial for a given n.
890                        </p>
891                        <p>
892                          <b> Input </b> : 1.An integer n
893                        </p>
894                        <p>
895                          <b> Output </b> : sum of factorial of all integers 1 to n.
896                        </p>
897                        To get the code for this test program <a href="testprograms/stage4/sum-to-n-fact.html" target="_blank">click here</a>.
898                      </p>
899                        </p>
900
901                        <br>
902
903                    </article>
904                    <article class="grid col-full" id="nav-stage5">
905                        <h2>Stage 5:  Adding Functions</h2>
906                           <b>Time Estimate :</b> 2 weeks, 5-10 hours/week
907                        <p>
908                            <b>Prerequisite Reading</b> :  You must read the following documents before proceeding with this stage:<br>
909                            <ul>
910                                 <li id="otis">1.  The main page of the document <a href="run-data-structures.html" target="_blank">Run time allocation</a>.</li>
911                                 <li id="otis">2.  <a href="run_data_structures/run-time-stack.html" target="_blank">Run time stack Allocation</a>.</li>
912                            </ul>
913                        </p>
914                         <p>
915                            <b>Learning Objectives</b>:
916                            <ul>
917                                 <li id="otis">You will extend the  language of Stage 4 by adding functions with support for recursion. Addition of functions to the language requires handling <b>scope</b> of variables.  Support for recursion demands <b>run-time storage allocation</b>. Only <i>integer</i> and <i>string</i> type variables will be supported.</li>
918                            </ul>
919                            <hr>
920                        </p>
921                        <p>
922                            This is the first major stage in the ExpL project. A skeletal outline of the syntax rules for defining the extension of the language of Stage 4 to supp
922ort subroutines is as below. You are required to fill in rules required to complete the grammar. Note that variables may be only of type integer/string.
923                            <div class="syntax">
924                                Program ::= GDeclBlock FdefBlock <a href="grammar-outline.html" target="_blank">MainBlock</a><br>
925                                &emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;| GdeclBlock MainBlock<br>
926                                &emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;| MainBlock<br>
927                                <br>
928                                GdeclBlock  ::=  DECL GdeclList ENDDECL | DECL ENDDECL<br>
929                                <br>
930                                GdeclList ::= GDeclList  GDecl | GDecl
931                                <br>
932                                GDecl ::=  Type GidList ; <br>
933                                <br>
934                                GidList ::=  GidList , Gid | Gid <br>
935                                <br>
936                                Gid ::= ID <br>
937                                &emsp;&emsp;&emsp;&emsp;&emsp;| ID[NUM] <br>
938                                &emsp;&emsp;&emsp;&emsp;&emsp;| ID(ParamList) <br>
939                                --------------------------------------------------------------------------------------
940                                <br>
941                                FDefBlock ::=  FdefBlock Fdef |  Fdef <br>
942                                <br>
943                                Fdef ::=Type ID ( ParamList ) { LdeclBlock Body } <br>
944                                <br>
945                                ParamList ::= ParamList , Param | Param<br>
946                                &emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;| &emsp;&emsp;/*param can be empty*/<br>
947                                <br>
948                                Param ::= Type ID <br>
949                                <br>
950                                Type ::= INT | STR  <br>
951                                -----------------------------------------------------------------------------------------
952                                LdeclBlock ::= DECL LDecList ENDDECL | DECL ENDDECL <br>
953                                <br>
954                                LDecList ::= LDecList LDecl | LDecl<br>
955                                <br>
956                                LDecl ::=  Type IdList ;  <br>
957                                <br>
958                                IdList ::=  IdList, ID | ID <br>
959                                <br>
960                                Type ::= INT | STR <br>
961                            </div>
962                        </p>
963                        <p>
964                            Since a function call is treated as an expression (whose value is the return value of the function),  the following rules must be added:
965                            <div class="syntax">
966                                E ::= ID ()  |  ID(ArgList) <br>
967                                <br>
968                                ArgList ::=  ArgList, E  |  E <br>
969                            </div>
970                        </p>
971                        <p>
972                            Here is an <a href="run_data_structures/run-time-stack.html#nav-illustration" target="_blank">example</a> for a program with a function. We will take up semantic analysis and AST representation before proceeding to code generation.
973                        </p>
974                        <p>
975                            Each function requires a <b>declaration</b>. The declaration of functions must be made along with the global declarations. The declaration of a function must specify the types and names of the <b>formal parameters</b> and the <b>return type</b> of the function. The compiler must store the declaration information in the global symbol table. For example, the declaration
976                            <div class="syntax">
977                                decl<br>
978                                ..<br>
979                                ..<br>
980                                &emsp;int factorial(int n);<br>
981                                ..<br>
982                                ..<br>
983                                enddecl<br>
984                            </div>
985
986                            specifies that <i>factorial</i> is a function that takes as input one integer argument and returns an integer.  This is sometimes called the <b>signature</b> of the function. Conceptually, to invoke the factorial function, the <b>caller</b> must know:
987
988                            <ul>
989                                <li id="otis">1. The memory address to which the function call must be directed (<b>binding</b>).</li>
990                                <li id="otis">2. The <b>types and names of the formal parameters</b> to the function and the order in which the actual <b>arguments</b> must be given as input to the function.</li>
991                                <li id="otis">3. The <b>return type</b> of the function.</li>
992                            </ul>
993
994                            This precisely is the information that the symbol table stores.
995                        </p>
996                        <p>
997                            A function <b>definition</b> contains:
998                            <ul>
999                                <li id="otis">a)  The function's signature.</li>
1000                                <li id="otis">b)  The declaration of <b>local variables</b> of the function.</li>
1001                                <li id="otis">c)  The code of the function.</li>
1002                            </ul>
1003                            For example, the definition of the factorial function could be as:
1004                            <div class="syntax">
1005                                int factorial(int n){<br>
1006                                &emsp;decl             <br>
1007                                &emsp;&emsp;int f;       <br>
1008                                &emsp;enddecl          <br>
1009                                &emsp;begin<br>
1010                                &emsp;&emsp;if( n==1 || n==0 ) then<br>
1011                                &emsp;&emsp;&emsp;f = 1;<br>
1012                                &emsp;&emsp;else<br>
1013                                &emsp;&emsp;&emsp;f = n * factorial(n-1); <br>
1014                                &emsp;&emsp;endif;<br>
1015                                &emsp;return f;<br>
1016                                &emsp;end<br>
1017                                }<br>
1018                            </div>
1019                            Local variables declared in a function are <i>visible only</i> within the function.  We say that the <b>scope</b> of a local declaration is limited to the function. Moreover, if a global variable is redeclared inside a function, <i>the local declaration overrides the global declaration</i>.
1020                        </p>
1021                        <p>
1022                            Thus, we have two kinds of variables. Global variables that are visible "everywhere" (or having a <b>global scope</b>) and local variables that are visible only within the functions (or having a <b>local scope</b>) where they are declared.
1023                        </p>
1024                        <p>
1025                            The compiler needs to know the binding addresses and types of the local variables for translation of statements of the function to assembly code.  However, this information is irrelevant outside the function.
1026                        </p>
1027                        <p>
1028                            To keep track of the local variable and scope information, our strategy is to keep global and local variables in different symbol tables.  We will have
1029                            <ul>
1030                                <li id="otis">
1031                                    1.  A single <b>global symbol table</b> storing the <i>(name, type, size, binding)</i> information of global variables as well as <i>(name, type, parameters, binding)</i> information for functions.  The following structure is suggested for storing a global symbol table entry.
1032
1033                                    <div class="syntax">
1034                                        <b>struct Gsymbol{</b><br>
1035                                        &emsp;&emsp;<b>char *name;</b>   //name of the variable or function<br>
1036                                        &emsp;&emsp;<b>int type;</b>     //type of the variable:(Integer / String)<br>
1037                                        &emsp;&emsp;<b>int size;</b>     //size of an array<br>
1038                                        &emsp;&emsp;<b>int binding;</b>  //static binding of global variables <br>
1039                                        &emsp;&emsp;<b>struct Paramstruct *paramlist;</b>//pointer to the head of the formal parameter list<br>
1040                                          &emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp; //in the case of functions<br>
1041                                        &emsp;&emsp;<b>int flabel;</b>              //a label for identifying the starting address of a function's code<br>
1042                                        &emsp;&emsp;<b>struct Gsymbol *next;</b>     //points to the next Global Symbol Table entry<br>
1043                                        <b>};</b>
1044                                    </div>
1045                                </li>
1046
1047                                <li id="otis">
1048                                    2.  Several <b>local symbol tables</b> - one for each function containing the <i>(name, type, binding)</i> information for each local variable of the function.  (Note that since the language does not permit arrays to be defined within a function, the size value of local variables is always 1, hence the field is not required).   A local symbol table entry can be stored in the following structure:</li>
1049
1050                                    <div class="syntax">
1051                                        <b>struct Lsymbol{</b><br>
1052                                        &emsp;&emsp;<b>char *name;</b>&emsp;&emsp;&emsp;&emsp; //name of the variable<br>
1053                                        &emsp;&emsp;<b>int  type;</b> &emsp;&emsp; //type of the variable:(Integer / String)    <br>
1054                                        &emsp;&emsp;<b>int binding;</b>&emsp;&emsp;&emsp;&emsp; //local binding of the variable<br>
1055                                        &emsp;&emsp;<b>struct Lsymbol *next;</b>&emsp;&emsp; //points to the next Local Symbol Table entry<br>
1056                                        <b>};</b>
1057                                    </div>
1058
1059                                    <b>Note:</b>
1059 As noted in the <a href="run-data-structures.html" target="_blank">run time storage allocation</a> documentation, local variables cannot be assigned static memory addresses.  Hence, the binding of a local variable is a relative address within the function's activation record.  We will discuss this matter in detail later.
1060                                </li>
1061                            </ul>
1062                            </p>
1063                        <p>
1064                            What is the <b>stored in flabel</b>?  When the compiler generates code for the function, a label is placed at the start of the function.  A call to the function is translated to a low-level CALL to the corresponding label.   Later, the label has to be replaced by the address  of the instruction during the <a href="label-translation.html" target="_blank">label translation phase</a>.
1065                        </p>
1066                        <p>
1067                            The simple scheme we suggest here is to put the label F0 before the code of the first function declared in the program, F1 before the code of the second and so on.  Hence, in the flabel field of the first function, store 0.  Similarly, store 1 in the flabel field of the second function and so on. A call to the first function must be translated to CALL F0 and so on.
1068                        </p>
1069                        <p>
1070                            With this, the global symbol table for the <a href="run_data_structures/run-time-stack.html#nav-illustration" target="_blank">program</a> would be as below.
1071                        </p>
1072                        <p>
1073                            <img src="img/gsymboltable3.png">
1074                        </p>
1075                        <p>
1076                            Continuing with the above example, we need two local symbol tables – one for the main function and one for the factorial function.  The local symbol table holds the (name, type, binding) triple for each <b>formal parameter</b> as well as <b>local variables</b> of the function.  We will discuss the binding of formal parameters and local variables later.  The local symbol tables of main and factorial would look as the following:
1077                        </p>
1078                        <p>
1079                            <img src="img/localsymboltable2.png">
1080                            <img src="img/localsymboltable1.png">
1081                        </p>
1082                        <p>
1083                            See <a href="data_structures/local-symbol-table.html" target="_blank">LINK</a> for more details. For now, ignore the type table pointer in the structure given in the link.  This will be discussed in the next stage.
1084                        </p>
1085                        <p>
1086
1087                            <div class="syntax">
1088                                <b>Task 1</b>:  Complete the program to build the global symbol table.  Test your program by printing out all global declarations in the program by displaying the contents of the symbol table.  You must not permit two variables/functions (or a function and a variable) to have the same name.
1089                            </div>
1090
1091                            Our next aim is to perform semantic analysis, build the AST and then generate code. The strategy will be the following:
1092                            <ul>
1093                                <li id="otis">1.  First, parse global declarations and create the global symbol table entries for functions andglobal variables (Already completed as Task 1)</li>
1094                                <li id="otis">2.  For each function for which code is not yet generated
1095                                    <ul>
1096                                        <li id="otis">a)  Check for <b>name equivalence</b> of the formal parameters of the function definition with the declaration.  Name equivalence requires that the type and name of each formal parameter of the function in the declaration and the definition must agree.</li>
1097                                        <li id="otis">b)  Create local symbol table containing local variables and parameters.</li>
1098                                        <li id="otis">c)  Build AST for the function. (Do type-checking when the tree is being built, as was done in the previous stages.)</li>
1099                                        <li id="otis">d)  Recursively traverse the tree and generate code for the function in the target file.</li>
1100                                    </ul>
1101                                </li>
1102                            </ul>
1103                            <b>After generating code for a function, the local symbol table and the abstract syntax tree for the function can be deallocated.</b> Proceed to step 2 for the next function.
1104                        </p>
1105                        <p>
1106                            Note that the code and the local variables of a function are not visible outside the function. Hence, the local symbol table and the AST for a function are not required once the code is generated. <b>To generate code for calling one function from another function, only the global symbol table information of the callee is needed. The global symbol table is maintained throughout the compilation process.</b>
1106 Note that the main function is just like any other function except that it has no arguments, its name must be <i>main</i> and return type must be <i>int</i> as per the specification.
1107                        </p>
1108                        <p>
1109                            The only non-trivial part about semantic analysis and AST construction pending discussion is how to build AST for a function call.
1110                        </p>
1111                        <p>
1112                            We start with an example. Suppose we have the following declarations:
1113                            <div class="syntax">
1114                                int Compute(int p, int q);   <br>
1115                                int find(int x);  <br>
1116                            </div>
1117
1118                            A call to the function would occur as in:
1119                            <div class="syntax">
1120                                t = Compute(a+b,find(a-b));
1121                            </div>
1122                            The statement is semantically valid provided a, b, and c  integer type variables.  Note that the call might occur in the code of <i>any function (including the same function – as in the case of a recursive call)</i>.
1123                        </p>
1124                        <p>
1125                            The expression tree for this could look as below:  <br>
1126                            <img src="img/expression tree.png">
1127                        </p>
1128                        <p>
1129                            A tree node for a function call contains a pointer to a list of expressions, one expression for each argument. <b>The compiler must type check each argument and match it with the type of the corresponding formal parameter of the called function.</b>
1130                        </p>
1131                        <p>
1132                            To get an overall picture of what is going on, you may read the documentation on <a href="data-structures.html" target="_blank"> compile time data structures</a> at this juncture. <b>Ignore type table entries for now</b> as we permit only integer/string variables in the present stage.
1133                        </p>
1134                          The expression tree structure given <a href="data_structures/abstract-syntax-tree.html" target="_blank">HERE</a> can be used (again, ignore type table pointer) The details of implementation are left to you.
1135                        </p>
1136                        <p>
1137                            With this information, the task of completing type checking and building expression tree for a function is straightforward.
1138                            <div class="syntax">
1139                                <b>Task 2</b>:  Construct AST for each function after checking type and scope rules (semantic analysis).  Right now, we are concerned just with type and scope analysis and not code generation. Note that a variable appearing in a function must first be searched for in the local symbol table of the function and then in the global symbol table, if not found in the local symbol table. Note that local declaration overrides global declaration. The compiler must report an error if the types, names and number of arguments in each function declaration are not matching with the function definition.
1140                            </div>
1141                        </p>
1142                        <p>
1143                            Now we turn to the code generation step.
1144                        </p>
1145                        <p>
1146                            The dynamics of a function call can be understood easily by dividing the process into the following three stages.
1147                            <ul>
1148                                <li id="otis">
1149                                    Step 1.  <b>Code executed in the calling function (caller)  before the transfer of control</b> to the called function (<b>callee</b>):
1150                                    <ul>
1151                                        <li id="otis">a)  The caller must <b>save the registers</b> in use so that even if the callee changes the values later,  the original values can be recovered after return from the callee.</li>
1152                                        <li id="otis">b)  The caller must <b>evaluate the arguments to the callee and store it</b> somewhere in a way that the <b>callee can access those values</b>.</li>
1153                                        <li id="otis"> c)  The caller must create some <b>space for the callee to place the return value</b> at the end of the call.</li>
1154                                        <li id="otis"> d)  The caller must <b>transfer control to the binding address of the callee</b>.</li>
1155                                    </ul>
1156                                </li>
1157                                <li id="otis">
1158                                    Step 2.  <b>Actions executed by the called function (callee)</b>:
1159                                    <ul>
1160                                        <li id="otis">a)  The callee must <b>allocate space for its local variables</b>.</li>
1161                                        <li id="otis">b)  Execute the callee code.</li>
1162                                        <li id="otis">c)   When encountering a return instruction, the <b>return value must be computed and stored</b> in the appropriate place specified by the caller (step 1.c above).</li>
1163                                        <li id="otis">d) <b> Return </b>control to the caller.</li>
1164                                    </ul>
1165                                </li>
1166                                <li id="otis">
1167                                    Step 3.  <b>Actions executed by the caller</b> after the callee returned control back to the caller.
1168                                     <ul>
1169                                        <li id="otis">a)  <b>Recover the return value</b> stored by the callee.</li>
1170                                        <li id="otis">b)  <b>Deallocate space allocated for arguments</b> for the call in step 1(b).</li>
1171                                        <li id="otis">c)  <b>Recover the machine registers</b> stored before the call in step 1(a).</li>
1172                                    </ul>
1173                                </li>
1174                            </ul>
1175
1176                            The machine code for actions in Step 1 and Step 3 must be generated 
1176when the compiler encounters a function call in the caller's code.   The compiler generates code for Step 2 while generating code for the callee function.
1177                        </p>
1178                        <p>
1179                            To implement the above plan, we need to create storage space whenever a function call is encountered.   We will be focusing on generating code containing labels.  Translation of labels to actual addresses can be easily done at the end as was done in Stage 4 following the <a href="label-translation.html" target="_blank">Label Translation Documentation</a>.
1180                        </p>
1181                        <p>
1182                            <b>Implementation Strategy</b>. <br>
1183                            <br>
1184                            The fundamental strategy for space allocation is to create an <b>activation record</b> for the callee in the <b>stack</b> when a function call is encountered.  <b>The compiler must generate code for creating the activation record at run-time when the call is encountered</b>. Since the storage requirements for arguments, local variables and the return value of a function are known at compile time, the compiler knows exactly how much space must be allocated for each function. We propose following general organization for activation records:  <br>
1185
1186                            <ul>
1187                                <li id="otis">
1188                                    1.  Each <b>activation record must have a base (memory location)</b> which is determined at run time.  The machine register <b>BP (base pointer)</b> is generally used to point to the base of the activation record of the function executing currently.
1189                                </li>
1190                                <li id="otis">
1191                                    2.  <b>Relative to the base, the address of each argument, each local variable, the address where the return value is stored etc are fixed by the compiler statically</b> (at compile time).
1192                                </li>
1193                                <li id="otis">
1194                                    3.  Initially, the activation record for the main function is created in the stack. BP is initialized to the base of this activation record and the main function starts execution.
1195                                </li>
1196                                <li id="otis">
1197                                    4.  <b>If function A calls function B, a new activation record is created in the stack for function B above the activation record of function A</b>. The BP is made to point to the base of activation record of B.  Upon return from B, the activation record of B is popped off the stack and BP is set back to the activation record of A.
1198                                </li>
1199                                <li id="otis">
1200                                    5.  If function A calls function B, the address of the instruction in A to resume execution (<b>return address</b> – value of current-IP +2 in XSM machine- why?) upon return from B must be saved.  Similarly, the <b>base pointer of the caller</b> (BP value) of A <b>must be saved in the stack</b> before BP is changed to point to the base of B.  Both the return address and BP values will be stored in pre-defined locations of the activation record of B.
1201                                </li>
1202                                <li id="otis">
1203                                    6.  In addition to the above, one additional <b>space</b> must be reserved in the activation record of B <b>to store the return value</b>.
1204                                </li>
1205                            </ul>
1206
1207                        </p>
1208                        <p>
1209                            A thorough reading of this <a href="run_data_structures/run-time-stack.html" target="_blank">page</a> is <b>absolutely essential</b> to proceed any further. Suppose  a function has n arguments (arg_1, arg_2,...,arg_n) and m local variables (loc_1, loc_2, ..., loc_m), its activation record in the stack may look as the following.(The stack is assumed to grow downwards.)
1210                        </p>
1211                        <p>
1212                            <img src="img/stack.png">
1213                        </p>
1214                        <p>
1215                            In this scheme, the following code must be generated by the caller when a call to the above function is encountered:
1216                             <ul>
1217                                <li id="otis">1.  Generate code to <b>push registers</b> in use into the stack.  After this, the callee's activation record begins.
1217</li>
1218                                <li id="otis">2.  Evaluate arg_n and push the value to the stack.  Now evaluate and push arg_n-1 and so on till arg_1.  The <b>arguments are pushed in reverse order</b>.  (You can do it in any order as long as the same convention is followed everywhere).</li>
1219                                <li id="otis">3. <b>Push one empty space</b> in the stack for the callee to store the <b>return value</b>.</li>
1220                                <li id="otis">4. Generate <b>Call instruction</b> to the binding (label) of the function. (The call instruction will push IP+2 into the stack and jump to label.)</li>
1221                            </ul>
1222                        </p>
1223                        <p>
1224                            <div class="col-full">
1225                                <div class="col-one-half fleft">
1226                                    Stack before the call instruction :<br>
1227                                    <img src="img/before call.png"><br><br>
1228                                </div>
1229                                <div class="col-one-half fright">
1230                                    Stack after the call instruction :<br>
1231                                    <img src="img/after call.png">
1232                                </div>
1233                            </div>
1234                            <br>
1235                            <br>
1236                            <br>
1237                        </p>
1238                        <p>
1239                            <br>
1240                                Figure: Actions in the stack done by the caller before the call <br><br><br>
1241                            <b>Once the call is made, the next instruction in the caller will be executed only after the callee executes a return statement</b>.  The caller must proceed from here assuming that <b>the callee would have placed the return value</b> in the location in the stack designated for it. The caller must generate code to extract the return value and clean up the stack.
1242                             <ul>
1243                                <li id="otis">5. Allocate a new register and <b>store the returned value</b> into the register.</li>
1244                                <li id="otis">6. <b>Pop out arguments</b> from the stack. (The arguments may be discarded now.)</li>
1245                                <li id="otis">7. <b>Restore registers</b> saved in the stack in step 1.</li>
1246                            </ul>
1247
1248                            The above actions are sufficient to generate code for handling a function invocation.  Note that to generate code for a call, only the callee's declaration information (argument information and call label) needs to be known. All that the caller needs to know is the callee's <b>interface</b>, and the <b>calling convention</b> (convention regarding in what order arguments must be pushed, where should the return value be stored etc.  See also <a href="https://en.wikipedia.org/wiki/Calling_convention" target="_blank">link</a>).
1249                        </p>
1250                        <p>
1251                            Now, we turn to the actions to be done by the callee. The callee must generate the following code before proceeding to the remaining instructions:
1252                            <ul>
1253                                <li id="otis">1.<b>Save the BP of the caller</b> by pushing the BP register into the stack.</li>
1254                                <li id="otis">2.<b>Set BP</b> to the present value of SP register.</li>
1255                                <li id="otis">3. Push enough space in the stack for storing the local variables.</li>
1256                            </ul>
1257
1258                            Relative to the BP value set in step 2 above, [BP-2] is the address to which the return value must be stored. [BP-3] stores arg_1, [BP-4] stores arg_2 and so on.  [BP+1] is for loc_1, [BP+2] for loc_2 and so on. Thus, after seeing the local variable declarations, the compiler can set the binding values for local variables relative to the base of activation record (BP) value as:
1259                        </p>
1260                        <p>
1261                            <img src="img/var-bind table.png">
1262                        </p>
1263                        <p>
1264                            With this convention, the code for each instruction inside a function can be generated following the rule:  <b>local variables/arguments are to be dereferenced a by adding the binding value to the contents of the BP register</b>.  Almost every modern architecture supports function calls by providing an explicit base pointer register.  <br>
1265                            <br>
1266                            Finally, the code for a return statement must:<br>
1267                            <ul>
1268                                <li id="otis">1.  <b>Pop out the local variables</b> from the stack.</li>
1269                                <li id="otis">2.  Calculate the return expression and store the value in [BP-2].</li>
1270                                <li id="otis">3.  <b>set BP to the old value</b> of BP in the stack.</li>
1271                                <li id="otis">4.  <b>Execute the RET instruction</b> to pass control back to the caller.</li>
1272                            </ul>
1273                            <br>
1274                            In the calling convention which we described above, the arguments were pushed in reverse order, space for the return value was allocated by the caller, BP of the caller was saved to the stack by the callee, and so on.   Space created in the stack by either the callee or the caller must be eventually reclaimed by the same party.
1275                        </p>
1276                        <p>
1277                            <b>IMPORTANT NOTE</b>:  In our calling convention, the caller was required to save the registers in use before the call.  What if instead, we design a  calling convention where the callee had to push the registers in use?  The problem here is that the callee does not know (and does not have to know) the caller and hence do not know at each call which were the registers in use.  Hence, the callee will have to save all machine registers, wasting time and space.  Hence, the convention of the caller storing registers in use is superior.  However, there are situations where this is not possible.  For instance, in hardware interrupt routines,  control is transferred to the callee without the caller executing a call.  In such cases, the callee will have to save (all) the machine registers for a successful return.
1278                        </p>
1279                        <p>
1280                            You have enough background now to complete the final task of this stage.<br>
1281
1282                            <div class="syntax">
1283                                <b>Task 3</b>:  Complete code generation for functional calls.  <br>
1284                            </div>
1285
1286                            <b>Exercise 1</b>:  Modify the function semantics to permit pointer type variables of <
1286a href="#stage4_ex2" target="_blank">Stage 4 (Exercise 2)</a> to be passed as arguments to functions.  This will allow a function to pass the address of a local variable to another function as an argument so that the callee can modify the contents.   Modify the syntax and semantics rules appropriately.  This feature must allow you to write functions like:<br>
1287                            <br>
1288                            <i>int</i> swap<i>(int</i> *p, <i>int</i> *q<i>)</i> <br>
1289                            <br>
1290                            Note that functions need to be permitted to return pointer type variables.  (Returning a pointer to local variable from a function is not advisable – Why?).
1291                        </p>
1292                        <p>
1293                            <b>Exercise 2</b> (Hard work, but insightful):  Suppose you want to extend the language with facility of <b>tuples</b>.  By a tuple, we mean an object declared as below:<br>
1294
1295                            <div class="syntax">
1296                                decl<br>
1297                                ..<br>
1298                                ..<br>
1299                                &emsp;tuple tnme(type fname_1, type fname_2, .... ,type fname_n) var_1, var_2 ..  var_k;  <br>
1300                                ..<br>
1301                                ..<br>
1302                                enddecl<br>
1303                            </div>
1304
1305                            Note that tuple is introduced as a new keyword.  For example, we could have:<br>
1306                            <div class="syntax">
1307                                decl<br>
1308                                <br>
1309                                 &emsp;tuple student (str name, int roll_no, str branchname, int year_of_admission) a, b, c, *sptr; <br>
1310                                 &emsp;tuple faculty (str name, int employee_id, str dept) x, y, z, *fptr;  <br>
1311                                 <br>
1312                                enddecl<br>
1313                            </div>
1314
1315                            To access a tuple you must introduce the "." operator.  Here is an example:<br>
1316
1317                            <div class="syntax">
1318                                read(a.name);<br>
1319                                read(x.name); <br>
1320                                if (a.name == x.name) then <br>
1321                                &emsp;write("They have same names"); <br>
1322                                endif; <br>
1323                            </div>
1324
1325                            You must also permit assignment of a tuple type variable to another, provided the variables are of the same tuple type.  <br>
1326                            <br>
1327                            Design the syntax and semantics rules, make necessary modifications to the lexer, parser, symbol table and AST structures to incorporate the addition of tuples and change the code generation module accordingly.    For now, assume that tuples cannot be passed as arguments to functions or be returned by functions.   However, you must permit local tuple declarations.  Note that you have considerable freedom in deciding on the grammar rules and data structures, and even the features permitted. <br>
1328                            <br>
1329                            <b>Exercise 3</b>:  (Hard work, optional, but insightful.  Can be done only after Exercise 1 and Exercise 2 are completed).<br>
1330
1331                            Allow tuples and pointers to tuples to be passed as arguments to functions.  (Allowing the whole tuple to be passed creates more work in parameter passing, though not difficult in principle).   Functions may be permitted to return tuples as return values.   Permit a function that takes an argument/returns a tuple or pointers to tuple type to be declared only after the declaration of the concerned tuples (this is to avoid the <a href="https://en.wikipedia.org/wiki/Forward_declaration" target="_blank">forward reference problem</a>).  Design syntax, semantics and code generation strategies appropriately.
1332                        </p>
1333                      <!--  <p>
1334                          Check your implementation with the following test cases : <br>
1335                          1) <a href="testprograms/test3.html" target="_blank">Test Case 1</a> <br>
1336                         2) <a href="testprograms/test4.html" target="_blank">Test Case 2</a> <br> -->
1337                    <!--      2) <a href="testprograms/test5.html" target="_blank">Test Case 3</a> <br>
1338                          3) <a href="testprograms/test6.html" target="_blank">Test Case 4</a> <br>
1339                          4) <a href="testprograms/test7.html" target="_blank">Test Case 5</a> <br>
1340                        </p> -->
1341
1342                        <h4> <b>Test Programs </b></h4>
1343                        <p>
1344                          Check your implementation with the following test cases : <br>
1345                          <a href="testprograms.html#test3" target="_blank">Test Program 1 : Bubblesort (recursive)</a> <br>
1346                          <a href="testprograms.html#test5" target="_blank">Test Program 2 : Factorial (recursive)
1347</a> <br>
1348                          <a href="testprograms.html#test6" target="_blank">Test Program 3 : Quicksort (recursive)</a> <br>
1349                          <a href="testprograms.html#test7" target="_blank">Test Program 4 : Constant Program (recursive)</a> <br>
1350                          <a href="testprograms.html#test10" target="_blank">Test Program 5 : Fibonacci (recursive)</a> <br>
1351                          <a href="testprograms.html#test2" target="_blank">Test Program 6 : Extended Euclid(with a Function)</a> <br>
1352                          <a href="testprograms.html#test1" target="_blank">Test Program 7 : BubbleSort (iterative)</a> <br>
1353                          <a href="testprograms.html#test12" target="_blank">Test Program 8 : Extended Euclid(iterative)</a> <br>
1354                        </p>
1355
1356                            <div class="up column3 mright">
1357                                <a href="#navtop">  &#x2191; </a>
1358                            </div>
1359                    </article>
1360                    <article class="grid col-full" id="nav-stage6">
1361                        <h2>Stage 6: User defined types and Dynamic Memory Allocation</h2>
1362                           <b>Time Estimate :</b> 2 weeks, 5-10 hours/week
1363                        <p>
1364                            <b>Prerequisite Reading</b>:
1365                            <ul>
1366                                <li id="otis">1.  Read the <a href="expl.html" target="_blank">ExpL specification</a>.</li>
1367                                <li id="otis">2.  Read about <a href="run_data_structures/heap.html" target="_blank">Dynamic memory allocation</a>.</li>
1368                            </ul>
1369                        </p>
1370
1371                            <!--done -->
1372                        <p>
1373                            <b>Learning Objectives</b>:
1374                            <ul>
1375                                 <li id="otis">You will extend the language of Stage 5 by adding support for <b>user-defined types</b> and <b>dynamic memory allocation</b>.  Issues of <b>Heap management</b> will be encountered en route.</li>
1376                            </ul>
1377                            <hr>
1378                        </p>
1379
1380                        <!--done-->
1381
1382                        <p>
1383                            This is the second major stage of the ExpL compiler project and will be implemented in two parts.  In the first part, we will see how user defined types can be added to the language syntax and how semantic analysis can be performed.  The ExpL specification demands storage for user-defined types dynamically.   We will discuss how dynamic memory allocation can be achieved in the second part.
1384                        </p>
1385
1386                        <!--done-->
1387                        <p>
1388                            See the <a href="expl.html" target="_blank">ExpL language specification</a> for an informal description of the language.   It is suggested that you design your own grammar using the outline provided <a href="grammar-outline.html" target="_blank">here</a> as a reference. The following <a href="testprograms.html#test8" target="_blank">link</a> provide examples of ExpL programs containing user defined types.
1389                        </p>
1390                        <p>
1391                            We will now take up the front end - semantic analysis and AST representation - before proceeding to code generation and dynamic memory allocation.    <br>
1392                             <br>
1393                            <b>Part I</b>:  <b>Front End</b> <br>
1394                            <br>
1395                            Every user defined type requires a <b>type definition</b>.  Type definitions are placed at the beginning of a program, ahead of global declarations.  A user-defined type in ExpL essentially defines an <b>aggregate type</b>.    The <b>member fields</b> of a user defined type may have arbitrary types (subject to certain constraints – to be discussed soon). <br>
1396                            <br>
1397
1398                            Consider the type definition:  <br>
1399                            <div class="syntax">
1400                                type<br>
1401                                &emsp;bst{<br>
1402                                &emsp;&emsp;int a;<br>
1403                                &emsp;&emsp;bst left;<br>
1404                                &emsp;&emsp;bst right;<br>
1405                                }<br>
1406                                endtype<br>
1407                                decl<br>
1408                                &emsp;int in,opt;<br>
1409                                &emsp;bst insert(bst h, int key);<br>
1410                                &emsp;int inOrder(bst h); <br>
1411                                &emsp;int preOrder(bst h);<br>
1412                                &emsp;int postOrder(bst h); <br>
1413                                enddecl<br>
1414                            </div>
1415                            This type definition specifies the node structure for a binary search tree.  The member field a has type integer, whereas <i>left</i> and <i>right</i> have type bst.   Note the <b>recursive</b> nature of the type definition.   The declaration section shows functions which take as input a <i>bst</i> or returns a <i>bst</i>.    Here is another type definition: <br>
1416                            <div class="syntax" id="nav-marklist">
1417                                type<br>
1418                                &emsp;linkedList {<br>
1419                                &emsp;&emsp;int data; <br>
1420                                &emsp;&emsp;linkedList next;  <br>
1421                                  }<br>
1422                                  <br>
1423                                &emsp;markList{<br>
1424                                &emsp;&emsp;str name;  <br>
1425                                &emsp;&emsp;linkedList marks; <br>
1426                                  }<br>
1427                                endtype<br>
1428                                decl<br>
1429                                &emsp; markList mList,temp; <br>
1430                                enddecl<br>
1431                            </div>
1432
1433                            Note here that in the type <i>markList</i>, the member field <i>marks</i> is of the type <i>linkedList</i>.  ExpL stipulates that the member fields of a user defined type, if not of type integer or string, can only be of the <b>
1433same</b> type or one of a <b>previously defined</b> type.
1434                        </p>
1435                        <p>
1436                            The compiler must keep track of the type definitions in some data structure.  For this purpose, we will maintain a <b>type table</b> storing the type definition information.  <b>Each user defined type will have a type table entry</b>.  In addition to user-defined types, the type table will also store "default" entries for <i>int</i>, <i>str</i>, <i>bool</i> and <i>void</i> type.   (Since logical expressions evaluate to a boolean value, they may be assigned boolean type.  The ExpL constant NULL can be assigned to a variable of any user-defined type.  Hence, having a NULL type is useful from a purely implementation perspective.  Note here that boolean is an <b>implicit type</b> in the language.  The language does not allow the programmer to declare a variable of type boolean).  <br>
1437                            <br>
1438                            <b>The type table entry for a user-defined type must provide information about the names and types of its member fields</b>.  For each member field, a pointer to its type table entry must be maintained.  This <a href="data_structures/type-table.html" target="_blank">link</a> gives you a simple type table implementation scheme.  (You have to fill in missing details).  <br>
1439                            <br>
1440                            Symbol table must also be modified to handle user-defined-types information.   The <b>type field of the symbol table entry of a variable/function</b> shall <b>refer to the type table entry of the corresponding type</b> (Recall that in the case of a function, the type of a function is its return type).  The following <a href="data_structures/global-symbol-table.html" target="_blank">link</a> illustrates the organization of the global symbol table.  The type entry of each formal parameter of a function must also refer to the corresponding type table entry.   <a href="data_structures/local-symbol-table.html" target="_blank">Local symbol tables</a> of functions will require similar modification.  <br>
1441                            <br>
1442                            The next question is how to assign memory for user defined type variables.  We will defer this issue temporarily and hence, for now, will not discuss how to assign bindings to variables of user-defined types right now.   This will be discussed in Part II.<br>
1443                            <br>
1444                            We must now discuss how to use the symbol table and type table for completing semantic analysis of the input program.   Let us look at an example.  <br>
1445                            <br>
1446                            Consider the declaration of the type <i>markList</i> in the example <a href="#nav-marklist">above</a>.  The language now permits statements like:<br>
1447
1448                            <div class="syntax">
1449                            temp = mList.next; <br>
1450                            if (mList.marks.data > mList.next.marks.data) then <br>
1451                            &emsp;write("first student performed better in the first subject"); <br>
1452                            endif;<br>
1453                            </div>
1454
1455                            <b>Note that the operands in expressions can now be member fields of user-defined-type variables</b>.  Similarly, the left side of an assignment statement or the variable for a read statement can now be a member field.  The grammar rules for various statements in the language are outlined <a href="grammar-outline.html" target="_blank">here</a>.   You must try to design your own grammar, keeping the grammar above as a guideline.  Many details are (deliberately) left out in the outline given to you.<br>
1456                            <br>
1457                            In the following, we use the term <b>field</b> generically to refer to <i>any</i> member field of <i>any</i> variable (of any user-defined type).  <br>
1458                            <br>
1459                            What must be the type of a field?  The type of <i>mList.next</i> in the above example must be the type of the member field <i>next</i> of the user defined type <i>markList</i>.  Once this information is extracted from the symbol table, the type of any statement, expression or variable c
1459an be determined correctly.   Thus, <b>an assignment statement is valid provided the types of the right side expression matches with that of the left side variable</b>.  <i>The only exception to this rule is that the constant NULL can be assigned to any variable of any user-defined type.</i> <br>
1460                            <br>
1461                            Stated formally,
1462                            <div class="syntax">
1463                            Field :: = Field '.' ID  {  $$.type = $3. type; }   <br>
1464                            &emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;             | ID  '.' ID { $$.type = $3.type; } <br>
1465                            </div>
1466
1467                            While constructing the AST,  the type entry for any field may be recursively computed using the formal rule noted above.   This information can be used for effective semantic analysis.  Arguments to functions must also be type checked against formal parameters of their declaration.
1468                        </p>
1469                        <p>
1470                            A plausible tree node structure and associated functions for AST construction are described <a href="data_structures/abstract-syntax-tree.html" target="_blank"> here</a>.
1471                        </p>
1472                        <p>
1473                            <b>Note</b>:  ExpL specification demands a rigid type analysis by <a href="https://en.wikipedia.org/wiki/Nominal_type_system" target="_blank">name equivalence</a>. This differs from the more liberal <a href="https://en.wikipedia.org/wiki/Structural_type_system" target="_blank">structural equivalance</a> in the C programming language.
1474                        </p>
1475                        <p>
1476                            With this background, the front end of the ExpL compiler can be completed.<br>
1477                            <br>
1478                                <b>Task 1</b>:  Complete the syntax and semantic analysis and construct AST for ExpL language. (<a href="expl.html" target="_blank">Specification</a>, <a href="grammar-outline.html" target="_blank">Grammar Outline</a>)
1479                            <br>
1480                            <br>
1481                        </p>
1482                        <p>
1483                            <b>Part II</b>:  <b>Back End</b>
1484                        </p>
1485                        <p>
1486                            <br>
1487
1488                            We will first discuss the underlying concepts before getting into the back-end implementation details.<br>
1489                            <br>
1490                            The ExpL specification stipulates that the storage for a variable of a user-defined-type is allocated through the <a href="expl.html#nav-user-defined-types" target="_blank"><i>Alloc()</i></a> function. Each user-defined-type variable in ExpL must store the <b>reference</b> to its actual memory store.  <b>The actual memory may be allocated</b> by <i>Alloc()</i> when a call to the function is encountered <b>at run time</b>.
1491                        </p>
1492                        <p>
1493                            From an implementation point of view, <b>a variable of a user-defined-type must be designed to hold the address of its actual memory store</b>. Whenever the <i>Alloc()</i> function is invoked for the variable,  a memory region sufficient for holding all the member fields of the variable must be allocated "somewhere" in memory and Alloc() must return the starting address of that memory region.  <b>The compiler must generate code to invoke <i>Alloc()</i> and store the return value into the variable</b>.    Thus, <b>the variable will essentially store a pointer</b> to the memory region allocated by <i>Alloc()</i>.  This is easy to do, provided we have the <i>Alloc()</i> function at our disposal.
1494                        </p>
1495                        <p>
1496                            <b>A variable of a user-defined-type must be allocated at compile time one memory word to store an address (basically an integer) returned by <i>Alloc()</i> at run time</b>.  The allocation could be static or run-time.    ExpL specification does not permit arrays of user-defined type.
1497                        </p>
1498                        <p>
1499                            Once the memory is allocated for a user-defined type variable, member field references can be translated easily.  The details are left to you.
1500                        </p>
1501                        <p>
1502                            The next problem is to design and implement the <i>Alloc()</i> function.   We will also take up the issue of designing the <i>Free()</i> function (to de-allocate some previously allocated memory).  This problem is known as the <b>dynamic memory allocation problem</b>.  (The <i>malloc()</i> and <i>free()</i> functions of the C library are <a href="https://en.wikipedia.org/wiki/C_dynamic_memory_allocation" target="_blank">dynamic memory allocation</a> routines of the C programming language.)
1503                        </p>
1504                        <p>
1505                            The strategy of Alloc() is to maintain a <b>memory pool</b> called <b>heap memory</b>.
1506                            Alloc() will need to manage a large run-time memory pool.  To make matters simple, we will assume that Alloc() divides the whole memory into fixed size blocks, each of size eight words.  In this case, the strategy is very simple:<br>
1507
1508                            <div class="syntax">
1509                            1. Before the start of the program, reserve a large area of the address space for heap. The ExpOS <a href="abi.html#nav-virtual-address-space-model" target="_blank">memory model</a>
1509 suggests that the address region 1024-2047 may be used for this purpose.<br>
1510                            2. Organize the heap into a linear linked list of blocks of size 8. We will design a heap initializer function <i>Initialize()</i> specifically for this.<br>
1511                            3. When an <i>Alloc()</i> request comes, return the start address of the first free block in the list (and remove the block from the free list).<br>
1512                            4. When a <i>Free(address)</i> request comes (assuming <i>address</i> refers to the start address of a block already allocated), return the block pointed to by <i>address</i> back to the memory pool.<br>
1513                            </div>
1514
1515                            The <i>pragmatic</i> restriction imposed by such a simple implementation is that a user-defined type cannot have more than eight-member fields.  Of course, we could have increased the block size to – say sixteen – in which case the number of member fields can be upto 16.  For now, we will be content with the simple fixed block size scheme.
1516                        </p>
1517                        <p>
1518                            With this, we can design our compiler to generate code for <i>Alloc()</i>, <i>Free()</i> and <i>Initialize()</i> functions along with the target code.   Techniques of Stage 5 suffices to build an executable file.
1519                        </p>
1520                        <p>
1521                            However, there is a better way of doing things when OS support for shared library is available.
1522                            Note that we have been using the shared library for console input, output etc.
1523                            <b>Since the routines <i>Alloc()</i>, <i>Free()</i> and <i>Initialize()</i> will be used by <b>every</b> ExpL program
1524                            (that uses user-defined types), it would be profitable to write these routines once
1525                            and add them as part of the library.</b>  Since the OS loader loads the
1526                            shared library to the memory region 0-1023 of the address space of each program,
1527                            the code for <i>Alloc()</i>, <i>Free()</i> and <i>Initialize()</i> too will be available to the program.
1528                            The library interface must be defined so that the calling conventions for invoking each of the above
1529                            functions are clearly specified.
1530                          </p>
1531                          <p>
1532                            With this strategy, when an ExpL program
1533                            is compiled, the compiler will not generate code to implement <i>Alloc()</i>, <i>Free()</i> or <i>Initialize()</i>.
1534                            <b>Instead, the compiler will generate a CALL to the library (using the
1535                            library interface) with appropriate arguments so that the corresponding library routine
1536                            is invoked.  You need to modify the library code so that the assembly code for <i>Alloc()</i>, <i>Free()</i> and <i>Initialize()</i> are added to the library.</b>
1537                            The advantage of this method is that
1538                               the code implementing <i>Alloc()</i>, <i>Free()</i> and <i>Initialize()</i> need not be part of the the code of every
1539                               executable program, saving both load-time and system memory.  The technical jargon calls
1540                               such a library a run time loading library.
1541                        </p>
1542
1543
1544
1545
1546
1547                        <p>
1548                            The <a href="abi.html" target="_blank">ABI</a> stipulates that calls to the dynamic memory functions shall be directed
1549                             through the Library.   Thus, you must add Alloc(), Free() and Initialize() as library functions.
1550                              As noted previously, the region of memory between address 1024 and 2047 must be used for heap memory allocation.
1551                        </p>
1552                        <p>
1553                            It is <b>absolutely necessary</b> to read and understand <a href="run_data_structures/heap.html" target="_blank">Dynamic memory allocation</a> (<b>except</b> Buddy System Allocation) to proceed further.  An overall picture of the ExpOS library design is outlined in the <a href="library-implementation.html" target="_blank">library implementation</a> documentation. We are now ready to complete the back end.
1554                        </p>
1555                        <p>
1556                            <b>Task 2</b>:  Complete the back-end adding <i>Alloc()</i>, <i>Free()</i> and <i>Initialize()</i> functions to the ExpOS library and complete the implementation of adding user defined types to ExpL.   Assume fixed block size of 8 words for memory allocation.  The compiler must flag an error "too many member fields" if a user-defined type definition has more than 8 member fields.  Note that the fixed block allocator is pretty simple to be written directly in assembly language. Read the note below before proceeding with the implementation.
1557                        </p>
1558                        <p>
1559                            <b>Important Note</b> : Your library functions will need to modify registers and hence before a library call,   ensure that registers in current use are saved in the stack (as was done with function calls in the previous stage).
1560                        </p>
1561                        <p>
1562                            <b>Exercise 1</b>:  Extend ExpL to permit arrays of user-defined type.
1563                        </p>
1564                        <p>
1565                            If you want to do <b>variable sized block allocation</b>, more complex allocation schemes like the <a href="run_data_structures/heap.html#nav-buddy-allocation" target="_blank"><b>Buddy System Algorithm</b></a> will be required.  One would also need to understand the issue of <a href="https://en.wikipedia.org/wiki/Fragmentation_(computing)" target="_blank"><b>memory fragmentation</b></a> that can arise when variable sized allocation is done.
1566                        </p>
1567                        <p>
1568                            <b>Exercise 2</b>:   (Optional)  Modify <i>Alloc()</i> and <i>Free()</i> library functions to implement the </b>Buddy memory allocator described <a href="run_data_structures/heap.html#nav-buddy-allocation" target="_blank">here</a>.  You will have to modify <i>Initialize()</i> appropriately.   The buddy system allocator is too complex to write in assembly language.  Hence write them in ExpL itself and modify your label translation scheme to generate target addresses correctly.<br>
1569                        </p>
1570                      <!--  <p>
1571                          Check your implementation with the following test cases : <br>
1572                          1) <a href="testprograms/test8.html" target="_blank">Test Case 1</a> <br>
1573                          2) <a href="testprograms/test9.html" target="_blank">Test Case 2</a> <br>
1574                          3) <a href="testprograms/test10.html" target="_blank">Test Case 3</a> <br>
1575                          4) <a href="testprograms/test11.html" target="_blank">Test Case 4</a> <br>
1576                        </p> -->
1577
1578                        <h4> <b>Test Programs </b></h4>
1579                        <p>
1580                          Check your implementation with the following test cases : <br>
1581                          <a href="testprograms.html#test8" target="_blank">Test Program 1: Linked List</a> <br>
1582                          <a href="testprograms.html#test9" target="_blank">Test Program 2: Binary Search Tree</a> <br>
1583                          <a href="testprograms.html#test11" target="_blank">Test Program 3: Extended Euclid Algorithm using linkedlist</a> <br>
1584                          <a href="testprograms.html#test4" target="_blank">Test Program 4: Extended Euclid Algorithm using Userdefined types</a> <br>
1585                        </p>
1586                        <div class="up column3">
1587                            <a href="#navtop">&#x2191; </a>
1588                        </div>
1589                    </article>
1590
1591                    <!--
1592
1593                    <article class="grid col-full" id="nav-stage7">
1594                      <h2>Stage 7: Register Allocation</h2>
1595                      <p>
1596                          <b>Learning Objectives</b>:
1597                          <ul>
1598                               <li id="otis">You will add a very primitive <a href="https://en.wikipedia.org/wiki/Register_allocation" target="_blank">
1599                               register allocation</a> scheme to compiler to make the target code generated by Stage 6 more efficient.</li>
1600                          </ul>
1601                          <hr>
1602                      </p>
1603                      <p>
1604                        Instructions whose operands are registers run much faster than instructions involving operand fetch from memory (why?). Hence, in order to make the target code run faster, variables could be stored in registers, whenever free registers are available.
1605                    </p>
1606                    <p>
1607                      If you observe the target code generated in Stage 4, you will see that only 3-4 registers are used for storage of intermediate results of expression evaluations, almost all the time. This leaves many registers unused, which could be utilized for storing variables.</p>
1608
1609                    <p>
1610                      We will use the following strategy.  When a variable is to be read/assigned by a statement inside a function, the variable will be bound to a temporary register.  This binding will be <b>retained even after the use</b>. This allows later program statements that read/write the same variable to access/update the value in the register, avoiding a memory access.
1611                    </p>
1612
1613                    <p>
1614                      Since temporary registers are few in number, we need to implement a register replacement policy that “caches out” some variables back to memory and re-binds registers to other variables when one runs out of registers.  The details are outlined below.
1615                    </p>
1616
1617                    <p>
1618                      Add the following logic to the compiler of the previous stage.
1619                        <ol>
1620                             <li>
1621                             For normal computations done in the previous stages involving <i>getReg()</i> and <i>freeReg()</i> functions,<b> reduce the free register pool to R0-R5
1622                             </b>.(Consequently, if an expression is too long requiring more than 6 registers for storing intermediate values, the compiler must flag an error indicating that it encountered an expression that was too long to handle).
1623                             </li>
1624                             <li>
1625                             <i>Temporary pool</i>:  Reserve registers  <b>R6-R19 as a separate register pool for temporary storage</b> of variables(We will refer to these registers as “temporaries”).  We will use this register pool as a “cache” where values of program variables (except for array type variables) will be stored for fast access.  We will design new functions <i>getTemp()</i> and
1626                              <i>freeTemp()</i> to allocate and de-allocate temporaries from this pool.  We will call this register pool the <b>temporary pool</b>.
1627                            </li>
1628                             <li>
1629                             <i>Modifications to Symbol Table structures:</i>  When the compiler encounters the declaration of a global/local variable, store is allocated in the normal way.   Temporaries are allocated only when a variable is accessed and not when the variable is declared.   Additionally, <b>in the global symbol table as well as local symbol tables of each function, the compiler has to maintain two fields</b> <i>temp</i> <b>and</b> <i>reference_count</i> <b>corresponding to each variable</b> [LINK].
1630                               <p>
1631
1632                               a) The field <i>temp</i> will store the index of the temporary register allocated for the variable by the compiler.   If no temporary is assigned to the variable, the temp field shall be set to 0.
1633                               <br>
1634                               b) The field <i>reference_count</i> of a variable will indicate the number of future (static) references to that variable within a function.  This is a heuristic used to identify variables whose allotted temporary register is to be deallocated, in the event of a conflict for temporary space.  The use of this field will be explained later.
1635                               </p>
1636                             </li>
1637                             <li>
1638                               <i>Temporary Allocation and Release</i>:   Register allocation is performed by two functions – <i>freeTemp()</i> and <i>getTemp</i>().
1639                               <p>
1640                                a) The function <i>freeTemp(argument:  variable_name)</i> releases the temporary register associated with the variable varname  (if any) and adds the temporary register to the free pool. <b> The function must generate code to store the contents of the temporary to the memory address of the variable</b>.    The function must also record the release of the temporary by setting the <i>temp</i> field to 0 in the symbol table entry of the variable.    <b>The function returns the index of the temporary register that was released</b>.
1641                                <br>
1642                                b) The <i>getTemp(varname)</i> function checks whether a temporary has been already allocated for the variable passed as argument (inspecting the <i>temp</i> field in the symbol table entry for the variable).   If so, the function simply returns the index of the register.  Otherwise, the following steps must be done to allocate a temporary:
1643                                <br>
1644                                Check whether an un-allocated temporary is available in the temporary pool.<br>
1645                                 If available,
1646                                 <br>
1647                                 {
1648                                  <br>
1649                                   &nbsp;&nbsp;&nbsp;&nbsp; Allocate an un-allocated temporary to the variable by setting the temp field in the   symbol table. Generate code to transfer the contents of &nbsp;&nbsp;&nbsp;&nbsp;the memory location storing the variable to the temporary and return the index of the temporary register.
1650                                   <br>
1651                                 }
1652                                 <br>
1653                                 else
1654                                 <br>
1655                                 {
1656                                  <br>
1657                                  &nbsp;&nbsp;&nbsp;&nbsp;1)Select a variable to be “<i>cached out</i>.”  A simple replacement policy is to <b>replace any variable with the lowest value of</b> <i>reference_count</i> and &nbsp;&nbsp;&nbsp;&nbsp;release its temporary by invoking the <i>freeTemp()</i> function (We will soon discuss how to assign reference count to variables).<br>
1658
1659                                  &nbsp;&nbsp;&nbsp;&nbsp;2)Allocate the released temporary register to the variable by setting the temp field in the symbol table.  <b> Generate code to load the contents &nbsp;&nbsp;&nbsp;&nbsp;of the variable from memory to the temporary register</b> (See also Exercise 1 below) and return the register index.
1660                                  <br>
1661                                 }
1662
1663                                 </p>
1664                             </li>
1665                             <li>
1666                              <i>  Changes to the code generation Phase</i>:  Since <i>getTemp()</i> returns a register holding the variable, it is not longer required to transfer contents of the register to another register for accessing values.  Similar changes are required when a variable is assigned a value.
1667                             </li>
1668                             <li>
1669                              <i>Simplifying Assumptions</i>:   To simplify the implementation, we assume the following:
1670                              <br>
1671                                 a)<b>Temporary allocation will be made afresh inside each function</b>. <i>Before a function call is made, all temporaries allocated by the caller must be pushed to the stack and popped back upon return</i>. Before a function returns, all temporary allocations made by the function are released.  (If a global variable is assigned a temporary register by the function, then code must be generated to store back the temporary to the memory location of the corresponding variable before return).
1672                                <br>
1673
1674                                 b)<b>Temporary allocation will not be done for arrays</b>.
1675                                <br>
1676                             </li>
1677                             <li>
1678                               <i>Assigning reference_count</i>:  Reference count for each variable will be computed incrementally during abstract synatax tree construction phase for the function and these values will be decremented during each access to the variable during the code generation phase.  The steps are detailed below.
1679                               <p>
1680                               a) While processing declarations in a function, reference_count for all variables visible to the function (global and local) is initalized to zero.
1681                                </p>
1682                               <p>
1683                                b)  For each function in the program, during the Abstract Syntax Tree construction phase for a function, each time when a reference to a variable is encountered in the function (that is, for each symbol table search to the variable), the reference count for the variable is incremented.    He
1683nce, at the end of the AST construction phase, the reference count will indicate the total number of times the variable was accessed in the program.
1684                                 </p>
1685                               <p>
1686                                c) During code generation, each time a variable is accessed, <i>reference_count</i> is decremented.  Hence, <i>reference_count</i> will indicate the number of times the variable will be accessed subsequently during the function's compilation.   Hence, if <i>reference_count</i> reaches zero, there are no static (compile time) references for the variable to be encountered further in the function.
1687                                 </p>
1688                             </li>
1689
1690                        </ol>
1691                        <hr>
1692                    </p>
1693
1694                    <p>
1695                        <b>Task 1</b>:  Implement the register allocation scheme as outline above.
1696                    </p>
1697                    <p>
1698                        <b> Important Note: </b> The fact that the reference to a variable at a program point is the last encounted during compilation of a function <b>by no means ensure</b> that the variable will not be accessed during run time after execution of the particular statement within the function (figure out why?)  Hence, <i>reference_count</i> is only a very naive heuristic for predicting  the future use of a variable (see exercises below).   You are advised to read standard text books on compiler design to gain further insight into various register allocation techniques in the literature.  Going further into these details is beyond the scope of this project.  However, we just note that the problem of allocating registers optimally is computationally hard [REF] and hence any solution to the problem will necessarily rely on heuristics.
1699                    </p>
1700
1701                    <p>
1702                        <i>Exercise 1</i>:  The present <i>getTemp()</i> function is inefficient during assignment of a new value to a variable because, it is wasteful to transfer its existing value from the memory to it's temporary register.  Modify the temporary allocator interface as:  <i> getTemp(variable_name, load_flag)</i>, where <i>load_flag=1</i> only if the variable's existing value must be loaded to the temporary, and  <i>load_flag=0</i> otherwise.  Modify the code generation phase to eliminate the inefficiency mentioned above.
1703                     </p>
1704
1705                </article>
1706
1707              -->
1708
1709                <article class="grid col-full" id="nav-stage7">
1710                         <h2>Stage 7: Adding Objects – Data encapsulation</h2>
1711                            <b>Time Estimate :</b> 2 weeks, 5-10 hours/week
1712                        <p>
1713                            <b>Prerequisite Reading</b>:
1714                            <ul>
1715                                <li id="otis">1.Read the <a href="oexpl-specification.html" target="_blank"> OExpL specification</a> (except for the section on inheritance, which may be read before the next stage).</li>
1716
1717                            </ul>
1718                        </p>
1719
1720                        <p>
1721                            <b>Learning Objectives</b>:
1722                            <ul>
1723                                 <li id="otis">You will extend the language of Stage 6
1724                                   by adding support to classes (except for inheritance) to make
1725                                   ExpL an <a href= "https://en.wikipedia.org/wiki/Object-based_language" target="_blank">  <i>object based language</i></a>.
1726                                   <!--You will also extend ExpL with support for splitting a source program into multiple class files and one main program.--></li>
1727                            </ul>
1728                            <hr>
1729                        </p>
1730
1731                         <p>
1732                            In this stage, we will extend ExpL to provide support for <a href="https://en.wikipedia.org/wiki/Data_encapsulation" target="_blank">data encapsulation</a> by supporting classes. <a href="https://en.wikipedia.org/wiki/Inheritance_(object-oriented_programming)" target="_blank">Inheritance</a> will be added in the next stage.
1733                        </p>
1734
1735                         <p>
1736                            From an implementation view-point, a class is similar to a user defined type that, apart from <i>member fields</i>, also contain <i>member functions</i> or <b>methods</b>. The access rules of class members and methods are more stringent. Read the (<a href="oexpl-specification.html" target="_blank">OExpL specification </a> carefully for access semantics.) Here, we will focus on how support for classes can be added to the compiler.
1737                        </p>
1738
1739                             <br>
1740                             <b>Part I</b>:  <b>Syntax and Semantic Analysis</b> <br>
1741                             <br>
1742
1743                        <p>
1744                          <!--  The structure of class definitions for this stage is outlined below:-->
1745
1746                            The grammar outline for class definitions is given <a href="oexpl-grammar-outline.html" target="_blank">here</a>.
1747                            The following grammar rule allowing class extension (in Class Definitions)
1748                            will not be supported in this stage.
1749
1750                            <div class="syntax">
1751                              <!--  ClassDefs ::= CLASS classDefList ENDCLASS <a href="oexpl-grammar-outline.html" target="_blank">LINK</a><br>
1752                                <br>
1753                                classDefList ::= oneClass | classDefList oneClass<br>
1754                                <br>
1755                                oneClass ::= .... /* to be added */-->
1756
1757                                Cname         : ID Extends ID	{Cptr = Cinstall($1->Name,$3->Name);}
1758
1759
1760
1761                                <br>
1762
1763                            </div>
1764
1765                            Support for class extension will be introduced in the next stage.
1766                        </p>
1767
1768                        <p>
1769                            The compiler must maintain a <b>class table</b> to store the information pertaining to each class
1770                            defined in an OExpL program. Class definitions appear after type definitions.
1771                            Each class definition specifies the member fields and methods of the class.
1772                            <i>Member field declarations must precede method declarations</i>.
1773                        </p>
1774
1775                        <p>
1776                            For simplifying the implementation,<b> we will assume here that a class may contain at
1777                            most 8 member fields and at most 8 methods</b>. Hence, fixed size allocation of dynamic memory will be sufficient,
1778                            as in the 6th stage.
1779                        </p>
1780                        <p>
1781                            Each <b>class table entry stores information pertaining to a class</b>. The names and types of each member
1782                            field along with its <i>position index </i> must be stored in the class table
1783                            (In any class, the method defined first will be assigned position index as <b>0</b>, the method defined next will
1784                            be assigned position index as <b>1</b> and so on).
1785                             For each method, the <i>signature</i> of the method (method name, return type,
1786                            types and names or arguments) along with the binding (<i>label</i> of the method – a call to the method must be translated to a
1787                            call to this label) needs to be stored. The type field for a variable/method must contain a pointer to the corresponding type table entry.
1788                            <i>An exceptional case is when a member field is of a previously defined class.
1789                            In this case, a pointer to the class table entry of the member field must be maintained</i>.
1790                          </p>
1791                          <p>
1792                               <b>A thorough reading of the details of <a href="oexpl-data-structures.html" target="_blank">class table implementation</a> is necessary to
1793                               proceed further</b>.
1794                               In this stage, we will not support class extension. Hence, the parent class pointer entry for each class must be set to NULL.
1795                        </p>
1796                        <p>
1797                          <!--  The program structure makes it possible to compile each class separately into a separate object file.-->
1798                           For
1799                            now, we will focus on syntax and semantics. Code generation will be taken up subsequently.
1800                        </p>
1801
1802                      <!--  <p>
1803                            Global variable declarations may contain declarations for class variables along with other variable declarations.
1804                            Hence, the <a href="data_structures/global-symbol-table.html" target="_blank">global symbol table</a> must be able to maintain
1805                            information about class variables.  <b>For class variables, a pointer to the class table entry of the variable's class
1806                            must be set in the the field <i>Ctype</i> of the <a href="data_structures/global-symbol-table.html" target="_blank">global symbol table entry</a></b>.
1807
1808                            </p>
1809-->
1810
1811                            <p>
1812                                When <b>a variable of a class</b> is declared (in the global declaration section),
1813                                <b>a pointer to the class table entry must be mainted in the <a href="data_structures/global-symbol-table.html" target="_blank">global symbol table entry</a></b> of the variable.
1814                                Hence, a new <i>class table pointer</i> field may be added to the global symbol table structure.
1815                                Note that the <a href="data_structures/global-symbol-table.html" target="_blank">global symbol table entry</a> for a global variable will have either a class table pointer entry or a type table pointer entry,
1816                                but not both.
1817                            </p>
1818                            The following scope rules must be carefully checked to ensure correct semantic analysis:
1819
1820
1821
1822                         <ul>
1823
1824                                <li id="otis">
1825                                1. Methods of a class variable are accessed as <i>self.method_name(..args..)</i>.
1826                                (If a member is of a previously class, <i>self.field_name.method_name(..args..)</i>).
1827                                </li>
1828                                <li id="otis">
1829                                2. <b>A member field in a class shall be accessed only within a method of the same class.</b>
1830                                The access syntax will be <i>self.field_name</i>. (<b>Note:</b> if <i>field_name</i> is variable of another
1831                                class (or the same class), accessing member fields of the member using syntax <i>self.field_name.sub_field.name</i> <b>is
1832                                not be permitted – why?</b>)
1833                                </li>
1834                                <li id="otis">
1835                                3. A method of one class is generally not permitted to access methods of other classes.
1836                                However, if a class contains a member field of another class, then the methods accessible
1837                                through the member field can be invoked as noted in point 1 above.
1838
1839                                                              </li>
1840                                <li id="otis">
1841                                4. There is <b>exactly one method carrying a name in a class</b>. Thus, <a href="https://en.wikipedia.org/wiki/Function_overloading" target="_blank">function overloading</a> is not permitted.
1842                                </li>
1843
1844
1845                        </ul>
1846
1847                        <!--This field is required only for the OEexpL.-->
1848
1849                        <p>
1850                            These rules are not difficult to check once the class table is properly constructed from the class definitions.
1851                            <b> All variable and function declarations visible to a method are contained in the class table entry of the relevant class</b>.
1852                        </p>
1853
1854
1855                        <p>
1856                            <b>Task 1:</b> Complete the front end - lexical, syntax and semantic analysis for the extended language with classes.
1857                        </p>
1858
1859                        <p>
1860                            <b>Part II: Code Generation </b>
1861                        </p>
1862                        <p>
1863                            Code generation is not hard, once the access semantics of <i>self</i> is understood.
1864                            <b>The basic observation is that the code for any method can be generated immediately as the definition of the method is processed</b>.
1865                             This is true because a method's access is limited to its member fields and previously declared methods of the class.
1866                             This information would be already entered into the class table entry for the class.
1867                        </p>
1868                        <p>
1869                            <b> When a method declaration is encountered, a unique label must be generated for the method and the label must be entered into the
1870                              class table entry of the method.</b> Thus, the call address to any method can be determined from the class table entry of the
1871                              corresponding class.  (In the next stage, we will see that a more sophisticated strategy will be needed to support inheritance).
1872                        </p>
1873                        <p>
1874                            Storage allocation for class variables is equally simple.  Just as was done for user defined types,
1875                            a call to <i>'new'</i> must allocate a block of 8 words in the heap for storing the member fields of the variable.
1876                            The start address of this block must be assigned to the variable.
1877                        </p>
1878                        <p>
1879                            Other matters being routine, the non-trivial point pending is the <b>deferencing of the self reference</b> – in <i>self.field_name</i>.
1880                        </p>
1881                        <p>
1882                             The following paragraphs summarize the key ideas:
1883                        </p>
1884
1885                        <ul>
1886
1887                            <li id="otis">
1888
1889                            1.  How to get the address of <i>
1889self?</i>  First observe that a reference to <i>self</i> will occur only within a member function
1890                            of a class variable.   Second, all variables of the same class share the code of all the methods of the class.
1891                            Thus, at run time, a method must be told which is the variable for which the current call is made.
1892                            In other words, <b>the address of self can be determined only at run-time
1893                              (<i>why? - ensure that you digest this point clearly before proceeding further!</i>)</b>
1894                            <br>
1895
1896                            <p>
1897                            The standard way to resolve this reference is to set the convention that <b>before a call to a method,
1898                              the caller must push the address of <i>self</i></b> (for the particular call) <b>as an argument into the stack.</b>
1899                              The convention we suggest is to push the address of <i>self</i> before pushing the arguments during method invocations.
1900                              Note that <i>self</i> is an <b>implicit argument</b>, not found either in the declaration or the definition of the method.
1901
1902                  In the next stage, we will need to push one more implicit argument for each method invocation.  It is instructive to have a quick look
1903                              at the <a href="oexpl-run-data-structures.html#nav-runtimestackmanagementformethodinvocations" target="_blank">run-time-stack management documentation</a> for OExpL at this stage
1904                            </p>
1905                            </li>
1906                            <br>
1907                            <li id="otis">
1908                            2.  The <b>local symbol table of a method must contain an entry for <i>self</i></b> along with the other arguments to the function.
1909                            The binding field of this entry must be the relative address (with respect to BP in the stack) where the address of self must
1910                            be pushed by the caller.  For example, if this value is -k, then the compiler expects that the caller would have pushed to
1911                            stack corresponding to  [BP-k] the address of the heap block holding the member fields of the variable.
1912                            </li>
1913                            </ul>
1914                        <p>
1915                            The task of completing code generation phase is now straightforward.
1916                        </p>
1917                        <p>
1918                            <b>Task 2:</b> Complete code generation for this stage.
1919                        </p>
1920                      <!--  <p>
1921                           <b> Part III:  Building Source Code in Multiple Files</b> (optional).
1922                        </p>
1923                        <p>
1924                            In this section, we will see how to support the ExpL programmar to compile each class separately and link them together with the main program.  Since the contents of this section are tangential to our principal concerns, this part is marked optional.  However support for modularity is <i>absolutely essential</i> if large programs have to be written and maintained.  Since the section is optional, the description here is brief.
1925                        </p>
1926                        <p>
1927                            To avoid too large code files, it would be advisable to code the source program into multiple files and compile each one separately.  The following structure is proposed:
1928                        <ul>
1929                             <li id="otis">
1930                            1. All type definitions may be collected together in the file <i>program_name.type</i> between the keywords <i>type</i> and <i>endtype.</i>  </li>
1931                            <li id="otis">
1932                            2.  Each class may be written into a separate class file (<i>class_name.class</i>).
1933                            </li>
1934                            <li id="otis">
1935                            3.  The main program (<i>progam_name.expl</i>) shall contain <b>no type definitions or class definitions</b>.   The main program contains global declarations, function definitions and the Main function.
1936                            </li>
1937                        </ul>
1938                        </p>
1939                        <p>
1940                            Your compiler must support two types of compilation options:
1941                        <ul>
1942                            <li id="otis">
1943                            1.  <b>expl -obj</b> <i>class_name.class program_name.type</i>
1944                            <br>
1945                            This option must compile a single class file into an object file.  The code generated 
1945will contain unresolved labels.   The output file may be named <i>class_name.obj</i>.  The structure for object files will be discussed soon.
1946
1947                            </li>
1948                            <li id="otis">
1949                            2.  <b>expl</b> <i>program_name.expl, program_name.type, class_name1.obj, class_name2.obj,class_namek.obj</i>
1950                            <br>
1951                            This option expects that the object files are created using the <b>-obj</b> option.  The main program is build by linking together all the object modules and the ouput file must be an ABI compatible <i>program_name.xsm</i>
1952                            </li>
1953                        </ul>
1954                        </p>
1955                        <p>
1956                            The key observation here is that to <b>generate assembly code with labels for a particular class, one needs only the class definition and all the type defintions</b>. The main points to be careful here are:
1957                        <ul>
1958                            <li id="otis">
1959
1960                            a.  As each class is compiled separately, <b>the labels in each object file must not be conflicting</b>.  To solve this issue, each label in an object file may be annotated by the corresponding class name (Ex.  <i>class_name1_L0</i>, <i>class_name1_L1</i> etc.)
1961                            </li>
1962                            <li id="otis">
1963                            b.  Since the class definitions must be made available in the final building step, during the compilation of a class, the <b>class definition must be copied into the object file</b>.
1964                            </li>
1965                        </ul>
1966                        </p>
1967                        <p>
1968                            Thus, each object file will contain a class definition followed by the assembly code (with labels) for the methods of the class.  Finally, during the final compilation process, class definitions from each object file will be combined into the class table and the final code generation and label translation steps will be done.
1969                        </p>
1970                        <p>
1971                            You must look at the YACC/Bison manual to find out how parsing of multiple files can be done.  We leave out the technical details.
1972                        </p>
1973                        <p>
1974                            <b>Task 3:</b>  Implement support for separate compilation of object files as outlined above.
1975                        </p>
1976                        <p>
1977                            <b>Note:</b>  The ABI given to you do not support object file formats.  Hence we have suggested an object format specific to the ExpL project.  However, standard binary interfaces support object file formats – (For example see the <a href="https://en.wikipedia.org/wiki/Executable_and_Linkable_Format" target="_blank"> Unix ELF)</a>.   These object files may be linked together by the operating system at load time – that is, when the program is loaded into the memory for execution.  A discussion of these matters is beyond the scope of this project.
1978                        </p> -->
1979
1980                        <p>
1981                            <i>Exercise 1</i>:  What modifications must be done to allow class variables to be passed as arguments to functions?
1982                        </p>
1983                        <p>
1984                            <i>Exercise 2</i>:  What modifications must be done to allow functions to have locally declared variables of class?
1985                        </p>
1986
1987                      <!--  <p>
1988                          Check your implementation with the following test cases : <br>
1989                          1) <a href="oexpltestprograms/test1.html" target="_blank">Test Case 1</a> <br>
1990                          2) <a href="oexpltestprograms/test2.html" target="_blank">Test Case 2</a> <br>
1991                          3) <a href="oexpltestprograms/test3.html" target="_blank">Test Case 3</a> <br>
1992                        </p> -->
1993
1994                        <h4> <b>Test Programs </b></h4>
1995                        <p>
1996                          Check your implementation with the following test cases : <br>
1997                          <a href="oexpl-testprograms.html#test1" target="_blank">Test Program 1: Binary Search Tree using Classes
1998</a> <br>
1999                          <a href="oexpl-testprograms.html#test2" target="_blank">Test Program 2: Linked list in OExpL
2000</a> <br>
2001                          <a href="oexpl-testprograms.html#test3" target="_blank">Test Program 3: Sum of factorials</a> <br>
2002
2003                        </p>
2004
2005
2006                        </article>
2007
2008                         <article class="grid col-full" id="nav-stage8">
2009                         <h2>Stage 8:  Inheritance and Sub-type Polymorphism</h2>
2010                            <b>Time Estimate :</b> 1 week, 5-10 hours/week
2011                        <p>
2012                            <b>Prerequisite Reading</b>:
2013                            <ul>
2014                                <li id="otis">1.  A rigorous reading of the <a href="oexpl-specification.html" target="_blank"> OExpL specification </a></li>
2015
2016                            </ul>
2017                        </p>
2018
2019                        <p>
2020                            <b>Learning Objectives</b>:
2021                            <ul>
2022                                 <li id="otis">You will extend the language of Stage 7 by adding support for single inheritance
2023                                   and subtype polymorphism to make OExpL an <i>object oriented</i> language.</li>
2024                            </ul>
2025                            <hr>
2026                        </p>
2027
2028                        <p>
2029
2030                        In this stage, we will extend ExpL to provide support for
2031                        <a href="https://en.wikipedia.org/wiki/Inheritance_(object-oriented_programming)" target="_blank">single inheritance</a> and
2032                        <a href="https://en.wikipedia.org/wiki/Subtyping" target="_blank">subtype polymorphism</a>.
2033                        These features qualifies OExpL to be called an object oriented language.
2034
2035                        </p>
2036                        <p>
2037
2038                        Addition of support for inheritance and polymorphism involves some intellectual complexity.
2039                        Fortunately, once the underlying conceptual issues are understood, the implementation is not difficult.
2040
2041                        </p>
2042
2043                        <p>
2044                        <b>Part I:  Syntax and Semantics</b>
2045                        </p>
2046
2047
2048                        <p>
2049                            The definition of a class could now be by extention of a previously defined class.
2050                            <div class="syntax">
2051                              Cname         : ID       	{Cptr = Cinstall($1->Name,NULL);} <br>
2052            &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;| ID Extends ID	{Cptr = Cinstall($1->Name,$3->Name);}
2053                            </div>
2054                        </p>
2055
2056                        <p>
2057                        An additional field called the <b>parent class pointer</b> must be added to each class table entry.
2058                        If the class is defined by extention of another class, the parent class pointer entry must point to the
2059                        class table entry of the parent class.  If the class is not an extention of any other class, this entry must be NULL.  (<a href="oexpl-data-structures.html" target="_blank">See class table structure</a>).
2060                        An outline of the grammar is given <a href="oexpl-grammar-outline.html" target="_blank">here</a>.
2061                        </p>
2062
2063
2064                        <p>
2065                            An extended class inherits all the member fields and methods of the parent class.
2066                            The descendent class is permitted to do additional definitions as specified below.
2067
2068                        <ul>
2069                            <li id="otis">
2070                            1.  The only member field declarations in the descendent class shall be for the  new member
2071                            fields that are not present in the parent.  (<b>The descendent cannot re-declare or remove any of
2072                            the parent's member fields.</b>)  Additionally, in our current implementation plan,
2073                            the number of member fields - including those inherited from the parent - must not exceed 8
2074                            (because our memory allocation policy allocates only 8 words for storing a class object).
2075                            <br>
2076                            From an implementation perspective, <b>whenever the definition of a class by extension of
2077                              another class is encountered, the compiler must copy all the member field information of the
2078                              parent to the descendent class.</b>  The member fields may be listed in the same order as they
2079                              appear in the parent.  Additional entries must be created for new members specific to the
2080                              descendent class.
2081                            </li><br>
2082                            <li id="otis">
2083                            2.   The descendent class may <b>define new methods</b> or <b><a href="https://en.wikipedia.org/wiki/Method_overriding" target="_blank">override</a></b> one or more
2084                            of the <b>parent's methods</b>.  OExpL allows a class to contain only one definition for a function.
2085                             <b>Once a method is over-ridden, the method of the parent class will no longer be visible inside the
2086                             descendent class</b>.  Moreover, the <b>signature of the overridden method must be identical with the
2087                               signature of the method in the parent class </b>(in both the number and the types of arguments).
2088                               In  other words, <a href="https://en.wikipedia.org/wiki/Function_overloading" target="_blank">function overloading</a>
2089                                is not permitted. (Exercise 1 at the end asks you to relax this condition).
2090
2091                            </li>
2092                        </ul>
2093                        </p>
2094
2095                        <p>
2096                            From an implementation perspective, the compiler may <b>initially copy the signatures of all methods
2097                              of the parent to the class table entry of the descendent</b>. New entries will have to be created for methods
2098                              that defined in the descendent, but not present in the parent.  Finally, the present implementation restricts
2099                              the number of methods in a class ( including inherited methods ) to 8.
2100                        </p>
2101
2102                        <p>
2103                            What about the labels of the methods of the descendent class? <b> If a method is over-ridden or defined new in a class,
2104                            the compiler must assign a new label for the method and store this label in the <i>Flabel</i> field of the method in the <a href="oexpl-data-structures.html" target="_blank">class table entry</a>.
2105                            Otherwise, the class inherits the parent's method and the label of the method in the parent class ( specified by the <i>Flabel</i> field of the parent class ) must be copied
2106                            into the <i>Flabel</i> field of the method in the descendent class</b>
2106 ( See Memberfunclist in the class table ).
2107                        </p>
2108
2109
2110                        <p>
2111                            Once the class table entries are created as described above, syntax and semantic analysis phases of
2112                            compilation can be completed easily.
2113                        </p>
2114
2115
2116                        <p>
2117                            An assignment of the form a = b; between class variables is valid if either <i>a</i> and <i>b</i> are variables of the
2118                            same class or <i>b</i> is a variable of a descendent class of the class <i>a</i>.  Similarly a=new(class_name); is
2119                            valid if the class identified by class_name is a descendent class of the class to which <i>a</i> belongs to.
2120                            Thus, <b>a variable of a certain class can hold a reference to any object of the same or descendent classes</b>.
2121                            Since the class table contains adequate information to perform this check, syntax and sematic analysis can be completed now.
2122
2123                        </p>
2124
2125
2126                        <p>
2127                            <b>Task 1:</b>  Complete the front end - lexical, syntax and Semantic analysis.
2128                        </p>
2129
2130
2131                    <!--    <p>
2132
2133                        <b>Note:</b>  If classes are defined in separate files, the parent class and all the desecndent classes in an
2134                        inheritance hierarchy must be defined in a single file.   Thus, each object file will contain the complete class table
2135                        information pertaining to a class hierarchy.
2136
2137                      </p>-->
2138
2139
2140
2141                        <p>
2142
2143                           <b>Part II:  Code Generation</b>
2144                        </p>
2145
2146
2147                        <p>
2148                        <ul>
2149
2150
2151                        The key differences between the language of Stage 7 and the present stage are the following:
2152
2153                        <li id="otis">
2154                            a).  A variable of a parent class may hold a reference to an object of any descendent class.
2155                        </li>
2156
2157                        <li id="otis">
2158                            b).  The class to which the referred object belongs to at run time cannot be determined at compile time (why?)
2159                        </li>
2160
2161                        <li id="otis">
2162                            c).  When a method is invoked using the variable of the parent class, if the method is over-ridden by the child class,
2163                            then the method of the child class must be invoked.
2164                        </li>
2165                        </ul>
2166                        </p>
2167                        <p>
2168
2169                        Assume that A, B, C are classes such that B extends A and C extends B.   Let x be a variable of class A.
2170                        Consider the program segment:
2171
2172                       </p>
2173
2174
2175<!-- CHECK THIS ONCE -->
2176
2177                       <p>
2178
2179                            <div class="syntax">
2180                                ...
2181                                <br>
2182                                Read(n);
2183                                <br>
2184                                if (n>0) then
2185                                <br>
2186                                &nbsp;&nbsp;x = new(B); <br>
2187                                else  <br>
2188                                &nbsp;&nbsp;x = new(C); <br>
2189                                endif <br>
2190                                &nbsp;&nbsp;retval = x.fun(); <br>
2191                                ... <br>
2192                            </div>
2193                        </p>
2194                        <p>
2195                        Let <i>fun()</i> be a function defined in class A.
2196                        Let us assume that the label for the function in the class table is L1.
2197                         Suppose that B does not over-ride <i>fun()</i>, but C over-rides <i>fun()</i>.
2198                          Let the label for the over-ridden function be L2.
2199                        </p>
2200                        <p><b>Important Note :</b> Unless fun() is defined in class A, the call <i>x.fun()</i> should result in a compilation error even if B and C contains the declaration for <i>fun()</i>. This is because
2201                          if a variable of a parent class holds the reference to an object of a descendent class, only
2202                           methods defined in the parent class are allowed to be invoked using the variable of the parent class.</p>
2203                        <p>
2204
2205                            The call <i>x.fun()</i>;   must translate to CALL L1 if (n>0) whereas <i>x.fun()</i> must translate to CALL L2 otherwise.
2206                             The value of n is known only at run-time and the compiler can't hope to guess it.   What will the compiler do now?!
2207
2208                        </p>
2209
2210                        <p>
2211                            It turns out that there is a remarkably simple and elegant way to handle the issue by maintaining what are known
2212                             as  <b>function tables</b> (called <a href="https://en.wikipedia.org/wiki/Virtual_method_table" target="_blank">virtual function tables</a> in OOP jargon) at run time.
2213
2214                        </p>
2215
2216                        <p>
2217
2218                            <b>The key to the solution to the problem is that the variable x must carry the information about which
2219                              class is it referring to at run time, and this information must be used to dereference the function call at run time. </b>
2220                        </p>
2221
2222                        <p>
2223                        <ul>
2224
2225                            The implementation details are outlined below: <br>
2226
2227                        <li id="otis">
2228                          <br>
2229                            1. <b> For each class, we will maintain a table of size 8 in the memory, listing labels of the
2230                              methods of the class. </b> (Recall that we permit a class to have at most 8 methods).
2231                              <b>The labels may be listed in the order in which the methods are defined in the class.</b>
2232                              This table is called the <b>virtual function table</b> for the class.
2233                              Since all the class definitions are known at compile time, the compiler can generate initial code to set
2234                              up all the class tables in the stack regi
2234on of the program.
2235                              (Typically, at the beginning of the stack, allocating space before global variables.)
2236
2237                        </li>
2238                          <br>
2239
2240                        <li id="otis">
2241                            2.  <b>The label for a method in the virtual function table will be set to the method's label in the corresponding
2242                              class table entry.</b>    Consequently, the label of a method in a descendent class will be the
2243                              label of the method in the parent class if the method is not over-ridden.  Referring to the
2244                              example above, the label for the method fun() in the virtual function tables of classes A and B will be L1, whereas, the
2245                              label will be L2 in the virtual function table of class C.
2246
2247                        </li>
2248                          <br>
2249                        <li id="otis">
2250                        3.  <b>The position of the label of a method in the virtual function tables of the parent class and all the descendent
2251                          classes in a class hierarchy must be the same.</b>  Referring to the above example,  if the label of the method fun()
2252                          is listed third in the virtual function table of A, then it must be listed third in the virtual function tables of classes B and C.
2253                          Thus the index of a method's entry in the virtual function table will be the same for every class in a class hierarchy.
2254                          The advantage of this convention is that while translating, <b>the position of a method's label relative to the base
2255                            address of the virtual function table is completely determined at compile time.</b> Note that since the language does not
2256                           permit function overloading, the entry for a given method name in a virtual function table will be unique.
2257                        </li>
2258                          <br>
2259
2260                        <li id="otis">
2261                            4.  In view of the above, to translate <i>x.fun()</i>, all that needs to be determined at run time is the
2262                            base address of the correct virtual function table.  To keep track of this information,<b> the compiler
2263                              must allocate two memory locations for each class variable -  One for the usual pointer to the
2264                              memory block allocated in the heap for storing the object's member fields .  The second, to store
2265                              a pointer to the virtual function table of the class to which the current object stored in the variable belongs to.</b>
2266                        </li>
2267
2268
2269                        </ul>
2270                        </p>
2271
2272                        <p>
2273
2274                            Conceptually, each class variable holds a pair <i>[MemberFieldPointer, VirtualFunctionTablePointer]</i>.  The statement <i>x=new(B)</i>;  in the
2275                            example above should do the following:
2276                            <ul>
2277                             <li>  Allocate a block of 8 words in the heap and store the start address
2278                            in the <i>MemberFieldPointer</i> field of x. <br> </li>
2279                              <li>  set the <i>VirtualFunctionTablePointer</i> field of x to the base address of the virtual function table of class B.</li>
2280                            </ul>
2281                            An assignment of the form y=x, if valid semantically, will result in both the pointers of x being copied
2282                            into the corresponding pointers of y.
2283                        </p>
2284
2285                        <p>
2286                            Note that once the base of the correct virtual function table is known, invoking the right function simply involves
2287                            adding the offset of the function to the base and making a call to the address (label) stored in the virtual function table entry.
2288
2289                        </p>
2290
2291                        <p>
2292                            Note that the labels will be automatically translated to actual addresses during the <a href="label-translation.html" target="_blank">label translation phase</a>.
2293
2294                        </p>
2295
2296                        <p>
2297                            To implement virtual function tables on the eXpOS ABI, the suggested method is to allocate space (8 words each)
2298                            for storing the virtual function tables of each class in the stack before allocating space for global variables.
2299
2300
2301                        </p>
2302
2303                        <!--
2304                        <p>
2305                            A detailed tutorial on the implementation of function tables is given <a href="#" target="_blank">here [LINK]</a>.
2306                        </p>
2307                      -->
2308
2309                        <p>
2310
2311                            <b>Read the <a href="oexpl-run-data-structures.html" target="_blank">OExpL run time data structures documentation</a>
2312                            before proceeding further.</b>
2313                          </p>
2314
2315
2316                        <p>
2317                            <b>Task 2:</b>  Complete the OExpL compiler.
2318                        </p>
2319
2320
2321                          <!--  You may test your compiler implementation with the test programs given <a href="oexpl-testprograms.html" target="_blank">here</a> -->
2322
2323                      <!--  <p>
2324                          Check your implementation with the following test cases : <br>
2325                          1) <a href="oexpltestprograms/test4.html" target="_blank">Test Case 1</a> <br>
2326                          2) <a href="oexpltestprograms/test5.html" target="_blank">Test Case 2</a> <br>
2327                          3) <a href="oexpltestprograms/test6.html" target="_blank">Test Case 3</a> <br>
2328                          4) <a href="oexpltestprograms/test7.html" target="_blank">Test Case 4</a> <br>
2329                        </p>
2330                      -->
2331
2332                        <h4> <b>Test Programs </b></h4>
2333                        <p>
2334                          Check your implementation with the following test cases : <br>
2335                          <a href="oexpl-testprograms.html#test4" target="_blank">Test Program 1: Testing the runtime binding of the variables of a class
2336</a> <br>
2337                          <a href="oexpl-testprograms.html#test5" target="_blank">Test Program 2: Testing the correct set up of the virtual function table
2338</a> <br>
2339                          <a href="oexpl-testprograms.html#test6" target="_blank">Test Program 3: Testing the implementation of inheritance and subtype polymorphism</a> <br>
2340
2341                          <a href="oexpl-testprograms.html#test7" target="_blank">Test Program 4: Testing the implementation of inheritance and subtype polymorphism</a> <br>
2342
2343
2344                        </p>
2345
2346
2347                        <p>
2348                        <i>Exercise 1</i>:  This exercise asks you to add a limited form of <b>function overloading</b>
2348 support to the language.
2349                        Here, when a descendent class overrides a method of a parent class, it can re-define the function with a signature that is
2350                        possibly different from that of the parent class.  In this case, both the definitions will be active in the child class; with
2351                        the compiler translating the call to the correct address (label) looking at the arguments.
2352                        Make necessary modifications to the language syntax to support this form of function overloading.
2353                        </p>
2354
2355                        <p>
2356                            Note:  Overloading and subtype polymorphism are two polymorphism types typiclly supported by most object
2357                            oriented langauges.
2358                          A third important type of polymorphism
2359                          called <i><a href="https://en.wikipedia.org/wiki/Parametric_polymorphism" target="_blank">parametric polymorphism</a></i> (templates in C++)
2360                          has not been touched upon in this project.
2361
2362
2363                        </p>
2364
2365                        </p>
2366                        </article>
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392                </div>
2393            </section>
2394            </body>
2395        </div>
2396
2397
2398        <footer class="center part clearfix">
2399            <ul class="social column3 fleft">
2400                <li><a href="https://github.com/silcnitc">Github</a></li>
2401                <li>  <a rel="license" href="http://creativecommons.org/licenses/by-nc/4.0/">
2402                    <img alt="Creative Commons License" style="border-width:0" src="img/creativecommons.png" /></a></li>
2403            </ul>
2404          <div class="up column3 mright"> <a href="#navtop" class="ir">Go up</a> </div>
2405          <nav class="column3">
2406            <ul>
2407              <li><a href="index.html">Home</a></li>
2408              <li><a href="about.html">About</a></li>
2409              <!-- <li><a href="uc.html">Contact</a></li> -->
2410            </ul>
2411          </nav>
2412      </footer>
2413    <!-- Javascript - jQuery
2414    
2414<script src="http://code.jquery.com/jquery.min.js"></script>
2414-->
2415    
2415<script>window.jQuery || document.write('
2415<script src="js/jquery-1.7.2.min.js"><\/script>')</script>
2415
2416    <!--[if (gte IE 6)&(lte IE 8)]>
2417    
2417<script src="js/selectivizr.js"></script>
2417
2418    <![endif]-->
2419    
2419<script src="js/scripts.js"></script>
2419
2420    
2420<script src="js/inject.js"></script>
2420
2421</html>

Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.