Abstract:
A method may include receiving an extensible markup language schema definition (XSD) including multiple elements having a datatype. Each of the multiple elements may include an attribute profile defining a presence or an absence of at least one attribute. A first two or more of the multiple elements may include a first particular attribute profile. The method may further include generating a first grammar based on the XSD. The first grammar may be associated with encoding and decoding extensible markup language (XML) documents based on the XSD to and from efficient XML interchange (EXI) streams. The first grammar may also be associated with the first particular attribute profile. The method may further include associating each of the first two or more of the multiple elements with the first grammar.

Description:
FIELD 
       [0001]    The embodiments discussed herein are related to grammar generation for augmented datatypes. 
       BACKGROUND 
       [0002]    Extensible markup language (XML) is a markup language that defines a set of rules for encoding documents in a plain-text format that may be both human-readable and machine-readable. One version of XML is defined in the XML 1.0 Specification produced by the World Wide Web Consortium (W3C) and dated Nov. 26, 2008, which is incorporated herein by reference in its entirety. The XML 1.0 Specification defines an XML document as a text that is well-formed and valid. 
         [0003]    An XML schema is a description of a type of XML document, typically expressed in terms of constraints on the structure and content of documents of that type, above and beyond the basic syntactical constraints imposed by the XML 1.0 Specification itself. These constraints are generally expressed using some combination of rules governing the order of elements, Boolean predicates associated with the content, data types governing the content of elements and attributes, and more specialized rules such as uniqueness and referential integrity constraints. An XML document or set of XML documents may include an associated XML schema definition (XSD). The XSD may generally describe the XML schema associated with an XML document. 
         [0004]    Efficient XML interchange (EXI) is a binary XML format in which XML documents are encoded in a binary data format rather than plain text. In general, using an EXI format may reduce the size and verbosity of XML documents, and may reduce the time and effort expended to parse XML documents. A formal definition of EXI is described in the EXI Format 1.0 Specification produced by the W3C and dated Feb. 11, 2014, which is incorporated herein by reference in its entirety. An XML document may be encoded in an EXI format as an EXI stream. Additionally, the EXI stream may be decoded to form an XML document similar to or the same as the original XML document. 
         [0005]    The subject matter claimed herein is not limited to embodiments that solve any disadvantages or that operate only in environments such as those described above. Rather, this background is only provided to illustrate one example technology area where some embodiments described herein may be practiced. 
       SUMMARY 
       [0006]    According to an aspect of an embodiment, a method may include receiving an extensible markup language schema definition (XSD) including multiple elements having a datatype. Each of the multiple elements may include an attribute profile defining a presence or an absence of at least one attribute. A first two or more of the multiple elements may include a first particular attribute profile. The method may further include generating a first grammar based on the XSD. The first grammar may be associated with encoding and decoding EXI documents based on the XSD. The first grammar may also be associated with the first particular attribute profile. The method may further include associating each of the first two or more of the multiple elements with the first grammar. 
         [0007]    The object and advantages of the embodiments will be realized and achieved at least by the elements, features, and combinations particularly pointed out in the claims. 
         [0008]    It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are not restrictive of the invention, as claimed. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0009]    Example embodiments will be described and explained with additional specificity and detail through the use of the accompanying drawings in which: 
           [0010]      FIG. 1  is a block diagram of an example efficient extensible markup language interchange (EXI) processing system; 
           [0011]      FIG. 2  is a flowchart of an example process of generating full-fledged EXI grammars from an extensible markup language schema definition (XSD); 
           [0012]      FIG. 3  illustrates a portion of an example XSD; 
           [0013]      FIG. 4  illustrates a portion of an example extensible markup language (XML) document based on the XSD of  FIG. 2 ; and 
           [0014]      FIG. 5  is a flowchart of an example process of generating grammars. 
       
    
    
     DESCRIPTION OF EMBODIMENTS 
       [0015]    Prior to encoding an extensible markup language (XML) document into an efficient XML interchange (EXI) stream or decoding an EXI stream into an XML document, an associated XML schema definition (XSD) may be normalized into grammars. The grammars are rules that may be used to predict specific sequences of the XML document. An algorithm to generate the grammars for an XSD is included in the EXI Format 1.0 Specification. 
         [0016]    According to some embodiments described herein, elements having a same particular attribute profile may be assigned the same generated grammar. Thus, in some instances, multiple elements may result in fewer generated grammars, potentially significantly reducing the memory space occupied by grammar definitions. 
         [0017]    Embodiments of the present disclosure will be explained with reference to the accompanying drawings. 
         [0018]      FIG. 1  is a block diagram of an example EXI processing system  100 . The EXI processing system  100  includes a normalization device  104 . The normalization device  104  may be configured to receive an XSD  102  and to output a normalization  106 . The normalization  106  of the XSD may be used, for example, in encoding and/or decoding an XML document. 
         [0019]    The normalization device  104  may be configured to perform one or more operations of a grammar-generating process. According to some embodiments described herein, the normalization device  104  may generate a grammar and assign multiple elements having a same particular attribute profile and using the same type to the generated grammar. Thus, in some instances, the XSD  102  including multiple elements may result in the normalization  106  including fewer generated grammars than the number of elements of the XSD  102 , which may potentially reduce the amount of memory used to store grammar definitions. 
         [0020]    The normalization  106  may be communicated to an encoder/decoder  108 . An example encoder/decoder  108  may be included in the OpenEXI project hosted at SourceForge.net. The source code and documentation of the OpenEXI project as of the filing date of this application are incorporated herein by reference in their entirety. The encoder/decoder  108  may be configured to receive an XML document  110  and to encode the XML document  110  as an EXI stream  112 . Alternately or additionally, the EXI stream  112  may also be received by the encoder/decoder  108  and decoded as the XML document  110 . An original XML document  110  and the XML document  110  generated by the encoder/decoder  108  may include substantially identical XML data. However, certain types of human-readable information, such as whitespace, comments, and/or processing instructions, may not be preserved by the encoder/decoder  108  depending on associated preservation settings of the encoder/decoder  108 . 
         [0021]    The normalization device  104  may include a processor  103   a  and a memory  105   a . The encoder/decoder  108  may include a processor  103   b  and a memory  105   b . The memory  105   a  and the memory  105   b  may include non-transitory computer-readable media. Instructions such as programming code executable by the processor  103   a  and the processor  103   b  may be encoded in the memory  105   a  and the memory  105   b , respectively. When the instructions are executed by the processor  103   a  and/or the processor  103   b , the normalization device  104  and/or the encoder/decoder  108  may perform operations related to and/or including the processes described herein. 
         [0022]    The normalization device  104  and/or the encoder/decoder  108  may be employed in an embedded device and/or a device with limited memory capacity. Examples of embedded devices and/or devices with limited memory capacity include, but are not limited to, sensors, microcontrollers, and appliances, such as energy management controllers, automobile microcontrollers, smart meters, or the like. 
         [0023]      FIG. 2  is a flowchart of an example process  200  of generating full-fledged EXI grammars  210  from an XSD  202 . In some embodiments, the process  200  may be performed by the normalization device  104  of  FIG. 1 . 
         [0024]    The process  200  may begin with the XSD  202 . A set of EXI proto-grammars  206  may be generated from the XSD  202  at block  204 . 
         [0025]    In some embodiments, proto-grammar generation  204  may correspond to section 8.5.4.1 of the EXI Format 1.0 Specification. Alternately, the proto-grammar generation  204  may be performed in a different or modified manner. 
         [0026]    The EXI proto-grammars  206  may be augmented at block  208 , forming the full-fledged EXI grammars  210 . Augmenting the EXI proto-grammars  206  may include inserting additional attributes, properties, or the like. One or more of the embodiments described herein may occur at block  206 . 
         [0027]      FIG. 3  illustrates a portion of an example XSD  300 . The XSD  300  may include element A  302   a  through element H  302   h  (collectively “elements  302 ”) that may have associated datatypes  304 . Although the datatypes  304  are shown as string datatypes, other datatypes may alternately or additionally be used. The datatypes  304  may be defined by an EXI specification, an XML specification, and/or may be user-defined. The datatypes  304  may be associated with one or more acceptable formats and/or values for characters associated with corresponding elements  302 . 
         [0028]      FIG. 4  illustrates a portion of an example XML document  400  based on the XSD  300  of  FIG. 3 . The XML document  400  includes elements  401   a - h  (collectively “elements  401 ”) corresponding, respectively, to the elements  302  of  FIG. 3 . Each of the elements  401  may include start elements  402   a - 402   h  (collectively “start elements  402 ”), followed by characters  404   a - 404   h  (collectively “characters  404 ”) and end elements  406   a - 406   h  (collectively “end elements  406 ”). Each of the characters  404  may be encoded according to a grammar generated according to some embodiments described herein. 
         [0029]    With reference to  FIG. 3 , each of the elements  302  may have an associated attribute profile. In some embodiments, attribute profiles may define a presence or an absence of one or more attributes. Alternately or additionally, the attribute profile may define a value of one or more attributes, a range of one or more attributes, or the like. 
         [0030]    Attributes may be defined for the elements  302  implicitly. For example, by default, each of the elements  302  may not be associated with an attribute unless the attribute is otherwise assigned to the elements  302 . In some embodiments, the elements  302  may be assigned an attribute based on characteristics of the elements  302 . For example, an element such as an element  302   b  may be assigned a particular attribute based on an interpretation of the XSD  300 , such as by considering the manner the element  302   b  is used in the XSD  300 . In some embodiments, attributes based on an interpretation of the XSD  300  may be determined at a compilation of the XSD  300 . Alternately or additionally, attributes of the elements  302  may be defined explicitly. For example, the element A  302   a  and an element E  302 E may be explicitly assigned a particular attribute designated as attribute 1   306  in the XSD. 
         [0031]    In some embodiments, each of the elements  302  may be associated with nillable and/or dynamically typable (“typable”) attributes. Alternately or additionally, the elements  302  may be associated with other attributes. 
         [0032]    An element associated with the nillable attribute may be given a null value. Conversely, an element not associated with the nillable attribute may not be given a null value. 
         [0033]    An element associated with the typable attribute may be associated with elements having derived types. For example, if the element  302   a  has children elements (not shown), the element  302   a  may be associated with the typable attribute. Alternatively, if the element  302   a  has no children elements, the element  302   a  may not be associated with the typable attribute. 
         [0034]    The attribute profiles for the elements  302  may define a presence of the typable attribute (e.g., the element may be “typable”) or an absence of the typable attribute (e.g., the element may be “not typable”) and a presence of the nillable attribute (e.g., the element may be “nillable”) or an absence of the nillable attribute (e.g., the element may be “not nillable”). 
         [0035]    According to some embodiments described herein, elements having the same particular attribute profile may be assigned the same generated grammar. For instance, a single first state and a single second state may be generated for all ten of the elements. By way of example, for an XSD including ten elements having both a “string” datatype and a particular attribute profile of typable and not nillable, one of the following first states and one of the following second states may be generated: 
         [0000]    
       
         
               
             
               
               
             
           
               
                   
               
               
                 First state: 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 &lt;Grammar&gt; 
               
               
                   
                  &lt;Productions&gt; 
               
               
                   
                   &lt;CharactersTyped/&gt; 
               
               
                   
                   &lt;Grammar&gt;1&lt;/Grammar&gt; 
               
               
                   
                   &lt;XsiType/&gt; 
               
               
                   
                  &lt;/Productions&gt; 
               
               
                   
                 &lt;/Grammar&gt; 
               
               
                   
                   
               
             
          
         
       
     
         [0000]    
       
         
               
             
               
               
             
           
               
                   
               
               
                 Second state: 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 &lt;Grammar&gt; 
               
               
                   
                  &lt;Productions&gt; 
               
               
                   
                   &lt;EndElement/&gt; 
               
               
                   
                  &lt;/Productions&gt; 
               
               
                   
                 &lt;/Grammar&gt; 
               
               
                   
                   
               
             
          
         
       
     
         [0036]    In some instances, the above first state may occupy 94 bytes and the above second state may occupy 59 bytes. In this embodiment, the total bytes occupied by the definition of a single grammar in the above example may be 153 bytes. 
         [0037]    By comparison, in some formats, e.g., in the current EXI Format 1.0 Specification, a separate grammar may be generated for each of the elements, which may occupy a relatively higher number of bytes. By way of example, for an XSD including ten elements having both a “string” datatype and a particular attribute profile of typable and not nillable as in the embodiment above, ten of the above first states and one of the above second states may be generated. In this example, the total bytes occupied by the definition of the ten grammars may be 999 bytes. 
         [0038]    In some embodiments, a single grammar may be generated for each particular attribute profile. Using nillable and typable attributes as an example, the elements  302  may have one of four particular attribute profiles: 1) not nillable and not typable, 2) not nillable and typable, 3) nillable and not typable, and 4) nillable and typable. A first grammar may be generated for not nillable and not typable elements, a second grammar may be generated for not nillable and typable elements, a third grammar may be generated for nillable and not typable elements, and a fourth grammar may be generated for nillable and typable elements. Thus, in some instances, four or fewer grammars may be generated for multiple elements, potentially significantly reducing the number of bytes occupied by grammar definitions. 
         [0039]    In some embodiments, an XML document such as the XML document  400  of  FIG. 4  may be encoded as an EXI stream. An associated normalization may include a single grammar for encoding multiple elements having the same particular attribute profile. 
         [0040]    For example, with combined reference to  FIG. 3  and  FIG. 4 , element A  401   a  and element E  401   e  may both include a first particular attribute profile, element B  401   b  and element F  401   f  may both include a second particular attribute profile, element C  401   c  and element G  401   g  may both include a third particular attribute profile, and element D  401   d  and element H  401   h  may both include a fourth particular attribute profile. A first grammar may be generated for the first particular attribute profile, a second grammar may be generated for the second particular attribute profile, a third grammar may be generated for the third particular attribute profile, and a fourth grammar may be generated for the fourth particular attribute profile. 
         [0041]    Therefore, encoding the XML document  400  as the EXI stream may include encoding characters  404   a  and characters  404   e  according to the first grammar, encoding characters  404   b  and characters  404   f  according to the second grammar, encoding characters  404   c  and characters  404   g  according to the third grammar, and encoding characters  404   d  and characters  404   h  according to the fourth grammar. Decoding the resulting EXI stream may be performed by decoding the encoded characters according to the associated first, second, third, or fourth grammars. 
         [0042]      FIG. 5  is a flowchart of an example process  500  of generating grammars for elements. By way of example, the process  500  is described with reference to elements having attribute profiles that may define the presence or absence of the typable attribute and the nillable attribute. However, other attributes may alternately or additionally be used. In some embodiments, the process  500  may be performed by the processor  103   a  of the EXI processing system  100  of  FIG. 1 . 
         [0043]    In some embodiments, the process  500  may be performed individually for each datatype used in an associated XSD. Alternately, the process  500  may be performed once for multiple datatypes. For example, where a single proto-grammar is generated for multiple datatypes, the process  500  may be performed once for the multiple datatypes. 
         [0044]    The process  500  may begin at block  502 , where an element may be considered. The element may be part of an XSD such as the XSD  300  of  FIG. 3 . 
         [0045]    At block  504 , the process  500  may determine whether the element is not typable and not nillable. If the element is not typable and not nillable, the process  500  may continue to block  506 . Otherwise, the process  500  may continue to block  508 . 
         [0046]    At block  506 , a grammar G may be used for the element such that the grammar G may be associated with the particular attribute profile “not typable and not nillable.” For example, the grammar G may be associated with the element within a normalization such as the normalization  106  of the EXI processing system  100  of  FIG. 1 . In some embodiments, the grammar G may be the proto-grammar associated with the element. For example, the grammar G may be the proto-grammar generated at block  204  of the process  200  of  FIG. 2  and may be associated with the element. 
         [0047]    At block  508 , the process  500  may determine whether the element is not typable and nillable. If the element is not typable and nillable, the process  500  may continue to block  510 . Otherwise, the process  500  may continue to block  516 . 
         [0048]    At block  510 , the process may determine whether a grammar G[ 0 ] is available. The grammar G[ 0 ] may be an augmented copy of the grammar G associated with the particular attribute profile “not typable and nillable.” If the grammar G[ 0 ] is available, the process  500  may continue to block  514 . 
         [0049]    If the grammar G[ 0 ] is not available, the grammar G[ 0 ] may be generated and stored at block  512  before continuing to block  514 . In some embodiments, the grammar G[ 0 ] may be generated via the process described in section 8.5.4.4.2 of the EXI Format 1.0 Specification. By way of example, the grammar G[ 0 ] may be stored in the memory  105   a  of the EXI processing system  100  of  FIG. 1 . 
         [0050]    At block  514 , the grammar G[ 0 ] may be used for the element. For example, the grammar G[ 0 ] may be associated with the element within the normalization. 
         [0051]    At block  516 , the process  500  may determine whether the element is typable and not nillable. If the element is typable and not nillable, the process  500  may continue to block  518 . Otherwise, the process  500  may continue to block  524 . 
         [0052]    At block  518 , the process may determine whether a grammar G[ 1 ] is available. The grammar G[ 1 ] may be an augmented copy of the grammar G associated with the particular attribute profile “typable and not nillable.” If the grammar G[ 1 ] is available, the process  500  may continue to block  522 . 
         [0053]    If the grammar G[ 1 ] is not available, the grammar G[ 1 ] may be generated and stored at block  520  before continuing to block  522 . In some embodiments, the grammar G[ 1 ] may be generated via the process described in section 8.5.4.4.2 of the EXI Format 1.0 Specification. By way of example, the grammar G[ 1 ] may be stored in the memory  105   a  of the EXI processing system  100  of  FIG. 1 . 
         [0054]    At block  522 , the grammar G[ 1 ] may be used for the element. For example, the grammar G[ 1 ] may be associated with the element within the normalization. 
         [0055]    At block  524 , it may be known that the element has the particular attribute profile of “typable and nillable,” and the process may determine whether a grammar G[ 2 ] is available. The grammar G[ 2 ] may be an augmented copy of the grammar G associated with the particular attribute profile “typable and nillable.” If the grammar G[ 2 ] is available, the process  500  may continue to block  528 . 
         [0056]    If the grammar G[ 2 ] is not available, the grammar G[ 2 ] may be generated and stored at block  526  before continuing to block  528 . In some embodiments, the grammar G[ 2 ] may be generated via the process described in section 8.5.4.4.2 of the EXI Format 1.0 Specification. By way of example, the grammar G[ 2 ] may be stored in the memory  105   a  of the EXI processing system  100  of  FIG. 1 . 
         [0057]    At block  528 , the grammar G[ 2 ] may be used for the element. For example, the grammar G[ 2 ] may be associated with the element within the normalization. 
         [0058]    After grammar G, G[ 0 ], G[ 1 ], or G[ 2 ] is associated with the element, the process  500  may optionally return to block  502  to begin again with a new element. 
         [0059]    The embodiments described herein may include the use of a special-purpose or general-purpose computer including various computer hardware or software modules, as discussed in greater detail below. 
         [0060]    Embodiments described herein may be implemented using computer-readable media for carrying or having computer-executable instructions or data structures stored thereon. Such computer-readable media may be any available media that may be accessed by a general-purpose or special-purpose computer. By way of example, and not limitation, such computer-readable media may include non-transitory computer-readable storage media including Random Access Memory (RAM), Read-Only Memory (ROM), Electrically Erasable Programmable Read-Only Memory (EEPROM), Compact Disc Read-Only Memory (CD-ROM) or other optical disk storage, magnetic disk storage or other magnetic storage devices, flash memory devices (e.g., solid state memory devices), or any other storage medium which may be used to carry or store desired program code in the form of computer-executable instructions or data structures and which may be accessed by a general-purpose or special-purpose computer. Combinations of the above may also be included within the scope of computer-readable media. 
         [0061]    Computer-executable instructions may include, for example, instructions and data which cause a general-purpose computer, special-purpose computer, or special-purpose processing device (e.g., one or more processors) to perform a certain function or group of functions. Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims. 
         [0062]    As used herein, the terms “module” or “component” may refer to specific hardware implementations configured to perform the operations of the module or component and/or software objects or software routines that may be stored on and/or executed by general-purpose hardware (e.g., computer-readable media, processing devices, etc.) of the computing system. In some embodiments, the different components, modules, engines, and services described herein may be implemented as objects or processes that execute on the computing system (e.g., as separate threads). While some of the system and methods described herein are generally described as being implemented in software (stored on and/or executed by general-purpose hardware), specific hardware implementations or a combination of software and specific hardware implementations are also possible and contemplated. In this description, a “computing entity” may be any computing system as previously defined herein, or any module or combination of modulates running on a computing system. 
         [0063]    All examples and conditional language recited herein are intended for pedagogical objects to aid the reader in understanding the invention and the concepts contributed by the inventor to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions. Although embodiments of the present inventions have been described in detail, it should be understood that the various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.