Incremental Parsing with Parallel Multiple Context-Free Grammars

Proceedings of the 12th Conference of the European Chapter of the ACL, pages 69–76, Athens, Greece, 30 March – 3 April 2009. c⃝2009 Association for Computational Linguistics Incremental Parsing with Parallel Multiple Context-Free Grammars Krasimir Angelov Chalmers University of Technology G¨oteborg, Sweden krasimir@chalmers.se Abstract Parallel Multiple Context-Free Grammar (PMCFG) is an extension of context-free grammar for which the recognition problem is still solvable in polynomial time. We describe a new parsing algorithm that has the advantage to be incremental and to support PMCFG directly rather than the weaker MCFG formal- ism. The algorithm is also top-down which allows it to be used for grammar based word prediction. 1 Introduction Parallel Multiple Context-Free Grammar (PMCFG) (Seki et al., 1991) is one of the grammar formalisms that have been proposed for the syntax of natural lan- guages. It is an extension of context-free grammar (CFG) where the right hand side of the production rule is a tuple of strings instead of only one string. Using tu- ples the grammar can model discontinuous constituents which makes it more powerful than context-free gram- mar. In the same time PMCFG has the advantage to be parseable in polynomial time which makes it attractive from computational point of view. A parsing algorithm is incremental if it reads the in- put one token at the time and calculates all possible consequences of the token, before the next token is read. There is substantial evidence showing that hu- mans process language in an incremental fashion which makes the incremental algorithms attractive from cog- nitive point of view. If the algorithm is also top-down then it is possible to predict the next word from the sequence of preced- ing words using the grammar. This can be used for example in text based dialog systems or text editors for controlled language where the user might not be aware of the grammar coverage. In this case the system can suggest the possible continuations. A restricted form of PMCFG that is still stronger than CFG is Multiple Context-Free Grammar (MCFG). In Seki and Kato (2008) it has been shown that MCFG is equivalent to string-based Linear Context- Free Rewriting Systems and Finite-Copying Tree Transducers and it is stronger than Tree Adjoining Grammars (Joshi and Schabes, 1997). Efficient recog- nition and parsing algorithms for MCFG have been de- scribed in Nakanishi et al. (1997), Ljungl¨of (2004) and Burden and Ljungl¨of (2005). They can be used with PMCFG also but it has to be approximated with over- generating MCFG and post processing is needed to fil- ter out the spurious parsing trees. We present a parsing algorithm that is incremental, top-down and supports PMCFG directly. The algo- rithm exploits a view of PMCFG as an infinite context- free grammar where new context-free categories and productions are generated during parsing. It is trivial to turn the algorithm into statistical by attaching probabil- ities to each rule. In Ljungl¨of (2004) it has been shown that the Gram- matical Framework (GF) formalism (Ranta, 2004) is equivalent to …

Content truncated to 500 words