5.1 Definition

The goal of the transformation scheme is to produce a PUTD invocation which has the function translated from the extended syntax as its actual parameter. A rule has a name in brackets <> by which it is known and is defined by what follows the meta symbol ::=. Each rule of the set consists of one or more “alternatives” separated by the meta symbol, being the different ways in which the rule will be matched by source text. Each alternative is composed of a “recognizer” and a “generator” separated by the =⇒ meta symbol. The recognizer is a concatenation of any of three different forms. 1) Terminals - Upper case lexemes and punctuation which is not part of the meta syntax represent items which must appear as is in the source text for the rule to succeed. 2) Rules - Lower case lexemes enclosed in <> are names of other rules. The source text is matched if the named rule succeeds. 3) Primitives - Lower case singletons not in brackets are names of primitives or primitive classes of Standard LISP. The syntax and semantics of the primitives are given in Part I.

The recognizer portion of the following rule matches an extended syntax procedure:

<function> ::= ftype PROCEDURE id (<id list>);
   <statement>; =⇒

A function is recognized as an “ftype” (one of the tokens EXPR, FEXPR, etc.) followed by the keyword PROCEDURE, followed by an “id” (the name of the function), followed by an <id list> (the formal parameter names) enclosed in parentheses. A semicolon terminates the title line. The body of the function is a <statement> followed by a semicolon. For example:


satisfies the recognizer, causes the generator to be activated and the rule to be matched successfully.

The generator is a template into which generated items are substituted. The three syntactic entities have corresponding meanings when they appear in the generator portion. 1) Terminals - These lexemes are copied as is to the generated text. 2) Rules - If a rule has succeeded in the recognizer section then the value of the rule is the result of the generator portion of that rule. 3) Primitives - When primitives are matched the primitive lexeme replaces its occurrence in the generator.

If more than one occurrence of an item would cause ambiguity in the generator portion this entity appears with a bracketed subscript. Thus:

<conditional> ::=

   IF <expression> THEN <statement1>

ELSE <statement2>

has occurrences of two different <statement>s. The generator portion uses the subscripted entities to reference the proper generated value.

The <function> rule appears in its entirety as:

<function> ::= ftype PROCEDURE id (<id list>);<statement>; =⇒

   (PUTD (QUOTE id)

(QUOTE ftype)

(QUOTE (LAMBDA (<id list>) <statement>)))

If the recognizer succeeds (as it would in the case of the NULL procedure example) the generator returns:


The identifier in the template is replaced by the procedure name NULL, <id list> by the single formal parameter X, the <statement> by (EQ X NIL) which is the result of the <statement> generator. EXPR replaces ftype, the type of the defined procedure.