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@3rown.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 leftqinear 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 grammm's 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 Ulhnan, 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 at> 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 ill 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 wins on sabbatical at the Xerox Research Centre in Grenoble, lh-ance. I would like to thank them and my colleages at Brown for their support. t)arsing algorithm and discusses how finite state approximations of top-down parsers can be con- strutted. The fact that this approximation is not ex- act for left linear grammars (which define finite-state languages) motivates a finite-state approxinlation 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 toi)-down approximation: it is not exact for right-linear grmnmars, but tile "optimized" variants presented in section 3 over- come this deficiency, resulting in finite-state CFG approximations which m'e exact for leftqinear and right-linear grmnmars. 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/ormatioTzs, i.e., functions T that map a context-free grammar G into another context- fi'ee grammar T(G). The transforms have the prop- erty that a top-down parse using …

Content truncated to 500 words