## Part 1: The Language

This article provides an informal definition of a simple language (a.k.a. "The Language") I am writing a compiler for. If you are new to this series, I would recommend to start reading with this post.

Let's start with a simple example which calculates an i-th Fibonacci number.

fib(i) {
if i < 3 {
return 1
} else {
return fib(i-2) + fib(i-1)
}
}

The code is quite simple. First two numbers in a Fibonacci sequence are 1 and every other Fibonacci number is a sum of previous two in the sequence.

The following rules describe the language (more or less):

• The Language is a C-style language.
• Spacing is ignored.
• There is only one data type - integer.
• There are only three operators: +, -, and <.
• a < b returns 1 if a is smaller then b, 0 otherwise.
• There are only two statements - if and return.
• If statement executes the then block if the test expression is not 0 and the else block otherwise. Else block is required.
• Return statement just sets a return value and doesn't interrupt the control flow.
• There is no assignment.
• Every function returns an integer.
• Parameters are always passed by value.
• A function without a return statement returns 0.
• A function can call other functions (or recursively itself).

As you can see, The Language is terribly limited, but it is still functional enough to provide for simple demos. (It is also functional in computer science terms. We'll use that to our advantage much later in this series.)

A bit more formal (but still very much informal) definition of the syntax:

/// program = {function}
///
/// function = identifier "(" [ identifier { "," identifier } ] ")" block
///
/// block = "{" statement {";" statement} [";"] "}"
///
/// statement = if
///           | return
///
/// if = "if" expression block "else" block
///
/// return = "return" expression
///
/// expression = term
///            | term operator term
///
/// term = numeric_constant
///      | function_call
///      | identifier
///
/// operator = "+" | "-" | "<"
///
/// function_call = identifier "(" [expression { "," expression } ] ")"