SUNY Geneseo, Department of Computer Science

The MinimL Language

CSci 331, Spring 2003

Prof. Doug Baldwin

Language Overview

MinimL is, as its name might suggest, a minimal programming language. It was deliberately designed to be as small and simple as a language can reasonably be, in order to serve as a manageable case study in compiler design. Despite its simplicity, however, one can code a surprising number of algorithms in MinimL.

All data in MinimL are integers, and just about everything in a program is an expression that produces an integer result. MinimL provides the following kinds of expression:

Comparison

Compares two integers, yielding 1 if the left operand is less than or equal to then second, and 0 otherwise. For example

     x <= y

Addition

Adds two integers. For example

     x + y

Subtraction

Subtracts two integers. For example

     x - y

Conditional

Evaluates a test expression, and uses its value to select one of two other expressions to evaluate. Yields the value of the first of these expressions if the test expression produced a non-zero value, and the value of the second if the test expression yielded zero (think of this as an "if-then-else", with zero being MinimL's version of "false", and non-zero "true"). For example, the following produces the sum of x and y if flag is 0 or less, otherwise it produces the difference:

     if flag <= 0 then
        x + y
     else
        x - y
     endif

Function Call

Applies a function to zero or more arguments, and yields the result. Note that all functions return integer results, MinimL has no notion of a "void" function. For example

     f( x+y, 1 )

The above expressions can be nested in any manner you wish. Conditionals and function calls have the highest precedence, then addition and subtraction, and finally comparisons. MinimL does not support parentheses for over-riding precedence.

A MinimL program is basically a series of function definitions. Every MinimL program must define a function named "minimain", which gets called automatically when the program runs. Users can provide arguments for minimain on the command line, and the result returned by minimain gets printed to standard output. For example, here is a complete MinimL program that computes the absolute value of its argument:

minimain( x )
    if 0 <= x then
        x
    else
        0 - x
    endif

Suppose this program is compiled into an executable file named "abs". Running this program under Unix might look something like this:

% abs -3
3

Here, the user has typed "abs -3" in response to a shell prompt, and the program has run and printed its result, 3.

Syntactic Details

The above overview demonstrated much of MinimL's syntax informally (there isn't much more to the language than what was shown above). I give a complete, precise, grammar for the language below. A few lexical conventions aren't defined by this grammar, namely:

• MinimL identifiers are strings of letters and/or digits, beginning with a letter. Identifiers are case sensitive, i.e., "a" and "A" are distinct identifiers. In a lex-like regular expression notation, MinimL identifiers are character sequences of the form [a-zA-Z][a-zA-Z0-9]^*. However, the words "if", "then", "else", and "endif" are reserved, and cannot be used as identifiers.
• Integer constants are strings of digits. Constants may not have leading signs. Thus integer constants are sequences of the form [0-9]⁺.
• Comments are introduced by semi-colons, and continue to the end of the line.
• Whitespace, including new lines, cannot appear inside an identifier, constant, keyword, or operator, but is otherwise insignificant.

Using these conventions, here is the formal definition of MinimL's syntax. (Note the word "epsilon" indicating an empty right-hand side in some of these productions):

A MinimL source file contains a sequence of function declarations. Each declaration consists of the function's name, its formal arguments, and its body, which is an expression:

    <Program> ::= <Declarations>

    <Declarations> ::=   <Decl>
                       | <Decl> <Declarations>

    <Decl> ::= identifier ( <Formals> ) <Expr>

    <Formals> ::=   epsilon
                  | <NonemptyFormals>

    <NonemptyFormals> ::=   identifier
                          | identifier , <NonemptyFormals>

Expressions are comparisons, additions, subtractions, conditionals, function calls, parameter names, or integer constants:

    <Expr> ::=   <Expr> <= <Term>
               | <Term>

    <Term> ::=   <Term> + <Atom>
               | <Term> - <Atom>
               | <Atom>

    <Atom> ::=   if <Expr> then <Expr> else <Expr> endif
               | identifier ( <Actuals> )
               | identifier
               | constant

    <Actuals> ::=   epsilon
                  | <NonemptyActuals>

    <NonemptyActuals> ::=   <Expr>
                          | <Expr> , <NonemptyActuals>