/
expl.html
486 lines (450 loc) · 34.2 KB
/
expl.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
<!Doctype html>
<html lang="en">
<head>
<title>ExpL Specification</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="css/style.css"> -->
<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>
<div class="Services-page main grid-wrap">
<header class="grid col-full">
<hr/>
<p class="fleft">ExpL Specification</p>
<br>
<br>
<a class="button" href="pdfs/expl.pdf">Download as PDF</a>
</header>
<aside class="grid col-one-quarter mq2-col-full sticky_sidebar">
<menu>
<ul>
<li><a class="sec" href="#nav-intro">Introduction</a></li>
<li><a class="sec" href="#nav-data-types">Supported data types</a></li>
<li><a class="sec" href="#nav-general-program-structure">General Program Structure</a></li>
<li><a class="sec" href="#nav-stmts-and-exprs">Statements and Expressions</a></li>
<li><a class="sec" href="#nav-dynamic-memory-allocation">Dynamic Memory Allocation</a></li>
<li><a class="sec" href="#nav-fun-par-passing">Parameter passing</a></li>
<li><a class="sec" href="#nav-sample-programs">Sample Programs</a></li>
<li><a class="sec" href="#nav-appendix">Appendix</a></li>
</ul>
</menu>
</aside>
<body>
<section class="grid col-three-quarters mq2-col-full">
<div class="grid-wrap">
<article class="grid col-full" id="nav-intro">
<h2>Introduction</h2>
<p>
ExpL (Experimental language) is the language for which we will build a compiler in this course. This document provides an informal specification for the language.
</p>
</article>
<article class="grid col-full" id="nav-data-types">
<h2>Supported Data Types</h2>
<h4>Primitive data types</h4>
<p><b>Integer</b> : An integer type variable is declared using the keyword <b>int</b>. <i>Example</i> : </p>
<pre >
int a, b, c; /* Declares variables a, b, c of type integer */
</pre>
<p><b>String</b> : A string is a sequence of alphanumeric characters. A string type variable is declared using the keyword <b>str</b>. <i>Example</i> : </p>
<pre>
str mystring; /* Declares a variable mystring of type string. */
</pre>
<p><b>Boolean</b> : ExpL does not permit boolean variables. But logical expressions like (a < b) or (a==b) and (a< 5) are supported and are considered to be of type boolean. </p>
<h4>Composite data types</h4>
<p><b>Arrays</b></p>
<p style="text-indent: 3em;">Arrays can be of <b>integer</b> or <b>string</b> types only. Only single-dimensional arrays are allowed. Arrays are <a href="https://en.wikipedia.org/wiki/Static_variable" target="_blank">statically allocated</a>. </p>
<p><i>Example</i> :</p>
<pre>
int a[10]; /* array a indexed a[0],a[1],..a[9], can store 10 integers*/
str stringlist[10]; /* stringlist is an array of 10 strings */
</pre>
<p id="nav-user-defined-types"><b>User-defined types</b></p> <p style="text-indent: 3em;">ExpL allows user defined data types. The (member) <b>fields</b> of a user defined type may be of type a) integer, b) string, c) a previously defined user defined type or d) the type that is currently being defined.</p>
<p><i>Note</i> : ExpL specifies that the <b>store</b> for variables of user defined types shall be <b>dynamically allocated</b>. Hence the programmer has to call the library function <i>alloc()</i> to allocate memory for variables of user defined types. <b> User defined types take default value NULL unless allocated or assigned otherwise.</b> Store allocated for a variable of a user defined type is de-allocated using the <i>free()</i> library function.</p>
<p><i>Example</i> : A user defined type, mytype is defined as:</p>
<pre>
mytype
{
int a;
str b;
}
</pre>
<p>a variable of type mytype is declared as:</p>
<pre>
mytype var1, var2;
</pre>
<p>Storage for the variable is allocated as:</p>
<pre>
var = alloc(); /* Note: Access without allocation can lead to run time errors */
</pre>
<p>Its fields may be accessed as:</p>
<pre>
var.a = 10; /* the “.” symbol is used to access member fields */
</pre>
<p>The memory allocated may be freed as:</p>
<pre>
retval = free(var);
</pre>
<p><i>Note</i> : The ExpL compiler may internally represent var like a pointer variable. The library function alloc may be designed so as to allocate memory and return a pointer to the allocated memory. The returned pointer is stored in var. (Library functions are explained in detail later on.) </p>
</article>
<article class="grid col-full" id="nav-general-program-structure">
<h2>General Program Structure</h2>
<p>
An ExpL program consists of the following sections:
</p>
<ul>
<li>Type Definitions - Optional (for user defined types)</li>
<li>Global Declarations - for global variables, arrays and functions </li>
<li> Function Definitions and the main Function Definition</li>.
</ul>
<p>
The following subsections explain each program section.
</p>
<h4>Type Definitions</h4>
<p>
All user-defined types in a program must be defined in the type definition section. The Type Definition section starts with the keyword <b>type</b> and ends with the keyword <b>endtype.</b>
</p>
<i>Example</i>
<script src="js/2db3126a41e423348793b76e85e7121e.js"></script>
<h4>Global Declarations</h4>
<p>
The global declaration part of an ExpL program begins with the keyword <b>decl</b> and ends with the keyword <b>enddecl</b>. All global variables, arrays and functions in a program must be declared in this section.
</p>
<p>
Global variables may be of type integer, string, a user defined type, an integer array, a string array. The <b>variables declared globally must be allocated statically</b> by the compiler. Global variables are visible throughout the program <b>unless suppressed</b> by a redeclaration within the scope of some function. Array type variables can be declared only globally. Only single dimensional arrays are allowed. Variables <b>cannot be assigned values during the declaration phase.</b>
</p>
<p>
For every function except the special <b>main</b> function defined in an ExpL program, there must be a declaration. A function declaration should specify the name of the function, the name and type of each of its arguments and the return type of the function. A function can have integer/string/user defined type arguments. The return type of a function also can be integer/string/user-defined type. ExpL enforces <b>call-by-value</b> semantics for integer and string parameters and <b>call-by-reference</b> for user-defined types. (A variable of a user defined type typically stores a reference to its store.) <b>Arrays cannot be passed as arguments.</b> If a global variable name appears as an argument of a function, then within the scope of the function, the new declaration will be valid and the global declaration is suppressed. Different functions may have arguments of the same name. However, the same name cannot be given to two or more arguments in a function. The general form of declarations is as follows:
</p>
<pre>
type VarName1, VarName2 ; /* variable declarations */
rettype FunctionName (ParameterList); /* A function declaration */
type VarName[ArraySize]; /* An array declaration */
</pre>
<p>
<i>Note</i> : Declarations for variables/functions of the same type can be combined as shown in the following example.
</p>
<p>
<i>Example : </i>
</p>
<pre>
decl /* Please note the use of "," and ";" */
int x,y,a[10],b[20]; /* x,y are integers, a,b are integer arrays */
str t, q[10], f3(str x); /*variable, array and a functions declared together*/
mytype m, fun(mytype t); /* myptype must be a user defined type */
/* The argument and the return value of fun are references to mytype */
enddecl
</pre>
<p>
Declaring functions at the beginning avoids the <a href = "https://en.wikipedia.org/wiki/Forward_declaration" target="_blank">forward reference</a> problem and facilitates single pass compilation. If a variable/function is declared multiple times, a compilation error should result.
</p>
<h4>Function Definitions and the Main Function</h4>
<p>
All globally declared variables are visible inside a function, unless suppressed by a re-declaration within the function. Variables declared inside a function are invisible outside. The general form of a function definition is given below:
</p>
<pre>
< Type > FunctionName(ArgumentList)
{
Local Declarations
Function Body
}
</pre>
<p>
The names and types of the arguments and return value of each function definition should match exactly (<i>name equivalence</i>) with the corresponding declaration. Every declared function must have exactly one definition. The compiler should report error otherwise.
</p>
<p>
The syntax of local declarations and definitions are similar to those of global declarations except that arrays and functions cannot be declared inside a function. Local variables are visible only within the scope of the function where they are declared. The scope of a parameter is limited to the function. Static scope rules apply.
A function can have a user defined type as its return type. Similarly, parameters to a function can be of user defined types.
</p>
<p>
The <b>main()</b> function, by specification, must be a <b>zero argument</b> function of <b>return type integer</b>. It must be defined immediately after declaration section, before all other functions are defined. Program execution begins from the body of the main function. The main function must not be declared. The definition part of main should be given in the same format as any other function.
</p>
<p>
The Body of a function is a collection of statements embedded within the keywords <b>begin and end</b>.
</p>
<p>
Example : The following is an example for a simple function definition.
</p>
<pre>
int fun(int a,int b)
{
decl
int c,d;
enddecl
begin
c = a + b;
d = a - b;
write(c);
write(d);
return c;
end
}
</pre>
<p>
Local Variables and parameters should be allocated space in the <a href="https://en.wikipedia.org/wiki/Call_stack" target="_blank"> run-time stack </a> of the function. The language <b>supports recursion</b>.
</p>
<p>
Each statement should end with a ‘;’ which is called the <b>statement terminator</b>.
</p>
<p>
There are seven types of statements in ExpL. They are:
<ol>
<li>Assignment Statement</li>
<li>Conditional Statement</li>
<li>Iterative statement</li>
<li>Return statement</li>
<li>Input/Output statements</li>
<li>Break statement</li>
<li>Continue statement</li>
</ol>
</p>
<p>
The next section discusses statements and expressions in ExpL.
</p>
</article>
<article class="grid col-full" id="nav-stmts-and-exprs">
<h2>Statements and Expressions</h2>
<p>Before taking up statements, we should look at the different kinds of <b>constants</b> and <b>expressions</b> in the language. ExpL has four kinds of expressions, a) <b>Arithmetic</b> expressions, b) <b>String </b> expressions, c) <b>Logical</b> expressions and d) Expressions that evaluate to <b>user defined types</b>. </p>
<h3 id="nav-constant">Constants</h3>
<p>Any numerical value (Example: 234) is an <i>integer constant</i>. A quoted string (Example: “hello”) is a <i>string constant</i>. ExpL allows a special constant NULL whose type is void. It is assumed that string constants contain only alphanumeric characters (and no special characters).
</p>
<h3>Arithmetic and String Expressions</h3>
<p>
Any integer(or string) constant/variable is a valid arithmetic (or string) expression, provided the scope rules are not violated. ExpL treats a function returning integer (or string) as an integer expression (or string expression) and the value of a function is its return value.
</p>
<p>
ExpL provides five <b>arithmetic operators</b>, viz., +, -, *, / (Integer Division) and % (Modulo operator) through which arithmetic expressions may be combined. Expression syntax and semantics are similar to standard practice in programming languages and normal rules of precedence, associativity and paranthesization apply. ExpL is strongly typed and <b>any type mismatch or scope violation must be reported at compile time</b>.
</p>
<p>
<i>Examples</i> : <i> 5, a[a[5+x]]+x , (f2() + b[x] + 5), sum + listObject.data , a[listObject.data] + f2(listObject) * 8</i> etc. are arithmetic expressions, provided type and scope rules are not violated. Note that the function f2() must have return type int for the expression to be valid.
</p>
<h3>Logical Expressions</h3>
<p>Logical expressions may be formed by combining arithmetic expressions using <b>relational operators</b>. The relational operators supported by ExpL are <, >, <=, >=, ==, and !=. Again <b>standard syntax and semantic conventions apply</b>. Logical expressions may be combined using logical operators <b>and</b>, <b>or</b> and <b>not</b>.</p>
<p>
The relational operators <, >, <=, >=, ==, and != can be used between two variables of type string, two string constants or a string constant and a variable of type string. Comparison will be performed for <b>lexicographic ordering</b>.
</p>
<p><i><b>Variables of user defined types can only be checked for equality/inequality using the ==/!= operator. </i></b></p>
<p><i>Example</i> : <i>((x==y)==a[3])</i> is <b>not valid</b> ExpL expression because (x==y) is a logical expression, while a[3] must be a variable of type integer/string. The "==" operator can be applied only between expressions of the same type. </p>
<p> <i>(“hello”==a and "hello" < a)</i> are a valid logical expressions provided, a is a variable of string type. (p==q) is a valid logical expression provided p and q are variables of the same type. </p>
<p> <i>SetOne.name == "a", SetOne.total >= SetTwo.total</i> are valid only if SetOne is a user defined type with a field 'name' of type string and another field 'total' of type integer.</p>
<h3>Expressions of user defined types</h3>
<p> Any variable of a user defined type or invocation of a function whose return type is a user defined type is considered as an expression of the corresponding user defined type.
</p>
<h3>Assignment Statement</h3>
<p>The general syntax of the assignment statement is :</p>
<pre>
Lvalue = Rvalue;
</pre>
<p>The possible Lvalues are variables or indexed array variables. If the Lvalue has type integer (or string) , the Rvalue must be an arithmetic (or string) expression. If the Lvalue is a user defined variable, then the Rvalue must either be an expression of the same type, or the special constant NULL, or an invocation of the function <i>alloc()</i> (to be explained later).</p>
<p><i>Example</i> : <i>q[3]= “hello” ; t= “world” ;</i> are both valid assignments to string variables provided q is declared as an array of type string and t is declared as a variable of type string. <i>x=y</i>; is valid if x and y are of the same type and scope rules are not violated. </p>
<p>In an assignment <i>x=y</i> where x and y are of a primitive type (integer or string), the value inside the location indicated by y is copied into the location indicated by x. On the other hand, if x and y are variables of a user defined type, the assignment only makes both x and y refer to the same memory object. This is because a variable of a user defined type stores a reference to its store allocated using alloc(). </p>
<h3>Conditional Statement</h3>
<p>The ExpL conditional statement has the following syntax:</p>
<pre>
if < Logical Expression > then
Statements
else
Statements
endif;
</pre>
<p>The <b>else</b> part is optional. The statements inside an <b>if</b>-block may be conditional, iterative, assignment, input/output, break or continue statements, but <b>not</b> the return statement.</p>
<h3>Iterative Statement</h3>
<p>The eXpL iterative statement has the following syntax:</p>
<pre>
while < Logical Expression > do
Statements
endwhile;
</pre>
<p>Standard conventions apply in this case too. The statements inside a <b>while</b>-block may be conditional, iterative, assignment, input/output, break or continue statements, but <b>not</b> the return statement.</p>
<h3>Return Statement</h3>
<p>The body of each function (including main) should have <b>exactly one</b> return statement and it should be the <b>last statement</b> in the body. The syntax is:</p>
<pre>
return < Expression* > ; /* The type of the expression should match with the return type of the function*/
Note* : As an exception to the rule above, the expression returned by a function whose return type is a user defined type can be the constant NULL.
</pre>
<p>If the return type of the function does not match the type of the expression/variable returned, a compilation error should occur. The return type of a function can be of type <b>int</b> , <b>str</b> or <b>user-defined type</b>. The <b>return type of main is integer</b> by specification</p>.
<h3>Input/Output statements</h3>
<p>
Using read statement, we can <b>read a string or an integer into a variable</b> of type string or integer respectively from the standard input. The syntax of the input statement is as follows :
<pre>
read( < variable > );
</pre>
</p>
<p>
Using the write statement, we can <b>write</b> the value of an <b>integer or string type variable</b> or <b>the value of an arithmetic expression</b> to the standard output. The output statement is as follows :
<pre>
write( < expr > );
</pre>
</p>
<h3>Break and Continue Statements</h3>
<p>A <b>break;</b> statement inside an iterative block tranfers control to the end of the block. A <b>continue;</b> inside a conditional/iterative block transfers control to the beginning of the block. These statements do nothing if not inside any conditional/iterative statement. </p>
<p>The next section briefly discusses the library functions for dynamic memory allocation.</p>
<h3>Breakpoint Statement</h3>
<p>This statement results in the ExpL compiler setting a break point in the program. This feature is useful for debugging.
<pre>
breakpoint;
</pre>
</p>
</article>
<article class="grid col-full" id="nav-dynamic-memory-allocation">
<h2>Dynamic memory allocation</h2>
<p>The library functions <b>initialize()</b>, <b>alloc()</b> and <b>free()</b> are used as follows: </p>
<pre>
intialize(); /* To Intialise the heap. */
t = alloc(); /* Allocates contiguous locations in the heap, t must be a user defined variable */
retval = free(t); /* Free the allocated block , t must be a user defined variable */
</pre>
<p>Intialize() must be invoked before any allocation is made and it resets the heap to default values. A call to alloc() allocates contiguous memory locations in the <b>heap memory</b> (memory reserved for dynamic memory allocation) and returns the address of the starting location. The Expl compiler sets the variable (of a user defined type) on the left of the assignment to store this memory address. A call to free() deallocates contiguous memory locations in the heap memory that is referenced by the user defined type variable. The function free() returns NULL on successful deallocation. Otherwise, the value of t is unchanged by a call to free(). All unallocated user defined variables are set to the predefined constant NULL.</p>
</article>
<article class="grid col-full" id="nav-fun-par-passing">
<h2>Parameter passing</h2>
<p>
Functions can take any number of arguments and must return a single value. The arguments and return values may be of integer, string or user defined types.
</p>
<p>
Arguments to functions are passed by value. This means that changes to made to the values of an argument inside a function will not be visible outside the function.
</p>
<p>
However, if a variable is of a user defined type, after allocation using the Alloc() function, the variable stores the memory address of the actual data in heap memory where the data associated with the variable is stored. ExpL specification allows the data to be modified using the variable. If the data stored variable is changed with in a function, the change will be visible globally. This is because heap memory is globally visible.
</p>
<p>
The scope rules are illustrated by the following example.
</p>
<script src="js/5815668e4a64869ec651f87981b483d5.js"></script>
</article>
<!-- <article class="grid col-full" id="nav-sample-programs">
<h2>Sample Programs</h2>
<h6>An Example ExpL Program without user defined types</h6>
<p>The following program calculates and prints out the factorial of the first n numbers, value of n read from standard input.</p>
<script src="js/ac11acaaf3a82ba24efe.js"></script>
<h6>Sample ExpL program using User Defined types</h6>
<p>The following program reads elements into a linked list and prints them.</p>
<script src="js/2d790a0323028fc9c5ed.js"></script>
</article> -->
<article class="grid col-full" id="nav-appendix">
<h2>Appendix</h2>
<h4>Keywords</h4>
<p>The following are the reserved keywords in ExpL and it cannot be used as identifiers.</p>
<table style="width:80%;text-align:center;">
<tbody>
<tr>
<td>read</td>
<td>write</td>
<td>if</td>
<td>then</td>
<td>else</td>
<td>begin</td>
<td>initialize</td>
</tr>
<tr>
<td>endif</td>
<td>do</td>
<td>endwhile</td>
<td>break</td>
<td>while</td>
<td>end</td>
</tr>
<tr>
<td>int</td>
<td>str</td>
<td>return</td>
<td>decl</td>
<td>enddecl</td>
<td>alloc</td>
</tr>
<tr>
<td>type</td>
<td>endtype</td>
<td>NULL</td>
<td>continue</td>
<td>main</td>
<td>free</td>
</tr>
</tbody>
</table>
<br/>
<h4>Operators and Delimiters</h4>
<p>The following are the operators and delimiters in ExpL</p>
<table style="width:80%;text-align:center;">
<tbody>
<tr>
<td>></td>
<td><</td>
<td>>=</td>
<td><=</td>
<td>!=</td>
<td>==</td>
<td>(</td>
<td>)</td>
</tr>
<tr>
<td>{</td>
<td>}</td>
<td>[</td>
<td>]</td>
<td>/</td>
<td>;</td>
<td>*</td>
<td>=</td>
</tr>
<tr>
<td>+</td>
<td>-</td>
<td>%</td>
<td>AND</td>
<td>NOT</td>
<td>OR</td>
<td>.</td>
</tr>
</tbody>
</table>
<br/>
<h4 id="expl-identifiers">Identifiers</h4>
<p>Identifiers are names of variables and user-defined functions. Identifiers should start with an letter, and may contain both letters and digits. Special characters are not allowed in identifiers.</p>
<p style="text-indent: 5em;">letter -> [a-z]|[A-Z]</p>
<p style="text-indent: 5em;">digit -> [0-9]</p>
<p style="text-indent: 5em;">identifier -> (letter)(letter | digit)*</p>
<br/>
</article>
</div>
</section>
<hr>
<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>Ashwathy T Revi</a>, <a>Subisha V</a>,<br> <a href="https://www.linkedin.com/in/suryaharshanunnaguppala">Nunnaguppala Surya Harsha</a>, <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>