A calculator in Algol 68
last modified November 14, 2026
A recursive-descent parser is the shortest route from a line of text to a value. The grammar is written as one procedure per precedence level, each procedure reads the part of the input that belongs to its level, and parentheses are handled by one call back to the top. Algol 68 suits the style: procedures nest inside other procedures, a structure carries the parser state, and a union models the tokens.
This article builds a calculator that evaluates integer expressions with
addition, subtraction, multiplication, division, powers, unary minus, and
parentheses. It tokenises a line into a row of unions, keeps the position in
a STRUCT, and reads lines until the user types
quit.
The grammar
The grammar has five rules. An expression is a sequence of terms joined by plus and minus, a term is a sequence of unary factors joined by times and divide, a unary factor is an optional minus in front of a power, and a power is a primary with an optional exponent. A primary is a number or a parenthesised expression.
expression := term { ("+" | "-") term }
term := unary { ("*" | "/") unary }
unary := "-" unary | power
power := primary [ "^" unary ]
primary := number | "(" expression ")"
The levels give the usual priorities: 2 + 3 * 4 is 14, not 20,
because the multiplication is consumed by term before the
addition sees its right operand. ^ takes its right operand from
unary, which makes it right associative, so 2^3^2 is
512. Each rule maps to one procedure, and the braces become a
WHILE loop.
Tokens as a union
Before parsing, a line can be split into tokens: a number becomes an
INT, and each operator or parenthesis becomes a
CHAR. A union holds either, so one row can carry both kinds, and
a CASE clause recovers the value together with its type.
MODE TOKEN = UNION (INT, CHAR);
PROC tokenize = (STRING s) FLEX [] TOKEN:
(
[1:UPB s] TOKEN ts;
INT n := 0;
INT i := LWB s;
WHILE i <= UPB s DO
CHAR c = s[i];
IF c = " " THEN
i +:= 1
ELIF c >= "0" AND c <= "9" THEN
INT v := 0;
BOOL digits := TRUE;
WHILE digits DO
IF i > UPB s THEN
digits := FALSE
ELIF s[i] >= "0" AND s[i] <= "9" THEN
v := v * 10 + (ABS s[i] - ABS "0");
i +:= 1
ELSE
digits := FALSE
FI
OD;
n +:= 1;
ts[n] := v
ELSE
n +:= 1;
ts[n] := c;
i +:= 1
FI
OD;
ts[1:n]
);
BEGIN
FLEX [] TOKEN toks = tokenize("12 + 345*(7-2)");
FOR i TO UPB toks DO
CASE toks[i] IN
(INT v): print(("number ", whole(v, 0), newline)),
(CHAR c): print(("symbol ", c, newline))
ESAC
OD
END
The row is declared with the length of the string, because a token cannot be
shorter than one character, and the result is the slice up to the number of
tokens that were stored. The two branches of the CASE clause name
the mode they accept, so v is an INT in the first
and c is a CHAR in the second. Digits are collected
by a loop with a flag, because AND evaluates both operands and
would index the string past its end.
$ a68g tokens.a68 number 12 symbol + number 345 symbol * symbol ( number 7 symbol - number 2 symbol )
Parser state
The parser itself does not need the token row: it can read the characters
directly and keep one position in the string. A structure holds the text and
the position, and every procedure receives a reference to it, so the
procedures share one cursor. Two helpers do the small work:
skip spaces moves the position over blanks, and
peek returns the next character without consuming it.
MODE PARSER = STRUCT (STRING text, INT pos);
PROC skip spaces = (REF PARSER p) VOID:
(
BOOL more := TRUE;
WHILE more DO
IF pos OF p > UPB text OF p THEN
more := FALSE
ELIF (text OF p)[pos OF p] = " " THEN
pos OF p +:= 1
ELSE
more := FALSE
FI
OD
);
PROC peek = (REF PARSER p) CHAR:
(
skip spaces(p);
IF pos OF p > UPB text OF p THEN "!" ELSE (text OF p)[pos OF p] FI
);
BEGIN
PARSER p := (" 42 + 8", 1);
print(("peek: ", peek(p), newline));
print(("pos: ", whole(pos OF p, 0), newline))
END
The end of the input is reported as "!", a character that cannot
appear in an expression, so the parser can test for the end with an ordinary
comparison. After peek the position stands on the character it
returned, which is why it reads 4 rather than 1: the three leading spaces have
been skipped and the character is the first digit.
$ a68g state.a68 peek: 4 pos: 4
Reading a number
A number is a sequence of digits with no sign, because the sign belongs to
the unary level. Each digit multiplies the value collected so far by ten and
adds its own value, which is the difference between the character code and
the code of "0". The loop stops at the first character that is
not a digit and leaves the position on it.
MODE PARSER = STRUCT (STRING text, INT pos);
PROC number = (REF PARSER p) INT:
(
INT n := 0;
BOOL more := TRUE;
WHILE more DO
IF pos OF p > UPB text OF p THEN
more := FALSE
ELSE
CHAR c = (text OF p)[pos OF p];
IF c >= "0" AND c <= "9" THEN
n := n * 10 + (ABS c - ABS "0");
pos OF p +:= 1
ELSE
more := FALSE
FI
FI
OD;
n
);
BEGIN
PARSER p := ("1234abc", 1);
INT n = number(p);
print((whole(n, 0), " pos ", whole(pos OF p, 0), newline))
END
The call returns 1234 and leaves the position at 5, the letter
a. The parser will then complain about that letter, because a
number must be followed by an operator, a closing parenthesis, or the end of
the line. For a calculator that accepts only integers this is enough; a real
one would accept a decimal point here and return a REAL.
$ a68g number.a68 1234 pos 5
The evaluator
The complete program puts the helpers and the five grammar rules together.
expression declares primary, power,
unary, and term in its body, which lets
primary call expression for a parenthesised group
and lets power call itself for a right-associative exponent.
MODE PARSER = STRUCT (STRING text, INT pos);
BOOL ok := TRUE;
PROC complain = (STRING msg) VOID:
(
ok := FALSE;
print(("error: ", msg, newline))
);
PROC skip spaces = (REF PARSER p) VOID:
(
BOOL more := TRUE;
WHILE more DO
IF pos OF p > UPB text OF p THEN
more := FALSE
ELIF (text OF p)[pos OF p] = " " THEN
pos OF p +:= 1
ELSE
more := FALSE
FI
OD
);
PROC peek = (REF PARSER p) CHAR:
(
skip spaces(p);
IF pos OF p > UPB text OF p THEN "!" ELSE (text OF p)[pos OF p] FI
);
PROC number = (REF PARSER p) INT:
(
INT n := 0;
BOOL more := TRUE;
WHILE more DO
IF pos OF p > UPB text OF p THEN
more := FALSE
ELSE
CHAR c = (text OF p)[pos OF p];
IF c >= "0" AND c <= "9" THEN
n := n * 10 + (ABS c - ABS "0");
pos OF p +:= 1
ELSE
more := FALSE
FI
FI
OD;
n
);
PROC expression = (REF PARSER p) INT:
(
PROC primary = (REF PARSER q) INT:
(
CHAR c = peek(q);
INT v;
IF c >= "0" AND c <= "9" THEN
v := number(q)
ELIF c = "(" THEN
pos OF q +:= 1;
v := expression(q);
IF peek(q) = ")" THEN
pos OF q +:= 1
ELSE
complain("missing )")
FI
ELSE
complain("unexpected " + c);
pos OF q +:= 1;
v := 0
FI;
v
);
PROC power = (REF PARSER q) INT:
(
INT base = primary(q);
IF peek(q) = "^" THEN
pos OF q +:= 1;
INT e := power(q);
INT r := 1;
TO e DO r *:= base OD;
r
ELSE
base
FI
);
PROC unary = (REF PARSER q) INT:
(
IF peek(q) = "-" THEN
pos OF q +:= 1;
-unary(q)
ELSE
power(q)
FI
);
PROC term = (REF PARSER q) INT:
(
INT v := unary(q);
WHILE peek(q) = "*" OR peek(q) = "/" DO
CHAR op = peek(q);
pos OF q +:= 1;
INT rhs = unary(q);
IF op = "*" THEN
v *:= rhs
ELIF rhs = 0 THEN
complain("division by zero")
ELSE
v := v OVER rhs
FI
OD;
v
);
INT v := term(p);
WHILE peek(p) = "+" OR peek(p) = "-" DO
CHAR op = peek(p);
pos OF p +:= 1;
INT rhs = term(p);
IF op = "+" THEN v +:= rhs ELSE v -:= rhs FI
OD;
v
);
BEGIN
STRING line := "";
BOOL done := FALSE;
on logical file end(stand in, (REF FILE f) BOOL: done := TRUE);
WHILE NOT done DO
print("> ");
read((line, newline));
IF NOT done THEN
IF line = "" THEN
print(newline)
ELIF line = "quit" THEN
done := TRUE
ELSE
PARSER p := (line, LWB line);
ok := TRUE;
INT v = expression(p);
IF peek(p) /= "!" THEN complain("trailing input") FI;
IF ok THEN print((whole(v, 0), newline)) FI
FI
FI
OD
END
Each level computes its first operand, then loops while the next character
belongs to it. The loop body reads the operator, consumes it, and calls the
next level down for the right operand, so the priorities fall out of the call
order. Division uses OVER, which truncates toward negative
infinity, and a zero divisor is reported before it is used.
$ printf '2+3*4\n(1+2)*3\n10/3\n7/0\n2^10\nquit\n' | a68g calc.a68 > 14 > 9 > 3 > error: division by zero > 1024 >
Errors and recovery
An error does not end the program. complain clears the flag
ok and prints a message, and the level that noticed the problem
returns a value so that the parse can continue; the read-eval loop prints the
result only when ok is still true. A mistyped line therefore
costs one message, not the session.
Three kinds of mistake are reported: a character that cannot start an
operand, a missing closing parenthesis, and a division by zero. A line with
leftover input after a complete expression is reported as trailing input,
which catches input such as 1 2 or (1)).
In the session below the first line reports the missing parenthesis; the
expression still evaluated to 20, but the flag suppressed the result. The
second line reports the letter, skips it, and then reports the rest of the
word as trailing input, which is why two messages follow one prompt. The
third line reports the 2, the empty line only finishes its
prompt, and the last expression prints 5. The session ends when
quit is read or the input reaches its end.
$ printf '4 * (2 + 3\nabc\n1 2\n\n9-4\nquit\n' | a68g calc.a68 > error: missing ) > error: unexpected a error: trailing input > error: trailing input > > 5 >
Extending the calculator
The structure leaves room for the usual next steps. A real mode and a decimal
point belong in number, and the arithmetic would then use
REAL values and / instead of OVER.
Variables need a table of names and values consulted by
primary, and an assignment statement would be parsed before
expression. Functions such as sqrt are another
branch in primary that reads a name and then an argument list.
The token union from the first section is the natural place to add a name: a third constituent of the union carries an identifier, and the parser looks it up. The unions article explains the mode, and the recursion article covers the call pattern that the five procedures use.
Source
Revised Report on the Algorithmic Language Algol 68
In this article we wrote the grammar of an integer calculator, tokenised a line into a row of unions, kept the parser position in a structure, read numbers digit by digit, built the five grammar rules as nested procedures, and recovered from errors without ending the session.
Author
List all Algol 68 tutorials.