Serialization

The first thing that the compiler needs to do, during description compilation, is to translate a description into a series of instructions that tell the compiler what code needs to be generated. This step is called serialization.

Six kind of instructions are generated in this step. These are instructions for types, variables, feature structures, inequations, functions, and disjunctions. The syntax of these instructions is provided in Table 4.1.

Table 4.1: The syntax of serialized instructions

Description	Instruction
Types	type Path, Type
Variables	var Path, Var
Feature Structures	fs Path, FS
Inequations	ineq Path1, Path2
Functions	fun Rel, Arity, ArgPaths, ResPath
Disjunctions	or Path, (Code1; Code2)

Path refers to the feature path that leads to the item in question. To illustrate, let us go through an example. Suppose we want to compile the feature structure below:

phrase,
  dtrs:(hc_struct,
        hdtr:synsem:local:cat:(head:H
                               subcat:append(NDS,MS)),
        ndtr:synsem:local:cat:subcat:NDS),
  synsem:local:cat:(head:H,
                    subcat:MS)

This feature structure will result in the following instructions. The numbers are added for ease of reference.

1: type [],phrase
2: type [dtrs],hc_struct
3: var  [head,cat,local,synsem,hdtr,dtrs],H
4: var  0,NDS
5: var  1,MS
6: fun  append,2,[0,1],
        [subcat,cat,local,synsem,hdtr,dtrs]
7: var  [subcat,cat,local,sysem,ndtr],NDS
8: var  [head,cat,local,synsem],H
9: var  [subcat,cat,local,synsem],MS

All instructions start with a terminal path, which is a path of length 0 refering to the root of a description. The terminal path is written as []. Therefore, the first instruction means that the root of the feature structure being compiled is of type phrase. Instruction 2 states that there is a path from the root through dtrs that leads to the type hc_struct. Instruction 3 says that the path [head,cat,local,synsem,hdtr,dtrs] leads to variable H. Note that paths are written in the reverse order of what is customary in linguistics. Paths are discussed in more detail in the next section. Instructions 4 and 5 inform the compiler that two variables, namely, NDS and MS have been encountered and they have been assigned the numbers 0 and 1. In the instruction number 6, we see these variables being used inside a function. This instruction says that the path [subcat,cat,local,synsem,hdtr,dtrs] leads to a function called append with an arity of two, and that the function makes use of variables 0 and 1 that have been previously seen. The last three instructions show where else the previously seen variables are used.