next up previous contents
Next: Over and Under Generation Up: SYNTAX Previous: Definite Clause Grammars   Contents


Feature Structure Unification Grammars

Although fixed arity can be introduced to DCGs to make the grammars more extensible, the order of each parameter in the list, (or in the predicate if fixed arity is not used) must be known and adhered to. A Feature Structure Unification Grammar (FSUG) allows much greater flexibility than DCGs although not offering any.

The key concept behind FSUGs is the feature structure which is a set of feature-value pairs, where features are unanalysable symbols drawn from a finite set, and values are either atomic symbols or feature structures themselves. Since the values are conceptually stored as sets, there is no ordering over them and the labels (or feature names) are necessary in order to determine which values belong to which feature [13].

Feature structures are often written, in the field of linguistics, as an Attribute Value Matrix (AVM). Figure 2.6 shows an example grammar rule for the transitive verb writes written in AVM form.

Figure 2.6: example AVM for word writes
\begin{figure}\begin{displaymath} \left[ \begin{array}{ll} & \\ CAT & v\\ VFO... ...nd{array}\right] \quad \rightarrow \quad writes\end{displaymath}\par\end{figure}

Since FSUGs use feature structures to represent words and rules, the existing method of combining rules to form a sentence will not be sufficient as they assume ordering on the arguments. Below are the three definitions with which FSUG rules can be combined.

  1. Given a feature structure \( G \), it can be extended in a consistent way by either adding new feature value pairs to \( G \), or by instantiating existing variables to constants or other feature structures.
  2. A feature structure \( S \) is a specialisation of another feature structure \( G \) if \( G \) can be extended to \( S \) in a consistent way (\( G \) is also a generalisation of \( S \)). Two features, \( S \) and \( T \), are unifiable if there exists another feature structure \( U \) which extends both \( S \) and \( T \) in a consistent way.
  3. The unification of two feature structures \( S \) and \( T \) is the minimal feature structure which extends both \( S \) and \( T \) in a consistent way.
Grammar rules of a DCG can be folded into much fewer rules in a FSUG because they are much more abstract. For example the grammar rule shown in Figure 2.8 covers both the rules in Figure 2.7, assuming values starting with an uppercase letter are variables, and those completely in lowercase are constants.

Figure 2.7: Two DCG rules
\begin{figure}\begin{displaymath} \begin{array}{ccc} VP(x_{num}) & \rightarrow &... ...(x_{num}), & PP(y_{num}) \end{array}\end{array}\end{displaymath}\par\end{figure}

Figure 2.8: FSUG grammar rule which generalised those shown in figure 2.7
\begin{figure}\begin{displaymath} \left[ \begin{array}{ll} & \\ HEAD & Head\\ ... ... OBJ2 & nil\\ & \end{array}\right] ,\; Obj1\end{displaymath}\par\end{figure}

FSUGs are very compact and abstract in comparison to DCGs and the difference is even more marked when compared to CFGs.

next up previous contents
Next: Over and Under Generation Up: SYNTAX Previous: Definite Clause Grammars   Contents
Andrew P Coates (UG) 2002-07-17