The More Definitive Guide to FLAME

CS326 Compilers - Spring 2001

Last update: April 4, 2001

FLAME is the language that you will be compiling for CS326. The name doesn't really mean much of anything except that, well, it has the word LAME in it and it gets right to heart of all programming languages--which is flame wars.

The language is largely derived from Pascal and similar languages. However, it has been greatly simplified to make your life a little easier. For instance, there are no pointers, records, multi-dimensional arrays, or objects. Similarly, the language is a little sparse when it comes to advanced features. Nevertheless, you should find it to be sufficiently challenging for an 8 week project.

Your task is to write a compiler for the FLAME language. Your compiler will read FLAME programs in the form of ".flm" source files and produce SPARC assembly code that can be compiled and executed on Sun workstations. Your first objective is to produce a compiler that works. However, compilers that produce optimized object code won't go unrewarded.

A Sample FLAME program

Here is a very simple FLAME program: 
fun quicksort(l:int, r:int, a:int[8192])
    i:int;
    j:int;
    x:int;
    w:int;
    tmp:int;
    done:int;
begin
    i := l;
    j := r;
    x := a[(l+r)/2];
    done := 0;
    while done == 0 do
        begin 
            while a[i] < x do
                i := i + 1;

            while x < a[j] do
                j := j - 1;

            if i <= j then
                begin 
                    tmp := a[i];
                    a[i] := a[j];
                    a[j] := tmp;
                    i:=i+1;
                    j:=j-1
                end;

            if i>j then
                done := 1
        end;

    if l<j then
        tmp := quicksort(l, j, a);

    if i<r then 
        tmp := quicksort(i, r, a)
end

fun main()
   v:int[8192];
   i:int;
   n:int;
begin
   print("Enter n: "); 
   read(n);
   i := 0;
   while i<n do
     begin
        read(v[i]);
        i := i+1
     end;
   quicksort(0, n-1, v);
   i := 0;
   while i<n-1 do
     begin
        write(v[i]); print(" ");
        if 0 < v[i] - v[i+1] then
        begin 
           print("Quicksort failed "); write(i); print("\n") ; return(0)
        end
        else
           i:=i+1
     end;
   write(v[i]);
   print("Success\n")
end

Program Structure

A FLAME program consists of one or more function declarations as shown in the above example. The general form of a function declaration is as follows:
fun name(arguments) locals begin statements end
Execution always starts in a function called main. This function takes no arguments and should return an integer to indicate success or failure. If a program does not define main, an error should be generated.

Statements

Within the body of a function, the following types of statements may appear: Anywhere a single statement is expected, multiple statements can be used provided that they are enclosed in a begin ... end block and separated by semicolons like this: 
begin
   statement1;
   statement2;
   ...
   statementn
end
It is important to note that a semicolon (;) is not used on the last statement of a block. This is because the semicolon is only used to separate multiple statements and is not a statement terminator.

The skip statement is used to denote an empty statement. It does nothing. For instance, an infinite loop would be written like this: 

while 1==1 do skip

The break statement is used to break out of a while loop. For instance: 

while expr do 
   begin
     ...
     ...
     break
     ...
   end

Data Types

FLAME only supports two basic datatypes In addition, fixed sized arrays of either type can be specified as follows: Arrays are always bounded and it is illegal for a program to access an element that is out of range. If this occurs, a FLAME program should generate a run-time error.

At the moment, FLAME doesn't have any support for characters or strings. Of course, something related to the implementation of this might make a good exam question.

Assignment

Assignment to a location is made as follows: The left hand side may either be the name of a variable or an array entry. Array indices must be integers. Expressions must be of the same type as the variable on the left-hand side. Otherwise, a type error should be generated.

Expressions

The following arithmetic operations are supported by FLAME: The type of an expression is determined by the types of its operands. It is illegal to mix operands of different types. However, the int() and float() operators can be used to perform an explicit type conversion.

A number is a literal appearing in a program and may be an integer such as "34" or a floating point number such as "2.8162". The type of a number is determined by its syntax (e.g., if it has a decimal point, it must be floating point). In addition, an integer literal can be promoted to floating point if it is used as part of a floating point expression.

An array index must always be an integer. If it is some other type (i.e., floating point), a type error should be generated.

The expression name(exprlist) denotes a function call. In this case, exprlist is a comma separated list of function arguments, each of which may be an expression.

Relational expressions

The following relational expressions can be used in conditional statements and while loops. In addition, relational expressions can be combined using and, or, and not like this: For example: 
if (n >= 2) and (n < 10) then statement

Functions

Functions are defined using the syntax For example: 
fun foo(n:int, f:float, d:int[32])
    temp1:int;
    temp2:float;
    p:int[32];
    begin
        statement1;
        statement2;
        ...
        statementn
    end
Each function argument must have a name and type as shown. Multiple arguments are separated by commas and a function may accept no arguments. Locals must be declared before the first begin and may include both variable declarations and function declarations. Each local is terminated by a semicolon.

A special feature of FLAME is that it supports nested function definitions. Nested functions are always defined in the locals section of a function definition like this: 

fun foo(n:int)
    i:int;
    j:int;

    /* A Nested function */
    fun bar(x:int, y:int)
        a:int;
        begin
             ...
        end;
  
    /* Start of the function foo */
    begin
        j := bar(n,i)
        ...
    end
Nested functions are only visible to statements in the function in which they are defined. That is, the function bar() above is only visible inside the function foo() and not anywhere else. Furthermore, nested functions use lexical scoping to bind to variable names. This means that the function bar() above is allowed to access the variables i,j, and n that are defined for foo() in addition to the variables x, y, and a that it received as parameters or defined as local variables. If a nested function redefines a variable already used in an outer function, the new definition is used (e.g., if bar() also defined a variable i, that variable would be different from the variable i defined in foo()).

The return type of a function is inferred by the type of the expression passed to the return statement. It is illegal for a function return two different types from different return statements. For example: 

fun foo(x:int)
    begin
        if x > 0 then
            return(3.4)
        else
            return(3)    /* Error! Inconsistent return type */
    end

Parameter Passing Conventions

When simple datatypes (int, float) are passed as function arguments, they are always passed by value. This means that a copy is made and that a function can modify the arguments without affecting their values in the calling function. When arrays are passed as arguments, they are passed by reference. This means that changes to an array will be reflected in both the current function and calling function.

I/O

I/O in FLAME is pretty lame. A few very simple I/O functions are supported by the language itself. The print statement is only used to print string literals to the output. For example: 
print("Hello World\n");
print("Please type something:");
The write statement is used to print the value of an expression to standard output. Its argument may be either an integer or floating point value.

The read statement is used to read a value from standard input into a given location. A location may be the name of a variable or an array location. The behavior of receiving invalid input is undefined (e.g., if a user types a floating point number where an integer is expected).

Comments and Formatting

Comments are denoted by enclosing text in /* ... */. Comments may span multiple lines, but may not be nested.

FLAME is not sensitive to whitespace or indentation. A program may be specified on one line if you want. Likewise, any statement can span multiple lines without any special line continuation characters.

Literals

Variable and function names (identifiers) may consist of letters, numbers, and the underscore (_) character. A name may not start with a digit. There is no limit on the length of a name.

An integer literal consists of one or more digits and does not include a preceding + or - sign (these are handled in the rules for an expression). It is illegal for an integer to have any leading zeroes. For example, "01234" is illegal. Of course, an integer can still have the value "0".

There are several ways to specify a floating point number:

In general a floating number number must always start with one or more digits followed by a decimal point or an "e" to indicate scientific notation. If more than one digit appears, no leading zeroes are allowed (e.g., "0123.45" and "0123e45" are illegal). After the decimal point, one or more digits may appear. In addition, scientific notation e[+-]nnnnn may be used as shown. For scientific notation, the sign is optional and is assumed to be positive if it is ommitted.

String literals are only used with the print statement. A string is enclosed in double quotes (") and may contain any combination of letters, digits, and special characters. A string may not span multiple lines. However, adjacent strings are concatenated to form a single string. For instance, writing "Hello" "World" is the same as "HelloWorld". In addition, FLAME recognizes the following character escape codes:

Miscellaneous

FLAME does not support global variables or heap allocated data--everything is stored on the stack. Therefore, you will not need to worry about dynamic memory allocation, implementing your own version of malloc(), or anything like that. However, you will have to sort out the complexity of having nested function scopes.

For this project, programs can only appear in a single source file. You do not need to worry about multiple files or preprocessing.

Project Overview

Here is a rough overview of the stages involved in completing the project: