fibonacci-grammar.a68
1 COMMENT
2
3 @section Synopsis
4
5 Compute Fibonacci numbers from the derivations of a suitable grammar.
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 modified
19 by Erwin Koning and 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
