1.1.3. The syntax of the strict language

1.1.3.1. Protonotions

1. "small syntactic marks", written, in this Report, as "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "(", ")";
2. "large syntactic marks", written, in this Report, as "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9";
3. "other syntactic marks", written, in this Report, as "." ("point"), "," ("comma"), ":" ("colon"), ";" ("semicolon"), "" ("apostrophe"), "-" ("hyphen") and "*" ("asterisk").

b) A "protonotion" is a possibly empty sequence of small syntactic marks.

c) A "notion" is a {nonempty} protonotion for which a production rule can be derived {1.1.3.2.a , 1.1.3.4.d}.

d) A "metanotion" is a {nonempty} sequence of large syntactic marks for which a metaproduction rule is given or created {1.1.3.3.a }.

e) A "hypernotion" is a possibly empty sequence each of whose elements either is a small syntactic mark or is a metanotion.

{Thus the class of protonotions {b} is a subclass of the class of hypernotions. Hypernotions are used in metaproduction rules {1.1.3.3 }, in hyper-rules {1.1.3.4 }, as paranotions {1.1.4.2} and, in their own right, to "designate" certain classes of protonotions {1.1.4.1 }.}

{A "paranotion" is a hypernotion to which certain special conventions and interpretations apply, as detailed in 1.1.4.2 .}

f) A "symbol" is a protonotion ending with 'symbol'. {Note that the paranotion symbol {9.1.1.h } designates a particular occurrence of such a protonotion.}

{Examples:

b)

'variable point'

c)

'variable point numeral' {8.1.2.1.b }

d)

"INTREAL" {1.2.1.C }

e)

'reference to INTREAL'

f)

'letter a symbol' .

Note that the protonotion 'twas brillig and the slithy toves' is neither a symbol nor a notion, in that it does not end with 'symbol' and no production rule can be derived for it. Likewise, "LEWIS" and "CAROLL" are not metanotions in that no metaproduction rules are given for them.

g) In order to distinguish the various usages in the text of this Report of the terms defined above, the following conventions are adopted:

1. No distinguishing marks {quotes, apostrophes or hyphens} are used in production rules, metaproduction rules or hyper-rules;
2. Metanotions, and hypernotions which stand for themselves {i.e., which do not designate protonotions}, are enclosed in quotes;
3. Paranotions are not enclosed in anything {but, as an aid to the reader, are provided with hyphens where, otherwise, they would have been provided with blanks};
4. All other hypernotions {including protonotions} not covered above are enclosed in apostrophes {in order to indicate that they designate some protonotion, as defined in 1.1.4.1.a };
5. Typographical display features, such as blank space, hyphen, and change to a new line or new page, are of no significance (but see also 9.4.d ).

1. LEAP :: local ; heap ; primal. is a metaproduction rule ;
2. "INTREAL" is a metanotion and designates nothing but itself;
3. reference-to-INTREAL-identifier, which is not enclosed in apostrophes but is provided with hyphens, is a paranotion designating a construct {1.1.4.2.a };
4. 'variable point' is both a hypernotion and a protonotion; regarded as a hypernotion, it designates itself regarded as a protonotion;
5. 'reference to real' means the same as 'referencetoreal'.

1.1.3.2. Production rules and production trees

b) A "production rule" consists of the following items, in order:

an optional asterisk ; a nonempty protonotion N ; a colon ; a nonempty sequence of "alternatives" separated by semicolons ; a point.

{The optional asterisk, if present, signifies that the notion is not used in other production rules, but is provided to facilitate discussion in the semantics. It also signifies that that notion may be used as an "abstraction" {1.1.4.2.b } of one of its alternatives.}

c) An "alternative" is a nonempty sequence of "members" separated by commas.

d) A "member" is either

1. a notion {and may then be said to be productive, or nonterminal},
2. a symbol {which is terminal},
3. empty, or
4. some other protonotion {for which no production rule can be derived}, which is then said to be a "blind alley".

{Examples:

b)

exponent part : times ten to the power choice, power of ten. {8.1.2.1.g }· times ten to the power choice : times ten to the power symbol ; letter e symbol. {8.1.2.1.h }

c)

times ten to the power choice, power of ten ·times ten to the power symbol ·letter e symbol

d)

times ten to the power choice ·power of ten ·times ten to the power symbol ·letter e symbol }

e) A "construct in the strict language" is any "production tree" {f} that may be "produced" from a production rule of the language.

f) A "production tree" T for a notion N, which is termed the "original" of T, is "produced" as follows:

• let P be some {derived} production rule for N;
• a copy is taken of N;
• a sequence of production trees, the "direct descendents" of T, one produced for each nonempty member of some alternative A of P, is attached to the copy; the order of the sequence is the order of those members within A;
• the copy of the original, together with the attached direct descendents, comprise the production tree T.

The "terminal production" of a production tree T is a sequence consisting of the terminal productions of the direct descendents of T, taken in order.

The "terminal production" of a production tree consisting only of a symbol is that symbol.

Example:

{The terminal production of this tree is the sequence of symbols at the bottom of the tree. In the reference language, its representation would be e+02.}

A "terminal production" of a notion is the terminal production of some production tree for that notion {thus there are many other terminal productions of 'exponent part' besides the one shown}.

{The syntax of the strict language has been chosen in such a way that a given sequence of symbols which is a terminal production of some notion is so by virtue of a unique production tree, or by a set of production trees which differ only in such a way that the result of their elaboration is the same (e.g., production trees derived from rules 3.2.1.e (balancing), 1.3.1.d,e (predicates) and 6.7.1.a,b (choice of spelling of the mode of a coercend to be voided); see also 2.2.2.a ).

Therefore, in practice, terminal productions (or representations thereof) are used, in this Report and elsewhere, in place of production trees. Nevertheless, it is really the production trees in terms of which the elaboration of programs is defined by the semantics of this Report, which is concerned with explaining the meaning of those constructs whose originals are the notion 'program'.}

g) A production tree P is a "descendent" of a production tree Q if it is a direct descendent {f} either of Q or of a descendent of Q. Q is said to "contain" its descendents and those descendents are said to be "smaller" than Q. {For example, the production tree

FIXME

occurs as a descendent in (and is contained within and is smaller than) the production tree for 'exponent part' given above.}

h) A "visible" ("invisible") production tree is one whose terminal production is not (is) empty.

i) A descendent {g}U of a production tree T is "before" ("after") a descendent V of T if the terminal production {f} of U is before (after) that of V in the terminal production of T. The {partial} ordering of the descendents of T thus defined is termed the "textual order". {In the example production tree for 'exponent part' {f}, the production tree whose original is 'plusminus' is before that whose original is 'digit two'.}

j) A descendent A of a production tree "follows" ("precedes") another descendent B in some textual order if A is after (before) B in that textual order, and there exists no visible {h} descendent C which comes between A and B. {Thus "immediately" following (preceding) is implied.}

k) A production tree A is "akin" to a production tree B if the terminal production {f} of A is identical to the terminal production of B.

1.1.3.3. Metaproduction rules and simple substitution

a) The "metaproduction rules" {b} of the language are those given in the sections of this Report whose heading begins with "Syntax", " Metasyntax" or "Metaproduction rules", together with those obtained as follows:

• for each given metaproduction rule, whose metanotion is M say, additional rules are created each of which consists of a copy of M followed by one of the large syntactic marks "0", "1", "2", "3", "4", "5", "6", "7", "8" or "9", followed by two colons, another copy of that M and a point.

b) A "metaproduction rule" consists of the following items, in order:

an optional asterisk ; a nonempty sequence M of large syntactic marks ; two colons ; a nonempty sequence of hypernotions {1.1.3.1.e } separated by semicolons ; a point.

{The asterisk, if present, signifies that the metanotion is not used in other metaproduction rules or in hyper-rules, but is provided to facilitate discussion in the semantics.}

{Examples:

}

INTREAL :: SIZETY integral ; SIZETY real. {1.2.1.C }·

SIZETY :: long LONGSETY ; short SHORTSETY ; EMPTY. {1.2.1.D }

c) A "terminal metaproduction" of a metanotion M is any protonotion which is a "simple substitute" {d} for one of the hypernotions {on the right hand side} of the metaproduction rule for M.

d) A protonotion P is a "simple substitute" for a hypernotion H if a copy of H can be transformed into a copy of P by replacing eaclo metanotion M in the copy by some terminal metaproduction of M.

{Thus two possible terminal metaproductions {c} of "INTREAL" are 'integral' and 'long long real'. This is because the hypernotions 'SIZETY integral' and 'SIZETY real' (the hypernotions of the metaproduction rule for "INTREAL") may, upon simple substitution {d}, give rise to 'integral' and 'long long real', which, in turn, is because '' (the empty protonotion) and 'long long' are terminal metaproductions of "SIZETY".}

{The metanotions used in this Report have been so chosen that no concatenation of one or more of them gives the same sequence of large syntactic marks as any other such concatenation. Thus a source of possible ambiguity has been avoided.

Although the recursive nature of some of the metaproduction rules makes it possible to produce terminal metaproductions of arbitrary length, the length of the terminal metaproductions necessarily involved in the production of any given program is finite.}

1.1.3.4. Hyper-rules and consistent substitution

b) A "hyper-rule" consists of the following items, in order:

an optional asterisk ; a nonempty hypernotion H ; a colon ; a nonempty sequence of "hyperalternatives" separated by semicolons ; a point.

c) A "hyperalternative" is a nonempty sequence of hypernotions separated by commas.

{Examples:

b)

NOTION sequence : NOTION ; NOTION, NOTION sequence. {1.3.3.b }

c)

NOTION, NOTION sequence

d) A production rule PR {1.1.3.2.b } is derived from a hyper-rule H R if a copy of HR can be transformed into a copy of PR by replacing the set of all the hypernotions in the copy by a "consistent substitute" {e} for that set.

e) A set of {one or more} protonotions PP is a "consistent substitute" for a corresponding set of hypernotions HH if a copy of HH can be transformed into a copy of PP by means of the following step:

Step :

If the copy contains one or more metanotions then, for some terminal metaproduction T of one such metanotion M, each occurrence of M in the copy is replaced by a copy of T and the Step is taken again.

{Since some metanotions have an infinite number of terminal metaproductions, the number of production rules which may be derived is infinite. The language is, however, so designed that, for the production of any program of finite length, only a finite number of those production rules is needed.}

{

f) The rules under Syntax are provided with "cross-references" to be interpreted as follows.

Each hypernotion H of a hyperalternative of a hyper-rule A is followed by a reference to those hyper-rules B whose derived production rules are for notions which could be substituted for that H. Likewise, the hypernotions of each hyper-rule B are followed by a reference back to A. Alternatively, if H is to be replaced by a symbol, then it is followed by a reference to its representation in section 9.4.1 . Moreover, in some cases, it is more convenient to give a cross-reference to one metaproduction rule rather than to many hyper-rules, and in these cases the missing cross-references will be found in the metaproduction rule.

Such a reference is, in principle, the section number followed by a letter indicating the line where the rule or representation appears, with the following conventions:

1. the references whose section number is that of the section in which they appear are given first and their section number is omitted; e.g., "8.2.1.a" appears as "a" in section "8.2.1 ";
2. all points and a final 1 are omitted, and 10 appears as A; e.g., "8.2.1.a" appears as "82a" elsewhere and "10.3.4.1.1.i" appears as "A341i";
3. a section number which is the same as that of the preceding reference is omitted; e.g., "82a,82b,82c" appears as "82a,b,c";
4. the presence of a blind alley derived from that hypernotion is indicated by "-"; e.g., in 8.0.1.a after "MOID denotation", since "MOID" may be replaced by, for example, 'reference to real', but 'reference to real denotation' is not a notion.