An Extended LR Parsing Algorithm for Grammars Using Feature-Based Syntactic Categories

AN EXTENDED LR PARSING ALGORITHM FOR GRAMMARS USING FEATURE-BASED SYNTACTIC CATEGORIES Tsuneko Nakazawa Beckman Institute for Advanced Science and Technology and Linguistics Department University of Illinois 4088 FLB, 707 S. Mathews, Urbana, IL 61801, USA tsuneko@grice.cogsci.uiuc.edu ABSTRACT This paper proposes an LR parsing algorithm modified for grammars with feature-based categories. The proposed algorithm does not instantiate categories during preprocessing of a grammar as proposed elsewhere. As a result, it constructs a minimal size of GOTO/ACTION table and eliminates the necessity of search for GOTO table entries during parsing. 1 Introduction The LR method is known to be a very efficient parsing algorithm that involves no searching or backtracking. However, recent formalisms for syntactic analyses of natural language make maximal use of complex feature-value systems, rather than atomic categories that have been presupposed in the LR method. This paper is an attempt to incorporate feature-based categories into Tomita's extended LR parsing algorithm (Tomita 1986). A straightforwmd adaptation of feature- based categories into the algorithm introduces the necessity of partial instantiation of categories during preprocessing, of a grammar as well as a nontenmnat~on problem. Furthermore, the parser is forced to search through instantiated categories for desired GOTO table entries during parsing. The major innovations of the proposed algorithm include the construction of a minimal size of GOTO table that does not require any preliminary instantiation of categories or a search for them, and a reduce action which pe,forms instanliation tit)ring parsing. Some details of the LR parsing algorithm are assumed from Aho and Ullman (1987) and Aho and Johnson (1974), and more formal definitions and notations of a feature- based grammar formalism from Pollard and Sag (1987) and Shieber (1986). 2 The LR Parsing Algorithm The LR parser is an efficient shift-reduce parser with optional lookahead. Parse u'ees for input strings are built bottom-up, while predictions are made top-down prior to parsing. The ACTION/GOTO table is constructed during preprocessing of a grammar and deterministically guides the parser at each step during parsing. The ACFION table determines whether the parser should take a shift o1" a reduce action next. The GOTO table determines the state the parser should be in after each action. Henceforth, entries for the ACTION/ GOTO table are referred to as the values of functions, ACTION and GOTO. The ACTION function takes a current state and an input string to return a next action, and GOTO takes a previous state and a syntactic category to return a next state. States of the LR parser are sets of dotted productions called items. The state, i.e. dotted productions, stored on top of the stack is called current state and the dot positions on the right hand side (rhs) of the productions indicate how much of the rhs the parser has found. Previous states are stored in the stack until the entire rhs, or the left hand side (lhs), of a production is found, at which time a reduce action pops previous states and pushes a new state in, i.e. the set of …

Content truncated to 500 words