Technical Report LCL9501

Authors: S. Wintner and N. Francez
Abstract: In this paper we provide for parsing with respect to grammars expressed in a general TS-based formalism, a restriction of ALE [2].Our motivation, being the design of an abstract (WAM-like) machine for the formalism [19], we consider parsing as a computation 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 the abstract typed feature structures (AFSs) that encode the essential information of TFSs and define unification ocer AFSs rather than over TFSs. We then introduce an explicit construct of multi-rooted feature structures (MFSs) 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 formally define grammars and the languages they generate, and then describe a model for computation that corresponds to bottom-up chart parsing: grammars written in the TFS-based formalisn are executed by the parser.We show that the computation is correct with respect to the independent definition. Finally, we discuss the class of grammars for which computations terminate and prove that termination can be guaranteed for off-line parsable grammars.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the LCL technical reports of 1995
To the main CS technical reports page

Computer science department, Technion