The Source Language

A source language program is a finite sequence of tokens. A token is represented by a finite character sequence, whose syntax is described by the following grammar (see Chapter II, section 1):

Token =
     KeyWord | Identifier | Numeral.
KeyWord =
     ";" | "(" | ")" | "+" | "-" | "*" | "-" |
     ":=" | "<=" | '<>' | "<" | ">=" | ">" | "=".
     "DO" | "ELSE" | "IF" | "READ" | "THEN" |
     "WHILE" | "WRITE".
Identifier = Letter { Letter | Digit }.
Numeral = Digit { Digit }.

The keywords are words reserved for special purposes and must not be used as normal identifier names.

Keywords are case insensitive, i.e. the small and capital letters appearing in the keywords are considered as completely equivalent.

Tokens may be separated by spaces, horizontal tabs, and newline characters, which cannot occur within tokens and are ignored unless they are essential to separate two consecutive tokens.

Some token sequences are not syntactically correct programs. Hence, the token sequence produced by scanning the input character stream must be parsed to see whether it has the following syntax:

Program = StatementSequence.
StatementSequence = Statement { ";" Statement }.
Statement =
     "IF" Test "THEN" Statement "ELSE" Statement |
     "WHILE" Test "DO" Statement |
     "READ" VariableName |
     "WRITE" Expression |
     "(" StatementSequence ")".
     VariableName ":=" Expression |
     Empty.
Empty = .
Test = Expression CompOperator Expression.
CompOperator = "=" | "<=" | "<>" | "<" | ">=" | ">".
Expression = Term { AddOperator Term }.
Term = Factor { MultOperator Factor }.
Factor = VariableName | Value | "(" Expression ")".
AddOperator = "+" | "-".
MultOperator = "*" | "/".
VariableName = Identifier.
Value = Integer.

A program is a statement sequence. The statements are executed sequentially, from left to right. Each statement may access, and change, the values of variables.

An if statement

    IF Cond THEN St₁ ELSE St₂

tests the condition Cond. If the condition is satisfied, the statement St₁ is executed, otherwise, the statement St₂ is executed.

A while statement

    WHILE Cond DO St

tests the condition Cond. If the condition is satisfied, the statement St is executed, and the execution of the whole construct is repeated. Otherwise, if the condition is not satisfied, the execution of the construct terminates.

A read statement

    READ Var

reads an integer from the input device, and assigns the integer as value to the variable Var.

A write statement

    WRITE Expr

evaluates the arithmetic expression Expr to produce an integer, which is written to the output device.

A compound statement

    ( St₁; St₂; ... St_N )

specifies the sequential execution of the statements St₁, St₂, ..., St_N.

An assignment statement

    Var := Expr

evaluates the expression Expr to produce an integer, which is assigned as value to the variable Var.

An empty statements specifies no action.

Conditions and arithmetic expressions have their conventional meaning. The multiplication and division operators have precedence over the addition and subtraction operators.

The variables appearing in the program don't have to be declared. The initial variable values are undefined.

Here is an example program, which inputs an integer, and then computes and outputs the factorial of the integer.

    read value;
    count:=1;
    result:=1;
    while count<value do
      (
      count:=count+1;
      result:=result*count
      );
    write result