home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-386-Vol-2of3.iso / v / vsnbl220.zip / BNF.SNO < prev    next >
Text File  |  1991-02-14  |  3KB  |  95 lines
  1. *    Program BNF.SNO
  2. *
  3. *    This program reads a series of definitions which comprise
  4. *    a formal grammar.  Sample statement lines are then input, and
  5. *    tested to see if they are legal for the defined grammar.
  6. *
  7. *    The grammar format used is Backus-Naur Form (BNF).  Briefly,
  8. *    TERMINALs are the characters from which language elements are created,
  9. *    and NONTERMINALs are the structures and elements of interest.  In the
  10. *    following, NONTERMINALs are enclosed in angle brackets, the string
  11. *    '::=' is used to define a NONTERMINAL, and vertical bar defines
  12. *    alternative choices.  The GOAL is the structure against which sample
  13. *    lines are tested.
  14. *
  15. *    The method used is to convert the BNF definitions to SNOBOL4 patterns.
  16. *    Note that more efficient forms could be used if BNF was extended to
  17. *    allow SNOBOL4 primitives, such as ANY(LETTER) instead of 'A' | 'B' | ...
  18. *
  19. *    The grammar definitions are read from the file BNF.DAT, and
  20. *    the sample lines are read from INPUT.  A test program is provided
  21. *    on file BNF.IN, and can be used by redirecting input:
  22. *
  23. *        >SNOBOL4 BNF <BNF.IN
  24. *
  25. *    From STRING AND LIST PROCESSING IN SNOBOL4 by Ralph E. Griswold,
  26. *             by permission of the author.
  27. *    ----------------------------------------------------------------
  28. *
  29. *    (c) Copyright 1985, 1987 - Catspaw, Incorporated
  30. *
  31.     &trim    =    1
  32.     &anchor    =    1
  33.     &case    =    0
  34.     &fullscan =    1
  35.     quote    =    "'"
  36.  
  37. * Pattern to break apart a non-terminal definition line:
  38.     defpat    =    '<' break('>') . name '>::=' rem . def
  39.  
  40. * Pattern to break apart alternatives within a definition:
  41.     altpat    =    break('|') . alt len(1) | (len(1) rem) . alt
  42.  
  43. * Pattern to examine sub-pattern within an alternative.  There are three
  44. *  forms: '<NONTERMINAL>', 'TERMINAL <NONTERMINAL>', and 'TERMINAL TERMINAL'.
  45. *   Note the use of the cursor operator to assign P the value 1 if SUB is a
  46. *    NONTERMINAL, and 0 if it is a TERMINAL.
  47.     subpat    =    '<' @p break('>') . sub '>' |
  48. +            @p (len(1) break('<')) . sub | @p (len(1) rem) . sub
  49.  
  50. * The goal is a NONTERMINAL without a definition:
  51.     goal    =    '<' break('>') . name
  52.  
  53.     input(.grammar, 2, , 'BNF.DAT')                :s(nextl)
  54.     output    =    'Cannot open file BNF.DAT'        :(end)
  55.  
  56. nextl    line    =    grammar                    :f(error)
  57.     line defpat                        :f(test)
  58.     output    =    line
  59.  
  60. * Initialize variable to accumulate the current definition.
  61.     pattern    =
  62.  
  63. * Get next alternative from definition, accumulate a next alternative.
  64. nexta    def altpat    =                    :f(eod)
  65.     pattern    =    differ(pattern) pattern ' |'
  66.  
  67. * Get next subpattern for this alternative
  68. nexts    alt subpat    =                    :f(nexta)
  69.  
  70. * If it's a nonterminal, use unevaluated expression operator:
  71.     pattern    =    gt(p,0) pattern ' *' sub        :s(nexts)
  72.  
  73. * Otherwise it's a terminal.  Put it in quotes:
  74.     pattern    =    pattern ' ' quote sub quote        :(nexts)
  75.  
  76. * No more alternatives, define this NONTERMINAL and display SNOBOL4 form.
  77. eod    $name    =    eval(pattern)
  78.     output    =    name " = " pattern
  79.     output  =                        :(nextl)
  80.  
  81. * Line with no definition, it must be the GOAL:
  82. test    line goal
  83.     pattern    =    pos(0) $name rpos(0)
  84.     endfile(2)
  85.     output    =    'Enter test lines:'
  86.  
  87. * Now read sample lines from the input file, and test them.
  88. testt    string    =    input                    :f(end)
  89.     output    =
  90.     output    =    string
  91.     string pattern                        :f(no)
  92.     output    =    'is a ' name                :(testt)
  93. no    output    =    'is not a ' name            :(testt)
  94. end
  95.