Parsing ambiguous grammar

• US 6,714,905 B1
• Filed: 05/02/2000
• Issued: 03/30/2004
• Est. Priority Date: 05/02/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: Pinehurst Tech, Inc. (International Business Machines Corporation)
• Inventors: Lau, Raymond, Chang, Jane Wen, McCandless, Michael Kyle
• Primary Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US09/563,802
• Time in Patent Office: 1,428 Days
• Field of Search: 704/1, 704/9, 704/10, 704/257, 707/530, 707/531, 707/532, 707/1, 707/2-5
• US Class Current: 704/9
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method of parsing ambiguous grammar includes pre-compiling the grammar into a binary format, parsing a query, outputting a graph by combining the parsed query and the binary format of the grammar and outputting a frame representation of potential parses in the graph.

Claims

1. A method of handling ambiguous grammar comprising:

extending a Left Right (LR) parser to permit non-determinism in a state machine containing a plurality of states, the state machine permitting more than one successor state in any given state with any given top stack symbol; and

inserting an epsilon representing an empty transition used in a replacement of a combination of symbols for collapsing common rules when a right-hand side of a grammar rule recurses into a non-terminal.

2. The method of claim 1 in which the plurality of states is represented in a priority queue.

3. The method of claim 2 in which the priority queue is a data structure that maintains a list of items sorted by a numeric score.

4. The method of claim 1 in which inserting the epsilon comprises reducing multiple possible epsilon transitions in series to a single epsilon transition.

5. The method of claim 1 in which the epsilon represents a marker to indicate on a stack when non-terminals are pursued.

6. The method of claim 1 in which extending further comprises inserting hints representing markers in grammar rules with associated penalty costs.

7. The method of claim 6 in which the penalty costs weight parses.

8. The method of claim 1 in which extending further comprises inserts hints representing markers in grammar rules with associated anchors.

9. The method of claim 8 in which anchors indicate that other putative parses that have not reached an anchor are to be eliminated.

10. The method of claim 1 in which extending further comprises providing a graph structure to represent a list of alternative parse trees.

11. The method of claim 10 in which the graph structure comprises:

edges corresponding to grammar rules; and

a given path through the graph structure representing a sequential application of a series of grammar rules.

12. The method of claim 11 further comprising:

converting the graph structure into a series of output directives; and

generating frames from the output directives.