rfc83.txt

RFC 的详细文档！

Network Working Group                                        R. Anderson
Request for Comments: 83                                      A. Harslem
NIC: 5621                                                     J. Heafner
                                                                    RAND
                                                        18 December 1970


               LANGUAGE-MACHINE FOR DATA RECONFIGURATION

Introduction

   In NWG/RFC #80 we mentioned the needs for data reconfiguration along
   with a complier/executor version of a Form Machine to perform those
   manipulations.

   This note proposes a different approach to the Form Machine.
   Specifically, we describe a syntax-driven interpreter that operates
   on a grammar which is an ordered set of replacement rules.  Following
   the interpreter description are some "real-world" examples of
   required data reconfigurations that must occur between RAND consoles
   and the Remote Job System on the UCLA 360/91.  Lastly, we suggest
   that the Protocol Manager mentioned in NWG/RFC #80 can be simplified
   by using the Form Machine and two system forms (specified a priori in
   the code).

   Caveat:  The Form Machine is not intended to be a general purpose
   programming language.  Note the absence of declaration statements,
   etc.

THE FORM MACHINE

I.  Forms

   A form is an ordered set of rules.

      F = {R1, ...,Rn}

   The first rule (R1) is the rule of highest priority; the last rule
   (Rn) is the rule of lowest priority.

   The form machine gets as input: 1) a list of addresses and lengths
   that delimit the input stream(s); 2) a list of addresses and lengths
   that delimit the output area(s); 3) a pointer to a list of form(s);
   4) a pointer to the starting position of the input stream; and 5) a
   pointer to the starting position of the output area.  The Form
   Machine applies a form to the input string emitting an output string
   in the output area.  The form is applied in the following manner:




Anderson, et. al.                                               [Page 1]

RFC 83                 Language Machine For Data        18 December 1970


      Step 1:  R1 is made the current rule.

      Step 2:  The current rule is applied to the input data.

      Step3:   a) If the rule fails, the rule of priority one lower is
                  made current.

               b) If the rule succeeds, the rule of highest priority is
                  made current

               c) When the rule of lowest priority fails, the form fails
                  and application of the form to the input data
                  terminates.

      Step 4:  Continue at Step 2.

   In addition, during Step 2, if the remainder of the input string is
   insufficient to satisfy a rule, then that rule fails and partial
   results are not emitted.  If a rule fills the output string,
   application of the form is terminated.

II.  Rules

   A rule is a replacement operation of the form:

      left-hand-side -> right-hand-side

   Both sides of a rule consists of a series of zero or more _terms_
   (see below) separated by commas.

   The left-hand-side of the rule is applied to the input string at the
   current position as a pattern-match operation.  If it exactly
   describes the input, 1) the current input position pointer is
   advanced over the matched input, 2) the right-hand-side emits data at
   the current position in the output string, and 3) the current output
   position pointer is advanced over the emitted data.

III.  Terms

   A term is a variable that describes the input string to be matched or
   the output string to be emitted.  A term has three formats.










Anderson, et. al.                                               [Page 2]

RFC 83                 Language Machine For Data        18 December 1970


Term Format 1
+---------------------------------------------------------------------+
|                                                                     |
|     name ( data  replication  .   value     :    length    )        |
|            type   expression    expression      expression          |
|                                                                     |
|_____________________________________________________________________|

   Any of the fields may be absent.

   The _name_ is a symbolic name of the term in the usual programming
   language sense.  It is a single, lower-case alphabetic that is unique
   within a rule.

   The _data type_ describes the kind of data that the term represents.
   It is a member of the set:

         {D, O, X, A, E, B}

      Data types have the following meanings and implied unit lengths:

      Char.       Meaning               Length
      -----       --------              -------
       D          decimal number        1 bit
       O          octal number          3 bits
       X          hexadecimal number    4 bits
       A          ASCII character       8 bits
       E          EBCDIC character      8 bits
       B          binary number         1 bit

   The _replication expression_ is a multiplier of the value expression.
   A replication expression has the formats.

      1)  an arithmetic expression of the members of the set:

          {v(name), L(name) , numerals, programming variables}

      The v(name) is a value operator that generates a numeric value of
      the named data type and L(name) is a length operator that
      generates a numeric value of the named string length.

      The programming variable is described under term format three.
      Arithmetic operators are shown below and have their usual
      meanings.

         {*, /, +, -}





Anderson, et. al.                                               [Page 3]

RFC 83                 Language Machine For Data        18 December 1970


   or 2) the terminal '#' which means an arbitrary multiple of the value
           expression.

   The _value expression_ is the unit value of a term expressed in the
   format indicated by the data type.  The value expression is repeated
   according to the replication expression.  A value expression has the
   format:

      1) same as part 1) of the replication expression where again
         v(name) produces a numeric value

   or 2) a single member of the set

         {v(name), quoted literal}

         where v(name) produces a data type (E or A) value).  (Note that
         concatenation is accomplished through multiple terms.)

   The _length expression_ is the length of the field containing the
   value expression as modified by the replication expression.  It has
   the same formats as a replication expression.

   Thus, the term

      x(E(7.'F'):L(x)) is named x, is of type EBCDIC, has the value
      'FFFFFFF' and is of length 7.

   The term

      y(A:8) on the left-hand-side of a rule would be assigned the next
      64 bits of input as its value; on the right-hand-side it would
      only cause the output pointer to be advanced 64 bit positions
      because is has no value expression (contents) to generate data in
      the output area.

















Anderson, et. al.                                               [Page 4]

RFC 83                 Language Machine For Data        18 December 1970


Term Format 2
+---------------------------------------------------------------------+
|                                                                     |
|           name (label)                                              |
|                                                                     |
+---------------------------------------------------------------------+

   The _label_ is a symbolic reference to a previously named term in the
   rule.  It has the same value as the term by that name.

   The identity operation below illustrates the use of the _label_
   notation.

      a(A:10) -> (a)

   The (a) on the right-hand side causes the term a to be emitted in the
   output area.  It is equivalent to the rule below.

      a(A:10) -> (Av(a):L(a))


Term Format 3
+---------------------------------------------------------------------+
|                                                                     |
|   name    (  programming    connective        operand  )            |
|              variable                       expression              |
|                                                                     |
+---------------------------------------------------------------------+

   A _programming variable_ is a user-controlled data item that does not
   explicitly appear in the input/output streams.  Its value can be
   compared to input data, to constants, and used to generate output
   data.  Programming variables are single, lower case Greek symbols.

   They are used: to generate indices, counters, etc. in the output
   area; to compare indices, counters, etc. in the input area, and; to
   bind replacement rules where the data is context sensitive (explained
   later).

   A _connective_ is a member of the set:

         {<-, =, !=, >=, <=, <, >}

   The left arrow denotes replacement of the left part by the right
   part; the other connectives are comparators.






Anderson, et. al.                                               [Page 5]

RFC 83                 Language Machine For Data        18 December 1970


   The _operand expression_ is an arithmetic expression of members of
   the set:

         {programming variables, v(name), l(name), numerals}

   For example, if the programming variable [alpha] has the value 0 and
   the rule

      a(H[alpha]:1) -> (a), ([alpha]<-[alpha]+1), (H[alpha]:1)

   is applied exhaustively to string of hexadecimal digits

      0 1 2 3 4 5

   the output would be the hexadecimal string

      0 1 1 2 2 3 3 4 4 5 5 6 .

   Note:  the above rule is equivalent to

      a(B[alpha]:4) -> (a), ([alpha]<-[alpha]+1), (B[alpha]:4)


IV.  Restrictions and Interpretations of Term Functions

   When a rule succeeds output will be generated.  In the rule

      a(A:#),(A'/':1)->(Ev(a):74),(E'?':1)

   the input string is searched for an arbitrary number of ASCIIs
   followed by a terminal '/'.  The ASCIIs (a) are converted to EBCDIC
   in a 74-byte field followed by a terminal '?'.  This brings out three
   issues:

      1. Arbitrary length terms must be separated by literals since the
         data is not type-specific.

      2. The # may only be used on the left-hand-side of a rule.

      3. A truncation padding scheme is needed.











Anderson, et. al.                                               [Page 6]

RFC 83                 Language Machine For Data        18 December 1970


      The truncation padding scheme is as follows:

         a. Character to Character (types: A, E)

            Output is left-justified with truncation or padding (with
            blanks) on the right.

         b. Character to Numeric (A, E to D, O, H, B)

         c. Numeric to Character (D, O, H, B to A, E)

         d. Numeric to Numeric (D, O, H, B)

            Output is right-justified with padding or truncation on the
            left.  Padding is zeros if output is numeric.


EXAMPLES OF SOME DATA RECONFIGURATIONS

   The following are examples of replacement rule types for specifically
   needed applications.

   Literal Insertion