Method for Validating Ambiguous W3C Schema Grammars

• US 20080228810A1
• Filed: 05/30/2008
• Published: 09/18/2008
• Est. Priority Date: 07/26/2006
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Perkins, Eric, Matsa, Moshe E.
• Application Number:
  US12/130,235
• Publication Number:
  US 20080228810A1
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/221 Parsing markup language streams streaming G06F40/149
• CPC Class Codes: G06F 40/226 Validation

Abstract

A method for generating XML (Extensible Markup Language) parsers, including: parsing an input document with a generated parser where the generated parser is generated by a three-stage compilation of an XML Schema, where in a first stage the XML Schema is read and modeled in terms of abstract schema components, where in a second stage the XML Schema is augmented with a set of calculated schema components and properties, and where in a third stage the XML Schema is traversed to generate validation code; the validation code is generated by: calculating prohibited occurrence ranges; generating code to: evaluate each of the plurality of particles in an inner loop conditioned on an effective upper bound; then, once the inner loop terminates, check forbidden occurrence ranges for an inner particle, and calculate a range of possible repetitions of an outer particle; and once an outer loop terminates, check a range of total possible repetitions of the outer particle against its actual occurrence limits.

Claims

1. A method for generating XML (Extensible Markup Language) parsers through compilation of XML Schema grammars, the method comprising:

parsing an input document with a generated parser, where the generated parser is generated by a three-stage compilation of an XML Schema, where in a first stage the XML Schema is read and modeled in terms of abstract schema components, where in a second stage the XML Schema is augmented with a set of calculated schema components and properties used to drive code generation, and where in a third stage the XML Schema is traversed to generate validation code for each of a collection of elements;

wherein the validation code for ambiguous but legal content models is generated by;

calculating prohibited occurrence ranges for each of the plurality of particles involved;

generating code to;

evaluate each of the plurality of particles in an inner loop conditioned on an effective upper bound;

then, once the inner loop terminates, check forbidden occurrence ranges for an inner particle, and calculate a range of possible repetitions of an outer particle; and

once an outer loop terminates, check a range of total possible repetitions of the outer particle against actual occurrence limits of the outer particle.

2. The method of claim 1, wherein the XML Schema includes either one of:

complex types, simple types or a combination of simple types and complex types.

3. The method of claim 1, wherein the XML Schema specifies content models.

4. The method of claim 1, wherein the generated parser is divided into two logical layers, one a scanning layer and the other a validation layer.

5. The method of claim 4, wherein the validation layer is a generated recursive-descent parser that drives a scanner by utilizing compiled, predictive knowledge from the XML Schema.

6. The method of claim 4, wherein the scanning layer includes a set of fixed XML primitives for scanning content at a byte level.