tailieunhanh - Báo cáo khoa học: "An alternative LR algorithm for TAGs"

We present a new LR algorithm for treeadjoining grammars. It is an alternative to an existing algorithm that is shown to be incorrect. Furthermore, the new algorithm is much simpler, being very close to traditional LR parsing for context-free grammars. The construction of derived trees and the computation of features also become straightforward. | An alternative LR algorithm for TAGs Mark-Jan Nederhof DFKI Stuhlsatzenhausweg 3 D-66123 Saarbriicken Germany E-mail nederhof@ Abstract We present a new LR algorithm for treeadjoining grammars. It is an alternative to an existing algorithm that is shown to be incorrect. Furthermore the new algorithm is much simpler being very close to traditional LR parsing for context-free grammars. The construction of derived trees and the computation of features also become straightforward. 1 Introduction The efficiency of LR Ã parsing techniques Sippu and Soisalon-Soininen 1990 appears to be very attractive from the perspective of natural language processing. This has stimulated the computational linguistics community to develop extensions of these techniques to general context-free grammar parsing. The best-known example is generalized LR parsing Tomita 1986 . A first attempt to adapt LR parsing to treeadjoining grammars TAGs was made by Schabes and Vijay-Shanker 1990 . The description was very complicated however and not surprisingly no implementation of the algorithm seems to have been made up to now. Apart from presentational difficulties the algorithm as it was published is also incorrect. Brief indications of the nature of the incorrectness have been given before by Kinyon 1997 . There seems to be no straightforward way to correct the algorithm. We therefore developed an alternative to the algorithm from Schabes and Vijay-Shanker 1990 . This alternative is novel in presentational aspects and is fundamentally different in that it incorporates reductions of subtrees. The new algorithm has the benefit that many theoretically and practically useful properties carry over from the context-free case. For example by making a straightforward translation from TAGs to linear indexed grammars one may identify computations of the parser with rightmost derivations in reverse. Also the extensions needed for construction of parse trees or derived trees as they are often called for