We are also interested in the derivational history of a parsed or generated expression, i.e., in the derivation tree which represents how a certain derivation is licensed by the rules and lexical entries of the grammar. Note that such a derivation tree does not necessarily reflect how the parser or generator goes about finding such a derivation tree for a given string or logical form.
We will represent such a derivation tree as a feature structure value of the feature . Each head of a definite clause of the grammar (i.e., the grammar rules and lexical entries) has to have an additional feature which value is a constant that uniquely identifies this clause. The feature is used to express the relationship between the \ features of the body of a clause and its head. For lexical entries and for empty productions, the value of this feature is the empty list, and for grammar rules other than empty productions, the value will be a list whose sequence corresponds with that of the elements of the body. Thus the general structure of a definite clause with the \ feature is (using our abbreviations for feature structures):
For unit clauses (representing for example lexical entries) we have the general form
Using the simple context-free grammar we can adapt it for representing the derivation feature as follows:
For the string ``Peter sleeps'' the resulting derivation tree represented as a feature structure is the following:
Note that the sequence of the daughters derivation directly reflects the sequence of elements of the clause's body. However, it does not indicate in which order the elements of the body have been processed. Furthermore, since we only require that the rule name identifier should be present in the derivation tree representation, the derivation tree represented in the grammar only specifies ``a backbone'', i.e., it only says, which rules have been applied. However, applying these rules exactly in this order (or structure) would ``replay'' the successful derivation of the result, which finally would result in the same feature structure.
We say that the value of a feature is complete, if every element of the feature is complete. The value of a unit clause is complete by definition, because its feature is empty. This means a value of the feature of a found answer is complete.
We say that the value of a feature is partial, if there exists an element of the feature, which is not complete. Since, this incomplete daughter element corresponds to an element of the body of a clause, this means that for this clause not all elements have been processed.