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
