tailieunhanh - Báo cáo khoa học: "Incremental Parsing with Parallel Multiple Context-Free Grammars"

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 formalism. The algorithm is also top-down which allows it to be used for grammar based word prediction. | Incremental Parsing with Parallel Multiple Context-Free Grammars Krasimir Angelov Chalmers University of Technology Goteborg Sweden krasimir@ 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 formalism. 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 languages. 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 tuples the grammar can model discontinuous constituents which makes it more powerful than context-free grammar. 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 input 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 humans process language in an incremental fashion which makes the incremental algorithms attractive from cognitive point of view. If the algorithm is also top-down then it is possible to predict the next word from the sequence of preceding 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 .