An Efficient Context-Free Parser for Augmented Phrase-Structure Grammars

AN EFFICIENT CONTEXT-FREE PARSER FOR AUGMENTED PHRASE-STRUCTURE GRAMMARS Massimo Marino*, Antonella Spiezio, Giacomo Ferrari*, Irina Prodanof+ *Linguistics Department, University of Pisa, Via S. Maria 36, 1-56100 Pisa - Italy + Computational Linguistics Institute - Cnr Via Della Faggiola 32, 1-56100 Pisa -Italy ABSTRACT In this paper we present an efficient context-free (CF) bottom-up, non deterministic parser. It is an extension of the ICA (Immediate Constituent Analysis) parser proposed by Grishman (1976), and its major improvements are described. It has been designed to run Augmented Phrase-Structure Grammars (APSG) and performs semantic interpretation in parallel with syntactic analysis. It has been implemented in Franz Lisp and runs on VAX 11/780 and, recently, also on a SUN workstation, as the main component of a transportable Natural Language Interface (SAIL = Sistema per I'Analisi e I'lnterpretazione del Linguaggio). Subsets of grammars of italian written in different formalisms and for different applications have been experimented with SAIL. In particular, a toy application has been developed in which SAIL has been used as interface to build a knowledge base in MRS (Genesereth et al. 1980, Genesereth 1981) about ski paths in a ski environment, and to ask for advice about the best touristic path under specific weather and physical conditions. 1. INTRODUCTION Many parsers for natural language have been developed in the past, which run different types of grammars. Among them, the most successful are the CF grammars, the augmented phrase-structure grammars (APSGs), and the semantic grammars. All of them have different characteristics and different advantages. In particular APSGs offer a natural tool for the treatment of certain natural language phenomena, such as subject- verb agreement. Semantic grammars are prone to a compositional algorithm for semantic interpretation. The aim of our work is to implement a parser which associates the full extension of an APSG to compositionality of semantics. The parser relies on the well stabilized ICA algorithm. This association allows a wide range of applications in syntactic/semantic analyses together with the efficiency of a CF parser. 2. Functional description of the parsing algorithm The parsing algorithm consists of the following modules: - a preprocessor; - a parser itself; - a post-processor and interpreter; and interacts with: - a dictionary, which is used by the preprocessor; - the grammar, used by the parser. Figure 1 shows the structure of the system we have designed. Some of the modules, such as the spelling corrector, the robusteness component, and the NL answer generator, are still being developed. 2.1. The dictionary The dictionary contains the 'word-forms', known to the interface, with the following associated information, called 'interpretation': - syntactic category; - semantic value; - syntactic features as gender, number, etc.; A form can be single (a single word) or multiple (more than one word). Multiple forms are frequent in natural language and are in general referred to as 'idioms'. However, in semantic grammars, the use of multiple words is wider than in syntactic ones as also some simpler phrases may be more conveniently treated in the dictionary. This is …

Content truncated to 500 words