Finite-state Approximation of Constraint-based Grammars using Left-corner Grammar Transforms

Finite-state Approximation of Constraint-based Grammars using Left-corner Grammar Transforms Mark Johnson* Cognitive and Linguistic Sciences, Box 1978 Brown University Mark_.Johnson@Brown.edu Abstract This paper describes how to construct a finite-state machine (FSM) approximating a 'unification-based' grammar using a left-corner grammar transform. The approximation is presented as a series of gram- mar transforms, and is exact for left-linear and right- linear CFGs, and for trees up to a user-specified depth of center-embedding. 1 Introduction This paper describes a method for approximat- ing grammars with finite-state machines. Unlike the method derived from the LR(k) parsing algo- rithm described in Pereira and Wright (1991), these methods use grammar transformations based on the left-corner grammar transform (Rosenkrantz and Lewis II, 1970; Aho and Ullman, 1972). One ad- vantage of the left corner methods is that they gen- eralize straightforwardly to complex feature "unifi- cation based" grammars, unlike the LR(k) based ap- proach. For example, the implementation described here translates a DCG version of the example gram- mar given by Pereira and Wright (1991) directly into a FSM without constructing an approximating CFG. Left-corner based techniques are natural for this kind of application because (with the simple opti- mization described below) they can parse pure left- branching or pure right-branching structures with a stack depth of one (two if terminals are pushed and popped from the stack). Higher stack depth occurs with center-embedded structures, which hu- mans find difficult to comprehend. This suggests that we may get a finite-state approximation to hu- man performance by simply imposing a stack depth bound. We provide a simple tree-geometric descrip- tion of the configurations that cause an increase in a left corner parser's stack depth below. The rest of this paper is structured as follows. The remainder of this section outlines the "gram- mar transform" approach, summarizes the top-down * This research was supported by NSF grant SBR526978. I began this research while I was on sabbatical at the Xerox Research Centre in Grenoble, France. I would like to thank them and my colleages at Brown for their support. parsing algorithm and discusses how finite state approximations of top-down parsers can be con- structed. The fact that this approximation is not ex- act for left linear grammars (which define finite-state languages) motivates a finite-state approximation based on the left-corner parsing algorithm (which is presented as a grammar transform in section 2). In its standard form the approximation based on the left-corner parsing algorithm suffers from the com- plementary problem to the top-down approximation: it is not exact for right-linear grammars, but the "optimized" variants presented in section 3 over- come this deficiency, resulting in finite-state CFG approximations which are exact for left-linear and right-linear grammars. Section 4 discusses how these techniques can be combined in an implementation. 1.1 Parsing strategies as grammar transformations The parsing algorithms discussed here are presented as grammar trans]ormations, i.e., functions T that map a context-free grammar G into another context- free grammar T(G). The transforms have the prop- erty that a top-down parse using …

Content truncated to 500 words