The Syntax

Context-free Rules

A context-free rule, as we have noted previously, describes the children which must be assigned to a tree node during the development of a syntax tree. Its most general form is that of a guarded rule:


    metavariable =
      < guard1: rhs1
      < guard2: rhs2
      ...
      > rhs_def
    %

where < marks individual subrules and > marks a default (if any). rhs1, rhs2, ... are sequences of child nodes, the right-hand sides of the examples in the Overview.

In the special case (actually the normal case) where the default is the only subrule, the marker > may be omitted.

The guards are conditions which involve attributes attached to the parent node or ones obtained from preselections, allowing the sequence of children to depend on these features. The guards are, in fact, a subset of those appearing in morphology rules, and will be discussed in that section. A simple example arises in generalizing the development of the NP node of earlier examples. Suppose that we replace the ROOT rule with:


    ROOT = choose No: Number, Pe: Person;
           NP[Pe, No]  V[vtdi, Pe, No, pres]  NP  PREP/"to"  NP %

permitting subject and verb to be any of first, second or third person. The NP rule must then take a form such as:


    NP =
      inherit Nu: Number;
      < first: PRON[first, Nu]
      < second: PRON[second, Nu]
      > (PRON[third, Nu] | DET[Nu]  N[Nu])
    %

restricting its child to be a pronoun if it has attribute value first or second, but permitting either a pronoun or a noun phrase if it has attribute value third.

Actually the ROOT rule must also indicate the function of the NP (subject or either object) in the sentence, so that the correct pronoun can be obtained from the lexicon. Also, the NP rule can be written more briefly here if the Person attribute is inherited:


    ROOT = choose No: Number, Pe: Person;
           NP[Pe, No, subj]  V[vtdi, Pe, No, pres]
                                         NP[obj] PREP/"to" NP[obj]
    %

    NP =
      inherit Nu: Number, Fu: Function, Pe: Person;
      < first | second: PRON[Pe, Nu, Fu]
      > (PRON[third, Nu, Fu] | DET[Nu]  N[Nu])
    %

where | in a guard denotes or. (In contrast to bars separating alternatives on the right-hand side of subrules, these need not be in parentheses.)

Stripped of its various attachments, each right-hand side in a context- free rule is a sequence of metavariables:


    A B C ... %

As we noted in the Overview, it may contain alternatives enclosed in parentheses, and these may be concatenated with metavariables and other alternatives. They may also be nested.

Some examples:


    (A | B) (C | D)
Choose either A or B, then either C or D; This is, of course, equivalent to (A C | A D | B C | B D).

    (A | B C | D (E | F))
Choose one of three alternatives. The third has an alternative of its own. Equivalent to (A | B C | D E | D F).

    (A | ) B
Equivalent to (A B | B).

As we see in the last example and we noted in the Overview, alternatives may be empty, but we must be careful that no empty alternative occurs in the "multiplied" expansion. If there is, and if this happens to be chosen, the node being developed will have no children and will become a leaf node. (The same happens if no guard is found true.) In this case, we presumably have a leaf node whose metavariable is not a word category and does not occur in the lexicon, leading to an error during lexicon search.

We have used the terms "factorization" and "multiplication" in connection with contracting or expanding the sequences on the right-hand side of context-free subrules. In fact, the analogy to algebraic factorization and muliplication is precise and complete if we interpret concatenation as multiplication and | as +, and also ensure that the order of the elements in multiplication is maintained. (In algebra, this is known as non-commutative multiplication. X Y is obviously not equivalent to Y X.)

Nested Structures, Recursion and Repetition

    This is the cat
    That killed the rat
    That ate the bran.

This example, taken from a well known nursery rhyme, shows a sentence involving a nested structure. The relative clause describing the cat itself contains a relative clause. We can generate this with context- free rules along the lines of:


    ROOT = TI/"this is" NPQUAL %

    NPQUAL = NP ( | REL) %

    NP = (DET N[common] | N[proper]) %

    REL = PRON/"that" (V[vtd, past] NPQUAL | NP V) %

where NP yields either "Jack" or a phrase like "the cat", NPQUAL may or may not attach REL, and REL produces a relative clause with the pronoun serving either as object ("that Jack built") or subject ("that killed the rat"). In the latter case, the object is NPQUAL once again, potentially leading to a further relative clause.

Leading scholars on The House That Jack Built will note a deficiency. NPQUAL must add an adjectival phrase ("with a crumpled horn", "all tattered and torn") to the first few lines, before switching to the simpler form. We leave it to these scholars to work out the necessary changes.

The rules shown here are recursive. Recursion occurs when a metavariable appears on the right-hand side of the rule which defines its children, either directly or, as here, a few levels removed. (NPQUAL may yield REL, which may yield NPQUAL, which may yield REL, and so on.)

Recursion can be used to produce not only nested structures, but also repetition. Suppose, for example, that we want a noun phrase to contain several adjectives. Omitting attachments, we may write:


    NP = DET ( | ADJLIST) N %

    ADJLIST = (ADJ | ADJ ADJLIST) %   or  ADJLIST = ADJ ( | ADJLIST) %

so that ADJLIST generates one or more ADJ's.

From a theoretical standpoint, we might have:


                NP = DET ADJLIST N %
                ADJLIST = ( | ADJ ADJLIST) %
                

where ADJLIST generates zero or more ADJ's; but, as mentioned earlier, the empty list will make ADJLIST into a leaf node.

The context-free rule:


    ADJLIST = (ADJ | ADJ ADJLIST) %

has the potential to generate very long strings of ADJ's. Consider the probabilities. If VINCI chooses the first alternative, a 1 in 2 chance, the list will end with a single ADJ. If it chooses the second, the other 1 in 2, the rule will recur and a second choice must be made. In half of the remaining cases, 1 in 4 of the original, it will choose the first this time. In the other half, it continues to a third choice; and so on. So ADJLIST will contain a single ADJ in about 1/2 of the time; two ADJ's, 1/4; three, 1/8; four, 1/16, ... There is a small chance, about 1 in a million, that the list will end up with 20 ADJ's, which means that if you generate a million ADJLIST's, one is likely to occur.

Are the percentages at the low end of this table realistic in natural language? Surely not. They are far higher than we see in normal writing. There is no direct mechanism in VINCI context-free rules analogous to the one in the lexicon to control the relative frequency of choices. We can achieve some control merely by replicating alternatives. For example, replacing the previous rule with:


    ADJLIST = (ADJ | ADJ | ADJ | ADJ ADJLIST) %

sharply reduces the probabilities of long strings.

Incidentally, these examples highlight a major difference between natural languages and the languages in which computer programs are expressed. In computer programs, deep nesting of linguistic structures and lengthy lists of items are commonplace. In natural language, notwithstanding the output of authors trying to demonstrate the possibility of 800-adjective sequences and the nesting of relative clauses in the complete Jack, repetition and nesting to more than one level are rare. Replacing the previous rule by:


    ADJLIST = (ADJ | ADJ ADJ) %

captures a very high proportion of the cases occurring in normal speech or writing.

Infinite Loops

Suppose we replace the earlier rules for ADJLIST by:


    ADJLIST = ADJ ADJLIST %

where there is no non-recursive way out. The recursion will never terminate and the syntax tree will never be completed -- a phenomenon known in computing as an infinite loop.

To prevent infinite loops, VINCI restricts the number of tree nodes on a tree. (The limit is currently about 400.) Once the tree reaches this limit, VINCI stops development, and all childless nodes become leaf nodes. Once again these will presumably lead to errors during lexicon search.

Parallel A: Comparing guarded rules and alternatives
(This section can safely be omitted on first reading)

If we consider the context-free rules:


    S1 =
      ( NP V NP PREP NP
      | NP V NP
      | NP V
      )
    %

and:


    S2 =
      < vtdi :  NP V NP PREP NP
      < vtd  :  NP V NP
      < vi   :  NP V
    %

we note a close similarity. The first offers three alternatives for the development of S1, to be chosen at random. The second offers the same alternatives, but the choice now depends on the presence of an attribute value attached to S2.

Unfortunately, the design of VINCI fails to exploit this parallel. Due largely to the long gap between the design of the former and the need to adapt its implementation for the latter, use of the latter is far more restrictive. Thus we cannot nest a set of guarded subrules within the right-hand side of another, or within an alternative. Guarded subrules can appear by themselves at the outermost level of the context-free rule. The effect, of course, can be obtained at the expense of introducing extra levels to the tree. So the NP rule above may itself be a guarded rule.

One day, perhaps ...

Attachments

We have seen that tree nodes may have a number of attachments placed on them while the tree is being developed, either by context-free rules or by syntax transformations. We will now define them fully and add others. Some of these attachments, those relevant to leaf nodes, may also appear on the terminal nodes in preselections and lexical transformations.

The kinds of attachments are:

transformation requestsNEG: INTERROG:
mandated choice V/"do"
attribute list V[vtdi, third, sing]
field restrictions V/5=$12
indirections N/@14: daughter
inverted indirections <not yet implemented>
_pre_ phrase N/_pre_ victim
frequency variation N/+5 or N/$2

Transformation requests, since they manipulate the children of a node, are useful only to non-leaf nodes. They appear before the metavariable. The more usual term for these in the computing field is calls.

A single attribute list can be present on either kind of node (leaf or non-leaf). It follows the metavariable and is enclosed in square brackets. Because of potential confusion with similar constructs linked to indirections, it must precede the remaining attachments. The others, since they cannot be inherited, are useful only on leaf/terminal nodes. They may appear in any order, though multiple indirections on the same node will be carried out in the order written.

All attachments except transformation calls restrict lexicon choice. A mandated choice, for example, is essentially a restriction on field 1; the metavariable itself, on field 2; the attribute list, on field 3. Field restrictions apply to fields higher than the third. The first of multiple indirections demands that its tag be present in the specified field. (For practical implementation reasons, no attempt is made to apply a similar restriction to subsequent indirections on the node. These may lead to errors when the indirection is executed.)

Transformation calls are simply placed on the node to await the end of context-free syntax tree development. At that point, the transformations are applied, starting at the root of the tree and proceeding downwards. Where several calls appear on a single node, the order of application may affect the outcome. For this situation, VINCI provides a priority feature, and the language describer should rely on this, not the order in which calls are attached. The reason for this will become apparent in a subsequent section.

A mandated choice involves a string pattern, possibly containing wildstars. (See Preliminaries.) Thus it may yield several lexicon entries for VINCI to choose from. If two mandated choices are placed on a single node, the current implementation ignores one of them. This contrasts with restrictions on fields above the third.

A field restriction has the form: /n=string where n is the number of a field higher than 3 and string is a string which may or may not be in double-quotes. The assumption is that the specified field of candidate lexicon entries contains one or more elements separated by commas, semicolons or colons. (Commas, semicolons and colons in double quotes don't count.) The string is required to match one of these. If the string is in double-quotes, it may contain a wildstar. Several different restrictions may apply to one field. All must be obeyed for the candidate entry to match the terminal node.

The frequency variation attachment demands a temporary change in the frequency associated with a chosen lexicon entry. It has one of the forms: /+n or /$n, where n is a number. The former specifies a new frequency. So /+0 makes the frequency zero, and prevents the entry being chosen again, while /+9999 might be expected to make its choice much more likely. The forms /$2, /$3, ... apply rules to increase, double, halve, ... the existing frequency. Full details are given in the on the Lexicon web page (see the Frequency Variation section). The frequencies revert to their original values when VINCI next installs the lexicon file.

The attribute list, enclosed in [ ], is more properly called a cf attribute list constructor. It has several close parallels: an indirection attribute list constructor, a transformation attribute list constructor and a preselection node attribute list constructor, which we will encounter in due course. Rather than being the attribute list itself, this constructs one. (The fixed list is just a special case.) It is a list of one or more components separated by commas, each constructing a compound attribute. The kinds of components are typified by:


    third.sing.masc,
    third.sing.Ge,
    Gender _pre_ villain,
    _pre_ Gender/obj,
    ...

Recalling our naming conventions (see Preliminaries), the first is just a compound attribute. The second involves an attribute variable, Ge, which itself represents a compound attribute. The value of Ge is used to build the list element. The third expects to get a Gender value from a preselected word tagged villain. This is an example of a _pre_ phrase. Its form will be discussed later. The same applies to _pre_ Gender/obj in the fourth example, which gets its value from a preselection tag itself. In this case, the example shows a deconstruction slash. Making assumptions about the nature of Gender, we can expect that the preselection tags include one of masc.obj or fem.obj. The _pre_ phrase finds the tag in question and discards its second component, leaving just the Gender value itself.

The _pre_ phrases cannot be used as part of longer compound attributes. This is essentially because of a potential ambiguity. X.Y _pre_ Z.W would be interpreted by VINCI as (X.Y) _pre_ (Z.W) rather than X.(Y _pre_ Z).W. These parentheses are not recognized by VINCI. In the context of a cf attribute list constructor, the effect can be obtained by associating Y _pre_ Z with an attribute variable and using this in the longer compound.

If the attribute list resulting from the construction is attached to a leaf node, it has two principal roles: to restrict lexical choice and to control morphology. If the leaf node also has a _pre_ phrase attached, the first of these roles is pre-empted (since the word has already been chosen), but the second remains. If it has an indirection, the second role is taken over by the attribute list linked to the indirection. (See below.)

Further roles for an attribute in the list attached to a tree node are to control the node's subsequent context-free development or to act as a marker for a transformation. In the latter case, if the node in question is a leaf node, the transformation must be careful to remove the marker or it may prevent any lexicon entry from being selected for the node.

An indirection has the general form:


     @n: tag[attlist_constr]

where:

One or more indirections may be attached to a terminal node. When a lexicon entry for the node has been chosen, VINCI is asked to replace it with a word that the lexicon entry is pointing at. The field number indicates the field where the pointer is to be found. The optional identifier is the tag labelling the pointer. (There may be several tags in one field.) If there is no tag, the pointer is expected to be untagged. If the tag labels more than one pointer, VINCI chooses one at random.

If several indirections are attached to a node, the action is repeated for each in turn, the one attached earliest being first.

The attribute list built by the indirection attribute list constructor takes over the second role (morphology control) from the list attached to the node itself. (The latter related to the original node word, and its attributes may be inappropriate to the new one. Indeed, the indirect word may not even be in the same word category.)

The constructor is very similar to the cf version described above. However, it does not permit attribute variables (they are no longer present at the time the list is built) and does permits a component typified by: !Gender/subj. This has the effect of "inheriting" a compound attribute from the immediately previous indirection or the node itself. Following the exclamation point there is an attribute pattern specifying the attribute to be inherited. The pattern may include deconstruction slashes. The list is optional. If it is not present, at least on the last indirection of the node, there will be no attributes to control its morphology, presumably because the ultimate word doesn't need any. Currently the constructor cannot include _pre_ phrases.

The _pre_ phrase attachment to a terminal node has the form: _pre_ D, where D is a compound attribute pattern. This bypasses lexical choice altogether, and requires VINCI to link the terminal node to the lexicon entry preselected for the tag which matches D. It overrides all restrictions, currently even the metavariable; VINCI is to make the connection regardless of any other considerations.

In regard to attachments, one further matter which must be addressed is the sharing of lexicon entries. This arises because subtrees can be replicated by syntax transformations or by copying a ROOT tree into other trees of a cluster. The intent is that the leaf nodes of the replicated trees refer to the same lexicon entries. Subsequent transformations, however, can add attachments to individual copies of the node.

What happens, then, in regard to the various search restrictions? In principle we want the restrictions from all sharing nodes to be combined. In practice, a closer look is necessary. First of all, note that nodes sharing an entry have the same metavariable at the time of lexicon search. The only attachments which can alter a word category are indirections, and these obviously cannot be performed until the entry has been chosen. It is common for these sharing nodes to have differing attributes: we may, for example, want a noun to be singular in a question, plural in an answer. The chosen noun must have both attribute values, and VINCI indeed combines them. The same applies to lexical field restrictions, just as it does when several restrictions are attached to one node. It is reasonable to combine these restrictions even if they apply to the same field, since each applies only to an element within the field. This is not the case with a mandated choice, since field 1 has only a single element. If mandated choices conflict between sharing nodes, all but one are discarded.

This is similar to the limitation mentioned earlier. There are a few specific cases where mandated choices could be combined; for example "p*" and "*d" could become "p*d", but VINCI does not attempt it.

What if one of the sharing nodes is given a _pre_ phrase attachment? Then that node will receive the preselected lexicon entry, and will no longer share an entry with the others. Caveat utilitor!

In general, and in contrast to current computing fashion, VINCI does not attempt to save a user from him/herself. If a user does something which appears wrongheaded, so be it. He/she may know better than the computer what is intended. Let the user beware. (With apologies to Latin scholars.)

Finally, if two sharing nodes have conflicting frequency variation attachments, all but one are ignored.

Choose, Inherit and Select Clauses

Choose, inherit and select clauses are used in context-free rules to associate compound attribute values with attribute variables. These can then be used to make compound attributes which share components. Choose clauses choose their values randomly; inherit clauses get them from the node being expanded; select clauses, from the preselections.

In this section, let Av denote an attribute variable: an identifier. Let C and D denote compound attribute patterns: compound attributes some of whose components are attribute types, which serve as wildcards matching any value of the type.

An inherit clause takes the form:


    inherit Av: C;

VINCI searches the attribute list of the tree node being developed, and assigns the compound attribute which matches C to the variable. C may contain deconstruction slashes, in which case components preceded by a slash are removed. If no compound attribute matches C, the inherit clause becomes a choose.

A choose clause is similar in form:


    choose Av: C;

but VINCI makes random choices for any type-components. In this case, deconstruction slashes serve no purpose, since the undesired components can simply be omitted.

Both presumably contain at least one type-component; otherwise the fixed compound attribute could directly replace the attribute variable. (The variable could, of course, serve as an abbreviation.)

A select clause has one of the forms:


    select Av: _pre_ D;
    select Av: C _pre_ D;

In both cases, VINCI looks for a preselection tag matching D. In the first, it takes the preselection tag itself as the desired compound attribute. In the second, it obtains the compound attribute from the lexicon entry associated with the tag. Both C and D may contain deconstruction slashes, though in the second form, slashes in D have no effect. If there is no match for D or, in the second form, no match for C in the lexicon entry, Av becomes empty and does not contribute to any compound attribute or attribute list in which it appears. Full details are given in the section on _pre_ phrases.

Since a choose clause cannot have _pre_ phrases, while a select clause must, these could have been synonyms. Hindsight is 20/20.

For choose and inherit clauses, we may contract:


    choose Na: Number; choose Nb: Number;

to:


    choose Na, Nb: Number;

and:


    choose Na, Nb: Number; choose Ge: Gender;

to:


    choose Na, Nb: Number, Ge: Gender;

We have not checked whether analogous contractions exist for select clauses.

The clauses can appear at the beginning of a context-free rule (before the first guard, if any), at the beginning of the right-hand side of any guarded subrule, or after any left parenthesis or vertical bar; and probably at other places too!

In the first case, the variable is local to the whole rule; in the second, to the subrule; in the third, to the particular alternative in which it appears.

Note the last case especially. If we have:


    inherit Na: Number; (X[Na] | choose Na: Number; Y[Na]) Z[Na]

X and Z receive the inherited Number value, Y the chosen one. In the second alternative, the choose clause temporarily "masks" the outer Na from sight.

Parallel B: Comparing context-free rules and a programming language
(This section can safely be omitted on first reading.)

Readers with programming experience may observe that the context-free component of the syntax is closely analogous to a programming language whose objective is to create a tree.

The context-free rules are, in essence, procedures. The appearance of a metavariable on the right-hand side of a subrule is a call to the corresponding procedure, and any attributes attached to it are parameters. Thus, NP[plur, subj] requests the creation of a subtree with NP as its root; NP is to be plural and to be in subject form (i.e. nominative). The process begins with a call to ROOT (and subsequently to any other tree roots which are present).

The leaf nodes are procedure calls of a different type. Their eventual role is to call the lexicon search process, with all of the attachments as parameters.

The if-then-else, if-then and case statements of programming languages are merely special instances of guarded rules. We note again the restriction on the latter which prevents them being nested or concatenated without introducing extra subprocedures. Loops are formed by recursion.

Choose and select clauses are assignments to "variables" (actually to constants, since they cannot be reassigned).

The inherit clause plays an interesting role. In contrast to the procedures in programming languages, these procedure definitions (i.e. the context-free rules themselves) have no formal parameters in their heads to which the actual parameters can be matched. Instead, the inherit clauses pick these up and assign them to attribute variables. This means that if there are two parameters of the same type, they must be compounded and have some component which distinguishes them. This is the exact characteristic of data in "associative memory", which must be accessed by the content of the data itself, not by an "address".

In contrast to the customary programming language procedure, VINCI does not suspend work on one tree node (say, NP) while the subprocedures are executed. This does not, however, affect the outcome, since the development of the subtree is not affected by the development of the sibling nodes nor vice versa. This is, of course, is exactly what context-free means.

Syntax and Attributes -- Generating the House That Jack Built

The House That Jack Built is a rather more complex example of context-free rules than the others we have shown. It also illustrates the use of some of the features.

Syntax Transformations

Let us review points already mentioned in earlier sections or in the Overview:

(a) Transformation requests (calls) are planted on syntax tree nodes by context-free rules. (They can also be added by transformations themselves for application later in the sequence.)

(b) The transformations themselves are applied when context-free development of the tree has been completed.

(c) The transformations manipulate the children of the node (along with their subtrees). They can duplicate them, reorder them, discard them, add new attachments, and even add new children.

(d) They are of use only on non-leaf nodes.

Transformations are applied from the top down, that is to say, they are applied to parent nodes before their children. They are also applied to siblings in left-to-right order, but this is of no consequence because a transformation cannot affect, nor can it be affected by, sibling nodes or their subtrees.

More important is the order of application when several are planted on one node. As we shall see in a later section, this can affect the outcome. Since, however, they can be planted at different times (by a context-free rule and by earlier transformations), it is not safe to rely on the order of placement, and VINCI has a priority numbering feature.

The Guards

Syntax transformations are guarded rules, each guard being a pattern of metavariables against which the children of the tree node are matched. Their use is illustrated by enlarging the negation example given in the Overview to permit verbs with direct objects only, as well as those with both direct and indirect:


    ROOT = NEG: S %

    S    = choose No: Number;
           (
              NP[No]  V[vtdi, third, No, pres]  NP  PREP/"to"  NP
           |
              NP[No]  V[vtd, third, No, pres]  NP
           )
    %


    NP   = inherit Nu: Number;
           DET[Nu]  N[Nu] %

    NEG  = TRANSFORMATION
      NP V NP PREP NP: 1  V[2!Number, 2!Person, 2!Tense]/"do"
                      ADV/"not"  2[-Number, -Person, bare_inf]  3  4  5;

      NP V NP: 1  V[2!Number, 2!Person, 2!Tense]/"do"
                      ADV/"not"  2[-Number, -Person, bare_inf]  3;
    %

S can now generate two varieties of sentence, and correspondingly NEG has two subrules. The first caters for the double-object sentence, the second for the direct object one.

The guard may also contain wildstars, *, which match zero or more children. So NEG might have been written more shortly as:


    NEG  = TRANSFORMATION
      NP V *: 1  V[2!Number, 2!Person, 2!Tense]/"do"
                      ADV/"not"  2[-Number, -Person, bare_inf]  3;
    %

with * matching either NP PREP NP or just NP.

Some further points:

A wildstar appearing by itself as the guard, of course, denotes a default rule.

A metavariable occurring in a guard may be accompanied by an attribute list pattern. So N[sing] in a guard will match only a child N having sing among its attributes, while V[Person, plur] matches only a child V having both plur and some Person value.

Two wildstars in a guard create the potential for ambiguity: the V in * V * can match either V in X V Y V Z. In such a case, VINCI finds the leftmost match (the first V in this example).

Two wildstars in a guard must not touch. (So NP * * V is not allowed.)

The Constructors

The right-hand side of each guarded subrule is a constructor, telling VINCI how to reassemble the children of the node. (To be more precise, we should say reassemble the subtrees headed by the children. When we duplicate, delete or move a child, its whole dependent subtree goes along.)

The components (metavariables and wildstars) of the guard are implicitly numbered in sequence. So, in the case of * V *, the first wildstar is 1, the V is 2, and the second wildstar is 3. When these numbers appear in the constructor, they refer to the subtree (or sequence of subtrees) which matched the component. (Be aware, of course, that the number corresponding to a wildstar may refer to zero or more subtrees.)

A constructor consists of a sequence of numbers and metavariables, and sets out the order in which the subtrees are to reassembled. The numbers can be in any order, and the corresponding subtrees will be reordered accordingly. They can be omitted, and the corresponding subtrees will vanish. They can be duplicated, in which case the corresponding subtrees will be duplicated. Note especially that when a subtree is copied, corresponding leaf nodes will eventually refer to the same lexicon entry.

Metavariables in the constructor call for the introduction of new nodes. These nodes are normally leaf nodes because no further context-free development will take place.

It would be reasonable to add a non-leaf node as a marker for a later transformation on the same node. The later one should then remove it to prevent a lexicon search error.

Attachments

Attachments may be added to the new metavariables of the constructor, or to numbers which correspond to a metavariable of the guard.

In principle, they may not be attached to numbers which correspond to a wildstar. This is because a wildstar may match many children or none, and it is not clear what is meant to be done with the attachments. In practice, the current implementation lets you get away with this, placing the attachments on the last node of several, and on the immediately preceding node of zero. (The answer to the obvious follow-up question is that this writer doesn't know!) We don't promise to retain this implementation.

Except for attribute constructors, attachments are the same as the ones described for context-free rules. Those attached to numbers, of course, are added to any already present on the tree node. It is perfectly legal to add new transformation calls to non-leaf nodes. These will be applied when the application stage arrives at the children of the node. (Recall that transformations attached to a parent are carried out before those on the children.)

The transformation attribute constructor is a little different from its context-free counterpart. The latter assumes a blank slate; the former may start with an existing attribute list. There are, of course, no attribute variables, since transformations have none of the assignment clauses. If C and D are compound attribute patterns and n is the number of a node, the possible components of the attribute constructor are:

-C
look for a compound attribute matching C in the existing list and remove it

There is, by the way, is no problem in removing a value which is to be picked up by a later component. The new lists do not take effect until the whole transformation is complete.

n!C
find a compound attribute matching C in the list attached to node n, and add it to the list

C
add C to the list (C presumably contains only values)

_pre_ D
C _pre_ D
obtain a compound attribute from the the preselections (as described under Select clauses) and added it to the list.

The lack of inherit clauses prevents a child inheriting a value from the parent. There is no obvious reason why transformations should not have contained inherit clauses. It would be difficult to add them now, but a further component: !Number (inherit Number from parent) would fill this gap.

The Attribute Force

If any of these components adds a simple (i.e. non-compound) attribute to the list, VINCI carries out an attribute force:

The list is checked to see if another value of the same type is already present. If so, this old value is changed to the new one. Then, if the child node is not a leaf node, all values down its subtree which were inherited from the old value are changed as well.

What is the rationale for this?

(a) Nothing in VINCI requires that values of a grammatical attribute type are mutually exclusive, but two simple attributes of the same type in a list attached to a tree node cause problems both for inheritance and morphology control. (An inherit clause, for example, must make an arbitrary choice.) Replacement is therefore more useful than addition.

(b) In the absence of an inherit clause or some equivalent, attributes attached to a non-leaf node cannot be passed down its subtree. There is therefore no way to transform, say, a singular subtree (whatever that may be) to a plural one.

(c) In applications to language teaching, an instructor often wants to do just that: to generate a "question" with a singular subject and a corresponding "answer" with a plural one.

The attribute force fills the gap in a convenient way.

Why not non-simple attributes too?

Essentially because, with non-simple compounds, it is quite normal for, say, sing.subj and plur.obj (which have the same type) to co-exist in the same list; indeed, this was the reason for introducing compound attributes in the first place.

If we are asked to "force" plur.subj into such a list, human intuition suggests that we probably want to change sing.subj, not plur.obj. Unfortunately, no such decision process is available to a computer.

The restriction can be circumvented when necessary by introducing extra simple attributes which combine the multiple pieces of information.

By the way, the current implementation is slightly flawed, and in contrived cases it is possible for VINCI to miss some of the forced changes.

Ordering of Transformations: Priorities

To consider the appearance of two or more transformations on a single node, we return to our negation example, but in French.


    ROOT = S %

    S = choose Ge1, Ge2, Ge3: Genre, No1, No2, No3: Nombre;
        NP[Ge1, No1] V[vtdi, No1, prés, p3] NP[Ge2, No2] NPI[Ge3, No3]
    %

    NP  =
        inherit No: Nombre, Ge: Genre;
        DET[Ge, No] N[Ge, No]
    %

    NPI =
        inherit No: Nombre, Ge: Genre;
        PREP/"à" NP[No, Ge]
    %

This is closely similar to the English example, but we have opted for identifiers which are French words, and have combined preposition and noun phrase into a single structure, NPI. The structures must also choose/inherit both number and gender values, because of the gendered nature of the French language, and these are chosen for the objects of the verb to allow for their conversion to pronouns. We assume, incidentally, that the morphology process will take care of contracting à le to au, etc. where necessary.

Font problem

Some of our examples from now on are taken from French. This may give you a problem if the type font being used by your browser does not conform to the ISO 8859-1 (Latin 1) standard. Accented letters may appear as Greek or Cyrillic characters or in some other form. The following should appear as:

e-acute é
e-grave è
e-circumflex ê
c-cedilla ç

If you are not seeing them correctly, or if you are unable to distinguish the accents even with a 100-power magnifying glass, please consider changing the font.

Suppose that we want to carry out either or both of two transformations; one to make the sentence negative, the other to replace the direct object by a pronoun.

Formation of negatives in French requires us to surround the active verb by ne ... pas, while the direct object pronoun (le here) must be placed before the verb. Thus:


    le professeur donne le livre à l'étudiant
    le professeur ne donne pas le livre à l'étudiant
    le professeur le donne à l'étudiant

If both changes are made together, the correct form is:


    le professeur ne le donne pas à l'étudiant

not:


    *le professeur le ne donne pas à l'étudiant

In other words, the negative adverbs must surround both the verb and its attendant pronoun.

We could write each of the two transformations with several guarded subrules, to account for the different patterns the children of S might take when the transformations are applied. This, however, would be very tedious, especially if the number of transformations is increased to seven, as we shall do in a later example! Instead, we shall note that each transformation simply requires us to place something before (and sometimes after) the verb, and will do so in the right order provided the transformations are carried out in the right order. Specifically, the item which is to end up closest to the verb must be moved last.


    NEG = TRANSFORMATION
    {causes sentence to become negative; V is surrounded by "ne" and "pas"}
    PRIORITY 4
        * V * : 1 ADV/"ne" 2 ADV/"pas" 3;
    %

    PRON_DIR = TRANSFORMATION
    {replaces the direct object by a pronoun}
    PRIORITY 6
        * V * NP * : 1 PRON[objd, pronper, clit, p3, 4!Genre, 4!Nombre] 2 3 5;
    %

The attributes attached to the pronoun cause VINCI to choose a third person, personal, direct object, clitic pronoun, carrying the number and gender of the direct object. The latter, of course, is eliminated.

The priority numbers ensure that NEG is applied before PRON_DIR. (The lowest number is the highest priority. If no priority number is shown, the default is 5.) The unusual choice of numbers here has to do the subsequent larger example.

The priority numbers allow us to attach the calls in any order. In fact, with some slight care over the ROOT, QUESTION and ANSWER rules, we can have positive or negative questions with direct pronoun answers, or pronoun or non-pronoun questions with negative answers.

Built-in Transformations

VINCI allows for built-in transformations, transformations which a user can simply call without having to write them. We have so far provided only one:


    FLATTEN

If this is applied to any non-leaf node, it replaces the subtree headed by that node by a flat tree containing just the node with all the leaf nodes of the original as its children. For example:

   < tree picture to follow > 

Among other things, this caters for a situation where a transformation needs to move a structure which is much further down a tree. If the context-free rules plant spurious leaf nodes as markers around the subtree, the transformation can flatten the tree and use a guard with a wildcard to locate and move it.

FLATTEN has priority 10, allowing user-written transformations either to precede or follow it.

Transformations: A More Complex Example

The Generous Professor is a rather more complex than our previous examples, and illustrates some of the capabilities of syntax transformations.

Sentence Clusters

In the Overview, we mentioned the generation of related "question" and "answer" sentences. This was achieved by defining context-free rules for the metavariables QUESTION and ANSWER, which act as root nodes for additional trees and, in their turn, yield the desired sentences.

VINCI provides twenty such root nodes: QUESTION, ANSWER, R_3, R_4, ..., R_20. Typically these generate one or more related questions, each with alternative expected answers. The relationship between them is provided by the ROOT tree. As we noted in the Overview, the syntax tree for ROOT is expanded first using context-free rules only. VINCI then expands the other roots in the same way, but if it encounters ROOT on the right-hand side of a rule, it copies the existing ROOT tree rather than re-expanding it. In effect, the related trees will usually be (or contain) transformations of a common ROOT. Corresponding leaf nodes in the copies refer to the same lexicon entry (though, of course, the transformations may alter this with indirections). As is the case when a syntax transformation duplicates a subtree, lexical choice for these leaf nodes tries to satisfy the combined restrictions from all copies.

Note that whenever any of the additional tree roots is present in the syntax, the ROOT tree is not developed beyond the context-free stage. It is not syntactically transformed, and does not yield a sentence of its own. It merely acts as a common subsidiary for the others. Any transformations it contains are, of course, performed separately on each of the other trees.

Syntax Files

All three kinds of syntax rule: context-free, transformation and preselection, may coexist in a single syntax file.

As the reader will no doubt have noticed, each rule ends with a % symbol.

VINCI actually allows two separate syntax files to be installed simultaneously. One of these, which we call the syntax file, typically contains fixed features of the language -- in essence, a library of common structures, which may be provided by a super-describer. It is likely to be used for many different sets of generations. The other, which we call the user file, typically contains transient rules, used for the current exercise or set of generations. We avoid the common terms: global and local, which may cause some confusion in this context.

In scanning the installed rules, VINCI searches from the bottom upwards, so that the latest installed rule supersedes any other of the same name.

Details are given in the section on Files and Installation.