METHOD AND SYSTEM FOR VALIDATION OF STRUCTURED DOCUMENTS

• US 20100083100A1
• Filed: 10/09/2009
• Published: 04/01/2010
• Est. Priority Date: 09/06/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Seetharam, Shirish
• Granted Patent: US 8,464,147 B2
• Time in Patent Office: Days
• US Class Current: 715/237
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/221 Parsing markup language streams streaming G06F40/149
• CPC Class Codes: G06F 40/226 Validation

Abstract

A method and apparatus for validation of structured documents are provided. The method includes searching a fast parser for an instance of a structured document. Further, the method includes parsing the instance by using the fast parser, if the fast parser is available. If no fast parser is available, the method includes parsing the instance by using a generic parser, and generating the fast parser for the structured document, in parallel. The generation of the fast parsers is based on the structure of the structured documents.

Claims

1. A method for validation of structured documents, the method comprising

parsing a first instance of a first structured document by using a generic parser;

generating a fast parser for the first structured document, the fast parser being faster than the generic parser, the fast parser being generated based on the structure of the first structured document;

parsing a second instance of the first structured document using the fast parser; and

identifying a subset of fast parsers from a group of fast parsers, wherein the group of fast parsers includes fast parsers used most recently and fast parsers used most frequently;

searching a corresponding fast parser for an instance of a second structured document from the identified subset of the fast parsers; and

if the corresponding fast parser is available in the identified subset of the fast parsers,

parsing the instance of the second structured document by using the corresponding fast parser;

else,

parsing the instance of the second structured document by using the generic parser.

2. The method of claim 1, wherein each structured document being represented by a Context Free Grammar (CFG).

3. The method of claim 1, wherein the generating comprises using Left-to-right Rightmost derivation with k-token look ahead (LR (k)) parse tables.

4. (canceled)

5. A method for validation of structured documents, each structured document being represented by a Context Free Grammar (CFG), the method comprising

parsing a first instance of a first structured document by using a generic parser;

generating a fast parser for the first structured document, the fast parser being faster than the generic parser, the fast parser being generated based on the structure of the first structured document, the fast parser being generated using Left-to-right Rightmost derivation with k-token look ahead (LR (k)) parse tables;

parsing a second instance of the first structured document using the fast parser;

identifying a subset of fast parsers from a group of fast parsers, wherein the group of fast parsers includes fast parsers used most recently and fast parsers used most frequently;

searching a corresponding fast parser for an instance of a second structured document from the identified subset of the fast parsers; and

if the corresponding fast parser is available in the identified subset of the fast parsers,

parsing the instance of the second structured document by using the corresponding fast parser;

else,

parsing the instance of the second structured document by using the generic parser.

6. A system for validation of structured documents, the system comprising

means for parsing a first instance of a first structured document by using a generic parser;

means for generating a fast parser for the first structured document, the fast parser being faster than the generic parser, the fast parser being generated based on the structure of the first structured document; and

means for parsing at least one instance of the first structured document, the at least one instance being different from the first instance, wherein the parsing comprises using the fast parser;

means for identifying a subset of fast parsers from a group of fast parsers, wherein the group of fast parsers includes fast parsers used most recently and fast parsers used most frequently; and

means for searching a corresponding fast parser for an instance of a second structured document from the identified subset of the fast parsers, whereby the parsing module parses the instance of the second structured document by using the corresponding fast parser.

7. A system for validation of structured documents, the system comprising

a generic parsing module for parsing a first instance of a first structured document by using a generic parser;

a parser generating module for generating a fast parser for the first structured document, the fast parser being faster than the generic parser, the fast parser being generated based on the structure of the first structured document;

a parsing module for parsing a second instance of the first structured document using the fast parser;

an identifying module for identifying a subset of fast parsers from a group of fast parsers, wherein the group of fast parsers includes fast parsers used most recently and fast parsers used most frequently; and

a searching module for searching a corresponding fast parser for an instance of a second structured document from the identified subset of the fast parsers, whereby the parsing module parses the instance of the second structured document by using the corresponding fast parser.

8. (canceled)

9. A machine-readable medium including instructions for validation of structured documents executable by the processor, the medium comprising

one or more instructions for parsing a first instance of a first structured document by using a generic parser;

one or more instructions for generating a fast parser for the first structured document, the fast parser being faster than the generic parser, the fast parser being generated based on the structure of the first structured document;

one or more instructions for parsing at least one instance of the first structured document, the at least one instance being different from the first instance, wherein the parsing comprises using the fast parser;

one or more instructions for identifying a subset of fast parsers from a group of fast parsers, wherein the group of fast parsers includes fast parsers used most recently and fast parsers used most frequently;

one or more instructions for searching a corresponding fast parser for an instance of a second structured document from the identified subset of the fast parsers;

one or more instructions for determining if the corresponding fast parser is available in the identified subset of the fast parsers,

one or more instructions for parsing the instance of the second structured document by using the corresponding fast parser; and

else,

one or more instructions for parsing the instance of the second structured document by using the generic parser.

10. An apparatus for validation of structured documents, the apparatus comprising

a processing system including one or more processors coupled to a display and user input device;

and

a machine-readable medium including instructions for validation of structured documents executable by the one or more processors, the medium comprising

one or more instructions for parsing a first instance of a first structured document by using a generic parser;

one or more instructions for generating a fast parser for the first structured document, the fast parser being faster than the generic parser, the fast parser being generated based on the structure of the first structured document;

one or more instructions for parsing a second instance of the first structured document using the fast parser;

one or more instructions for identifying a subset of fast parsers from a group of fast parsers, wherein the group of fast parsers includes fast parsers used most recently and fast parsers used most frequently;

one or more instructions for searching a corresponding fast parser for an instance of a second structured document from the identified subset of the fast parsers;

one or more instructions for determining if the corresponding fast parser is available in the identified subset of the fast parsers,

one or more instructions for parsing the instance of the second structured document by using the corresponding fast parser; and

else,

one or more instructions for parsing the instance of the second structured document by using the generic parser.