-
Notifications
You must be signed in to change notification settings - Fork 14
/
Copy pathData_Structures.html
907 lines (894 loc) · 72.8 KB
/
Data_Structures.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
<!Doctype html>
<html lang="en">
<head>
<title>Data Structures</title>
<meta charset="UTF-8">
<!--<link rel="stylesheet" href="css/bootstrap.min.css">-->
<link rel="stylesheet" href="css/style_new.css">
<link rel="stylesheet" href="js/embed-2cd369fa1c0830bd3aa06c21d4f14a13e060d2d31bbaae740f4af4.css"><div id="gist28627206" class="gist">
<link rel="stylesheet" href="js/embed-cbe5b40fa72b0964f90d4919c2da8f8f94d7c9f6c2aa49c07f6fa3.css"><div id="gist28627206" class="gist">
</head>
<div class="container">
<header id="navtop">
<a href="index.html" class="logo fleft"><img src="img/logo.png" alt=""></a>
<nav class="fright">
<ul>
<li><a href="index.html">Home</a></li>
<li><a href="about.html">About</a></li>
<!-- <li><a href="help.html">Help</a></li> -->
<li><a href="roadmap.html">Roadmap</a></li>
<li><a href="documentation.html" class="navactive">Documentation</a></li>
</ul>
</nav>
</header>
<div class="Services-page main grid-wrap">
<header class="grid col-full">
<hr/>
<p class="fleft">Data Structures for ExpL Compilation/Interpretation</p>
<br>
<br>
<!-- <a class="button" href="">Download as PDF</a> -->
</header>
<aside class="grid col-one-quarter mq2-col-full">
<menu>
<ul>
<li><a class="sec" href="#nav-introduction">Introduction</a></li>
<li><a class="sec" href="#nav-analysis-structures">Data Structures for Analysis Phase</a></li>
<li><a class="subsec" href="#nav-typetable">Type Table</a></li>
<li><a class="subsec" href="#nav-symbol-table">Symbol Table</a></li>
<li><a class="subsubsec" href="#nav-global-symbol-table">Global Symbol Table</a></li>
<li><a class="subsubsec" href="#nav-local-symbol-table">Local Symbol Table</a></li>
<li><a class="subsec" href="#nav-abstract-syntax-tree">Abstract Syntax Tree</a></li>
<li><a class="sec" href="#nav-execution-structures">Data Structures for execution phase</a></li>
<li><a class="subsec" href="#nav-memory-model">The memory model</a></li>
<li><a class="subsec" href="#nav-register-allocation">Register Allocation</a></li>
<li><a class="subsec" href="#nav-static-allocation">Static Allocation</a></li>
<li><a class="subsec" href="#nav-run-time-stack">Run Time Stack Allocation</a></li>
<li><a class="subsec" href="#nav-heap">Heap Allocation</a></li>
</ul>
</menu>
</aside>
<section class="grid col-three-quarters mq2-col-full">
<div class="grid-wrap">
<article class="grid col-full" id="nav-introduction">
<h2>INTRODUCTION</h2>
<p>
The compilation/interpretation of an ExpL program involves two phases. In the first phase (called the <b>analysis phase</b>), the source ExpL program is analyzed (lexical, syntax and semantic analysis are completed in this phase) and if the program is free of syntax and semantic errors, an intermediate representation of the source program called the <b>abstract syntax tree</b> is generated.
</p>
<p>
This is followed by a second phase, whose functionality is different for a compiler and an interpreter.
</p>
<p>
In the case of a compiler, the second phase (called the <b>synthesis phase</b>) recursively traverses the abstract syntax tree and generates target code.
</p>
<p>
[<b>Note</b>: the abstract syntax tree representation is only one among several intermediete representations used in practical compilers. “Lower level” intermediete representations like three address code are often more useful for applying code optimization algorithms. In our present experiment, we do not perform any code optimizations and hence the code generation phase will directly work with the abstract syntax tree.]
</p>
<p>
In the case of interpretation, the second phase (called the execution phase) involves direct execution of the program by recursive evaluation of the abstract syntax tree.
</p>
<p>
<i>The description of data structures below assumes an interpreter is being designed</i>. This choice has been made to avoid target machine dependency in the documentation. Notes/comments are added wherever appropriate explaining the modifications to be made to the data structures to implement a compiler.
</p>
<p>
There are three basic data structures that are maintained during the analysis phase. These are the following:
<ol>
<li> The <b>global symbol table</b> is used to store information about the global variables and functions in the program.</li>
<li>For each function, a separate <b>local symbol table</b> is maintained to store the information about local variables and arguements of the function. </li>
<li>Finally, the <b>abstract syntax tree</b> that is constructed as the outcome of the analysis phase is the third data structure.</li>
</ol>
</p>
<p>
An abstract syntax tree is a tree representation of a program. It is a generalization of the tree representation for expressions (called the expression tree). For example, the arithmetic expression (3+5)*(5+9) is typically represented as an expression tree as below:
</p>
<p>
<img src="img/data_structure_28.png" alt="" />
</p>
<p>
We can generalize this representation to come up with a tree representation for the whole sequence of statements of a ExpL function in a program. Each funcion in an ExpL program will be represented by an abstract syntax tree. Thus, the whole program will be a collection of abstract syntax trees, one for each function.
</p>
<p>
In the following, the definitions node structures for each of the above data structures is discussed. The organization of data in these data structures is also discussed with illustrative examples.
</p>
</article>
<article class="grid col-full" id="nav-analysis-structures">
<h2>DATA STRUCTURES FOR ANALYSIS PHASE</h2>
</article>
<article class="grid col-full" id="nav-typetable">
<h2>Type Table</h2>
<p>
The Type Table stores all the necessary information regarding the various user defined types in the source program. The compiler creates an entry in the Type Table for each user defined type. In addition to this, there are default entries created for primitive types (<i>int</i>, <i>str</i>) and special entries <i>null</i>, <i>boolean</i> and <i>void</i> for the internal purposes of the interpreter. The default and special entries are made beforehand whereas entries for user defined types are made as the Type Declaration Section of the source code is parsed.
</p>
<h4>Structure</h4>
<p>
The structure of Type Table is as follows:
</p>
<script src="js/9d481cdd2e29c3eadc3d.js"></script>
<p>
The variable 'fields' is a pointer to the head of 'fieldlist'. Here 'fieldlist' stores the information regarding the different fields in the case of a user-defined type.
</p>
<script src="js/79a0b8b91299662b744d.js"></script>
<h4>Associated Methods</h4>
<ul>
<li>void TypeTableCreate() : Function to initialise the type table entries with primitive types <i>(int,str)</i> and internal data types <i>(boolean,null,void)</i>.</li>
<li>struct Typetable* TLookup(char *name) : Search through the type table and return pointer to type table entry of type 'name'. </li>
<li>struct Typetable* TInstall(char *name, struct Fieldlist *fields) : Creates a type table entry for the type of 'name' with given 'fields' and returns the pointer to the type table entry.</li>
<li>void FInstall(char *name, struct Typetable *type) : Adds a fieldlist entry with given 'name' and 'type'.</li>
<li>struct Fieldlist* FLookup(char *name, struct Fieldlist *list) : Searches for a field of given 'name' in the given 'fieldlist' (of some user-defined type) and returns a pointer to the matching entry.</li>
</ul>
<h4>Illustration</h4>
<p>
Let us consider the following sample code:
</p>
<script src="js/67898e19a3cb8f2dc010.js"></script>
<ol>
<li>The type table is first created and initialised to contain the default entries for each of the primitive and internal datatypes. This is done through a call to the function TypeTableCreate() from main function before yyparse() is called to start parsing the code. After the execution of TypeTableCreate() , the type table will be as follows:
<br/><img src="img/data_structure_1.png" style="width:40%;margin-top:1em;margin-bottom:1em"></img><br>
</li>
<li>As soon as the compiler encounters the declaration of a user defined type, it is installed into the type table. Subsequently the fields are attached to this type table entry. For instance, in the case of the user-defined type <i>linkedlist</i>, as soon as the name <i>linkedlist</i> is encountered, a type table entry with 'name' set to <i>linkedlist</i> and 'fields' set to <i>NULL</i> is created. Later, on finishing the complete parse of the type definition, the fieldlist is created and it is attached to the type table entry. <br><b>NOTE</b> : A type table entry is created as soon as the type name is seen. This is because a field of the type may be of same type (For example, just like <i>next</i> is of type <i>linkedlist</i> in the type definition of <i>linkedlist</i>). When the 'fieldlist' is created, the type of the field is set by looking up the type table.
<br/><img src="img/data_structure_2.png" style="width:70%;margin-top:1em;margin-bottom:1em"></img><br>
</li>
<li>Similar actions are carried out for user-defined type <i>marklist</i> also.
<br/><img src="img/data_structure_3.png" style="width:90%;margin-top:1em;margin-bottom:1em"></img><br>
</li>
<li>Once the type declaration section is completely parsed, the type table is fully created and will not be further modified or updated.</li>
</ol>
</article>
<article class="grid col-full" id="nav-symbol-table">
<h2>Symbol Tables</h2>
<p>
Symbol tables are used to store information pertaining to the variables and functions in a program.
</p>
<h4 id="nav-global-symbol-table">Global Symbol Table</h4>
<p>
The global symbol table stores information pertaining to all the global variables and functions in an ExpL program.
</p>
<h6>Structure</h6>
<p>
The structure of Global Symbol Table(GST) is as follows:
</p>
<script src="js/4f483469c1dccd2e9a64.js"></script>
<p>
<span style="color:red;font-size:12px;">✛</span><b>NOTE</b>: In the case of a compiler, fbinding must store the starting address of the function's code in memory. A call to the function must translate into an assembly level call to the function's code in memory. Hence, in this case fbining has to be an integer storing a memory address.
</p>
<p>
Arglist is used to store information regarding the types and names of the arguements. ArgStruct has the following structure.
</p>
<script src="js/f583d3a3ee857a50d496.js"></script>
<p>Read about ASTNode <a href="#nav-abstract-syntax-tree">here</a>.</p>
<h6>Associated Methods</h6>
<ul>
<li>struct Gsymbol* GInstall(char *name,struct Typetable *type, int size, struct ArgStruct *arglist) : Creates a Global Symbol object of given 'name', 'type', 'size' and 'argument list' and assigns a 'binding' to the variable.</li>
<li>struct Gsymbol* GLookup(char *name) : Search for a GST entry with the given 'name', if exists, return pointer to GST entry else return NULL.</li>
</ul>
<h6>Illustration</h6>
<p>
Continuing with earlier example, let us add Global declaration section to it.
</p>
<script src="js/f1d20b44ca4389ed1be6.js"></script>
<ol>
<li>As soon as the compiler encounters the global declaration of a variable or funtion, it is installed into Global Symbol Table. Subsequently, the arguments are attached to the entry in case of functions. Following is how GST looks when <i>studentname</i> is installed.
<a href="img/data_structure_5.png"> <img src="img/data_structure_5.png" style="height:90%"></img></a>
</li>
<li>
Similarly for <i>rollno,average,findaverage(linkedlist marks)</i>, symbol table entries are formed and installed. The fbinding for a function is the abstract syntax tree of the function definition and is set only after complete parsing of the function definition.
<br><a href="img/data_structure_6.png"> <img src="img/data_structure_6.png"></img></a>
</li>
<li>After this, the types for rollno,average and findaverage will be set and these objects are appended to the global symbol table. The final Global Symbol table looks as follows:
<br><a href="img/data_structure_7.png"> <img src="img/data_structure_7.png"></img></a>
</li>
</ol>
<h4 id="nav-local-symbol-table">Local Symbol Table</h4>
<p>
In addition to the global symbol table, the ExpL compiler maintains a separate local symbol table for each function for storing information regarding the functions arguments and local variables. Each function has its own list of local variables. So each function has its own LST.
</p>
<h6>Structure</h6>
<script src="js/b2f1dd17ecc21780f898.js"></script>
<h6>Associated methods</h6>
<ul>
<li>struct Lsymbol* LInstall(char *name,struct Typetable *type) : Creates a local symbol tbale with given 'name' and 'type' and also sets its 'binding'.</li>
<li>struct Lsymbol* LLookup(char *name) : search the LST and if any entry with given 'name' is found ,return the entry,else returns NULL. </li>
</ul>
<p>
Arrays cannot be local variables, so we don't need to store the size of a variables. Also nested functions are not allowed in ExpL, so we don't require fbinding and arglist as in Gsymbol. The LST is formed for the Local Declaration Section in the same way GST was created for the Global declaration section.
</p>
<p>
Memory is allocated for local variables of a function from a seperate memory area called the <a href="#nav-stack" class="imp">stack</a>. Hence, the binding for a local variable is the relative address of the variable with respect to the base of the <a href="#"><b>Activation Record</b></a>. The <a href="#"><b>Base Pointer</b></a> points to the base of an activation record of a function. The binding is added to the Base Pointer to obtain the address of variable in stack. This will be explained in detail later.
</p>
</article>
<article class="grid col-full" id="nav-abstract-syntax-tree">
<h2>Abstract Syntax Tree</h2>
<p>
The machine independent <b>front-end</b> phase of a compiler constructs an intermediate representation of the source program called the <b>Abstract Syntax Tree (AST)</b>. An interpretter will evaluate the AST whereas a compiler will run a machine dependent <b>back-end</b> to generate a target assembly language program. The following structure may be used to represent a node of the AST.
</p>
<script src="js/ecec5cc25b3834dd40a8.js"></script>
<p>
The union Constant is used to store the value of an integer or sting constant.
</p>
<script src="js/8cb0db40153ff46dabfa.js" charset="utf-8"></script>
<h6>Associated methods</h6>
<ul>
<li>struct ASTNode* TreeCreate (</br><span style="padding-left:5em;">struct Typetable *type,</span></br><span style="padding-left:5em;">int nodetype,</span></br><span style="padding-left:5em;">char *name,</span></br><span style="padding-left:5em;">union Constant value,</span></br><span style="padding-left:5em;">struct ASTNode *arglist,</span></br><span style="padding-left:5em;">struct ASTNode *ptr1,</span></br><span style="padding-left:5em;"> struct ASTNode *ptr2,</span></br><span style="padding-left:5em;"> struct ASTNode *ptr3</span></br><span style="padding-left:5em;">) </span></br>Creates a node with the fields set according to the arguements passed.</li>
<li>regindex evaluate(struct ASTNode *t)</br> Evaluation of an AST node results in a value. A compiler generates code for evaluating an AST node and assigns the result of evaluation to a register. An interpreter directly evaluates the AST node and simulates the compiler by storing the result in an array (called reg) and returning the index. We make use of the following structure to store the results of evaluation by an interpreter:
<script src="js/14917a901e497a38abf7.js"></script>
<p>
In 'valstruct' the field 'valtype' can take one of the following values:
<ol>
<li>EMPTY : Indicates that no value is stored in it.</li>
<li>INT : Indicates that value stored in the union constant 'value' is an integer.</li>
<li>STR : Indicates the value stored in the union constant 'value' is a string.</li>
<li>H_INDEX : Indicates that valstruct stores the (integer) index of a location in the heap.</li>
</ol>
</p>
</li>
</ul>
<p>
Follwing are the nodetypes that may appear while contructing the abstract syntax free for ExpL program:
</p>
<table class="doctable" style="text-align:left;">
<tr>
<th>Nodetype</th>
<th>Description</th>
</tr>
<tr>
<td>LEAF</td>
<td>For interger and string constants.</td>
</tr>
<tr>
<td>ID</td>
<td>For all variable literals.</td>
</tr>
<tr>
<td>PLUS</td>
<td>For arithmetic operator '+'. <br> Attributes 'ptr1' and 'ptr2' of the 'ASTNode' are set to AST of left and right operands respectively and must be of type 'int'. <br>'ptr3' is set to NULL.</td>
</tr>
<tr>
<td>MINUS</td>
<td>For arithmetic operator '-'. <br>Attributes 'ptr1' and 'ptr2' of the 'ASTNode' are set to AST of left and right operands respectively and must be of type 'int'.<br> 'ptr3' is set to NULL.</td>
</tr>
<tr>
<td>MUL</td>
<td>For arithmetic operator '*'. <br>Attributes 'ptr1' and 'ptr2' of the 'ASTNode' are set to AST of left and right operands respectively and must be of type 'int'.</td>
</tr>
<tr>
<td>DIV</td>
<td>For arithmetic operator '/'. <br>Attributes 'ptr1' and 'ptr2' of the 'ASTNode' are set to AST of left and right operands respectively and must be of type 'int'.</td>
</tr>
<tr>
<td>GT</td>
<td>For relational operator '>'. <br>Attributes 'ptr1' and 'ptr2' of the 'ASTNode' are set to AST of left and right operands respectively and must be of type 'int'.</td>
</tr>
<tr>
<td>LT</td>
<td>For relational operator '<'. <br>Attributes 'ptr1' and 'ptr2' of the 'ASTNode' are set to AST of left and right operands respectively and must be of type 'int'.</td>
</tr>
<tr>
<td>GE</td>
<td>For relational operatot '>='. <br>Attributes 'ptr1' and 'ptr2' of the 'ASTNode' are set to AST of left and right operands respectively and must be of type 'int'.</td>
</tr>
<tr>
<td>LE</td>
<td>For relational operatot '<='. <br>Attributes 'ptr1' and 'ptr2' of the 'ASTNode' are set to AST of left and right operands respectively and must be of type 'int'.</td>
</tr>
<tr>
<td>EQ</td>
<td>For relational operator '=='. <br>Attricutes 'ptr1' and 'ptr2' of the 'ASTNode' are set to AST of left and right operands respectively and both must be of same type.</td>
</tr>
<tr>
<td>NE</td>
<td>For relational operator '!='. <br>Attricutes 'ptr1' and 'ptr2' of the 'ASTNode' are set to AST of left and right operands respectively and both must be of same type.</td>
</tr>
<tr>
<td>IF</td>
<td>For the conditional contruct 'if'. <br>Attribute 'ptr1' of the 'ASTNode' is set to AST of the conditional logical expression, 'ptr2' is set to AST of list of statements that are executed when conditional expression evaluates to true and 'ptr3' is set to AST of list of statements that are to be executed when conditional expression is evalusted false.</td>
</tr>
<tr>
<td>WHILE</td>
<td>For conditional construct 'while'. <br>Attribute 'ptr1' os 'ASTNode' is set to the conditional logical expression and 'ptr2' is set to AST of list of statements under the while construct.</td>
</tr>
<tr>
<td>READ</td>
<td>For input statement 'read'. Attribute 'ptr1' is set to AST of nodetype ID, which carries the information of the variable for which we are taking the input.</td>
</tr>
<tr>
<td>WRITE</td>
<td>For output statement 'write'. Attibute 'ptr1' is set to AST of the expression, whose value is to be written to the standard output.</td>
</tr>
<tr>
<td>ASGN</td>
<td>For assignment statement (<var> = <expr>). <br>Attribute 'ptr1' is set to AST of nodetype ID or FIELD and 'ptr2' is set to AST of expression whose value will be assigned to lvalue given by 'ptr1'. </td>
</tr>
<tr>
<td>SLIST</td>
<td>To connect statements.</td>
</tr>
<tr>
<td>BODY</td>
<td>For body of a function.</td>
</tr>
<tr>
<td>RET</td>
<td>For return statement of a function.</td>
</tr>
<tr>
<td>FUNCTION</td>
<td>For function calls.</td>
</tr>
<tr>
<td>PARAM</td>
<td>For passing actual parameters during function calls.</td>
</tr>
<tr>
<td>MAIN</td>
<td>For main function.</td>
</tr>
<tr>
<td>FIELD</td>
<td>For user-defined types.</td>
</tr>
</table>
<h6>Illustration</h6>
<p>
Consider the following program
</p>
<script src="js/f0127bf97757874e7cc2.js"></script>
<p>
1. Lets construct the abstract syntax tree step by step. The AST for conditional expression <code>n==1</code> (in line 9) will be as follows:
</p>
<br>
<img src="img/data_structure_50.png" alt="" />
<br>
<p>
2. Similarly we have AST fot <code>n==0</code> (in line 9) as follows.
</p>
<br>
<img src="img/data_structure_51.png" alt="" />
<br>
<p>
3. Next consider the complete conditional expression <code>n==1 || n==0</code>.
</p>
<br>
<img src="img/data_structure_52.png" alt="" />
<br>
<p>
4.Next we will form the AST for assignment statement <code>f = 1</code> (in line 10).
</p>
<br>
<img src="img/data_structure_53.png" alt="" />
<br>
<p>
5. Next, lets consider the statement <code> f = n * factorial(n-1)</code> which consists of arthimetic expressions with operands '-','*' and an assignment statement.
</p>
<p>
AST for <code>n-1</code> is as follows.
</p>
<br>
<img src="img/data_structure_54.png" alt="" />
<br>
<p>
AST for <code>n * factorial(n-1)</code> is as follows.
</p>
<br>
<img src="img/data_structure_55.png" alt="" />
<br>
<p>
AST for <code> f = n * factorial(n-1)</code> is as below.
</p>
<br>
<img src="img/data_structure_56.png" alt="" />
<br>
<p>
6. Following is the AST for the if condition.
</p>
<br>
<img src="img/data_structure_57.png" alt="" />
<br>
<p>
7. The AST for return statement is as folows
</p>
<br>
<img src="img/data_structure_58.png" alt="" />
<br>
<p>
8. Finally the AST for the factorial function will be as follows.
</p>
<br>
<img src="img/data_structure_59.png" alt="" />
<!--<p>
The abstract syntax tree for the factorial function looks as follows:
</p>
<a href="img/data_structure_29.png"><img src="img/data_structure_29.png" alt="" /></a>
<p>
Try to contruct the abstract syntax tree for main function.
</p>-->
<!--
<p>
Continuing with the previous example,
</p>
<script src="js/089ce170e43be95bff60.js"></script>
-->
</article>
<article class="grid col-full" id="nav-execution-structures">
<h2>DATA STRUCTURES FOR EXECUTION PHASE</h2>
<p>
Before explaining the data structures used for the execution phase, it is necessary to understand the requirements and the underlying theoretical concepts in some detail.
</p>
<h4>The storage allocation Problem </h4>
<p>
This part of the documentation primarily focuses on program interpretation. However, our interpreter will be somewhat mimicing the actions of a compiler and hence the reader will be able to easily adapt what is learned here to handle the synthesis phase of compilation by going through this documentation.
</p>
<p>
An interpreter needs to "execute" the abstract syntax tree and hence the interpreter must arrange storage for run time data and subroutine invocations (function calls).
</p>
<p>
A program contains global variables as well as variables that are local to functions, both requiring memory space. Of these, global variables are the simplest to handle because during the analysis phase we know how many global variables are there in the program (all global variables are declared) and how much space needs to be allocated for each of them (why?). Thus, the storage requirements of global variables are completely determined at compile time and they can be assigned memory addresses during the analysis phase itself. Such allocation is called <b>static allocation</b>. The binding field of the global symbol table entry for a variable stores a pointer (address) to the memory allocated to the variable. The symbol table information will be used during the execution phase to find out the location in memory where the variable is stored.
</p>
<p>
[In the case of compilation, the memory addresses for each global variable in the target machine is determined during the analysis phase and are stored in the <i>binding</i> field of the symbol table.]
</p>
<p>
As a point aside, the binding field of the symbol table entry for a function is set to hold a <i>pointer to the abstract syntax tree of the function</i>. This helps the evaluation phase to locate the corresponding abstract syntax tree whenever a function call is encountered during the execution phase.
</p>
<p>
[In the case of a compiler, the the analysis phase will decide on the addresses in the <b>code area</b> of memory where the function's code is loaded. The address to which a call to the function must be directed to is stored in the binding field of the symbol table.]
</p>
<p>
Variables which are local to functions demands more complicated allocation. This is because a function may be invoked several times and <i>for each invocation, separate storage needs to be allocated for variables defined within the scope of the function</i> (i.e., local variables and arguments). [Why?] Moreover, we do not know during the analysis phase how many times a function will be invoked during the execution phase. [Why?]
</p>
<p>
To understand this, consider the factorial program below.
</p>
<script src="js/f0127bf97757874e7cc2.js"></script>
<p>
The function factorial contains an argument n. Suppose the initial value of n input by the user at run time was 5, then factorial(n) with n=5 is invoked from the main. This function invokes factorial(n) with n=4. However, we need to retain the old value of n since the orginal factorial function must resume execution after the completion of factorial(4). Thus, we cannot statically assign a fixed memory address to the variable n. Instead, for each invocation of the function, we need to create a different memory space for storing the value of n. Moreover, the initial value of n given by the user is not known at compile time. Hence cannot determine at compile time the exact storage requirement. We will have to design the compiler/interpreter to allocate memory space as is necessary during run time.
</p>
<p>
In addition to allocating storage for local variables and arguments, additional storage needs to be allocated at run time for each invocation of a function to store the return values of the call and control information like a pointer to the next instruction in the calling function (return address)].
</p>
<p>
The classical solution to handling function invocation is to maintain a <b>run time stack</b>. Whenever a function is invoked during execution, <b>an activation record</b> is created in the run time stack with sufficient space for storing local variables, arguments, return values and return address and the stack grows. Upon return from the function, the activation record is popped out of the stack and the activation record of the calling program will be in the top of the stack. Thus, at each point during execution, the activation record of the currently executing function will be on the top of the stack. Such storage allocation is called <b>stack based run time allocation</b>.
</p>
<p>
[Note: The semantics of ExpL makes stack based allocation possible. Primarily, this is possible because data stored in an activation record can be forgotten once the execution of the call is finished. There are languages like LISP which permit <a href="https://en.wikipedia.org/wiki/Higher-order_function">higher order functions</a> where a stack based run time allocation is not possible. Languages which permit stack based run time allocation for function invocations are said to follow <b>stack discipline</b>.]
</p>
<p>
Observe that for each function defined in an ExpL program, the amount of storage needed in its activation record is known during the analysis phase. [Why?] What is not known is how many activation records will have to be created in the stack as this is known only during execution time.
</p>
<p>
In addition to allocating storage for global variables and variables local to functions, ExpL supports <b>dynamic memory allocation</b> through the alloc() function. The alloc() function allows a program to request for memory space at run time. Since the amount of memory requested is not known during the analysis phase (why?), static allocation is not possible in this case. Stack allocation also is ruled out because memory allocated by alloc() inside a function is not de-allocated when the function returns. Hence, a mechanism to dynamically allocate memory on demand at run time is required.
</p>
<p>
The classical solution to this problem is to maintain an contiguous area of memory called the heap memory from which memory is allocated by alloc() on demand. Heap management algorithms like the <b>fixed size allocator algorithm</b> and the <b>buddy system algorithm</b> are explained in detail later in this documentation.
</p>
<p>
Finally, intermediate values generated during program execution needs <b>temporary storage</b>. For example, while evaluating an expression (a+b)*(c+d), the values of the sub-expressions (a+b) and (c+d) might need temporary storage. In a compiler, the <b>machine registers</b> are used for temporary storage. Our interpreter will simulate the compiler by having an array of “registers” for storing such temporary values. When a function invokes another function, the registers in current use will be pushed to the stack (activation record of the caller) so that the called function (callee) has the full set of registers free for its use. Upon return from the callee, the values pushed into the stack are restored to the registers before the caller resumes its execution.
</p>
<p>
To summarize, we have four kinds of memory allocation – static, stack, heap and register (temporary). The data structures and algorithms necessary for implementing each of these are discussed below.
</p>
<!--<p>
Compiler creates and manages a run-time environment in which a variety of issues such as allocation of storage locations for the objects named in the source program, the linkages between procedures, the mechanisms for passing parameters are taken care of. From the perspective of compiler writer, the executing target program has its own logical address space in which each program value has its location. Following is the representation of run-time memory.
</p>
<img src="img/data_structure_9.png" style="margin-left:40%"></img>
<p>
Stack and heap are dynamic, their size changes as the program executes. We will discuss these structures in detail.
</p>-->
</article>
<article class="grid col-full" id="nav-memory-model">
<h2>The memory model</h2>
<p>
Our interpreter will simulate machine memory and registers by defining three memory arrays, named <i>stack, heap and registers</i>.
</p>
<br>
<img src="img/data_structure_33.png" alt="" />
<br>
<br>
<p>
The basic unit of memory (called a <b>memory word</b>) is assumed to be able to store an integer or a string. This model is assumed because the primitive data types of ExpL are integer and string. The interpreter therefore defines the following memory structure:
</p>
<script src="js/2e982915b856ce98791b.js"></script>
<p>
The interpreter works with three arrays of memory words, to implement temporary storage (registers), the run time stack and the heap. There will be no sperarate memory array for static data. Instead, the intial part of the stack will be used for storing static data.
</p>
<script src="js/7ba4d3b4da44863b028d.js"></script>
</article>
<article class="grid col-full" id="nav-register-allocation">
<h2>Register Allocation</h2>
<p>
Register allocation is performed through two simple functions.
</p>
<p>
<ul>
<li>int get_register(): Allocates a free register from the register pool reg[16] and returns the index of the register, returns -1 if no free register is available.</li>
<li>int free_register(): Frees the last register that was allocated,returns 0 if success, returns -1 if the function is called with none of the registers being allocated.</li>
</ul>
</p>
<p>
The interpreter invokes these functions in the course of evalaution of expressions to create temporary store.
</p>
</article>
<article class="grid col-full" id="nav-static-allocation">
<h2>Static Allocation</h2>
<p>
As noted previously, global variables are allocated statically. In our interpreter, the initial portion of the stack will be used for static allocation. The rest of the stack memory region will be used for run time allocation. The amount of static storage required is known from the variable declarations.
</p>
</article>
<article class="grid col-full" id="nav-run-time-stack">
<h2>Run Time Stack Allocation</h2>
<p>
During run-time, when an ExpL function is invoked, space has to be allocated for storing
<ul>
<li>the arguments to the function,</li>
<li>return value of the function,</li>
<li>local variables declared in the function.</li>
</ul>
For this, an <b>activation record</b> is created in the stack for each function call (and the stack grows). The activation record is also used to save the state (registers in use) of the invoking function and some control information (like the return address of the calling program in the case of a compiler).
</p>
<p>
Each activation record has a base, and the <b>base pointer (BP)</b> is a variable (or a machine register in the case of a compiler) that points to the base of the current functions activation record. When one function invokes another, the base pointer value of the caller is pushed on to the stack and BP is set to point to the new activation record base. Upon return, the activation record is popped off the stack and old value of base pointer is restored. The <b>stack pointer (SP)</b> points to the top of the stack.
</p>
<p>
The <b>calling convension</b> fixes in what order arguments to a function must be pushed by the caller to the called function, the place in the activation record where the return value is expected to be written by the callee etc. The structure of the activation record explained below will clarify the calling convension.
</p>
<img src="img/data_structure_34.png" alt="" style="padding-left:30%; margin-bottom:2em"/>
<p>
When a function is invoked, a part of the activation record is set up by the caller and the rest is set up after invocation of the function. Similarly, when a function returns, the callee and the caller are responsible for removing the parts they have set up.
</p>
<p>
The following sequence of actions occur when a function A calls another function B.
</p>
<ol>
<li>A pushes its machine state (registers in use) into the stack so that the registers are free for use in B.</li>
<li>A pushes to arguments to B in the order they appear in the declaration.</li>
<li>A pushes one empty space in the stack for B to place its return value.</li>
<li>A invokes B. (In the case of a compiler, this results in generation of a CALL instruction which results in pushing the instruction pointer into the stack and transfer of control to B).</li>
</ol>
<p>
Inside B, the following space allocations take place:
</p>
<ol start="5">
<li>B saves the BP value of A to the stack and sets its own BP to the location where the BP of A is stored.</li>
<li>B allocates space for local variables (in the order in which they appear in the delcaration.</li>
</ol>
<p>This completes the activation record for B. If B later calls another function C, then it starts saving its registers, pushes arguments to C and so on.</p>
<p>When B completes execution the following sequence of actions take place:</p>
<ol>
<li>B pops out the local variables.</li>
<li>The old BP value is popped off and saved into BP.</li>
<li>B returns (in the case of a compiler, this results in generation of a RET instruction which results in setting the instruction pointer to the value saved in the stack).</li>
</ol>
<p>On re-entry, A does the following:</p>
<ol start="4">
<li>Retrieve the return value from stack and save it to a new register. This is the result of the function call.</li>
<li>Pop off the arguments.</li>
<li>Restore the saved register context.</li>
</ol>
<p>Consider the following example:</p>
<script src="js/f0127bf97757874e7cc2.js"></script>
<ol>
<li>
<p>
The global variables are allocated statically in the initial portion of the stack.
</p>
<br>
<img src="img/data_structure_39.png" alt="" /><br>
</li>
<li>
<p>
The main functions sets up stack locations for its local variables and calls the function factorial(3) after setting up a part of the callee's activation record.
</p>
<br>
<img src="img/data_structure_40.png" alt="" /><br>
</li>
<li>
<p>
Factorial(3) saves the old Base pointer and sets up locations for its local variables.
</p>
<br>
<img src="img/data_structure_41.png" alt="" /><br>
</li>
<li>
<p>
Factorial(3) calls factorial(2) and the activation record of factorial(2) is setup similar to the above steps.
</p>
<br>
<img src="img/data_structure_42.png" alt="" /><br>
</li>
<li>
<p>
Activation record for factorial(1) (called by factorial(2)) is seup similarly.
</p>
<br>
<img src="img/data_structure_43.png" alt="" /><br>
</li>
<li>
<p>
factorial(1) calculates the result and returns it by setting the value at return value location and pops off it local variables and sets back the base pointer.
</p>
<br>
<img src="img/data_structure_44.png" alt="" /><br>
</li>
<li>
<p>
Similarly, factorial(2) calculates the steps and pops off its activation record till the result value after setting back the old base pointer.
</p>
<br>
<img src="img/data_structure_45.png" alt="" /><br>
</li>
<li>
<p>
Similarly, factorial(3) also calculates the result and returns it to the main function.
</p>
<br>
<img src="img/data_structure_46.png" alt="" /><br>
</li>
<li>
<p>
Main function calculates and sets the 'result' variable.
</p>
<br>
<img src="img/data_structure_47.png" alt="" /><br>
</li>
</ol>
</article>
<article class="grid col-full" id="nav-stack">
<h2>Stack</h2>
<p>
The stack is used to store data structures called activation records that are generated during procedure calls. An <a href="#" class="imp">activation record</a> is used to store the information such as value of program counter and machine registers when a function call occurs. When control returns from the function call, the activation of the calling procedure can be restarted after restoring the relevant registers and setting program counter to the point immediately after the call. Also, data of objects whose lifetime are contained in that of an activation can be allocated on the stack along with other information associated with activation.
</p>
<h6>Structure</h6>
<p>
So, for the implementation of the interpreter, we create a stack which is an array of memstruct. Memstruct has the following structure.<br>
<b>NOTE</b> : for compiler, the stack structure and functions supported functions depends and is taken care of by the target machine.
</p>
<script src="js/29434fa8b266749088cb.js"></script>
<p>
The type field in memstruct can take the following values
</p>
<ol>
<li>EMPTY : Indicates no value is stored in it.</li>
<li>INT : Indicates that it stores an integer value.</li>
<li>STR : Indicates that it stores a string value.</li>
<li>H_INDEX : Indicates that valstruct stores the (integer) index of a location in the heap.</li>
<li>SIZE : Indicates that this memstruct is the first index of the allocated block for a dynamically allocated variable, and it stores the size of the block allocated for the variable.</li>
</ol>
<ol>
</ol>
<h6>Associated methods</h6>
<ul>
<li>void push(struct valstruct *v) : pushes the values in valstruct to stack accordingly.</li>
<li>struct valstruct* pop() : pops a value on top of the stack as a valstruct.</li>
<li>void load(struct memstruct *m, struct valstruct *v) : loads the values in stack location pointed by m to the value structure v</li>
<li>void store(struct memstruct *m,struct valstruct *v) : stores the values in value structure v to the stack location pointed by m.</li>
</ul>
<p>
NOTE : valstruct and memstruct structures have been used here to keep the fine line between a value object and a object in the memory.
</p>
</article>
<article class="grid col-full" id="nav-heap">
<h2>Heap Allocation</h2>
<p>
A storage allocation decision can be static or dynamic. A decision is dynamic if it can be decided only while the program executes. In simple terms, consider the previous example, the size of the linkedlist marks is not known at the compile time, its size is only known at the run-time when we read in the count of subjects.
</p>
<p>
In interpreter, for heap we will be using an memstruct array of size 1024.
</p>
<h6>Associated methods</h6>
<ul>
<li>void intialise() : To initialise the heap with required initial values.</li>
<li>int alloc(int size) : allocates continuos locations of given size and returns the starting address of allocated block.</li>
<li>int free(int addr) : frees the memory block starting with the given addr are erasing the data in that block and returns a value indicating the success and failure of free operation.</li>
</ul>
<h6>Allocation algorithms</h6>
<p>
The two types of allocation-deallocation algorithms we will discuss here for heap management are fixed memory and buddy memory management.
</p>
<h6>Fixed Memory Allocation</h6>
<p>
In this algorithm, the chunk size allocated is fixed. Lets call the fixed size as HB_SIZE, say 8. The heap is considered here as a list of blocks of HB_SIZE.
</p>
<p>
The first block in the list is reserved. Initially, the first index of reserved block stores the index of first free block. The first index of every free block stores the index of next available free block. The last block stores -1 in the first index. This is how it looks initially(after the call to initialise function).
</p>
<img src="img/data_structure_10.png" alt="Figure : Intial Heap diagram" />
<p>
Following is the <b>allocation algorithm.</b>
</p>
<ol>
<li>First index of reserved block is checked, let the value be v.</li>
<li>If v is -1, return -1 indicating no free blocks are available.</li>
<li>Else, allocate the free block at v, after copying the next free block index stored at v to the reserved block.Return v.</li>
</ol>
<p>
Following is the pseudo code of the algorithm.
</p>
<script src="js/60abadc1a9b7554fba73.js"></script>
<p>
Following is the <b>deallocation algorithm.</b>
</p>
<ol>
<li>The arguement passed : starting address of the block(say s) to be deallocated</li>
<li>The block s is cleared by setting all memstructs in the block to type EMPTY.</li>
<li>The value in the first index of reserved block is copied to first index of block s.</li>
<li>The first index of reserved block is set with starting address of block s.</li>
</ol>
<h6>Illustration</h6>
<p>
This section shows how the heap looks after each step of allocation or free. This is for the better understanding of the algorithms.
</p>
<ul>
<li>
<p>
x = alloc();
</p>
<img src="img/data_structure_11.png" alt="" />
<p>
x is a memstruct in the run-time stack of type MEMSTRUCT_BIND with intval 8.
</p>
</li>
<li>
<p>
y = alloc();
</p>
<img src="img/data_structure_12.png" alt="" />
</li>
<li>
<p>
z = alloc();
</p>
<img src="img/data_structure_13.png" alt="" />
</li>
<li>
<p>
dealloc(x);
</p>
<img src="img/data_structure_14.png" alt="" />
</li>
<li>
<p>
dealloc(z);
</p>
<img src="img/data_structure_15.png" alt="" />
</li>
<li>
<p>
z = alloc();
</p>
<img src="img/data_structure_16.png" alt="" />
</li>
</ul>
<h6>Buddy Memory Allocation</h6>
<p>
In this technique, memory is divided into partitions to try to satisfy a memory request as suitably as possible. This technique makes use of splitting memory into halves to give a best-fit.
</p>
<p>
Every memory block in this technique has an order, a number ranging from 0 to a specified upper limit. The size of block of order n is 2<sup>n</sup>. So the blocks are exacly twice the size of blocks of one order lower. Power-of-two block sizes makes address computation simple, because all buddies are aligned on memory address boundaries that are powers of two. When a larger block is split, it is divided into two smaller blocks, and each smaller block becomes a unique <b>buddy</b> to the other. A split block can only be merged with its unique buddy block, which then reforms the larger block they were split from.
</p>
<p>
Starting off, the size of the smallest possible block is determined, i.e. the smallest memory block that can be allocated. The smallest block size is then taken as the size of an order-0 block, so that all higher orders are expressed as power-of-two multiples of this size. In our implementation, we consider the smallest memory block size to be 8. So, the memory block sizes will be 8, 16, 32, 64, and so on. In our implementation, we take the heap of size 1024.
</p>
<p>
In our implementation, we have a heap of size 1024. The smallest block size possible in the heap is 8 (order 0). The highest block size of 2<sup>n</sup> that is free is 1024.We maintain a free list for all possible block sizes. So we have freelists for sizes 8,16,32,64,128,256,512 and 1024, i.e, we maintain eight freelists.
<ul>
<li>We have only one block of size 1024 and so the size of freelist for 1024 is 1(2<sup>0</sup>).</li>
<li>In the 1024 sized heap, we have two blocks of size 512. Note that, both blocks cannot be free at the same time. If both blocks are free, they will be merged to a free block of size 1024(whose information will be maintained in the freelist for blocks of 1024 size). So at a time, maximum number of blocks that are free of size 512 is 1 ( 2<sup>0</sup>).</li>
<li>Similarly in case of blocks of size 256, 1024 sized heap has 4 blocks of size 256 (say a,b,c and d in their respective order).a and b are buddies of each other, of which both cannot be free at a time due to merging, so only one of them can be free. Similarly in case of c and d, only one of them can be free. 1 + 1 , 2 ( 2<sup>1</sup>) is the maximum size of free list for blocks of 256.</li>
<li>Similarly, there are 8 blocks of 128 in 1024 (a,b,c,d,e,f,g and h). (a,b)(c,d)(e,f)(g,h) are buddy pairs and only one of each pair can be free. So the maximum size of freelist for blocks of 128 is 4 ( 2<sup>2</sup>).</li>
<li>Similarly, the maximum size of freelist for blocks of sizes 64,32,16 and 8 are 8 ( 2<sup>3</sup>),16( 2<sup>4</sup>),32( 2<sup>5</sup>) and 64( 2<sup>6</sup>) respectively.</li>
</ul>
So, the size of the complete freelist is 2<sup>0</sup> + 2<sup>0</sup> + 2<sup>1</sup> + 2<sup>2</sup> + 2<sup>3</sup> + 2<sup>4</sup> + 2<sup>5</sup> +2<sup>6</sup> = 128.
</p>
<p>
We will maintain the freelist inside the heap, So initially we won't have the complete heap of 1024 free. So we need not require a freelist for size 1024. We will store the complete freelist in a 128 sized block. Therefore, initially we have the first 128 block(0-127) of the heap reserved for freelist maintainence. Then we have a 128 sized free block(128-255), then a 256 block(256-511) and then a free block of 512 size(512-1023). Following is the diagrammatic representation of the heap initial status.
</p>
<img src="img/data_structure_17.png" alt="" />
<p>
The free-list in the heap has to be initialised as above. Also, the first index of each allocated block through alloc function will store the size of allocated block. This is to figure out the size that has been allocated when the dealloc function is called for a variable, which provides only the starting address of the block that has been allocated.
</p>
<p>
Following is the <b>allocation algorithm</b> : (argument : Request for a block of size 'A')
</p>
<ul>
<li>Look for a memory slot of suitable size(i.e, the <b>minimal 2<sup>k</sup> block</b> that is larger or equal to that of the requested memory A + 1, a plus one as first index is used to store the size of block allocated), lets call the ceiled size as 'B'.
<ol style="list-style-type:upper-roman">
<li>If found, the starting index of the allocated block is returned to the program after removing it from the freelist.</li>
<li>If not, it tries to make a suitable memory slot by following the below steps
<ol style="list-style-type:lower-alpha">
<li>Split a the <b>next larger suitable free memory slot</b> into half.(Remove the next larger suitable free memory slot from it free list and add both the halves to the corresponding freelist).(Note : of there is no larger free memory slot - return -1 indicating that no free space is available).</li>
<li>If the required size 'B' is reached, one of the halves is allocated to the program.</li>
<li>Else go to the step a and repeat it until the memory slot of required size 'B' is found.</li>
</ol>
</li>
</ol>
</li>
</ul>
<p>
Following is the <b>deallocation algorithm</b> (arguement : the starting address of the allocated block)
</p>
<ol>
<li>Get the size, say 's' of the block from the first index of the block. Free the complete block with the help of size obtained by setting all the memstruct type to MEMSTRUCT_EMPTY.</li>
<li>Check if the buddy of the block is free by checking the whether the buddy's starting address is present in the free list for blocks of size 's' .</li>
<li>If the buddy is not free, add the current freed block to its free list.</li>
<li>If the buddy is free, remove the buddy from the freelist and combine the two, and go back to step 2 to check for the buddy of merged block. Repeat this process until the upper limit is reached or buddy is not free.</li>
</ol>
<p>
The psuedo code for alloc and dealloc functions is as follows :
</p>
<script src="js/459816dfb4d095778c37.js"></script>
<h6>Illustration</h6>
<p>
For a better understanding purpose, we will have a simple illustration of how heap memory looks like through a set of some allocations and deallocations.
</p>
<p>
For illustration, we will have 64-sized heap and smallest block size as 8. So we free lists for sizes 8,16 and 32 of lengths 4 ,2 and 1. So we will use a 8-size block to store the free-list.
</p>
<ol>
<li>
<p>
The heap looks initially as follows.
</p>
<img src="img/data_structure_18.png" alt="" />
</li>
<li>
<p>
Request for memory of size 5. Lets call this request as A. The nearest 2^k value for 5 is 8. We search for a 8 sized free block. We have one such! Allocate it!
</p>
<img src="img/data_structure_19.png" alt="" />
<br/>
</li>
<li>
<p>
Next we will have a reuqest B of size 14.
</p>
<img src="img/data_structure_20.png" alt="" />
<br/>
</li>
<li>
<p>
Now we have a request C of size 7.
</p>
<img src="img/data_structure_21.png" alt="" />
<br/>
<img src="img/data_structure_22.png" alt="" />
<br/>
<img src="img/data_structure_23.png" alt="" />
<br/>
</li>
<li>
<p>
Now, C releases its memory.
</p>
<img src="img/data_structure_24.png" alt="" />
<br/>
<img src="img/data_structure_25.png" alt="" />
<br/>
<img src="img/data_structure_26.png" alt="" />
<br/>
</li>
</ol>
</article>
</div>
</section>
</div>
</div>
<footer class="center part clearfix">
<ul class="grid col-one-third social">
<li><a href="http://github.com/silcnitc">Github</a></li>
<li> <a rel="license" href="http://creativecommons.org/licenses/by-nc/4.0/">
<img alt="Creative Commons License" style="border-width:0" src="img/creativecommons.png" /></a></li>
</ul>
<div class="grid col-one-third" style="color:black;">
</div>
<nav class="grid col-one-third ">
<ul >
<li><a href="index.html">Home</a></li>
<li><a href="about.html">About</a></li>
<!-- <li><a href="uc.html">Contact</a></li> -->
</ul>
</nav>
<br>
</footer>
<script>window.jQuery || document.write('<script src="js/jquery-1.7.2.min.js"><\/script>')</script>
<script src="js/scripts.js"></script>
<script src="js/inject.js"></script>
</html>