The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Aug. 31, 2004
Filed:
Oct. 15, 2001
Thomas E. Hayosh, Lake Zurich, IL (US);
Harry Martin Bliss, Evanston, IL (US);
William Thompson, Evanston, IL (US);
Guido A. Minnen, Arlington Heights, IL (US);
Motorola, Inc., Schaumburg, IL (US);
Abstract
A chart parser and a method for generating a parse chart for a sequence of input symbols in accordance with an abbreviated representation of a grammar. According to the method, an abbreviated representation of a grammar is stored as a set of finite-state automata, each finite-state automaton corresponding to a rule of the grammar. Chart edges are derived chart edges from the sequence of input symbols in accordance with the set of finite-state automata and are stored in the parse chart. Each chart edge spans a portion of the sequence of input symbols and may include a left input vertex index corresponding to the start of the span of the chart edge, a right input vertex index corresponding to the end of the span of the chart edge, a rule number, indicating which finite-state automaton of the plurality of finite-state automata has been used to generate the chart edge, a left state index, indicating the left most state of the finite-state automaton that has been matched and a right state index, indicating the right most state of the finite-state automaton that has been matched, the left-hand side of the rule and a path through the finite state comprising the right-hand side of the rule or so-called backpointers to the edges used to derive the current edge. The chart parser includes a chart controller and an agenda controller, together with associated memory.