## all-parser.a68

```
1  COMMENT
2
3  @section Synopsis
4
5  Non-left-recursive context-free grammar parser.
6
7  This program originates from the legacy "REVISED MC ALGOL 68 TEST SET":
8
9      Dick Grune, The Revised MC ALGOL 68 Test Set, IW XX/79,
10      Mathematical Centre, Amsterdam.
11
12  The Mathematical Centre ("Stichting Mathematisch Centrum" or SMC) was a Dutch
13  non-profit institution aiming at the promotion of pure mathematics and its
14  applications.
15
16  SMC is now "Stichting Centrum Wiskunde & Informatica" (CWI). The test set
17  is available as an open access publication from the CWI repository:
18
19     https://ir.cwi.nl/pub/
20
21  Selected (modified) "Revised MC ALGOL 68 Test Set" programs are distributed
22  with Algol 68 Genie with kind permission of Dick Grune.
23
24  COMMENT
25
26  BEGIN # All-parser, Dick Grune, 20-11-74.
27          The following is an example of a technique that will give a
28          parser for any non-left-recursive context-free grammar.
29          The parser gives all possible parsings.
30        #
31
32    MODE ACT = VOID, TAIL = PROC ACT, RULE = PROC (TAIL) ACT;
33
34    #         R u l e                      G r a m m a r #
35
36    RULE t = (TAIL q) ACT: s (ACT: b (q)); # t: s, b.    #
37
38    RULE s = (TAIL q) ACT:                 # s:          #
39      (a (ACT: s(ACT: s(q)));              #    a, s, s; #
40       a (q)                               #    a.       #
41      );
42
43    RULE a = (TAIL q) ACT:
44      (n +:= 1; IF inp[n] = "a" THEN q FI; # a: "a".     #
45       n -:= 1);
46
47    RULE b = (TAIL q) ACT:
48      (n +:= 1; IF inp[n] = "b" THEN q FI; # b: "b".     #
49       n -:= 1);
50
51    INT max = 10; STRING inp, INT n := 0;
52
53    FOR i FROM 0 TO max
54    DO inp := i * "a" + "b"; INT count:= 0;
55       t(ACT: count+:=1);
56       print(("The sentence """, inp, """ has ", whole (count, 0), " parsings", newline))
57    OD
58
59  END

```