Algol 68 Genie

all-parser.a68

     
   1  COMMENT
   2  
   3  @section Synopsis
   4  
   5  Non-left-recursive context-free grammar parser.
   6  
   7  This program originates from the legacy "REVISED MC ALGOL 68 TEST SET":
   8  
   9      Dick Grune, The Revised MC ALGOL 68 Test Set, IW XX/79,
  10      Mathematical Centre, Amsterdam.
  11  
  12  The Mathematical Centre ("Stichting Mathematisch Centrum" or SMC) was a Dutch 
  13  non-profit institution aiming at the promotion of pure mathematics and its 
  14  applications. 
  15  
  16  SMC is now "Stichting Centrum Wiskunde & Informatica" (CWI). The test set 
  17  is available as an open access publication from the CWI repository:
  18  
  19     https://ir.cwi.nl/pub/
  20  
  21  Selected (modified) "Revised MC ALGOL 68 Test Set" programs are distributed 
  22  with Algol 68 Genie with kind permission of Dick Grune.
  23  
  24  COMMENT
  25  
  26  BEGIN # All-parser, Dick Grune, 20-11-74.
  27          The following is an example of a technique that will give a
  28          parser for any non-left-recursive context-free grammar.
  29          The parser gives all possible parsings.
  30        #
  31  
  32    MODE ACT = VOID, TAIL = PROC ACT, RULE = PROC (TAIL) ACT;
  33  
  34    #         R u l e                      G r a m m a r #
  35  
  36    RULE t = (TAIL q) ACT: s (ACT: b (q)); # t: s, b.    #
  37  
  38    RULE s = (TAIL q) ACT:                 # s:          #
  39      (a (ACT: s(ACT: s(q)));              #    a, s, s; #
  40       a (q)                               #    a.       #
  41      );
  42  
  43    RULE a = (TAIL q) ACT:
  44      (n +:= 1; IF inp[n] = "a" THEN q FI; # a: "a".     #
  45       n -:= 1);
  46  
  47    RULE b = (TAIL q) ACT:
  48      (n +:= 1; IF inp[n] = "b" THEN q FI; # b: "b".     #
  49       n -:= 1);
  50  
  51    INT max = 10; STRING inp, INT n := 0;
  52  
  53    FOR i FROM 0 TO max
  54    DO inp := i * "a" + "b"; INT count:= 0;
  55       t(ACT: count+:=1);
  56       print(("The sentence """, inp, """ has ", whole (count, 0), " parsings", newline))
  57    OD
  58  
  59  END
Deze website is gearchiveerd door de KB, nationale bibliotheek.

This website is archived by the National Library of the Netherlands.