-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathassignments.html
597 lines (549 loc) · 46.7 KB
/
assignments.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
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<!-- saved from url=(0044)http://cgi.di.uoa.gr/~compilers/project.html -->
<html xmlns="http://www.w3.org/1999/xhtml"><!-- #BeginTemplate "compilers_uoa.dwt" --><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<!-- #BeginEditable "doctitle" -->
<title>Compilers, University of Athens - Project</title>
<!-- #EndEditable -->
<meta content="en-us" http-equiv="Content-Language">
<meta content="no-cache" http-equiv="pragma">
<meta content="-1" http-equiv="expires">
<meta name="keywords" content="compilers, yannis smaragdakis, yannis, javacc, dragon book, flex, yacc, bison, jtb, visitor, sablecc, smaragdakis, smaragd, uoa, kapodistrian, nkua, γιάννης σμαραγδάκης, μεταγλωττιστές, μεταγλωττιστής, καποδιστριακό, σμαραγδάκης, ενδιάμεσος κώδικας, τελικός κώδικας, di.uoa.gr">
<!-- #BeginEditable "meta" -->
<meta name="description" content="Main project of Compilers course.">
<style type="text/css">
.auto-style3 {
font-family: Arial, Helvetica, sans-serif;
font-size: 15px;
}
.auto-style4 {
color: #993300;
}
.auto-style5 {
text-decoration: line-through;
}
.auto-style7 {
text-align: left;
}
.myPre,
code {
color: black;
margin: 6px;
background-color: #ffffff;
}
pre code {
margin: 0;
}
pre.sourceCode {
padding: 5px 10px;
background-color: #ffffff;
}
a.sourceLine { display: inline-block; line-height: 1.25; }
a.sourceLine { pointer-events: none; color: inherit; text-decoration: inherit; }
a.sourceLine:empty { height: 1.2em; }
.sourceCode { overflow: visible; }
code.sourceCode { white-space: pre; position: relative; }
div.sourceCode { margin: 1em 0; }
@media screen {
div.sourceCode { overflow: auto; }
}
@media print {
code.sourceCode { white-space: pre-wrap; }
a.sourceLine { text-indent: -1em; padding-left: 1em; }
}
pre.numberSource a.sourceLine
{ position: relative; left: -4em; }
pre.numberSource a.sourceLine::before
{ content: attr(title);
position: relative; left: -1em; text-align: right; vertical-align: baseline;
border: none; pointer-events: all; display: inline-block;
-webkit-touch-callout: none; -webkit-user-select: none;
-khtml-user-select: none; -moz-user-select: none;
-ms-user-select: none; user-select: none;
padding: 0 4px; width: 4em;
color: #aaaaaa;
}
pre.numberSource { margin-left: 3em; border-left: 1px solid #aaaaaa; padding-left: 4px; }
div.sourceCode
{ }
@media screen {
a.sourceLine::before { text-decoration: underline; }
}
</style>
<style type="text/css">code{white-space: pre;}</style>
<style type="text/css">
div.sourceCode { overflow-x: auto; }
table.sourceCode, tr.sourceCode, td.lineNumbers, td.sourceCode {
margin: 0; padding: 0; vertical-align: baseline; border: none; }
table.sourceCode { width: 100%; line-height: 100%; }
td.lineNumbers { text-align: right; padding-right: 4px; padding-left: 4px; color: #aaaaaa; border-right: 1px solid #aaaaaa; }
td.sourceCode { padding-left: 5px; }
code > span.kw { color: #007020; font-weight: bold; } /* Keyword */
code > span.dt { color: #902000; } /* DataType */
code > span.dv { color: #40a070; } /* DecVal */
code > span.bn { color: #40a070; } /* BaseN */
code > span.fl { color: #40a070; } /* Float */
code > span.ch { color: #4070a0; } /* Char */
code > span.st { color: #4070a0; } /* String */
code > span.co { color: #60a0b0; font-style: italic; } /* Comment */
code > span.ot { color: #007020; } /* Other */
code > span.al { color: #ff0000; font-weight: bold; } /* Alert */
code > span.fu { color: #06287e; } /* Function */
code > span.er { color: #ff0000; font-weight: bold; } /* Error */
code > span.wa { color: #60a0b0; font-weight: bold; font-style: italic; } /* Warning */
code > span.cn { color: #880000; } /* Constant */
code > span.sc { color: #4070a0; } /* SpecialChar */
code > span.vs { color: #4070a0; } /* VerbatimString */
code > span.ss { color: #bb6688; } /* SpecialString */
code > span.im { } /* Import */
code > span.va { color: #19177c; } /* Variable */
code > span.cf { color: #007020; font-weight: bold; } /* ControlFlow */
code > span.op { color: #666666; } /* Operator */
code > span.bu { } /* BuiltIn */
code > span.ex { } /* Extension */
code > span.pp { color: #bc7a00; } /* Preprocessor */
code > span.at { color: #7d9029; } /* Attribute */
code > span.do { color: #ba2121; font-style: italic; } /* Documentation */
code > span.an { color: #60a0b0; font-weight: bold; font-style: italic; } /* Annotation */
code > span.cv { color: #60a0b0; font-weight: bold; font-style: italic; } /* CommentVar */
code > span.in { color: #60a0b0; font-weight: bold; font-style: italic; } /* Information */
</style>
<!-- #EndEditable -->
<script language="javascript" type="text/javascript">
var d=new Date();
var monthname=new Array("January","February","March","April","May","June","July","August","September","October","November","December");
var TODAY = monthname[d.getMonth()] + " " + d.getDate() + ", " + d.getFullYear();
</script>
<link rel="stylesheet" type="text/css" href="./Compilers, University of Athens - Project_files/style.css">
</head>
<body style="position: absolute; top: 0px; left: 0px; width:100%; z-index: 1;" class="vsc-initialized">
<table border="0" cellspacing="0" style="height:100%;" width="100%">
<tbody><tr style="background-color: #D5EDB3">
<td id="logo" align="center" colspan="5" style="height: 51px; white-space: nowrap" valign="bottom">
<a href="http://cgi.di.uoa.gr/~compilers" style="text-decoration: none; color: #5C743D">
</a><a class="auto-style1" href="http://cgi.di.uoa.gr/~compilers"><span class="auto-style2">K31 Compilers</span></a></td>
</tr>
<tr style="background-color: #D5EDB3">
<td id="tagline" align="center" colspan="5" style="height: 51px" valign="top">
<span class="style4"><span>Spring Semester</span> 2021</span>
</td>
</tr>
<tr>
<td colspan="7" style="background-color: #5C743D">
<img alt="image" height="2" src="./Compilers, University of Athens - Project_files/mm_spacer.gif" style="border: 0" width="1"></td>
</tr>
<tr>
<td colspan="7" style="background-color: #99CC66; background: mm_dashed_line.gif">
<img alt="line decor" height="3" src="./Compilers, University of Athens - Project_files/mm_dashed_line.gif" style="border: 0" width="4"></td>
</tr>
<tr style="background-color: #99CC66">
<td id="dateformat" colspan="7" style="height: 20px"> <script language="javascript" type="text/javascript">
document.write(TODAY); </script>June 22, 2021 </td>
</tr>
<tr>
<td colspan="7" style="background: mm_dashed_line.gif; background-color: #99CC66; height: 3px">
<img alt="line decor" height="3" src="./Compilers, University of Athens - Project_files/mm_dashed_line.gif" style="border: 0" width="4"></td>
</tr>
<tr>
<td colspan="7" style="background-color: #5C743D">
<img alt="image" height="2" src="./Compilers, University of Athens - Project_files/mm_spacer.gif" style="border: 0" width="1"></td>
</tr>
<tr style="height:100%">
<td style="background-color: #5C743D; width: 165px;height:100%" valign="top">
<table id="navigation" cellpadding="0" cellspacing="0" style="border: 0; width: 165px;height:100%">
<tbody><tr>
<td class="style4" style="height: 31px"><br><br>
</td>
</tr>
<tr>
<td class="style4"><a class="navText" href="http://cgi.di.uoa.gr/~compilers/index.html">Compilers</a></td>
</tr>
<tr>
<td class="style4"><a class="navText" href="http://cgi.di.uoa.gr/~compilers/description.html">Course Description</a></td>
</tr>
<tr>
<td class="style4"><a class="navText" href="http://cgi.di.uoa.gr/~compilers/lectures.html">Lectures</a></td>
</tr>
<tr>
<td class="style4"><a class="navText" href="http://cgi.di.uoa.gr/~compilers/tutorials.html">Tutorials</a></td>
</tr>
<tr>
<td class="style4"><a class="navText" href="http://cgi.di.uoa.gr/~compilers/project.html">Project</a></td>
</tr>
<tr>
<td class="style4"><a class="navText" href="http://piazza.com/uoa.gr/spring2021/19809/home">Piazza course link</a></td>
</tr>
<tr>
<td class="style4"><a class="navText" href="http://cgi.di.uoa.gr/~compilers/tools.html">Compiler Tools</a></td>
</tr>
<tr style="height:100%">
<td> </td>
</tr>
</tbody></table>
</td>
<td style="width: 50px">
<img alt="image" height="1" src="./Compilers, University of Athens - Project_files/mm_spacer.gif" style="border: 0" width="50">
</td>
<td colspan="2" valign="top">
<p>
<img alt="image" height="1" src="./Compilers, University of Athens - Project_files/mm_spacer.gif" style="border: 0" width="305">
<br>
</p>
<!-- #BeginEditable "main_region" -->
<h1>Course Project</h1>
<p>Design and implementation of a compiler for the MiniJava language (a small
subset of Java)</p>
<p>To implement the compiler you will use the tools JavaCC
and JTB</p>
<p>The implementation for phases 2 and 3 of the project
will be done in
Java utilizing the visitor pattern</p>
<table border="1" cellpadding="8" cellspacing="0" class="style3">
<tbody><tr>
<th>Homework</th>
<th align="center">Description</th>
<th align="center">D<span>eadline</span></th>
</tr>
<tr>
<td><a href="http://cgi.di.uoa.gr/~compilers/project.html#hw1">1</a></td>
<td>Implementation of a LL(1) parser for a simple calculator and a translator to Java for a simple language</td>
<td align="center">18/4/2021</td>
</tr>
<tr>
<td><a href="http://cgi.di.uoa.gr/~compilers/project.html#hw2">2</a></td>
<td>Semantic Check (MiniJava)</td>
<td align="center">16/05/2021</td>
</tr>
<tr>
<td><a href="http://cgi.di.uoa.gr/~compilers/project.html#hw3">3</a></td>
<td>Generating intermediate code (MiniJava -> LLVM)</td>
<td align="center">13/06/2021</td>
</tr>
<!---
--->
</tbody></table>
<h2 id="part-1"><a name="hw1">Homework 1 - LL(1) Calculator Parser - Translator to Java</a></h2>
<h2 id="part-1">Part 1</h2>
<p>For the first part of this homework you should implement a simple calculator. The calculator should accept expressions with the addition, subtraction, and exponentiation operators, as well as parentheses. The grammar (for multi-digit numbers) is summarized in:</p>
<p>exp -> num | exp op exp | (exp)</p>
<p>op -> + | - | **</p>
<p>num -> digit | digit num</p>
<p>digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9</p>
<p>You need to change this grammar to support priority between the operators, to remove the left recursion for LL parsing, etc.</p>
<p>This part of the homework is divided in two tasks:</p>
<ol style="list-style-type: decimal">
<li><p>For practice, you can write the FIRST+ & FOLLOW sets for the LL(1) version of the above grammar. In the end you will summarize them in a single lookahead table (include a row for every derivation in your final grammar). This part will not be graded.</p></li>
<li><p>You have to write a recursive descent parser in Java that reads expressions and computes the values or prints "parse error" if there is a syntax error. You don't need to identify blank spaces. You can read the symbols one-by-one (as in the C getchar() function). The expression must end with a newline or EOF.</p></li>
</ol>
<p>Your parser should read its input from the standard input (e.g., via an InputStream on System.in) and write the computed values of expressions to the standard output (System.out). Parse errors should be reported on standard error (System.err).</p>
<h2 id="part-2">Part 2</h2>
<p>In the second part of this homework you will implement a parser and translator for a language supporting string operations. The language supports the concatenation (+) operator over strings, function definitions and calls, conditionals (if-else i.e, every "if" must be followed by an "else"), and the following logical expressions:</p>
<ul>
<li>is-prefix-of (string1 prefix string2): Whether string1 is a prefix of string2.</li>
<li>is-suffix-of (string1 suffix string2): Whether string1 is a suffix of string2.</li>
</ul>
<p>All values in the language are strings.</p>
<p>The precedence of the operator expressions is defined as: <em>precedence</em>(if) < <em>precedence</em>(concat).</p>
<p>Your parser, based on a context-free grammar, will translate the input language into Java. You will use JavaCUP for the generation of the parser combined either with a hand-written lexer or a generated-one (e.g., using JFlex, which is encouraged).</p>
<p>You will infer the desired syntax of the input and output languages from the examples below. The output language is a subset of Java so it can be compiled using javac and executed using Java or online Java compilers like <a href="http://repl.it/languages/java">this</a>, if you want to test your output.</p>
<p>There is no need to perform type checking for the argument types or a check for the number of function arguments. You can assume that the program input will always be semantically correct.</p>
<p>Note that each file of Java source code you produce must have the same name as the public Java class in it. For your own convenience you can name the public class "Main" and the generated files "Main.java". In order to compile a file named Main.java you need to execute the command: javac Main.java. In order to execute the produced Main.class file you need to execute: java Main.</p>
<p>To execute the program successfully, the "Main" class of your Java program must have a method with the following signature: public static void main(String[] args), which will be the main method of your program, containing all the translated statements of the input program. Moreover, for each function declaration of the input program, the translated Java program must contain an equivalent static method of the same name. Finally, keep in mind that in the input language the function declarations must precede all statements.</p>
<p>As with the first part of this assignment, you should accept input programs from stdin and print output Java programs to stdout.</p>
<h3 id="example-1">Example #1</h3>
<p><strong>Input:</strong></p>
<pre><code>name() {
"John"
}
surname() {
"Doe"
}
fullname(first_name, sep, last_name) {
first_name + sep + last_name
}
name()
surname()
fullname(name(), " ", surname())</code></pre>
<p><strong>Output (Java):</strong></p>
<pre><code>public class Main {
public static void main(String[] args) {
System.out.println(name());
System.out.println(surname());
System.out.println(fullname(name(), " ", surname()));
}
public static String name() {
return "John";
}
public static String surname() {
return "Doe";
}
public static String fullname(String first_name, String sep, String last_name) {
return first_name + sep + last_name;
}
}</code></pre>
<h3 id="example-2">Example #2</h3>
<p><strong>Input:</strong></p>
<pre><code>name() {
"John"
}
repeat(x) {
x + x
}
cond_repeat(c, x) {
if (c prefix "yes")
if("yes" prefix c)
repeat(x)
else
x
else
x
}
cond_repeat("yes", name())
cond_repeat("no", "Jane")</code></pre>
<h3 id="example-3">Example #3</h3>
<p><strong>Input:</strong></p>
<pre><code>findLangType(langName) {
if ("Java" prefix langName)
if(langName prefix "Java")
"Static"
else
if("script" suffix langName)
"Dynamic"
else
"Unknown"
else
if ("script" suffix langName)
"Probably Dynamic"
else
"Unknown"
}
findLangType("Java")
findLangType("Javascript")
findLangType("Typescript")</code></pre>
<h2 id="hw2">Homework 2 – MiniJava Static Checking (Semantic Analysis)</h2>
<p>This homework introduces your semester project, which consists of building a compiler for MiniJava, a subset of Java. MiniJava is designed so that its programs can be compiled by a full Java compiler like javac.</p>
<p>Here is a partial, textual description of the language. Much of it <strong>can be safely ignored</strong> (most things are well defined in the grammar or derived from the requirement that each MiniJava program is also a Java program):</p>
<ul>
<li><p>MiniJava is fully object-oriented, like Java. It does not allow global functions, only classes, fields and methods. The basic types are int, boolean, and int [] which is an array of int. You can build classes that contain fields of these basic types or of other classes. Classes contain methods with arguments of basic or class types, etc.</p></li>
<li><p>MiniJava supports single inheritance but not interfaces. It does not support function overloading, which means that each method name must be unique. In addition, all methods are inherently polymorphic (i.e., “virtual” in C++ terminology). This means that foo can be defined in a subclass if it has the same return type and argument types (ordered) as in the parent, but it is an error if it exists with other argument types or return type in the parent. Also all methods must have a return type–there are no void methods. Fields in the base and derived class are allowed to have the same names, and are essentially different fields.</p></li>
<li>All MiniJava methods are “public” and all fields “protected”. A class method cannot access fields of another class, with the exception of its superclasses. Methods are visible, however. A class’s own methods can be called via “this”. E.g., this.foo(5) calls the object’s own foo method, a.foo(5) calls the foo method of object a. Local variables are defined only at the beginning of a method. A name cannot be repeated in local variables (of the same method) and cannot be repeated in fields (of the same class). A local variable x shadows a field x of the surrounding class.</li>
<li><p>In MiniJava, constructors and destructors are not defined. The new operator calls a default void constructor. In addition, there are no inner classes and there are no static methods or fields. By exception, the pseudo-static method “main” is handled specially in the grammar. A MiniJava program is a file that begins with a special class that contains the main method and specific arguments that are not used. The special class has no fields. After it, other classes are defined that can have fields and methods.<br>
Notably, an A class can contain a field of type B, where B is defined later in the file. But when we have “class B extends A”, A must be defined before B. As you’ll notice in the grammar, MiniJava offers very simple ways to construct expressions and only allows < comparisons. There are no lists of operations, e.g., 1 + 2 + 3, but a method call on one object may be used as an argument for another method call. In terms of logical operators, MiniJava allows the logical and (“&&”) and the logical not (“!”). For int arrays, the assignment and [] operators are allowed, as well as the a.length expression, which returns the size of array a. We have “while” and “if” code blocks. The latter are always followed by an “else”. Finally, the assignment “A a = new B();” when B extends A is correct, and the same applies when a method expects a parameter of type A and a B instance is given instead.</p></li>
<li><p>You should only accept expressions of type int as the argument of the PrintStatement.</p></li>
</ul>
<p>The MiniJava grammar in BNF can be downloaded <a href="http://cgi.di.uoa.gr/~compilers/project_files/minijava-new/minijava.html">here</a>. You can make small changes to grammar, but you must accept everything that MiniJava accepts and reject anything that is rejected by the full Java language. Making changes is not recommended because it will make your job harder in subsequent homework assignments. Normally you won’t need to touch the grammar.</p>
<p>The MiniJava grammar in JavaCC form is <a href="http://cgi.di.uoa.gr/~compilers/project_files/minijava-new/minijava.jj">here</a>. You will use the JTB tool to convert it into a grammar that produces class hierarchies. Then you will write one or more visitors who will take control over the MiniJava input file and will tell whether it is semantically correct, or will print an error message. It isn’t necessary for the compiler to report precisely what error it encountered and compilation can end at the first error. But you should not miss errors or report errors in correct programs.</p>
<p>The visitors you will build should be subclasses of the visitors generated by JTB, but they may also contain methods and fields to hold information during static checking, to transfer information from one visitor to the next, etc. In the end, you will have a Main class that runs the semantic analysis initiating the parser that was produced by JavaCC and executing the visitors you wrote. You will turn in your grammar file, if you have made changes, otherwise just the code produced by JavaCC and JTB alongside your own classes that implement the visitors, etc. and a Main. The Main should parse and statically check all the MiniJava files that are given as arguments.</p>
<p>Also, for every MiniJava file, your program should store and print some useful data for every class such as the names and the offsets of every field and method this class contains. For MiniJava we have only three types of fields (int, boolean and pointers). Ints are stored in 4 bytes, booleans in 1 byte and pointers in 8 bytes (we consider functions and int arrays as pointers). Corresponding offsets are shown in the example below:</p>
<p>Input:</p>
<div class="sourceCode" id="cb1"><pre class="sourceCode java"><code class="sourceCode java"><a class="sourceLine" id="cb1-1" title="1"> <span class="kw">class</span> A{</a>
<a class="sourceLine" id="cb1-2" title="2"> <span class="dt">int</span> i;</a>
<a class="sourceLine" id="cb1-3" title="3"> <span class="dt">boolean</span> flag;</a>
<a class="sourceLine" id="cb1-4" title="4"> <span class="dt">int</span> j;</a>
<a class="sourceLine" id="cb1-5" title="5"> <span class="kw">public</span> <span class="dt">int</span> <span class="fu">foo</span>() {}</a>
<a class="sourceLine" id="cb1-6" title="6"> <span class="kw">public</span> <span class="dt">boolean</span> <span class="fu">fa</span>() {}</a>
<a class="sourceLine" id="cb1-7" title="7"> }</a>
<a class="sourceLine" id="cb1-8" title="8"></a>
<a class="sourceLine" id="cb1-9" title="9"> <span class="kw">class</span> B <span class="kw">extends</span> A{</a>
<a class="sourceLine" id="cb1-10" title="10"> A type;</a>
<a class="sourceLine" id="cb1-11" title="11"> <span class="dt">int</span> k;</a>
<a class="sourceLine" id="cb1-12" title="12"> <span class="kw">public</span> <span class="dt">int</span> <span class="fu">foo</span>() {}</a>
<a class="sourceLine" id="cb1-13" title="13"> <span class="kw">public</span> <span class="dt">boolean</span> <span class="fu">bla</span>() {}</a>
<a class="sourceLine" id="cb1-14" title="14"> }</a></code></pre></div>
<p>Output:</p>
<pre><code> A.i : 0
A.flag : 4
A.j : 5
A.foo : 0
A.fa: 8
B.type : 9
B.k : 17
B.bla : 16</code></pre>
<p>There will be a tutorial for JavaCC and JTB. You can use <a href="http://cgi.di.uoa.gr/~compilers/project_files/minijava-examples-new.zip">these</a> files as MiniJava examples and to test your program. Obviously you are free to make up your own files, however the homework will be graded purely on how your compiler performs on all the files we will test it against (both the above sample files and others). You can share ideas and test files, but you are not allowed to share code.</p>
<p>Your program should run as follows:</p>
<pre><code>java [MainClassName] [file1] [file2] ... [fileN]</code></pre>
<p>That is, your program must perform semantic analysis on all files given as arguments. May the Force be with you!</p>
<h2 id="part-3"><a name="hw3">Homework 3 - Generating intermediate code (MiniJava -> LLVM)</a></h2>
<p>In this part of the project you have to write visitors that convert MiniJava code into the intermediate representation used by the LLVM compiler project. The MiniJava language is the same as in the previous exercise. The LLVM language is documented in the <a href="https://llvm.org/docs/LangRef.html#instruction-reference">LLVM Language Reference Manual</a>, although you will use only a subset of the instructions.</p>
<h2 id="types">Types</h2>
<p>Some of the available types that might be useful are:</p>
<ul>
<li><code>i1</code> - a single bit, used for booleans (practically takes up one byte)</li>
<li><code>i8</code> - a single byte</li>
<li><code>i8*</code> - similar to a char* pointer</li>
<li><code>i32</code> - a single integer</li>
<li><code>i32*</code> - a pointer to an integer, can be used to point to an integer array</li>
<li>static arrays, e.g., <code>[20 x i8]</code> - a constant array of 20 characters</li>
</ul>
<h2 id="instructions-to-be-used">Instructions to be used</h2>
<ul>
<li><p><code>declare</code> is used for the declaration of external methods. Only a few specific methods (e.g., <code>calloc</code>, <code>printf</code>) need to be declared.<br>
Example: <code>declare i32 @puts(i8*)</code></p></li>
<li><p><code>define</code> is used for defining our own methods. The return and argument types need to be specified, and the method needs to end with a <code>ret</code> instruction of the same type.<br>
Example: <code>define i32 @main(i32 %argc, i8** argv) {...}</code></p></li>
<li><p><code>ret</code> is the return instruction. It is used to return the control flow and a value to the caller of the current function. Example: <code>ret i32 %rv</code></p></li>
<li><p><code>alloca</code> is used to allocate space on the stack of the current function for local variables. It returns a <em>pointer</em> to the given type. This space is freed when the method returns.<br>
Example: <code>%ptr = alloca i32</code></p></li>
<li><p><code>store</code> is used to store a value to a memory location. The parameters are the value to be stored and a pointer to the memory.<br>
Example: <code>store i32 %val, i32* %ptr</code></p></li>
<li><p><code>load</code> is used to load a value from a memory location. The parameters are the type of the value and a pointer to the memory.<br>
Example: <code>%val = load i32, i32* %ptr</code></p></li>
<li><p><code>call</code> is used to call a method. The result can be assigned to a register. (LLVM bitcode temporary variables are called "registers".) The return type and parameters (with their types) need to be specified.<br>
Example: <code>%result = call i8* @calloc(i32 1, i32 %val)</code></p></li>
<li><p><code>add, and, sub, mul, xor</code> are used for mathematical operations. The result is the same type as the operands.<br>
Example: <code>%sum = add i32 %a, %b</code></p></li>
<li><p><code>icmp</code> is used for comparing two operands. <code>icmp slt</code> for instance does a signed comparison of the operands and will return <code>i1 1</code> if the first operand is less than the second, otherwise <code>i1 0</code>.<br>
Example: <code>%case = icmp slt i32 %a, %b</code></p></li>
<li><p><code>br</code> with a <code>i1</code> operand and two labels will jump to the first label if the <code>i1</code> is one, and to the second label otherwise.<br>
Example: <code>br i1 %case, label %if, label %else</code></p></li>
<li><p><code>br</code> with only a single label will jump to that label.<br>
Example: <code>br label %goto</code></p></li>
<li><p><code>label:</code> declares a label with the given name. The instruction before declaring a label needs to be a <code>br</code> operation, even if that <code>br</code> is simply a jump to the label.<br>
Example: <code>label123:</code></p></li>
<li><p><code>bitcast</code> is used to cast between different pointer types. It takes the value and type to be cast, and the type that it will be cast to.<br>
Example: <code>%ptr = bitcast i32* %ptr2 to i8**</code></p></li>
<li><p><code>getelementptr</code> is used to get the pointer to an element of an array from a pointer to that array and the index of the element. The result is also a pointer to the type that is passed as the first parameter (in the case below it's an <code>i8*</code>). This example is like doing <code>ptr_idx = &ptr[idx]</code> in C (you still need to do a <code>load</code> to get the actual value at that position).<br>
Example: <code>%ptr_idx = getelementptr i8, i8* %ptr, i32 %idx</code></p></li>
<li><p><code>constant</code> is used to define a constant, such as a string. The size of the constant needs to be declared too. In the example below, the string is 12 bytes (<code>[12 x i8]</code>). The result is a pointer to the given type (in the example below, <code>@.str</code> is a <code>[12 x i8]*</code>).<br>
Example: <code>@.str = constant [12 x i8] c"Hello world\00"</code></p></li>
<li><p><code>global</code> is used for declaring global variables - something you will need to do for creating v-tables. Just like <code>constant</code>, the result is a pointer to the given type.<br>
Example:<br>
<code>@.vtable = global [2 x i8*] [i8* bitcast (i32 ()* @func1 to i8*), i8* bitcast (i8* (i32, i32*)* @func2 to i8*)]</code></p></li>
<li><p><code>phi</code> is used for selecting a value from previous basic blocks, depending on which one was executed before the current block. Phi instructions must be the first in a basic block. It takes as arguments a list of pairs. Each pair contains the value to be selected and the predecessor block for that value. This is necessary in single-assignment languages, in places where multiple control-flow paths join, such as if-else statements, if one wants to select a value from the different paths. In the context of the exercise, you will need this for short-circuiting and (&&) expressions.<br>
Example:<br>
<code>br i1 1, label %lb1, label %lb2</code><br>
<code>lb1:</code><br>
<code>%a = add i32 0, 100</code><br>
<code>br label %lb3</code><br>
<code>lb2:</code><br>
<code>%b = add i32 0, 200</code><br>
<code>br label %lb3</code><br>
<code>lb3:</code><br>
<code>%c = phi i32 [%a, %lb1], [%b, %lb2]</code></p></li>
</ul>
<h2 id="v-table">V-table</h2>
<p>If you do not remember or haven't seen how a virtual table (v-table) is constructed, essentially it is a table of function pointers, pointed at by the first 8 bytes of an object. The v-table defines an address for each dynamic function the object supports. Consider a function <code>foo</code> in position 0 and <code>bar</code> in position 1 of the table (with actual offset 8). If a method is overridden, the overriding version is inserted in the same location of the virtual table as the overridden version. Virtual calls are implemented by finding the address of the function to call through the virtual table. If we wanted to depict this in C, imagine that object <code>obj</code> is located at location <code>x</code> and we are calling <code>foo</code> which is in the 3rd position (offset 16) of the v-table. The address of the function that is going to be called is in memory location <code>(*x) + 16</code>.</p>
<h2 id="execution">Execution</h2>
<p>You will need to execute the produced LLVM IR files in order to see that their output is the same as compiling the input java file with <code>javac</code> and executing it with <code>java</code>. To do that, you will need Clang with version >=4.0.0. You may download it on your Linux machine, or use it via SSH on the linuxvm machines.</p>
<h3 id="in-ubuntu-trusty">In Ubuntu Trusty</h3>
<ol style="list-style-type: decimal">
<li><code>sudo apt update && sudo apt install clang-4.0</code></li>
<li>Save the code to a file (e.g. <code>ex.ll</code>)</li>
<li><code>clang-4.0 -o out1 ex.ll</code></li>
<li><code>./out1</code></li>
</ol>
<h3 id="in-linuxvm-machines">In linuxvm machines</h3>
<ol style="list-style-type: decimal">
<li><code>/home/users/thp06/clang/clang -o out1 ex.ll</code></li>
<li><code>./out1</code></li>
</ol>
<h2 id="deliverable">Deliverable</h2>
<p>Your program should run as follows:<br>
<code>java [MainClassName] [file1.java] [file2.java] ... [fileN.java]</code><br>
That is, your program must compile to LLVM IR all .java files given as arguments. Moreover, the outputs must be stored in files named <code>file1.ll</code>, <code>file2.ll</code>, ... <code>fileN.ll</code> respectively.</p>
<h2 id="tips">Tips</h2>
<ul>
<li>You will need to use a lot of registers in order to 'glue' expressions together. This means that each visitor will produce the code for storing the value of an expression to a register, and then return the name of that register so that other expressions may use it, if necessary.</li>
<li>Registers are single-assignment. This means you can only write to them once (but read any number of times). This also implies that registers cannot be used for local variables of the source program. Instead, you will allocate space on the stack using <code>alloca</code> and keep the address in a register. You will use the <code>load</code> and <code>store</code> instructions to read and write to that local variable.</li>
<li>Because registers are single-assignment, you will probably need to keep a counter to produce new ones. For example, you may produce registers of the form <code>%_1</code>, <code>%_2</code>, etc.</li>
<li>You will only support compilation to a 64-bit architecture: pointers are 8-bytes long.</li>
<li>Everything new in Java is initialized to zeroes.</li>
<li>Memory allocated with <code>@calloc</code> will leak since you're not implementing a Garbage Collector, but that's fine for this homework.</li>
<li>You will need to check each array access in order not to write or read beyond the limits of an array. If an illegal read/write is attempted, you will print the message "Out of bounds" and the program will exit (you may call the <code>@throw_oob</code> defined below for that). Of course, you need to know the length of an array for that.</li>
<li>You will also need to check if an array is allocated with a negative length, and do the same process as above in that case.</li>
<li>You may see some examples of LLVM code produced for different Java input files <a href="http://cgi.di.uoa.gr/~compilers/project_files/llvm-examples.zip">here</a> (corresponding to the earlier MiniJava <a href="http://cgi.di.uoa.gr/~compilers/project_files/minijava-examples-new.zip">examples</a> from HW2).</li>
<li>You may define the following helper methods once in your output files, in order to be able to call <code>@calloc</code>, <code>@print_int</code> and <code>@throw_oob</code>.</li>
</ul>
<div class="sourceCode"><pre class="sourceCode llvm"><code class="sourceCode llvm"><span class="kw">declare</span> <span class="dt">i8</span>* <span class="fu">@calloc</span>(<span class="dt">i32</span>, <span class="dt">i32</span>)
<span class="kw">declare</span> <span class="dt">i32</span> <span class="fu">@printf</span>(<span class="dt">i8</span>*, ...)
<span class="kw">declare</span> <span class="dt">void</span> <span class="fu">@exit</span>(<span class="dt">i32</span>)
<span class="fu">@_cint</span> = <span class="kw">constant</span> [<span class="dv">4</span> x <span class="dt">i8</span>] c<span class="st">"%d\0a\00"</span>
<span class="fu">@_cOOB</span> = <span class="kw">constant</span> [<span class="dv">15</span> x <span class="dt">i8</span>] c<span class="st">"Out of bounds\0a\00"</span>
<span class="kw">define</span> <span class="dt">void</span> <span class="fu">@print_int</span>(<span class="dt">i32</span> <span class="fu">%i</span>) {
<span class="fu">%_str</span> = <span class="kw">bitcast</span> [<span class="dv">4</span> x <span class="dt">i8</span>]* <span class="fu">@_cint</span> <span class="kw">to</span> <span class="dt">i8</span>*
<span class="kw">call</span> <span class="dt">i32</span> (<span class="dt">i8</span>*, ...) <span class="fu">@printf</span>(<span class="dt">i8</span>* <span class="fu">%_str</span>, <span class="dt">i32</span> <span class="fu">%i</span>)
<span class="kw">ret</span> <span class="dt">void</span>
}
<span class="kw">define</span> <span class="dt">void</span> <span class="fu">@throw_oob</span>() {
<span class="fu">%_str</span> = <span class="kw">bitcast</span> [<span class="dv">15</span> x <span class="dt">i8</span>]* <span class="fu">@_cOOB</span> <span class="kw">to</span> <span class="dt">i8</span>*
<span class="kw">call</span> <span class="dt">i32</span> (<span class="dt">i8</span>*, ...) <span class="fu">@printf</span>(<span class="dt">i8</span>* <span class="fu">%_str</span>)
<span class="kw">call</span> <span class="dt">void</span> <span class="fu">@exit</span>(<span class="dt">i32</span> <span class="dv">1</span>)
<span class="kw">ret</span> <span class="dt">void</span>
}</code></pre></div>
<h2 id="example-program">Example program</h2>
<p>The program below demonstrates all of the above instructions. It creates an array of 3 methods (add, sub and mul), calls all of them with the same arguments and prints the results.</p>
<div class="sourceCode"><pre class="sourceCode llvm"><code class="sourceCode llvm"><span class="fu">@.funcs</span> = <span class="kw">global</span> [<span class="dv">3</span> x <span class="dt">i8</span>*] [<span class="dt">i8</span>* <span class="kw">bitcast</span> (<span class="dt">i32</span> (<span class="dt">i32</span>*, <span class="dt">i32</span>*)* <span class="fu">@add</span> <span class="kw">to</span> <span class="dt">i8</span>*),
<span class="dt">i8</span>* <span class="kw">bitcast</span> (<span class="dt">i32</span> (<span class="dt">i32</span>*, <span class="dt">i32</span>*)* <span class="fu">@sub</span> <span class="kw">to</span> <span class="dt">i8</span>*),
<span class="dt">i8</span>* <span class="kw">bitcast</span> (<span class="dt">i32</span> (<span class="dt">i32</span>*, <span class="dt">i32</span>*)* <span class="fu">@mul</span> <span class="kw">to</span> <span class="dt">i8</span>*)]
<span class="kw">declare</span> <span class="dt">i32</span> <span class="fu">@printf</span>(<span class="dt">i8</span>*, ...)
<span class="fu">@.comp_str</span> = <span class="kw">constant</span> [<span class="dv">15</span> x <span class="dt">i8</span>] c<span class="st">"%d %c %d = %d\0A\00"</span>
<span class="fu">@.ret_val</span> = <span class="kw">constant</span> [<span class="dv">20</span> x <span class="dt">i8</span>] c<span class="st">"Returned value: %d\0A\00"</span>
<span class="kw">define</span> <span class="dt">i32</span> <span class="fu">@main</span>() {
<span class="co">; allocate local variables</span>
<span class="fu">%ptr_a</span> = <span class="kw">alloca</span> <span class="dt">i32</span>
<span class="fu">%ptr_b</span> = <span class="kw">alloca</span> <span class="dt">i32</span>
<span class="fu">%count</span> = <span class="kw">alloca</span> <span class="dt">i32</span>
<span class="co">; initialize var values</span>
<span class="kw">store</span> <span class="dt">i32</span> <span class="dv">100</span>, <span class="dt">i32</span>* <span class="fu">%ptr_a</span>
<span class="kw">store</span> <span class="dt">i32</span> <span class="dv">50</span>, <span class="dt">i32</span>* <span class="fu">%ptr_b</span>
<span class="kw">store</span> <span class="dt">i32</span> <span class="dv">0</span>, <span class="dt">i32</span>* <span class="fu">%count</span>
<span class="kw">br</span> <span class="dt">label</span> <span class="fu">%loopstart</span>
<span class="fu">loopstart:</span>
<span class="co">;load %i from %count</span>
<span class="fu">%i</span> = <span class="kw">load</span> <span class="dt">i32</span>, <span class="dt">i32</span>* <span class="fu">%count</span>
<span class="co">; while %i < 3</span>
<span class="fu">%fin</span> = <span class="kw">icmp</span> <span class="kw">slt</span> <span class="dt">i32</span> <span class="fu">%i</span>, <span class="dv">3</span>
<span class="kw">br</span> <span class="dt">i1</span> <span class="fu">%fin</span>, <span class="dt">label</span> <span class="fu">%next</span>, <span class="dt">label</span> <span class="fu">%end</span>
<span class="fu">next:</span>
<span class="co">; get pointer to %i'th element of the @.funcs array</span>
<span class="fu">%func_ptr</span> = <span class="kw">getelementptr</span> [<span class="dv">3</span> x <span class="dt">i8</span>*], [<span class="dv">3</span> x <span class="dt">i8</span>*]* <span class="fu">@.funcs</span>, <span class="dt">i32</span> <span class="dv">0</span>, <span class="dt">i32</span> <span class="fu">%i</span>
<span class="co">; load %i'th element that contains an i8* to the method</span>
<span class="fu">%func_addr</span> = <span class="kw">load</span> <span class="dt">i8</span>*, <span class="dt">i8</span>** <span class="fu">%func_ptr</span>
<span class="co">; cast i8* to actual method type in order to call it</span>
<span class="fu">%func</span> = <span class="kw">bitcast</span> <span class="dt">i8</span>* <span class="fu">%func_addr</span> <span class="kw">to</span> <span class="dt">i32</span> (<span class="dt">i32</span>*, <span class="dt">i32</span>*)*
<span class="co">; call casted method</span>
<span class="fu">%result</span> = <span class="kw">call</span> <span class="dt">i32</span> <span class="fu">%func</span>(<span class="dt">i32</span>* <span class="fu">%ptr_a</span>, <span class="dt">i32</span>* <span class="fu">%ptr_b</span>)
<span class="co">; print result</span>
<span class="fu">%str</span> = <span class="kw">bitcast</span> [<span class="dv">20</span> x <span class="dt">i8</span>]* <span class="fu">@.ret_val</span> <span class="kw">to</span> <span class="dt">i8</span>*
<span class="kw">call</span> <span class="dt">i32</span> (<span class="dt">i8</span>*, ...) <span class="fu">@printf</span>(<span class="dt">i8</span>* <span class="fu">%str</span>, <span class="dt">i32</span> <span class="fu">%result</span>)
<span class="co">; increase %i and store to %count</span>
<span class="fu">%next_i</span> = <span class="kw">add</span> <span class="dt">i32</span> <span class="fu">%i</span>, <span class="dv">1</span>
<span class="kw">store</span> <span class="dt">i32</span> <span class="fu">%next_i</span>, <span class="dt">i32</span>* <span class="fu">%count</span>
<span class="co">; go to loopstart</span>
<span class="kw">br</span> <span class="dt">label</span> <span class="fu">%loopstart</span>
<span class="fu">end:</span>
<span class="kw">ret</span> <span class="dt">i32</span> <span class="dv">0</span>
}
<span class="kw">define</span> <span class="dt">i32</span> <span class="fu">@add</span>(<span class="dt">i32</span>* <span class="fu">%a</span>, <span class="dt">i32</span>* <span class="fu">%b</span>) {
<span class="fu">%str</span> = <span class="kw">bitcast</span> [<span class="dv">15</span> x <span class="dt">i8</span>]* <span class="fu">@.comp_str</span> <span class="kw">to</span> <span class="dt">i8</span>*
<span class="co">; load values from addresses</span>
<span class="fu">%val_a</span> = <span class="kw">load</span> <span class="dt">i32</span>, <span class="dt">i32</span>* <span class="fu">%a</span>
<span class="fu">%val_b</span> = <span class="kw">load</span> <span class="dt">i32</span>, <span class="dt">i32</span>* <span class="fu">%b</span>
<span class="co">; add them and print the result</span>
<span class="fu">%res</span> = <span class="kw">add</span> <span class="dt">i32</span> <span class="fu">%val_a</span>, <span class="fu">%val_b</span>
<span class="kw">call</span> <span class="dt">i32</span> (<span class="dt">i8</span>*, ...) <span class="fu">@printf</span>(<span class="dt">i8</span>* <span class="fu">%str</span>, <span class="dt">i32</span> <span class="fu">%val_a</span>, [<span class="dv">1</span> x <span class="dt">i8</span>] c<span class="st">"+"</span>, <span class="dt">i32</span> <span class="fu">%val_b</span>, <span class="dt">i32</span> <span class="fu">%res</span>)
<span class="co">; return the result</span>
<span class="kw">ret</span> <span class="dt">i32</span> <span class="fu">%res</span>
}
<span class="kw">define</span> <span class="dt">i32</span> <span class="fu">@sub</span>(<span class="dt">i32</span>* <span class="fu">%a</span>, <span class="dt">i32</span>* <span class="fu">%b</span>) {
<span class="co">; similar as above</span>
<span class="fu">%str</span> = <span class="kw">bitcast</span> [<span class="dv">15</span> x <span class="dt">i8</span>]* <span class="fu">@.comp_str</span> <span class="kw">to</span> <span class="dt">i8</span>*
<span class="fu">%val_a</span> = <span class="kw">load</span> <span class="dt">i32</span>, <span class="dt">i32</span>* <span class="fu">%a</span>
<span class="fu">%val_b</span> = <span class="kw">load</span> <span class="dt">i32</span>, <span class="dt">i32</span>* <span class="fu">%b</span>
<span class="fu">%res</span> = <span class="kw">sub</span> <span class="dt">i32</span> <span class="fu">%val_a</span>, <span class="fu">%val_b</span>
<span class="kw">call</span> <span class="dt">i32</span> (<span class="dt">i8</span>*, ...) <span class="fu">@printf</span>(<span class="dt">i8</span>* <span class="fu">%str</span>, <span class="dt">i32</span> <span class="fu">%val_a</span>, [<span class="dv">1</span> x <span class="dt">i8</span>] c<span class="st">"-"</span>, <span class="dt">i32</span> <span class="fu">%val_b</span>, <span class="dt">i32</span> <span class="fu">%res</span>)
<span class="kw">ret</span> <span class="dt">i32</span> <span class="fu">%res</span>
}
<span class="kw">define</span> <span class="dt">i32</span> <span class="fu">@mul</span>(<span class="dt">i32</span>* <span class="fu">%a</span>, <span class="dt">i32</span>* <span class="fu">%b</span>) {
<span class="co">; similar as above</span>
<span class="fu">%str</span> = <span class="kw">bitcast</span> [<span class="dv">15</span> x <span class="dt">i8</span>]* <span class="fu">@.comp_str</span> <span class="kw">to</span> <span class="dt">i8</span>*
<span class="fu">%val_a</span> = <span class="kw">load</span> <span class="dt">i32</span>, <span class="dt">i32</span>* <span class="fu">%a</span>
<span class="fu">%val_b</span> = <span class="kw">load</span> <span class="dt">i32</span>, <span class="dt">i32</span>* <span class="fu">%b</span>
<span class="fu">%res</span> = <span class="kw">mul</span> <span class="dt">i32</span> <span class="fu">%val_a</span>, <span class="fu">%val_b</span>
<span class="kw">call</span> <span class="dt">i32</span> (<span class="dt">i8</span>*, ...) <span class="fu">@printf</span>(<span class="dt">i8</span>* <span class="fu">%str</span>, <span class="dt">i32</span> <span class="fu">%val_a</span>, [<span class="dv">1</span> x <span class="dt">i8</span>] c<span class="st">"*"</span>, <span class="dt">i32</span> <span class="fu">%val_b</span>, <span class="dt">i32</span> <span class="fu">%res</span>)
<span class="kw">ret</span> <span class="dt">i32</span> <span class="fu">%res</span>
}</code></pre></div>
<!---
-->
<noscript>Your browser does not support JavaScript!</noscript>
<!-- #EndTemplate -->
</td></tr></tbody></table></body></html>