An Abstract Machine for Unification Grammars Shuly Wintner PhD thesis, Technion - Israel Institute of Technology, Haifa, Israel January 1997 Contemporary linguistic formalisms have become so rigorous that it is now possible to view them as very high level declarative programming languages. Consequently, {\em grammars\/} for natural languages can be viewed as {\em programs}; this view enables the application of various methods and techniques that were proved useful for programming languages to the study of natural languages. One of the most successful implementation techniques for logic programming languages involves the use of an abstract machine. In this approach one defines an abstract machine with the following properties: it is close enough to the high-level language, thus allowing efficient compilation to the abstract machine language; and it is sufficiently low-level to allow efficient interpretation of the machine instructions on a variety of host architectures. Abstract machines were used for processing procedural and functional languages, but they gained much popularity for logic programming languages since the introduction of the Warren Abstract Machine (WAM). Most current implementations of Prolog, as well as other logic languages, are based on abstract machines. The incorporation of such techniques usually leads to very efficient compilers in terms of both space and time requirements. In this work we have designed and implemented an abstract machine, \amalia, for the linguistic formalism ALE, which is based on typed feature structures. This formalism is one of the most widely accepted in computational linguistics and has been used for designing grammars in various linguistic theories, most notably HPSG. \amalia\ is composed of data structures and a set of instructions, augmented by a compiler from the grammatical formalism to the abstract instructions, and a (portable) interpreter of the abstract instructions. The effect of each instruction is defined using a low-level language that can be executed on ordinary hardware. The advantages of the abstract machine approach are twofold. From a theoretical point of view, the abstract machine gives a well-defined operational semantics to the grammatical formalism. This ensures that grammars specified using our system are endowed with well defined meaning. It enables, for example, to formally verify the correctness of a compiler for HPSG, given an independent definition. From a practical point of view, \amalia\ is the first system that employs a direct compilation scheme for unification grammars that are based on typed feature structures. The use of \amalia\ results in a much improved performance over existing systems. In order to test the machine on a realistic application, we have developed a small-scale, HPSG-based grammar for a fragment of the Hebrew language, using \amalia\ as the development platform. This is the first application of HPSG to a Semitic language.