Back to results
US 6,714,905 B1Granted
Parsing ambiguous grammar
AssigneeiPhrase.com, Inc.
InventorsJane Wen Chang, Raymond Lau, Michael Kyle McCandless
Life of this patent
Estimating the term…
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.
Claims12
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.
Dependencies are inferred from the claim text.