Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science 6.035, Spring 2010 Handout — Decaf Language Tuesday, Feb 2 The project for the course is to write a compiler for a language called Decaf. Decaf is a simple imperative language similar to C or Pascal. Lexical Considerations All Decaf keywords are lowercase. Keywords and identifiers are case-sensitive. For example, if is a keyword, but IF is a variable name; foo and Foo are two different names refe rr i n g to two distinct variables. The reserved words are: boolean break callout class continue else false for if int return true void Note that Program (see below) is not a keyword, but an identifier with a special meaning in certain circumstances. Comments are started by // and are terminated by the end of the line. White space may appear be tween any lexical tokens. White space is defined as one or more spaces, tabs, page and line-breaking characters, and comments. Keywords and identifiers must be separated by whit e space, or a token that is neither a keyword nor an identifier. For example, thisfortrue i s a single identifier, not three distinct keywords. If a sequence begins with an alphabetic character or an underscore, then it, and the longest sequence of characters following it forms a token. String lite r al s are composed of �char�s enclosed in double quotes. A character literal consists of a �char� enclosed in single quotes. Numbers in Decaf are 32 bit signed. That is, decimal values between -2147483648 and 2147483647. If a s eq ue nc e begins with 0x, th en these first two characters and the longest sequenc e of characters drawn from [0-9a-fA-F] form a hexadecimal integer literal . If a se q uen ce begins with a decimal digit (but not 0x), then the longest prefix of decimal digits forms a decimal integer literal. Note that range checking is perfor me d later. A long sequence of digits (e.g. 123456789123456789) is still scanned as a single token. A �char� is any printable ASCII character (ASCII values between decimal value 32 and 126, or octal 40 and 176) other than quote ("), single quote (’), or backslash (\), plus the 2-character sequences “\"” to denote quote, “\’” to denote single quote, “\\” to denote backslash, “\t” to denote a literal tab, or “\n” to denote newline. 1� � � � � � � � � � Reference Grammar Meta-notation: �foo� means foo is a nonterminal. foo (in bold font) means that foo is a terminal i.e., a token or a part of a token. � � x means zero or one occurrence of x, i.e., x is optional; note that brackets in quotes ′ [ ′ ′ ] ′ are terminals. x ∗ means zero or more occurrences of x. x + , a comma-separated list of one or more x’s. � � large braces are used for grouping; note that braces in quotes ′{′ ′}′ are terminals. | separates alternatives. ′ ′ hprogrami → class Program { ′ hfield decli ∗ hmethod decli ∗ } ′ hfield decli → htypei � hidi | hidi ′ [ ′ hint literali ′ ] ′ �+ , ; � � � �+ hmethod decli → htypei | void hidi ( htypei hidi , ) hblocki hblocki → ′ { ′ hvar decli ∗ hstatementi ∗′ } ′ hvar decli → htypei hidi+ , ; htypei → int | boolean hstatementi → hlocationi hassign opi hexpri ; | hmethod calli ; | if ( hexpri ) hblocki else hblocki | for hidi = hexp ri , hexpri hblocki | return hexpri ; | break ; | continue ; | hblocki hassign opi → = | += | -= hmethod calli → hmethod namei ( hexpri+ , ) | callout ( hstring literali , hcallout argi+ , ) hmethod name i → hidi hlocationi → hidi | hidi ′ [ ′ hexpri ′ ] ′ 2hexpri → hlocationi | hmethod calli | hliterali | hexpri hbin opi hexpri | - hexpri | ! hexpri | ( hexpri ) hcallout argi → hexpri | hstring literali hbin opi → harith opi | hrel opi | heq opi | hcond opi harith opi → + | - | * | / | % hrel opi → < | > | <= | >= heq opi → == | != hcond opi → && | || hliterali → hint literali | hchar literali | hbool literali hidi → halphai halpha numi ∗ halpha numi → halphai | hdigiti halphai → a | b | ... | z | A | B | ... | Z | hdigiti → 0 | 1 | 2 | ... | 9 hhex digiti → hdigiti | a | b | c | d | e | f | A | B | C | D | E | F hint literali → hdecimal literali | hhex literali hdecimal literali → hdigiti hdigiti ∗ hhex literali → 0x hhex digiti hhex digiti ∗ hbool literali → true | false hchar literali → ’ hchari ’ hstring literali → " hchari ∗ " Semantics A Decaf program consists of a si n gle class declaration for a class calle d Program. The class decla-ration consists of field declarations and method declarations. Field declarations introduce variables that can be accessed global l y by all methods in the program. Method declarati ons introduce func -tions/procedures. The program must contain a declaration for a method called main that has no parameters. Execution of a Decaf program starts at method main. 3Types There are two basic types in Decaf — int and boolean. In addition, there are arrays of integers (int [ N ]) and arrays of booleans (boolean [ N ]). Arrays may be declared only in the global (class declarati on ) scope. All arrays are one-dim ens i onal and have a compile-time fixed size. Arrays are indexed from 0 to N − 1, where N > 0 is the size of the array. The usual bracket notation is used to index ar r ays. Since arrays have a compile-time fixed size and cannot be declared as parameters (or local variables) , there i s no facility for querying the length of an array variable in Decaf. Scope Rules Decaf has simple and quite restrictive scope rules. All identifiers must be defined (textually) before use. For example: • a variable must be declared before it is used. • a method can be called only by code appearing after its header. (Note that