Memoization of Coroutined Constraints

Memoization of Coroutined Constraints Mark Johnson Cognitive and Linguistic Sciences, Box 1978 Brown University Providence, l~I 02912, USA Mark_Johnson~Brown.edu Jochen DSrre* Institut fiir maschinelle Sprachverarbeitung Universit~it Stuttgart D-70174 Stuttgart, Germany Jochen.Doerre~ims.uni-stuttgart.de Abstract Some linguistic constraints cannot be effec- tively resolved during parsing at the loca- tion in which they are most naturally intro- duced. This paper shows how constraints can be propagated in a memoizing parser (such as a chart parser) in much the same way that variable bindings are, providing a general treatment of constraint coroutining in memoization. Prolog code for a sim- ple application of our technique to Bouma and van Noord's (1994) categorial gram- mar analysis of Dutch is provided. 1 Introduction As the examples discussed below show, some lin- guistic constraints cannot be effectively resolved du- ring parsing at the location in which they are most naturally introduced. In a backtracking parser, a natural way of dealing with such constraints is to coroutine them with the other parsing processes, re- ducing them only when the parse tree is sufficiently instantiated so that they can be deterministically resolved. Such parsers are particularly easy to im- plement in extended versions of Prolog (such as Pro- loglI, SICStus Prolog and Eclipse) which have such coroutining facilities built-in. Like all backtracking parsers, they can exhibit non-termination and expo- nential parse times in situations where memoizing parsers (such as chart parsers) can terminate in po- lynomial time. Unfortunately, the coroutining ap- proach, which requires that constraints share varia- bles in order to communicate, seems to be incompa- tible with standard memoization techniques, which *This research was largely conducted at the Institut ffir maschinelle Sprachverarbeitung in Stuttgart. We would like to thank Andreas Eisele, Pascal van Hen- tenryck, Martin Kay, Fernando Pereira, Edward Stabler and our colleagues at the Institut ffir maschinelle Sprach- verarbeitung for helpful comments and suggestions. All remaining errors are our own. The Prolog code presen- ted in this paper is available via anonymous ftp from Ix.cog.brown.edu as/pub/lernrna.tar.Z require systematic variable-renaming (i.e., copying) in order to avoid spurious variable binding. For generality, conciseness and precision, we for- malize our approach to memoization and constraints within H6hfeld and Smolka's (1988) general theory of Constraint Logic Programming (CLP), but we discuss how our method can be applied to mote stan- dard chart parsing as well. This paper extends our previous work reported in DSrre (1993) and John- son (1993) by generalizing those methods to arbi- trary constraint systems (including feature-structure constraints), even though for reasons of space such systems are not discussed here. 2 Lexical rules in Categorial Grammar This section reviews Bouma and van Noord's (1994) (BN henceforth) constraint-based categorial gram- mar analysis of modification in Dutch, which we use as our primary example in this paper. However, the memoizing CLP interpreter presented below has also been applied to GB and HPSG parsing, both of which benefit from constraint coroutining in parsing. BN can explain a number of puzzling scope phe- nomena by proposing that heads (specifically, verbs) subcategorize for …

Content truncated to 500 words