Algol 68 regular expressions
last modified November 13, 2026
The Revised Report has no regular expressions. Algol 68 Genie adds them as two
predeclared procedures: grep in string searches a string and
sub in string replaces text. Both use the POSIX extended regular
expression syntax that tools such as grep and sed
understand, so a pattern written for the shell works here too.
This article shows how to search, how to extract the matched text, how to walk every match in a string, how the replacement procedure works, and how to use an anchored pattern as a validation.
Searching for a pattern
grep in string takes the pattern first, the string second, and two
INT variables that receive the bounds of the match. It returns 0
when the pattern matches and a non-zero value when it does not. The bounds are
1-based subscripts into the string, so the matched text is a slice.
BEGIN
STRING s = "the cat sat on the mat";
INT b, e;
IF grep in string("cat", s, b, e) = 0 THEN
print(("found in positions ", whole(b, 0), " to ", whole(e, 0), newline));
print((s[b:e], newline))
ELSE
print(("no match", newline))
FI
END
The pattern cat matches the word in the middle of the sentence,
and the bounds 5 and 7 are the positions of its three characters. The slice
s[b:e] is therefore the text that matched, without any copying
loop.
$ a68g search.a68 found in positions 5 to 7 cat
When nothing matches
A failed search leaves the two bounds untouched, so a program that reads them afterwards must initialise them first. The return value is the only reliable test, and the procedure does not raise an error for a pattern that matches nothing.
BEGIN
STRING s = "the cat sat on the mat";
INT b := 0, e := 0;
INT result = grep in string("dog", s, b, e);
print(("result ", whole(result, 0), newline));
IF result /= 0 THEN print(("no match", newline)) FI
END
The word dog does not occur, the procedure returns 1, and the
bounds keep the value 0 that the declarations gave them. The conditional clause
prints the message instead of a slice.
$ a68g nomatch.a68 result 1 no match
The pattern language
Patterns are POSIX extended regular expressions: character classes such as
[0-9], the quantifiers *, +,
? and {m,n}, alternation with |, groups
in parentheses, the anchors ^ and $, and named
classes such as [[:digit:]]. A backslash makes the next character
literal.
BEGIN
INT b, e;
STRING s = "order 42 costs 3.50";
IF grep in string("[0-9]+", s, b, e) = 0 THEN
print(("first number: ", s[b:e], newline))
FI;
IF grep in string("[0-9]+\.[0-9]+", s, b, e) = 0 THEN
print(("price: ", s[b:e], newline))
FI;
IF grep in string("^order", s, b, e) = 0 THEN
print(("the text starts with order", newline))
FI;
IF grep in string("cats?|dogs?", s, b, e) /= 0 THEN
print(("no pet is mentioned", newline))
FI
END
The first search finds the first run of digits, the second one a number with a
decimal point, and the third shows that ^ anchors the pattern at
the start of the string. The last test uses alternation and an optional
s, and reports that neither word occurs.
$ a68g classes.a68 first number: 42 price: 3.50 the text starts with order no pet is mentioned
Every match
grep in string finds the first match only. To walk all of them, the
program searches the part of the string that follows the previous match and
adds the offset of the part it has already passed. The remainder starts at the
character after the match, so no match is counted twice.
BEGIN
STRING s = "one two one two one";
STRING rest := s;
INT offset := 0, b, e, count := 0;
WHILE grep in string("one", rest, b, e) = 0 DO
count +:= 1;
print((whole(count, 0), ": position ", whole(offset + b, 0), newline));
offset +:= e;
rest := rest[e + 1:]
OD;
print(("matches: ", whole(count, 0), newline))
END
Three occurrences are found, at positions 1, 9, and 17 of the original string. The loop ends when the remainder holds no match, and the counter is the number of occurrences. A program that only needs the count can drop the printing.
$ a68g iterate.a68 1: position 1 2: position 9 3: position 17 matches: 3
Splitting a value
A search anchored at the end of a string is a convenient way to split a value
in two. The pattern :[0-9]+$ matches only the colon and the digits
that end the string, so the match bounds divide the text into a host and a
port.
BEGIN
STRING s = "example.com:8080";
INT b, e;
IF grep in string(":[0-9]+$", s, b, e) = 0 THEN
print(("host: ", s[:b - 1], newline));
print(("port: ", s[b + 1:], newline))
ELSE
print(("no port given", newline))
FI
END
The host is the slice before the colon and the port is the slice after it. Because the pattern is anchored, an address with a port in the middle would not match, and the program would report that no port was given instead of taking the wrong text.
$ a68g extract.a68 host: example.com port: 8080
Replacing text
sub in string takes the pattern, the replacement, and a
STRING variable. The third argument is a reference, so it must be
a variable and not a denotation. The procedure replaces the first match and
returns 0, or returns non-zero when the pattern does not match.
BEGIN
STRING s := "the cat sat on the mat";
INT n;
n := sub in string("at", "AT", s);
print((whole(n, 0), " ", s, newline));
n := sub in string("at", "AT", s);
print((whole(n, 0), " ", s, newline));
n := sub in string("at", "AT", s);
print((whole(n, 0), " ", s, newline));
n := sub in string("at", "AT", s);
print((whole(n, 0), " ", s, newline))
END
The replacement is literal text: a sequence such as \1 is copied
as it stands, because the procedure does not interpret back references. The
example replaces one occurrence per call, and the four return values show when
the string has run out of matches.
$ a68g replace.a68 0 the cAT sat on the mat 0 the cAT sAT on the mat 0 the cAT sAT on the mAT 1 the cAT sAT on the mAT
Compressing spaces
A loop with sub in string normalises whitespace. As long as the
string contains two adjacent spaces, one of them is removed, and the two loops
at the end strip the leading and trailing spaces. Each replacement shortens the
string, and the loop ends when no double space is left.
BEGIN
STRING s := " lots of spaces ";
WHILE sub in string(" ", " ", s) = 0 DO SKIP OD;
WHILE UPB s > 0 AND s[1] = " " DO s := s[2:] OD;
WHILE UPB s > 0 AND s[UPB s] = " " DO s := s[:UPB s - 1] OD;
print(("[", s, "]", newline))
END
The result has single spaces between the words and none at the ends, which is
the form that a comparison or a hash of the text expects. The pattern could be
widened to [[:space:]], the POSIX class that covers spaces, tabs,
and newlines, and the same loop would then collapse every kind of whitespace.
$ a68g tidy.a68 [lots of spaces]
Checking the whole string
Anchoring the pattern at both ends turns a search into a validation: the match
must start at the first character and end at the last one. A procedure hides
the two bound variables and returns a BOOL, so the caller reads
like a question about the text.
PROC valid number = (STRING s) BOOL:
(
INT b, e;
grep in string("^[+-]?[0-9]+(\.[0-9]+)?$", s, b, e) = 0
);
BEGIN
print(("12345: ", valid number("12345"), newline));
print(("12a45: ", valid number("12a45"), newline));
print(("-3.50: ", valid number("-3.50"), newline));
print(("empty: ", valid number(""), newline))
END
The pattern accepts an optional sign, at least one digit, and an optional
fraction. The empty string is rejected, because the pattern requires a digit,
and the letters in 12a45 break the run of digits before the end of
the string is reached.
$ a68g validate.a68 12345: T 12a45: F -3.50: T empty: F
Next steps
The strings article describes indexing, slicing, and concatenation, which every example here uses, and the reading input article shows where the text comes from. The command-line arguments article reads the words of a command line, and TCP/IP sockets parses the status line of a reply with a pattern.
Source
Revised Report on the Algorithmic Language Algol 68
In this article we have searched strings with grep in string, read
the bounds of a match and turned them into a slice, walked every occurrence,
split a value at an anchored pattern, replaced one match at a time with
sub in string, compressed whitespace in a loop, and validated a
whole string with anchors.
Author
List all Algol 68 tutorials.