fibonacci-grammar.a68
1 COMMENT
2
3 @section Synopsis
4
5 Illustration of the use of procedure closures.
6
7 This example computes Fibonacci numbers by counting the number of derivations of the
8 "Fibonacci grammar":
9
10 fib: "a";
11 "a", fib;
12 "aa", fib.
13
14 The purpose is to illustrate the use of procedure closures which we call continuations.
15 We use this to generate a recursive descent with backup parser following a simple translation
16 from grammar rules to procedures.
17
18 This program was contributed by Eric Voss and simplified/modified by Erwin Koning and
19 Marcel van der Veer.
20
21 COMMENT
22
23 PROC grammar fib = (INT i, STRING s, CONT q) VOID:
24 BEGIN terminal (i, "a", s, q);
25 terminal (i, "a", s, (INT j) VOID: grammar fib (j, s, q));
26 terminal (i, "aa", s, (INT j) VOID: grammar fib (j, s, q))
27 END;
28
29 PROC terminal = (INT i, STRING a, s, CONT q) VOID: (INT u = i + UPB a; u <= UPB s | q (u));
30
31 MODE CONT = PROC (INT) VOID;
32
33 FOR k TO 10
34 DO STRING sentence = k * "a";
35 INT nr derivations := 0;
36 grammar fib (0, sentence, (INT j) VOID: (j = UPB sentence | nr derivations +:= 1));
37 print (("Fibonacci number ", UPB sentence, " = ", nr derivations, new line))
38 OD
