An Extension of Earley’s Algorithm for S-Attributed Grammars

An Extension of Earley's Algorithm for S-Attributed Grammars Nelson Correa Department of Electrical Engineering Universidad de los Andes Apartado A6reo 4976, Bogotti, D.E., Colombia bitnet : NCORREA at ANDESCOL Abstract Attribute grammars are an elegant formalization of the augmented context-free grammars characteristic of most current natural language systems. This paper presents an extension of Earley's algorithm to Knuth's attribute grammars, considering the case of S-attributed grammars. For this case, we study the conditions on the underlying base grammar under which the extended algorithm may be guaranteed to terminate. Finite partitioning of attribute domains is proposed to guarantee the termination of the algorithm, without the need for any restrictions on the context-free base. 1. Introduction Earley's (1970) algorithm is a general algorithm for context-free languages, widely used in natural language processing (King, 1983; Shieber, 1985) and syntactic pattern recognition (Fu, 1982), where the full generative power of context-free grammar is required. The original algorithm and its common implementations, however, assume the atomic symbols of context-free grammars, thus limiting its applicability to systems with attributed symbols, or attribute grammars (Knuth, 1968). Attribute grammar is an elegant formalization of the augmented context-free grammars characteristic of most current NLP systems. It is more general than members of the family of unification-based grammar formalisms (Kay, 1985; Shieber, 1986), mainly in that it allows and encourages the use of simpler attribution functions than unification for the definition of attribute values, and hence can lead to computationally efficient grammatical definitions, while maintaining the advantages of a well-understood declarative formalism. Attribute grammar has been used in the past by the author to define computational models of Chomsky's Government-binding theory, from which practical parsing programs were developed (Correa, 1987a). Many systems based on Earley's algorithm have a clear division between the phases of syntactic and semantic analysis. Yellin (1988), for instance, uses a syntactic analysis phase in which Earley's algorithm builds a factored parse tree (FPT) for the given input, which is then followed by up to two phases of semantic analysis, during which the FPT is attributed and evaluated. Watt (1980) and Jones and Madsen (1980) propose a close interaction between syntactic and semantic analysis in the form of "attribute-directed" parsing. However, their particular realization of the technique is severely restricted for NLP applications, since it uses a deterministic one-path (LR) algorithm, applicable only to semantically unambiguous grammars. Pereira and Warren (1983) and Shieber (1985) present v6rsions of Earley's algorithm for unification grammars, in which unification is the sole operation responsible for attribute evaluation. However, given the high computational cost of unification, important differences between attribute and unification grammars in their respective attribution domains and functions (Correa, forthcoming), and the more general nature of attribute grammars in this regard, it is of interest to investigate the extension of Earley's algorithm directly to the main subclasses of attribute grammar. The paper is organized as follows: Section 2 presents pieliminary elements, including a definition of attribute grammar and Earley's algorithm. Section 3 presents the extension of the algorithm for S-attributed …

Content truncated to 500 words