Guided Parsing of Range Concatenation Languages

Guided Parsing of Range Concatenation Languages Fran¸cois Barth´elemy, Pierre Boullier, Philippe Deschamp and ´Eric de la Clergerie INRIA-Rocquencourt Domaine de Voluceau B.P. 105 78153 Le Chesnay Cedex, France � Francois.Barthelemy Pierre.Boullier Philippe.Deschamp Eric.De La Clergerie � @inria.fr Abstract The theoretical study of the range concatenation grammar [RCG] formal- ism has revealed many attractive prop- erties which may be used in NLP. In particular, range concatenation lan- guages [RCL] can be parsed in poly- nomial time and many classical gram- matical formalisms can be translated into equivalent RCGs without increas- ing their worst-case parsing time com- plexity. For example, after transla- tion into an equivalent RCG, any tree adjoining grammar can be parsed in ���� � time. In this paper, we study a parsing technique whose purpose is to improve the practical efficiency of RCL parsers. The non-deterministic parsing choices of the main parser for a lan- guage are directed by a guide which uses the shared derivation forest output by a prior RCL parser for a suitable su- perset of . The results of a practi- cal evaluation of this method on a wide coverage English grammar are given. 1 Introduction Usually, during a nondeterministic process, when a nondeterministic choice occurs, one explores all possible ways, either in parallel or one after the other, using a backtracking mechanism. In both cases, the nondeterministic process may be as- sisted by another process to which it asks its way. This assistant may be either a guide or an oracle. An oracle always indicates all the good ways that will eventually lead to success, and those good ways only, while a guide will indicate all the good ways but may also indicate some wrong ways. In other words, an oracle is a perfect guide (Kay, 2000), and the worst guide indicates all possi- ble ways. Given two problems  and  and their respective solutions  and  , if they are such that  � , any algorithm which solves is a candidate guide for nondeterministic al- gorithms solving  . Obviously, supplementary conditions have to be fulfilled for  to be a guide. The first one deals with relative efficiency: it as- sumes that problem ciently than problem  can be solved more effi-  . Of course, parsers are privileged candidates to be guided. In this pa- per we apply this technique to the parsing of a subset of RCLs that are the languages defined by RCGs. The syntactic formalism of RCGs is pow- erful while staying computationally tractable. In- deed, the positive version of RCGs [PRCGs] de- fines positive RCLs [PRCLs] that exactly cover the class PTIME of languages recognizable in de- terministic polynomial time. For example, any mildly context-sensitive language is a PRCL. In Section 2, we present the definitions of PRCGs and PRCLs. Then, in Section 3, we de- sign an algorithm which transforms any PRCL into another PRCL  , oretical) parse time for  such that the (the- is less than or equal to the …

Content truncated to 500 words