\title{\bf PARSING WITH TYPED FEATURE STRUCTURES}
\author{Shuly Wintner \\\mbox{}\\ Nissim Francez}
\date{\normalsize Computer Science\\
        Technion, Israel Institute of Technology\\
        32000 Haifa, Israel\\ 
        {\tt \{shuly,francez\}@cs.technion.ac.il}}
\maketitle
\thispagestyle{empty}

\begin{abstract}
In this paper we provide for parsing with respect to grammars
expressed in a general TFS-based formalism, a restriction of ALE
(\cite{ale}). Our motivation being the design of an abstract
(WAM-like) machine for the formalism (\cite{shuly:nlulp-95}), we
consider parsing as a computational process and use it as an operational
semantics to guide the design of the control structures
for the abstract machine.

We emphasize the notion of {\bf abstract typed
feature structures} (AFSs) that encode the essential information of
TFSs and define unification over AFSs rather than over TFSs. We then
introduce an explicit construct of {\bf multi-rooted feature
structures} (MRSs) that naturally extend TFSs and use them to
represent phrasal signs as well as grammar rules. We also
employ abstractions of MRSs and give the mathematical foundations
needed for manipulating them. We
then present a simple bottom-up chart parser as a model for
computation: grammars written in the TFS-based formalism are executed
by the parser. Finally, we show that the parser is correct.
\end{abstract}