Algol 68 Genie

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