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