Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Some linguistic constraints cannot be effectively resolved during parsing at the location in which they are most naturally introduced. 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 simple application of our technique to Bouma and van Noord's (1994) categorial grammar analysis of Dutch is provided. | Memoization of Coroutined Constraints Mark Johnson Cognitive and Linguistic Sciences Box 1978 Brown University Providence RI 02912 USA Mark_JohnsonQBrown.edu Jochen Dorre Institut fur maschinelle Sprachverarbeitung Universităt Stuttgart D-70174 Stuttgart Germany Jochen. DoerreQims.uni-stuttgart.de Abstract Some linguistic constraints cannot be effectively resolved during parsing at the location in which they are most naturally introduced. 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 simple application of our technique to Bouma and van Noord s 1994 categorial grammar analysis of Dutch is provided. 1 Introduction As the examples discussed below show some linguistic constraints cannot be effectively resolved during 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 reducing them only when the parse tree is sufficiently instantiated so that they can be deterministically resolved. Such parsers are particularly easy to implement in extended versions of Prolog such as Pro-logll SICStus Prolog and Eclipse which have such coroutining facilities built-in. Like all backtracking parsers they can exhibit non-termination and exponential parse times in situations where memoizing parsers such as chart parsers can terminate in polynomial time. Unfortunately the coroutining approach which requires that constraints share variables in order to communicate seems to be incompatible with standard memoization techniques which This research was largely conducted at the Institut fur 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
