-
Notifications
You must be signed in to change notification settings - Fork 29
/
tiger.html
2649 lines (2140 loc) · 108 KB
/
tiger.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
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<html lang="en">
<head>
<title>Tiger Compiler Reference Manual</title>
<meta http-equiv="Content-Type" content="text/html">
<meta name="description" content="Tiger Compiler Reference Manual">
<meta name="generator" content="makeinfo 4.13">
<link title="Top" rel="top" href="#Top">
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
<!--
This document presents the EPITA version of the Tiger
language and compiler. This revision, $Id: 876d616066c9c622f713c5bb3a8d6d463cf780cf $, was last updated
September 3, 2013.
Copyright (C) 2002-2007 Akim Demaille.
Copyright (C) 2005-2010, 2012-2013 Roland Levillain.
Permission is granted to copy, distribute and/or modify this
document under the terms of the GNU Free Documentation License,
Version 1.1 or any later version published by the Free Software
Foundation; with no Invariant Sections, no Front-Cover texts and
with the no Back-Cover Texts. A copy of the license is included
in the section entitled ``GNU Free Documentation License.''
-->
<meta http-equiv="Content-Style-Type" content="text/css">
<style type="text/css"><!--
pre.display { font-family:inherit }
pre.format { font-family:inherit }
pre.smalldisplay { font-family:inherit; font-size:smaller }
pre.smallformat { font-family:inherit; font-size:smaller }
pre.smallexample { font-size:smaller }
pre.smalllisp { font-size:smaller }
span.sc { font-variant:small-caps }
span.roman { font-family:serif; font-weight:normal; }
span.sansserif { font-family:sans-serif; font-weight:normal; }
body {
padding: 2em 1em 2em 70px;
margin: 0;
font-family: sans-serif;
color: black;
background: white;
background-position: top left;
background-attachment: fixed;
background-repeat: no-repeat;
}
:link { color: #00C; background: transparent }
:visited { color: #609; background: transparent }
a:active { color: #C00; background: transparent }
a:link img, a:visited img { border-style: none } /* no border on img links */
a img { color: white; } /* trick to hide the border in Netscape 4 */
@media all { /* hide the next rule from Netscape 4 */
a img { color: inherit; } /* undo the color change above */
}
th, td { /* ns 4 */
font-family: sans-serif;
}
h1, h2, h3, h4, h5, h6 { text-align: left }
/* background should be transparent, but WebTV has a bug */
h1, h2, h3 { color: #005A9C; background: white }
h1 { font: 170% sans-serif }
h2 { font: 140% sans-serif }
h3 { font: 120% sans-serif }
h4 { font: bold 100% sans-serif }
h5 { font: italic 100% sans-serif }
h6 { font: small-caps 100% sans-serif }
.hide { display: none }
div.head { margin-bottom: 1em }
div.head h1 { margin-top: 2em; clear: both }
div.head table { margin-left: 2em; margin-top: 2em }
p.copyright { font-size: small }
p.copyright small { font-size: small }
@media screen { /* hide from IE3 */
a[href]:hover { background: #ffa }
}
pre { margin-left: 2em }
/*
p {
margin-top: 0.6em;
margin-bottom: 0.6em;
}
*/
dt, dd { margin-top: 0; margin-bottom: 0 } /* opera 3.50 */
dt { font-weight: bold }
pre, code { font-family: monospace } /* navigator 4 requires this */
ul.toc {
list-style: disc; /* Mac NS has problem with 'none' */
list-style: none;
}
@media aural {
h1, h2, h3 { stress: 20; richness: 90 }
.hide { speak: none }
p.copyright { volume: x-soft; speech-rate: x-fast }
dt { pause-before: 20% }
pre { speak-punctuation: code }
}
/*
* Style sheet for the HTML 4.0 specification
* $Id: default.css,v 1.13 1999/03/08 17:25:02 ijacobs Exp $
*/
div.example {
width: 100%;
color: black;
}
div.dtd-example {
width: 100%;
color: black;
}
tt.example {
color: maroon;
margin-left: 1em;
}
pre {
color: maroon;
margin-left: 1em;
}
div.dtd-fragment {
width: 100%;
border: none;
background-color: #eee;
}
pre.dtd-fragment {
margin-left: 0;
}
pre.dtd {
color: black;
margin-left: 0;
}
div.illegal-example {
width: 100%;
color: red;
border: solid red;
}
div.illegal-example p {
color: black;
}
div.deprecated-example {
width: 100%;
color: red;
border: solid rgb(255,165,0); /* orange */
}
div.deprecated-example p {
color: black;
}
div.note {
color: green;
margin-left: 1em;
}
p.note {
color: green;
margin-left: 1em;
}
ul.toc {
list-style-type: none;
}
a.normref {
color : red;
}
a.informref {
color : green;
}
DIV.subtoc {padding: 1em; border: solid thin; margin: 1em 0;
background: #ddd}
body {
background-image: url(tiger.img/tiger.png);
}
--></style>
</head>
<body>
<h1 class="settitle">Tiger Compiler Reference Manual</h1>
<div class="node">
<a name="Top"></a>
<p><hr>
Next: <a rel="next" accesskey="n" href="#Tiger-Language-Reference-Manual">Tiger Language Reference Manual</a>,
Up: <a rel="up" accesskey="u" href="#dir">(dir)</a>
</div>
<h2 class="unnumbered">The Tiger Project</h2>
<p>This document describes the Tiger project for <acronym><span class="sc">epita</span></acronym>
students as of
September 3, 2013. It is available under various forms:
<ul>
<li><a href="http://www.lrde.epita.fr/~akim/ccmp/tiger.html">Tiger manual in a single <acronym><span class="sc">html</span></acronym> file</a>.
<li><a href="http://www.lrde.epita.fr/~akim/ccmp/tiger.split">Tiger manual in several <acronym><span class="sc">html</span></acronym> files</a>.
<li><a href="http://www.lrde.epita.fr/~akim/ccmp/tiger.pdf">Tiger manual in <acronym><span class="sc">pdf</span></acronym></a>.
<li><a href="http://www.lrde.epita.fr/~akim/ccmp/tiger.txt">Tiger manual in text</a>.
<li><a href="http://www.lrde.epita.fr/~akim/ccmp/tiger.info">Tiger manual in Info</a>.
</ul>
<p>More information is available on the <a href="http://tiger.lrde.epita.fr/"><acronym><span class="sc">epita</span></acronym> Tiger Compiler Project Home Page</a>.
<p>Tiger is derived from a language introduced by
<a href="http://www.cs.princeton.edu/~appel/">Andrew Appel</a> in his book
<a href="http://www.cs.princeton.edu/~appel/modern/">Modern Compiler Implementation</a>. This document is by no means sufficient to produce an
actual Tiger compiler, nor to understand compilation. You are
<strong>strongly</strong> encouraged to buy and read Appel's book: it is an
<em>excellent</em> book.
<p>There are several differences with the original book, the most important
being that <acronym><span class="sc">epita</span></acronym> students have to implement this compiler <strong>in C++
and using modern object oriented programming techniques</strong>. You ought to
buy the original book, nevertheless, pay extreme attention to
implementing the version of the language specified below, not that of
the book.
<div class="contents">
<h2>Table of Contents</h2>
<ul>
<li><a name="toc_Top" href="#Top">The Tiger Project</a>
<li><a name="toc_Tiger-Language-Reference-Manual" href="#Tiger-Language-Reference-Manual">1 Tiger Language Reference Manual</a>
<ul>
<li><a href="#Lexical-Specifications">1.1 Lexical Specifications</a>
<li><a href="#Syntactic-Specifications">1.2 Syntactic Specifications</a>
<li><a href="#Semantics">1.3 Semantics</a>
<ul>
<li><a href="#Declarations">1.3.1 Declarations</a>
<ul>
<li><a href="#Type-Declarations">1.3.1.1 Type Declarations</a>
<li><a href="#Variable-Declarations">1.3.1.2 Variable Declarations</a>
<li><a href="#Function-Declarations">1.3.1.3 Function Declarations</a>
<li><a href="#Method-Declarations">1.3.1.4 Method Declarations</a>
</li></ul>
<li><a href="#Expressions">1.3.2 Expressions</a>
</li></ul>
</li></ul>
<li><a name="toc_Language-Extensions" href="#Language-Extensions">2 Language Extensions</a>
<ul>
<li><a href="#Additional-Lexical-Specifications">2.1 Additional Lexical Specifications</a>
<li><a href="#Additional-Syntactic-Specifications">2.2 Additional Syntactic Specifications</a>
<li><a href="#Additional-Semantics">2.3 Additional Semantics</a>
</li></ul>
<li><a name="toc_Predefined-Entities" href="#Predefined-Entities">3 Predefined Entities</a>
<ul>
<li><a href="#Predefined-Types">3.1 Predefined Types</a>
<li><a href="#Predefined-Functions">3.2 Predefined Functions</a>
</li></ul>
<li><a name="toc_Implementation" href="#Implementation">4 Implementation</a>
<ul>
<li><a href="#Invoking-tc">4.1 Invoking <samp><span class="command">tc</span></samp></a>
<li><a href="#Errors">4.2 Errors</a>
<li><a href="#Extensions">4.3 Extensions</a>
</li></ul>
<li><a name="toc_The-Reference-Implementation" href="#The-Reference-Implementation">5 The Reference Implementation</a>
</li></ul>
</div>
<ul class="menu">
<li><a accesskey="1" href="#Tiger-Language-Reference-Manual">Tiger Language Reference Manual</a>: The Tiger Language Definition
<li><a accesskey="2" href="#Language-Extensions">Language Extensions</a>: Additional constructions used internally
<li><a accesskey="3" href="#Predefined-Entities">Predefined Entities</a>: Primitive Functions and Types
<li><a accesskey="4" href="#Implementation">Implementation</a>: The <samp><span class="command">tc</span></samp> Tiger Compiler
<li><a accesskey="5" href="#The-Reference-Implementation">The Reference Implementation</a>: The compiler of the <acronym><span class="sc">lrde</span></acronym>
</li></ul>
<p>--- The Detailed Node Listing ---
<p>Tiger Language Reference Manual
</p>
<ul class="menu">
<li><a accesskey="6" href="#Lexical-Specifications">Lexical Specifications</a>: Tokens
<li><a accesskey="7" href="#Syntactic-Specifications">Syntactic Specifications</a>: <acronym><span class="sc">ebnf</span></acronym> grammar
<li><a accesskey="8" href="#Semantics">Semantics</a>: The meaning of Life, Universe and the rest
</li></ul>
<p>Semantics
</p>
<ul class="menu">
<li><a accesskey="9" href="#Declarations">Declarations</a>: The semantics of declarations
<li><a href="#Expressions">Expressions</a>: The semantics of expressions
</li></ul>
<p>Declarations
</p>
<ul class="menu">
<li><a href="#Type-Declarations">Type Declarations</a>: Semantics of type constructions
<li><a href="#Variable-Declarations">Variable Declarations</a>: Semantics of variable definitions
<li><a href="#Function-Declarations">Function Declarations</a>: Function and primitive declaration semantics
<li><a href="#Method-Declarations">Method Declarations</a>: Method declaration semantics
</li></ul>
<p>Language Extensions
</p>
<ul class="menu">
<li><a href="#Additional-Lexical-Specifications">Additional Lexical Specifications</a>: New Tokens
<li><a href="#Additional-Syntactic-Specifications">Additional Syntactic Specifications</a>: <acronym><span class="sc">ebnf</span></acronym> grammar extension
<li><a href="#Additional-Semantics">Additional Semantics</a>: Beyond Life, the Universe and Everything
</li></ul>
<p>Predefined Entities
</p>
<ul class="menu">
<li><a href="#Predefined-Types">Predefined Types</a>: Built-in types
<li><a href="#Predefined-Functions">Predefined Functions</a>: Primitives
</li></ul>
<p>Implementation
</p>
<ul class="menu">
<li><a href="#Invoking-tc">Invoking tc</a>: Command line options
<li><a href="#Errors">Errors</a>: Handling invalid input
<li><a href="#Extensions">Extensions</a>: Making extensions to your compiler
</li></ul>
<p>The Reference Implementation
</ul>
<!-- ====================================== Tiger Language Reference Manual -->
<div class="node">
<a name="Tiger-Language-Reference-Manual"></a>
<p><hr>
Next: <a rel="next" accesskey="n" href="#Language-Extensions">Language Extensions</a>,
Previous: <a rel="previous" accesskey="p" href="#Top">Top</a>,
Up: <a rel="up" accesskey="u" href="#Top">Top</a>
</div>
<h2 class="chapter">1 Tiger Language Reference Manual</h2>
<p>This document defines the Tiger language, derived from a
language introduced by Andrew Appel in his “Modern Compiler
Implementation” books (see <a href="assignments.html#Modern-Compiler-Implementation">Modern Compiler Implementation</a>). We insist so that our
students buy this book, so we refrained from publishing a complete
description of the language. Unfortunately, recent editions of this
series of book no longer address Tiger (see <a href="assignments.html#In-Java-_002d-Second-Edition">In Java - Second Edition</a>), and therefore they no
longer include a definition of the Tiger compiler. As a result,
students were more inclined to xerox the books, rather than buying newer
editions. To fight this trend, we decided to publish a complete
definition of the language. Of course, the definition below is not a
verbatim copy from the original language definition: these words are
ours.
<ul class="menu">
<li><a accesskey="1" href="#Lexical-Specifications">Lexical Specifications</a>: Tokens
<li><a accesskey="2" href="#Syntactic-Specifications">Syntactic Specifications</a>: <acronym><span class="sc">ebnf</span></acronym> grammar
<li><a accesskey="3" href="#Semantics">Semantics</a>: The meaning of Life, Universe and the rest
</ul>
<!-- Lexical Specifications -->
<div class="node">
<a name="Lexical-Specifications"></a>
<p><hr>
Next: <a rel="next" accesskey="n" href="#Syntactic-Specifications">Syntactic Specifications</a>,
Up: <a rel="up" accesskey="u" href="#Tiger-Language-Reference-Manual">Tiger Language Reference Manual</a>
</div>
<h3 class="section">1.1 Lexical Specifications</h3>
<dl>
<dt><dfn>Keywords</dfn><dd>‘<samp><span class="samp">array</span></samp>’, ‘<samp><span class="samp">if</span></samp>’, ‘<samp><span class="samp">then</span></samp>’, ‘<samp><span class="samp">else</span></samp>’, ‘<samp><span class="samp">while</span></samp>’,
‘<samp><span class="samp">for</span></samp>’, ‘<samp><span class="samp">to</span></samp>’, ‘<samp><span class="samp">do</span></samp>’, ‘<samp><span class="samp">let</span></samp>’, ‘<samp><span class="samp">in</span></samp>’, ‘<samp><span class="samp">end</span></samp>’,
‘<samp><span class="samp">of</span></samp>’, ‘<samp><span class="samp">break</span></samp>’, ‘<samp><span class="samp">nil</span></samp>’, ‘<samp><span class="samp">function</span></samp>’, ‘<samp><span class="samp">var</span></samp>’,
‘<samp><span class="samp">type</span></samp>’, ‘<samp><span class="samp">import</span></samp>’ and ‘<samp><span class="samp">primitive</span></samp>’
<br><dt><dfn>Object-related keywords</dfn><dd>The keywords ‘<samp><span class="samp">class</span></samp>’, ‘<samp><span class="samp">extends</span></samp>’, ‘<samp><span class="samp">method</span></samp>’ and ‘<samp><span class="samp">new</span></samp>’
are reserved for object-related constructions. They are valid keywords
when the object extension of the language is enabled, and reserved
words if this extension is disabled (i.e., they cannot be used as
identifiers in object-less syntax).
<br><dt><dfn>Symbols</dfn><dd>‘<samp><span class="samp">,</span></samp>’, ‘<samp><span class="samp">:</span></samp>’, ‘<samp><span class="samp">;</span></samp>’, ‘<samp><span class="samp">(</span></samp>’, ‘<samp><span class="samp">)</span></samp>’, ‘<samp><span class="samp">[</span></samp>’, ‘<samp><span class="samp">]</span></samp>’,
‘<samp><span class="samp">{</span></samp>’, ‘<samp><span class="samp">}</span></samp>’, ‘<samp><span class="samp">.</span></samp>’, ‘<samp><span class="samp">+</span></samp>’, ‘<samp><span class="samp">-</span></samp>’, ‘<samp><span class="samp">*</span></samp>’, ‘<samp><span class="samp">/</span></samp>’,
‘<samp><span class="samp">=</span></samp>’, ‘<samp><span class="samp"><></span></samp>’, ‘<samp><span class="samp"><</span></samp>’, ‘<samp><span class="samp"><=</span></samp>’, ‘<samp><span class="samp">></span></samp>’, ‘<samp><span class="samp">>=</span></samp>’, ‘<samp><span class="samp">&</span></samp>’,
‘<samp><span class="samp">|</span></samp>’, and ‘<samp><span class="samp">:=</span></samp>’
<br><dt><dfn>White characters</dfn><dd>Space and tabulations are the only white space characters supported.
Both count as a single character when tracking locations.
<br><dt><dfn>End-of-line</dfn><dd>End of lines are ‘<samp><span class="samp">\n\r</span></samp>’, and ‘<samp><span class="samp">\r\n</span></samp>’, and ‘<samp><span class="samp">\r</span></samp>’, and
‘<samp><span class="samp">\n</span></samp>’, freely intermixed.
<br><dt><dfn>Strings</dfn><dd>The strings are <acronym><span class="sc">ansi</span></acronym>-C strings: enclosed by ‘<samp><span class="samp">"</span></samp>’, with support for
the following escapes:
<dl>
<dt>‘<samp><span class="samp">\a</span></samp>’, ‘<samp><span class="samp">\b</span></samp>’, ‘<samp><span class="samp">\f</span></samp>’, ‘<samp><span class="samp">\n</span></samp>’, ‘<samp><span class="samp">\r</span></samp>’, ‘<samp><span class="samp">\t</span></samp>’, ‘<samp><span class="samp">\v</span></samp>’<dd>control characters.
<br><dt>\<var>num</var><dd>The character which code is <var>num</var> in octal. Valid character codes
belong to an extended (8-bit) <acronym><span class="sc">ascii</span></acronym> set, i.e. values between 0 and 255
in decimal (0 and 377 in octal). <var>num</var> is composed of exactly three
octal characters, and any invalid value is a scan error.
<br><dt>\x<var>num</var><dd>The character which code is <var>num</var> in hexadecimal (upper case or
lower case or mixed). <var>num</var> is composed of exactly 2 hexadecimal
characters. Likewise, expected values belong to an extended (8-bit)
<acronym><span class="sc">ascii</span></acronym> set.
<br><dt>‘<samp><span class="samp">\\</span></samp>’<dd>A single backslash.
<br><dt>‘<samp><span class="samp">\"</span></samp>’<dd>A double quote.
<br><dt>\<var>character</var><dd>If no rule above applies, this is an error.
</dl>
<p>All the other characters are plain characters and are to be included in
the string. In particular, multi-line strings are allowed.
<br><dt><dfn>Comments</dfn><dd>Like C comments, but can be nested:
<pre class="example"> Code
/* Comment
/* Nested comment */
Comment */
Code
</pre>
<br><dt><dfn>Identifiers</dfn><dd>Identifiers start with a letter, followed by any number of alphanumeric
characters plus the underscore. Identifiers are case sensitive.
Moreover, the special <strong>_main</strong> string is also accepted as a valid
identifier.
<pre class="display"> id ::= letter { letter | digit | <strong>_</strong> } | <strong>_main</strong>
letter ::=
<strong>a</strong> | <strong>b</strong> | <strong>c</strong> | <strong>d</strong> | <strong>e</strong> | <strong>f</strong> | <strong>g</strong> | <strong>h</strong> | <strong>i</strong> | <strong>j</strong> | <strong>k</strong> | <strong>l</strong> |
<strong>m</strong> | <strong>n</strong> | <strong>o</strong> | <strong>p</strong> | <strong>q</strong> | <strong>r</strong> | <strong>s</strong> | <strong>t</strong> | <strong>u</strong> | <strong>v</strong> | <strong>w</strong> | <strong>x</strong> |
<strong>y</strong> | <strong>z</strong> |
<strong>A</strong> | <strong>B</strong> | <strong>C</strong> | <strong>D</strong> | <strong>E</strong> | <strong>F</strong> | <strong>G</strong> | <strong>H</strong> | <strong>I</strong> | <strong>J</strong> | <strong>K</strong> | <strong>L</strong> |
<strong>M</strong> | <strong>N</strong> | <strong>O</strong> | <strong>P</strong> | <strong>Q</strong> | <strong>R</strong> | <strong>S</strong> | <strong>T</strong> | <strong>U</strong> | <strong>V</strong> | <strong>W</strong> | <strong>X</strong> |
<strong>Y</strong> | <strong>Z</strong>
digit ::= <strong>0</strong> | <strong>1</strong> | <strong>2</strong> | <strong>3</strong> | <strong>4</strong> | <strong>5</strong> | <strong>6</strong> | <strong>7</strong> | <strong>8</strong> | <strong>9</strong>
</pre>
<br><dt><dfn>Numbers</dfn><dd>There are only integers in Tiger.
<pre class="display"> integer ::= digit { digit }
op ::= <strong>+</strong> | <strong>-</strong> | <strong>*</strong> | <strong>/</strong> | <strong>=</strong> | <strong><></strong> | <strong>></strong> | <strong><</strong> | <strong>>=</strong> | <strong><=</strong> | <strong>&</strong> | <strong>|</strong>
</pre>
<br><dt><dfn>Invalid characters</dfn><dd>Any other character is invalid.
</dl>
<!-- Syntactic Specifications -->
<div class="node">
<a name="Syntactic-Specifications"></a>
<p><hr>
Next: <a rel="next" accesskey="n" href="#Semantics">Semantics</a>,
Previous: <a rel="previous" accesskey="p" href="#Lexical-Specifications">Lexical Specifications</a>,
Up: <a rel="up" accesskey="u" href="#Tiger-Language-Reference-Manual">Tiger Language Reference Manual</a>
</div>
<h3 class="section">1.2 Syntactic Specifications</h3>
<p>We use Extended <acronym><span class="sc">bnf</span></acronym>, with ‘<samp><span class="samp">[</span></samp>’ and ‘<samp><span class="samp">]</span></samp>’ for zero or once, and
‘<samp><span class="samp">{</span></samp>’ and ‘<samp><span class="samp">}</span></samp>’ for any number of repetition including zero.
<pre class="example"> program ::=
exp
| decs
exp ::=
<i># Literals.</i>
<strong>nil</strong>
| integer
| string
<i># Array and record creations.</i>
| type-id <strong>[</strong> exp <strong>]</strong> <strong>of</strong> exp
| type-id <strong>{</strong>[ id <strong>=</strong> exp { <strong>,</strong> id <strong>=</strong> exp } ] <strong>}</strong>
<i># Object creation.</i>
| <strong>new</strong> type-id
<i># Variables, field, elements of an array.</i>
| lvalue
<i># Function call.</i>
| id <strong>(</strong> [ exp { <strong>,</strong> exp }] <strong>)</strong>
<i># Method call.</i>
| lvalue <strong>.</strong> id <strong>(</strong> [ exp { <strong>,</strong> exp }] <strong>)</strong>
<i># Operations.</i>
| <strong>-</strong> exp
| exp op exp
| <strong>(</strong> exps <strong>)</strong>
<i># Assignment.</i>
| lvalue <strong>:=</strong> exp
<i># Control structures.</i>
| <strong>if</strong> exp <strong>then</strong> exp [<strong>else</strong> exp]
| <strong>while</strong> exp <strong>do</strong> exp
| <strong>for</strong> id <strong>:=</strong> exp <strong>to</strong> exp <strong>do</strong> exp
| <strong>break</strong>
| <strong>let</strong> decs <strong>in</strong> exps <strong>end</strong>
lvalue ::= id
| lvalue <strong>.</strong> id
| lvalue <strong>[</strong> exp <strong>]</strong>
exps ::= [ exp { <strong>;</strong> exp } ]
decs ::= { dec }
dec ::=
<i># Type declaration.</i>
<strong>type</strong> id <strong>=</strong> ty
<i># Class definition (alternative form).</i>
| <strong>class</strong> id [ <strong>extends</strong> type-id ] <strong>{</strong> classfields <strong>}</strong>
<i># Variable declaration.</i>
| vardec
<i># Function declaration.</i>
| <strong>function</strong> id <strong>(</strong> tyfields <strong>)</strong> [ <strong>:</strong> type-id ] <strong>=</strong> exp
<i># Primitive declaration.</i>
| <strong>primitive</strong> id <strong>(</strong> tyfields <strong>)</strong> [ <strong>:</strong> type-id ]
<i># Importing a set of declarations.</i>
| <strong>import</strong> string
vardec ::= <strong>var</strong> id [ <strong>:</strong> type-id ] <strong>:=</strong> exp
classfields ::= { classfield }
<i># Class fields.</i>
classfield ::=
<i># Attribute declaration.</i>
vardec
<i># Method declaration.</i>
| <strong>method</strong> id <strong>(</strong> tyfields <strong>)</strong> [ <strong>:</strong> type-id ] <strong>=</strong> exp
<i># Types.</i>
ty ::=
<i># Type alias.</i>
type-id
<i># Record type definition.</i>
| <strong>{</strong> tyfields <strong>}</strong>
<i># Array type definition.</i>
| <strong>array</strong> <strong>of</strong> type-id
<i># Class definition (canonical form).</i>
| <strong>class</strong> [ <strong>extends</strong> type-id ] <strong>{</strong> classfields <strong>}</strong>
tyfields ::= [ id <strong>:</strong> type-id { <strong>,</strong> id <strong>:</strong> type-id } ]
type-id ::= id
op ::= <strong>+</strong> | <strong>-</strong> | <strong>*</strong> | <strong>/</strong> | <strong>=</strong> | <strong><></strong> | <strong>></strong> | <strong><</strong> | <strong>>=</strong> | <strong><=</strong> | <strong>&</strong> | <strong>|</strong>
</pre>
<p>Precedence of the <var>op</var> (high to low):
<pre class="example"> * /
+ -
>= <= = <> < >
&
|
</pre>
<p>Comparison operators (<code><</code>, <code><=</code>, <code>=</code>, <code><></code>,
<code>></code>, <code>>=</code>) are not associative. All the remaining operators
are left-associative.
<!-- Semantics -->
<div class="node">
<a name="Semantics"></a>
<p><hr>
Previous: <a rel="previous" accesskey="p" href="#Syntactic-Specifications">Syntactic Specifications</a>,
Up: <a rel="up" accesskey="u" href="#Tiger-Language-Reference-Manual">Tiger Language Reference Manual</a>
</div>
<h3 class="section">1.3 Semantics</h3>
<ul class="menu">
<li><a accesskey="1" href="#Declarations">Declarations</a>: The semantics of declarations
<li><a accesskey="2" href="#Expressions">Expressions</a>: The semantics of expressions
</ul>
<div class="node">
<a name="Declarations"></a>
<p><hr>
Next: <a rel="next" accesskey="n" href="#Expressions">Expressions</a>,
Up: <a rel="up" accesskey="u" href="#Semantics">Semantics</a>
</div>
<h4 class="subsection">1.3.1 Declarations</h4>
<dl>
<!-- -->
<dt><em>import</em><dd>An <code>import</code> clause denote the same expression where it was
(recursively) replaced by the set of declarations its corresponding
import-file contains. An import-file has the following syntax (see
<a href="#Syntactic-Specifications">Syntactic Specifications</a>, for a definition of the symbols):
<pre class="example"> import-file ::= decs
</pre>
<p>Because the syntax is different, it is convenient to use another
extension. We use <samp><span class="file">*.tih</span></samp> for files to import, for instance:
<pre class="example"> /* fortytwo-fn.tih. */
function fortytwo () : int = 42
/* fortytwo-var.tih. */
import "fortytwo-fn.tih"
var fortytwo := fortytwo ()
/* fortytwo-main.tig. */
let
import "fortytwo-var.tih"
in
print_int (fortytwo); print ("\n")
end
</pre>
<p class="noindent">is rigorously equivalent to:
<pre class="example"> let
function fortytwo () : int = 42
var fortytwo := fortytwo ()
in
print_int (fortytwo); print ("\n")
end
</pre>
<p>There can never be a duplicate-name conflict between declarations from
different files. For instance:
<pre class="example"> /* 1.tih */
function one () : int = 1
let
import "1.tih"
import "1.tih"
in
one () = one ()
end
</pre>
<p class="noindent">is <em>valid</em> although
<pre class="example"> let
function one () : int = 1
function one () : int = 1
in
one () = one ()
end
</pre>
<p class="noindent">is not: the function <code>one</code> is defined twice in a row of function
declarations.
<p>Importing a nonexistent file is an error. A imported file may not
include itself, directly or indirectly. Both these errors must be
diagnosed, with status set to 1 (see <a href="#Errors">Errors</a>).
<p>When processing an import directive, the compiler starts looking for
files in the current directory, then in all the directories of the
include path, in order.
<!-- -->
<br><dt><em>name spaces</em><dd><a name="index-name-spaces-1"></a>There are three name spaces: types, variables and functions. The
original language definition features two: variables and functions share
the same name space. The motivation, as noted by Sébastien Carlier, is
that in FunTiger, in the second part of the book, functions can be
assigned to variables:
<pre class="example"> let
type a = {a : int}
var a := 0
function a (a : a) : a = a{a = a.a}
in
a (a{a = a})
end
</pre>
<p>Three name spaces support is easier to implement.
</dl>
<ul class="menu">
<li><a accesskey="1" href="#Type-Declarations">Type Declarations</a>: Semantics of type constructions
<li><a accesskey="2" href="#Variable-Declarations">Variable Declarations</a>: Semantics of variable definitions
<li><a accesskey="3" href="#Function-Declarations">Function Declarations</a>: Function and primitive declaration semantics
<li><a accesskey="4" href="#Method-Declarations">Method Declarations</a>: Method declaration semantics
</ul>
<div class="node">
<a name="Type-Declarations"></a>
<p><hr>
Next: <a rel="next" accesskey="n" href="#Variable-Declarations">Variable Declarations</a>,
Up: <a rel="up" accesskey="u" href="#Declarations">Declarations</a>
</div>
<h5 class="subsubsection">1.3.1.1 Type Declarations</h5>
<dl>
<dt><em>arrays</em><dd><a name="index-arrays-2"></a>The size of the array does not belong to the type. Index of arrays
starts from 0 and ends at size - 1.
<pre class="example"> let
type int_array = array of int
var table := int_array[100] of 0
in
...
end
</pre>
<p>Arrays are initialized with the <em>same</em> instance of value. This
leads to aliasing for entities with pointer semantics (strings, arrays
and records).
<pre class="example"> let
type rec = { val : int }
type rec_arr = array of rec
var table := rec_arr[2] of rec { val = 42 }
in
table[0].val := 51
/* Now table[1].val = 51. */
end
</pre>
<p class="noindent">Use a loop to instantiate several initialization values.
<pre class="example"> let
type rec = { val : int }
type rec_arr = array of rec
var table := rec_arr[2] of nil
in
for i := 0 to 1 do
table[i] := rec { val = 42 };
table[0].val := 51
/* table[1].val = 42. */
end
</pre>
<!-- -->
<br><dt><em>records</em><dd>Records are defined by a list of fields between braces. Fields are
described as “fieldname : type-id” and are separated by a coma. Field
names are unique for a given record type.
<pre class="example"> let
type indexed_string = {index : int, value : string}
in
...
end
</pre>
<!-- -->
<br><dt><em>classes</em><dd>(See also <a href="#Method-Declarations">Method Declarations</a>.)
<p>Classes define a set of attributes and methods. Empty classes are
valid. Attribute declaration is like variable declaration; method
declaration is similar to function declaration, but uses the keyword
<code>method</code> instead of <code>function</code>.
<p>There are two ways to declare a class. The first version (known as
<em>canonical</em>) uses <code>type</code>, and is similar to record and array
declaration :
<pre class="example"> let
type Foo = class extends Object
{
var bar := 42
method baz () = print ("Foo.\n")
}
in
/* ... */
end
</pre>
<p>The second version (known as <em>alternative</em> or Appel's) doesn't make
use of <code>type</code>, but introduces classes declarations directly. This
is the syntax described by Andrew Appel in his books:
<pre class="example"> let
class Foo extends Object
{
var bar := 42
method baz () = print ("Foo.\n")
}
in
/* ... */
end
</pre>
<p>For simplicity reasons, constructs using the alternative syntax are
considered as <em>syntactic sugar</em> for the canonical syntax, and are
<em>desugared</em> by the parser into this first form, using the following
transformation:
<pre class="example"> <strong>class</strong> <var>Name</var> [ <strong>extends</strong> <var>Super</var> ] <strong>{</strong> <var>Classfields</var> <strong>}</strong>
=> <strong>type</strong> <var>Name</var> <strong>=</strong> <strong>class</strong> [ <strong>extends</strong> <var>Super</var> ] <strong>{</strong> <var>Classfields</var> <strong>}</strong>
</pre>
<p>where <var>Name</var>, <var>Super</var> and <var>Classfields</var> are respectively the
class name, the super class name and the contents of the class
(attributes and methods) of the class.
<p>In the rest of the section, Appel's form will be often used, to offer a
uniform reading with his books, but remember that the <em>main syntax
is the other one</em>, and <em>Appel's syntax is to be desugared into the
canonical one</em>.
<pre class="sp">
</pre>
Declarations of class members follow the same rules as variable and
function declarations: <em>consecutive</em> method declarations constitute
a block (or chunk) of methods, while a block of attributes contains only
<em>a single one</em> attribute declaration (several attribute
declarations thus form several blocks). An extra rule holds for class
members: there shall be no two attributes with the same name in the same
class definition, nor two methods with the name.
<pre class="example"> let
class duplicate_attrs
{
var a := 1
method m () = ()
/* Error, duplicate attribute in the same class. */
var a := 2
}
class duplicate_meths
{
method m () = ()
var a := 1
/* Error, duplicate method in the same class. */
method m () = ()
}
in
end
</pre>
<p class="noindent">Note that this last rule applies only to the strict scope of the class,
not to the scopes of inner classes.
<pre class="example"> let
type C = class
{
var a := 1
method m () =
let
type D = class
{
/* These members have same names as C's, but this is allowed
since they are not in the same scope. */
var a := 1
method m () = ()
}
in
end
}
in
end
</pre>
<pre class="sp">
</pre>
Objects of a given class are created using the keyword <code>new</code>.
There are no constructors in Tiger (nor destructors), so the
attributes are always initialized by the value given at their
declaration.
<pre class="example"> let
class Foo
{
var bar := 42
method baz () = print ("Foo.\n")
}
class Empty
{
}
var foo1 : Foo := new Foo
/* As for any variable, the type annotation is optional. */
var foo2 := new Foo
in
/* ... */
end
</pre>
<p>The access to a member (either an attribute or a method) of an object
from outside the class uses the <em>dotted</em> notation (as in C++, Java,
C#, etc.). There are no visibility qualifier/restriction (i.e., all
attributes of an object accessible in the current scope are accessible
in read and write modes), and all its methods can be called.
<pre class="example"> let
class Foo
{
var bar := 42
method baz () = print ("Foo.\n")
}
var foo := new Foo
in
print_int (foo.bar);
foo.baz ()
end
</pre>
<p>To access to a member (either an attribute or a method) from within the
class where it is defined, use the <code>self</code> identifier (equivalent to
C++'s Or Java's <em>this</em>), which refers to the current instance of the
object.
<pre class="example"> let
class Point2d
{
var row : int := 0
var col : int := 0
method print_row () = print_int (self.row)
method print_col () = print_int (self.col)
method print () =
(
print ("(");
self.print_row ();
print (", ");
self.print_col ();
print (")")
)
}
in
/* ... */
end
</pre>
<p>The use of <code>self</code> is mandatory to access a member of the class (or
of its super class(es)) from within the class. A variable or a method
not preceded by `<code>self.</code>' won't be looked up in the scope of the
class.
<pre class="example"> let
var a := 42
function m () = print ("m ()\n")
class C
{
var a := 51
method m () = print ("C.m ()\n")
method print_a () = (print_int (a); print ("\n"))
method print_self_a () = (print_int (self.a); print ("\n"))
method call_m () = m ()
method call_self_m () = self.m ()
}
var c := new C
in
c.print_a (); /* Print `42'. */
c.print_self_a (); /* Print `51'. */
c.call_m (); /* Print `m ()'. */
c.call_self_m () /* Print `C.m ()'. */
end
</pre>
<p>The Tiger language supports single inheritance thanks to the
keyword <code>extends</code>, so that a class can inherit from another class
declared previously, or declared in the same block of class
declarations. A class with no manifest inheritance (no <code>extends</code>
statement following the class name) automatically inherits from the
built-in class <code>Object</code> (this feature is an extension of Appel's
object-oriented proposal).
<p>Inclusion polymorphism is supported as well: when a class <var>Y</var>
inherits from a class <var>X</var> (directly or through several inheritance
links), any object of <var>Y</var> can <em>be seen as</em> an object of type
<var>X</var>. Hence, objects have two types: the static type, known at
compile time, and the dynamic (or exact) type, known at run time, which
is a subtype of (or identical to) the static type. Therefore, an object
of static type <var>Y</var> can be assigned to a variable of type <var>X</var>.
<pre class="example"> let
/* Manifest inheritance from Object: an A is an Object. */
class A extends Object {}
/* Implicit inheritance from Object: a B is an Object. */
class B {}
/* C is an A. */
class C extends A {}
var a : A := new A
var b : B := new B
var c1 : C := new C
/* When the type is not given explicitly, it is inferred from the
initialization; here, C2 has static and dynamic type C. */
var c2 := new C
/* This variable has static type A, but dynamic type C. */
var c3 : A := new C
in
/* Allowed (upcast). */
a := c1
/* Forbidden (downcast). */
/* c2 := a */
end
</pre>
<p>As stated before, a class can inherit from a class<a rel="footnote" href="#fn-1" name="fnd-1"><sup>1</sup></a>
declared previously (and visible in the scope), or from a class declared
in the same block of <em>type</em> declarations (recall that a class
declaration is in fact a type declaration). Recursive inheritance is
not allowed.
<pre class="example"> let
/* Allowed: A declared before B. */
class A {}