tailieunhanh - Báo cáo khoa học: "AN INTEGRATED HEURISTIC SCHEME FOR PARTIAL PARSE EVALUATION"

GLR* is a recently developed robust version of the Generalized LR Parser [Tomita, 1986], that can parse almost any input sentence by ignoring unrecognizable parts of the sentence. On a given input sentence, the parser returns a collection of parses that correspond to maximal, or close to maximal, parsable subsets of the original input. This paper describes recent work on developing an integrated heuristic scheme for selecting the parse that is deemed "best" from such a collection. We describe the heuristic measures used and their combination scheme. . | AN INTEGRATED HEURISTIC SCHEME FOR PARTIAL PARSE EVALUATION Alon Lavie School of Computer Science Carnegie Mellon University 5000 Forbes Ave. Pittsburgh PA 15213 email Abstract GLR is a recently developed robust version of the Generalized LR Parser Tomita 1986 that can parse almost any input sentence by ignoring unrecognizable parts of the sentence. On a given input sentence the parser returns a collection of parses that correspond to maximal or close to maximal parsable subsets of the original input. This paper describes recent work on developing an integrated heuristic scheme for selecting the parse that is deemed best from such a collection. We describe the heuristic measures used and their combination scheme. Preliminary results from experiments conducted on parsing speech recognized spontaneous speech are also reported. The GLR Parser The GLR Parsing Algorithm The Generalized LR Parser developed by Tomita Tomita 1986 extended the original LR parsing algorithm to the case of non-LR languages where the parsing tables contain entries with multiple parsing actions. Tomita s algorithm uses a Graph Structured Stack GSS in order to efficiently pursue in parallel the different parsing options that arise as a result of the multiple entries in the parsing tables. A second data structure uses pointers to keep track of all possible parse trees throughout the parsing of the input while sharing common subtrees of these different parses. A process of local ambiguity packing allows the parser to pack subparses that are rooted in the same non-terminal into a single structure that represents them all. The GLR parser is the syntactic engine of the Universal Parser Architecture developed at CMU Tomita et al. 1988 . The architecture supports grammatical specification in an LFG framework that consists of context-free grammar rules augmented with feature bundles that are associated with the non-terminals of the rules. Feature structure computation is for the most .