Bali Specifications for Part 3

CS 212 - Fall 2007

Bali is designed to be reasonably simple to compile.  The Bali language changes every semester.

We use the following notation throughout this document:

Bali Syntax

program [declarations ] : function* A program consists of zero or more declarations (global variables) followed by zero or more functions.
function type name ( [declarations] ) : [ declarations ] : statement* end A function has a return-type, a name, 0 or more parameters, and a body consisting of optional declarations (local variables) followed by zero or more statements.
declarations type name ( , type name )* Each declaration is a type followed by a name.
type int | boolean | void There are predefined types (int, boolean, void).  Void is only used as a return type for functions.
statement reference = expression ; An assignment statement.  
  reference ; Function call (useful for side-effects).
  if expression then statement* [ else statement*] endif An if-statement has an optional else part.
  loop statement* ( while | until ) expression ; statement* endloop Looping.  Note that there are two blocks of statements.  The loop works by executing the first block, then checking the condition and possibly exiting the loop, then executing the second block.  If the condition causes a loop-exit then the second block is not executed.  After executing the second block the loop starts over again with the first block.  Either statement-block in a loop can be empty or both blocks be nonempty.  
  return [ expression ] ; Return statement. The type of the expression must match the return-type of the function. The no-expression version is used iff the function's return-type is void.
  print expression ( , expression )* ; Print statement.  Multiple expressions can be printed.  Ideally, all are printed on a single line with a space between adjacent items, but this isn't possible with SaM-code.
reference name [ functionArgs ] A reference typically evaluates to a specific "location" appropriate for storage or retrieval.
functionArgs ( [ expression ( , expression )* ] ) Function arguments.
expression [ + | - | not ] term ( binaryOp term )* An expression is a sequence of terms separated by binary operators.  There can be an optional sign or boolean-negation in front of the first term of an expression; it is applied to the first term.  Operators are evaluated left-to-right (i.e., no precedence rules).
binaryOp arithmeticOp | comparisonOp | booleanOp The three kinds of binary operators.
arithmeticOp + | - | * | / | %  Operators for arithmetic.
comparisonOp < | <= | == | != | > | >= Comparison operators.
booleanOp and | or Boolean  operators (both are short-circuiting).
term literal | ( expression ) | inputValue | reference A term is a literal, a parenthesized expression, an input value, or a reference.
literal integer | true | false Unsigned integers (e.g., 123, 6, 44) and boolean constants.
inputValue readInt   This "value" is read from standard input; readInt expects an integer (initial blanks are ignored, an initial + or - is OK).

 

Bali Semantics

comments Anything following a # on a line is considered to be a comment. This doesn't show up in the grammar above because it's handled by the scanner (Scanner212.java).
keywords
  • Keywords (those shown in bold-blue above) cannot be used as names.
  • The complete list of keywords:
    • end, void
    • class, extends, endclass, this, super, null
    • if, then, else, endif
    • loop, while, until, endloop
    • return, print
    • and, or, not, true, false
  • The following words have special meaning, but they are not keywords (i.e., they are defined in the global namespace---see below):
    • int, boolean, char, float
    • readInt, readChar, readLine, readFloat

program
  • All functions of a program must be in one file.
  • Running  a program means the program's main function is executed.
main function
  • There must be a function called main that has an empty parameter list. It is a semantic error if this function does not exist.
  • The return type for the main function must be int; this integer value appears as the exit code when the SaM Simulator halts.
declarations
  • Variables have default values : 0 for int and false for boolean.
  • Variables must be declared before use.
  • Variables declared at the program level are global variables.  Variables declared at the function level are local to that function.
namespaces
  • At any point in a program there are at most 2 active namespaces: the global level and the function level.
  • Any name can be used at most once per level.  This means, for instance, that a function name must be different from all global-variable names.  Names can be re-used if they are at different levels.  For instance, a function can have a local variable that has the same name as a global variable; in this case, the global variable is inaccessible from within the function.
  • To determine the meaning of a name that is not a type, Bali first checks the function-level namespace, then the global-level namespace.
  • A name does not have to be defined before it is used.  This rule allows, for instance, function A and function B to each refer to the other.  A name always refers to the meaning within the current namespace.  [Comment: This rule is easy to implement because, in effect, we are designing a 2-pass compiler.  In the first pass, we build the AST and determine meaning for each name.  In the second pass, we walk over the AST to detect semantic errors and generate code.]
namespace rules for types
  • All type names in Bali reside in the global namespace.  The types in Bali consist of the predefined types and any classes created by the program (there are no such classes for Part 3).
  • For a type-name (a name that appears as syntactic type as specified in the grammar above), the name is looked up in the global namespace.  All other names are looked up in the active namespaces as specified above.
functions
  • The type of the expression in the return statement must match the type specified in the function header. A return statement with no expression is used iff the function's return type is void.
  • If you "fall off the end" of the function body (i.e., you execute the last statement and that statement is not a return statement) then a default return is automatically executed.  This default-return returns a value using the same default rules as for a variable declaration (i.e., 0 for int, false for boolean).
  • Functions cannot be overloaded.  There is at most one function with a given name.
  • The declared type (i.e., the type that can be determined from declarations within the program) for an argument of a function call must be compatible with the corresponding parameter type.
  • Functions cannot be assigned to variables since there is no type that can be used to declare such a variable. 
parameters
  • Parameters pass by value.
  • Parameter names are local to the current function (see namespaces).
statements
  • Expressions in if and loop statements must be of type boolean.
  • For assignment statements, the types of the left-hand and right-hand sides must be compatible.
  • Rudimentary output is available via the print statement.
expressions
  • For all binary operators, the operands must be of the same type.
  • For logical operators (and, or, not), operands must be of type boolean.
  • For arithmetic operators (+, -, *, /), operands must be of type int.  Division (/) is integer division.
  • For the mod operator (%), operands must be of type int.
  • For the relational operators (<, <=, >, >=), operands must be of type int.
  • The equality (==) and inequality (!=) operators both work with both operands int or both operands boolean.
  • Bali does not support division by zero, NaN, or infinity.
input
  • Rudimentary input is available using the predefined "variable" readInt.
  • It is a semantic error to use this variable on the left side of an assignment statement.
predefined names
  • The names int and boolean are predefined as global variables. You can have local variables that use these names if you want; it's legal even though it's bad programming style.
  • The name readInt is also a predefined global variable.
  • The namespace rules (see above) imply that it is illegal to have functions that use any of these names.