Method and system for validation of structured documents

• US 8,464,147 B2
• Filed: 10/09/2009
• Issued: 06/11/2013
• Est. Priority Date: 09/06/2005
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Seetharam, Shirish
• Primary Examiner(s): Hutton, Jr., Doug
• Assistant Examiner(s): DYER, ANDREW R
• Application Number:
  US12/576,567
• Publication Number:
  US 20100083100A1
• Time in Patent Office: 1,341 Days
• Field of Search: 715/234, 715/237
• 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 comprising:

receiving a first request for validating a first structured document;

parsing a first instance of a structured document using the generic parser, wherein an Abstract Syntax Tree (AST) for the first structured document is being generated while the parsing is in progression;

while parsing the first instance of the first structured document using the generic parser, generating a fast parser for the first structured document, wherein the fast parser being generated is based on (i) the structure of the first structured document, and (ii) the AST that is concurrently being generated for the first structured document while the first instance of the first structured document is being parsed; and

adding the fast parser to a group of fast parsers for processing subsequently received structured documents.

2. The method of claim 1, further comprising:

receiving a second request for validating a second structured document; and

responsive to receiving the second request;

identifying a second subset of fast parsers from the group of fast parsers,

searching the second subset of fast parsers for a fast parser corresponding to an instance of the second structured document,

determining that the generated fast parser for the first structured document is available within the second subset of fast parsers and corresponds to an instance of the second structured document, and

responsive to determining that the generated fast parser for the first structured document is available within the second subset of fast parsers and corresponds to an instance of the second structured document, parsing the instance of the second structured document using the generated fast parser for the first structured document.

3. A system for validation of structured documents, the system comprising:

one or more processing devices; and

a non-transitory computer-readable medium coupled to the one or more processing devices having instructions stored thereon which, when executed by the one or more processing devices, cause the one or more processing devices to perform operations comprising;

parsing a first instance of a structured document using the generic parser, wherein an Abstract Syntax Tree (AST) for the first structured document is being generated while the parsing is in progression;

while parsing the first instance of the first structured document using the generic parser, generating a fast parser for the first structured document, wherein the fast parser being generated is based on (i) the structure of the first structured document, and (ii) the AST that is concurrently being generated for the first instance of the first structured document while the first structured document is being parsed; and

adding the fast parser to a group of fast parsers for processing subsequently received structured documents.

4. The system of claim 3, further comprising:

receiving a request for validating a second structured document; and

responsive to receiving the request;

identifying a subset of fast parsers from the group of fast parsers,

searching the subset of fast parsers for a fast parser corresponding to an instance of the second structured document,

determining that the generated fast parser for the first structured document is available within the subset of fast parsers and corresponds to an instance of the second structured document, and

responsive to determining that the generated fast parser for the first structured document is available within the subset of fast parsers and corresponds to an instance of the second structured document, parsing the instance of the second structured document using the generated fast parser for the first structured document.

5. A system for validation of structured documents, the system comprising:

one or more processing devices;

a generic parsing module for parsing a first instance of a first structured document by using a generic parser and the one or more processing devices, wherein an Abstract Syntax Tree (AST) for the first structured document being generated while the parsing is in progression;

a parser generating module for, while parsing the first instance of the first structured document using the generic parser, generating a fast parser for the first structured document, the fast parser being faster than the generic parser, wherein the fast parser being generated is based on (i) the structure of the first structured document, and (ii) the AST that is concurrently being generated for the first structured document while the first instance of the first structured document is being parsed by the generic parsing module, and adding the generated fast parser to a group of fast parsers;

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

an identifying module for identifying a subset of fast parsers from the 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.

6. A method for validation of structured documents, the method comprising:

receiving a first request for validating a first structured document;

responsive to receiving the first request;

identifying a first subset of fast parsers from a group of fast parsers, searching the first subset of fast parsers for a fast parser corresponding to an instance of the first structured document,

determining that no fast parser that corresponds to an instance of the first structured document is available within the first subset of fast parsers, and

responsive to determining that no fast parser that corresponds to an instance of the first structured document is available within the first subset of fast parsers, performing in parallel;

(a) parsing the first instance of the first structured document using a generic parser, wherein an Abstract Syntax Tree (AST) for the first structured document is being generated while the parsing is in progression, and

(b) generating a fast parser for the first structured document, wherein the fast parser being generated is based on (i) the structure of the first structured document, and (ii) the AST that is concurrently being generated for the first structured document while the first instance of the first structured document is being parsed, and

adding the generated fast parser to the group of fast parsers for processing subsequently received structured documents.

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

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

9. The method of claim 6, further comprising:

receiving a second request for validating a second structured document; and

responsive to receiving the second request;

identifying a second subset of fast parsers from the group of fast parsers,

searching the second subset of fast parsers for a fast parser corresponding to an instance of the second structured document,

determining that the generated fast parser for the first structured document is available within the second subset of fast parsers and corresponds to an instance of the second structured document, and

responsive to determining that the generated fast parser for the first structured document is available within the second subset of fast parsers and corresponds to an instance of the second structured document, parsing the instance of the second structured document using the generated fast parser for the first structured document.

10. A non-transitory machine-readable medium including instructions for validation of structured documents executable by a processor, the medium comprising:

one or more instructions for parsing a first instance of a first structured document by using a generic parser, wherein an Abstract Syntax Tree (AST) for the first structured document being generated while the parsing is in progression;

one or more instructions for while parsing the first instance of the first structured document using the generic parser, generating a fast parser for the first structured document, the fast parser being faster than the generic parser, wherein the fast parser being generated is based on (i) the structure of the first structured document, and (ii) the AST that is concurrently being generated for the first structured document while the first instance of the first structured document is being parsed, and adding the generated parser to a group of fast parsers;

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 generated fast parser;

one or more instructions for identifying a subset of fast parsers from the 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

one or more instructions for parsing the instance of the second structured document by using the generic parser in response to the corresponding fast parser being unavailable in the identified subset of fast parsers.

11. 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 non-transitory 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, wherein an Abstract Syntax Tree (AST) for the first structured document being generated while the parsing is in progression;

one or more instructions for while parsing the first instance of the first structured document using the generic parser, generating a fast parser for the first structured document wherein the fast parser being generated is based on (i) the structure of the first structured document, and (ii) the AST that is concurrently being generated for the first structured document while the first instance of the first structured document is being parsed, and adding the generated parser to a group of fast parsers;

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 the 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

one or more instructions for parsing the instance of the second structured document by using the generic parser in response to the corresponding fast parser being unavailable in the identified subset of fast parsers.