Description Compilation

[User's Manual]
[Code] The description compiler in ALE is responsible for compiling feature structure descriptions into Prolog code. Carpenter (1992) defines a description as follows:

Definition 15   (Descriptions) The set of descriptions over the collection $Type$ of types and $Feat$ of features is the least set $Desc$ such that:

• $\sigma\in Desc$ if $\sigma\in Type$
• $\top\in Desc$
• $\pi: \phi\in Desc$ if $\pi\in Path$, $\phi\in Desc$
• $\pi_1\doteq\pi_2\in Desc$ if $\pi_1,\pi_2\in Path$
• $\phi\wedge\psi,\phi\vee\psi\in Desc$ if $\phi,\psi\in Desc$

The most basic kind of description is a simple type $\sigma$. Such a description applies to objects which are of the type $\sigma$. Since $\bot\in Type$, $\bot$ is a description, and it describes any feature structure while $\top$, which must be explicitly defined to be a description, is not satisfied by any feature structure. In practice, $\top$ is used to denote failure in unification. A description of the form $\pi:\phi$ applies to objects whose value for the path $\pi$ satisfies the description $\phi$. A description of the form $\phi_1\doteq\phi_2$ is taken to mean that the value of the object that you get by following the path $\pi_1$ is structure-shared to the value of the object that you get by following the path $\pi_2$. Conjunction and disjunction are interpreted in the usual way. Descriptions are used in various places in a grammar including phrase-structure rules, lexical entries, constraints, macros, and procedural attachments.

Description compilation is performed in four steps as follows:

• Serialization
• Sorting
• Peephole optimization
• Code Generation

These steps are described in the following sections.