Chart Parsing and Constraint Programming

Chart Parsing and Constraint Programming Frank Morawietz Seminar f¨ur Sprachwissenschaft Universit¨at T¨ubingen Wilhelmstr. 113 72074 T¨ubingen, Germany frank@sfs.nphil.uni-tuebingen.de Abstract In this paper, parsing-as-deduction and constraint pro- gramming are brought together to outline a procedure for the specification of constraint-based chart parsers. Fol- lowing the proposal in Shieber et al. (1995), we show how to directly realize the inference rules for deductive parsers as Constraint Handling Rules (Fr¨uhwirth, 1998) by viewing the items of a chart parser as constraints and the constraint base as a chart. This allows the direct use of constraint resolution to parse sentences. 1 Introduction The parsing-as-deduction approach proposed in Pereira and Warren (1983) and extended in Shieber et al. (1995) and the parsing schemata defined in Sikkel (1997) are well established parsing paradigms in computational lin- guistics. Their main strengths are their flexibility and the level of abstraction concerning control information inherent in parsing algorithms. Furthermore, they are easily extensible to more complex formalisms, e.g., aug- mented phrase structure rules or the ID/LP format. Constraint Programming (CP) has been used in com- putational linguistics in several areas, for example in (typed) feature-based systems (Smolka, 1995), or condi- tional constraints (Matiasek, 1994), or advanced compi- lation techniques (G¨otz and Meurers, 1997) or special- ized constraint solvers (Manandhar, 1994). But none of these approaches uses constraint programming tech- niques to implement standard chart parsing algorithms directly in a constraint system. In this paper, I will bring these two paradigms to- gether by showing how to implement algorithms from the parsing-as-deduction scheme by viewing the parsing process as constraint propagation. The core idea is that the items of a conventional chart parser are constraints on labeled links between the words and positions of an input string. Then the inference rules allow for the deduction of new constraints, again labeled and spanning parts of the input string, via constraint propagation. The resulting constraint store represents the chart which can be accessed to determine whether the parse was successful or to reconstruct a parse tree. While this may seem a trivial observation, it is not just another way of implementing deductive parsing in yet another language. The approach allows for a rapid and very flexible but at the same time uniform method of implementation of all kinds of parsing algorithms (for constraint-based theories). The goal is not necessarily to build the fastest parser, but rather to build – for an ar- bitrary algorithm – a parser fast and perspicuously. For example, the advantage of our approach compared to the one proposed in Shieber et al. (1995) is that we do not have to design a special deduction engine and we do not have to handle chart and agenda explicitly. Furthermore, the process can be used in any constraint-based formal- ism which allows for constraint propagation and there- fore can be easily integrated into existing applications. The paper proceeds by reviewing the parsing-as- deduction approach and a particular way of imple- menting constraint systems, Constraint Handling Rules (CHR) as presented in Fr¨uhwirth …

Content truncated to 500 words