-
Notifications
You must be signed in to change notification settings - Fork 14
/
Copy pathdata-structures.html
168 lines (161 loc) · 11.3 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
<!Doctype html>
<html lang="en">
<head>
<title>Compile Time 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">
<script src="js/jquery-1.12.1.min.js" charset="utf-8"></script>
<script src="js/bootstrap.min.js" charset="utf-8"></script>
<script src="js/sticky_sidebar.js" charset="utf-8"></script>
</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>
<body>
<div class="Services-page main grid-wrap">
<header class="grid col-full">
<hr/>
<p class="fleft">Compile Time Data Structures</p>
<br>
<br>
</header>
<aside class="grid col-one-quarter mq2-col-full sticky_sidebar">
<menu>
<ul>
<li><a class="sec" href="#nav-introduction">Introduction</a></li>
<li><a class="sec" href="#nav-analysis-structures">Data Structures</a></li>
</ul>
</menu>
<!-- <a class="button" href="">Download as PDF</a> -->
</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 of an ExpL program involves two phases. In the first phase (called the <b>analysis phase</b>), the source ExpL program is analyzed (<i>lexical, syntax and semantic</i> analysis are completed in this phase) and if the program is free of syntax and semantic errors, an <i>intermediate representation</i> of the source program called the <b>abstract syntax tree</b> is generated.
</p>
<p>
This is followed by a second phase, the second phase (called the <b>synthesis phase</b>) recursively traverses the abstract syntax tree and generates target code.
</p>
<p>
[<b>Note</b> : In the case of an<i> interpreter</i>, the second phase (called the execution phase) involves direct execution of the program by recursive evaluation of the abstract syntax tree.]
</p>
<p>
[<b>Note</b>: the abstract syntax tree representation is only one among several intermediate representations used in practical compilers. “Lower level” intermediete representations like <i>three address code</i> 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>
There are four basic data structures that are maintained during the analysis phase. These are the following:
<ol>
<li>The <b>Type table</b> is used to store information regarding the primitive and user-defined types in the program.</li>
<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 arguments of the function. </li>
<li>Finally, the <b>abstract syntax tree</b> is constructed as the outcome of the analysis phase.</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.
As a very simple example, consider the three program statements:<br>
a = b+c;<br>
d = a-b;<br>
c = a+d;<br>
A syntax tree representation for the three statements above would look as below: <br>
</p>
<p> <img src="img/symboltable.png" alt="" /> </p>
<sub>
Note: The memory addresses assigned to each variable in the figure above (100-103) has been chosen
arbitrary. The Application Binary Interface specifies the valid range of addresses that a compiler
can allocate for variables. For instance, the ExpOS <a href="abi.html#nav-virtual-address-space-model">ABI</a> requires that addresses must be in the range 4096 to 5119.
</sub>
<p>
Whenever a variable occurs in the syntax tree representation, it is convenient to maintain a pointer to the symbol table entry of the variable as shown in the figure. Note that since there are multiple symbol tables (global and local), the reference maintained for each variable must be to the right symbol table containing the variable entry.
</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>Analysis Phase Data Structures </h2>
</article>
<article class="grid col-one-half mq3-col-full">
<div class="sepmini"></div>
<h4>TYPETABLE</h4>
<div class="sepmini"></div>
<p>The Type Table stores all the necessary information regarding the various user defined types in the source program. The compiler creates .....</p>
<a href="data_structures/type-table.html" target="_blank" class="arrow fright">Read more</a>
</article>
<article class="grid col-one-half mq3-col-full">
<div class="sepmini"></div>
<h4>GLOBAL SYMBOL TABLE</h4>
<div class="sepmini"></div>
<p>Symbol tables are used to store information pertaining to the variables and functions in a program. The global symbol table stores information pertaining to....</p>
<a href="data_structures/global-symbol-table.html" target="_blank" class="arrow fright">Read more</a>
</article>
<article class="grid col-one-half mq3-col-full">
<div class="sepmini"></div>
<h4>LOCAL SYMBOL TABLE</h4>
<div class="sepmini"></div>
<p>In addition to the global symbol table, the ExpL compiler maintains a separate local symbol table for each function for storing information regarding ....</p>
<a href="data_structures/local-symbol-table.html" target="_blank" class="arrow fright">Read more</a>
</article>
<article class="grid col-one-half mq3-col-full">
<div class="sepmini"></div>
<h4>ABSTRACT SYNTAX TREE</h4>
<div class="sepmini"></div>
<p>The machine independent front-end phase of a compiler constructs an intermediate representation of the source program called the Abstract Syntax Tree (AST). An interpreter will evaluate ....</p>
<a href="data_structures/abstract-syntax-tree.html" target="_blank" class="arrow fright">Read more</a>
</article>
<!-- <article class="grid col-one-half mq3-col-full">
<div class="sepmini"></div>
<h4>CLASS TABLE</h4>
<div class="sepmini"></div>
<p>The Class Table carries information about members and methods of the class in Object oriented extension of ExpL....</p>
<a href="data_structures/class-table.html" target="_blank" class="arrow fright">Read more</a>
</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;">
<p style="font-weight: bold;">Contributed By : <a href="https://www.linkedin.com/in/suryaharshanunnaguppala">Nunnaguppala Surya Harsha</a>, <br>        <a href="https://in.linkedin.com/in/vishnupriyamatha">Vishnu Priya Matha</a>
</p>
</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>
</body>
</html>