## 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

```

 © 2002-2024 J.M. van der Veer (jmvdveer@xs4all.nl)