Abstract:
A computer-implemented method of parsing markup-language source data is described. The markup-language source data comprises a plurality of elements. A first portion of the elements is processed by interoperating with a symbol table to determine unique string objects associated with the elements of the first portion of the elements. A structure is recorded associated with the first portion of the elements collectively, including the determined unique string objects in association with the corresponding elements of the first portion. A second portion of the elements is processed, using the structure determined associated with the first portion of the elements, to determine the unique string objects associated with the elements of the second portion, without interoperating with the symbol table.

Description:
TECHNICAL FIELD 
   The present invention is in the field of markup language (such as XML) parsing and, in particular, relates to an optimization related to recognizing repeated structures in markup language source. 
   BACKGROUND 
   Generally speaking, a parser is a program to check whether an input file has the correct grammar for the language, and also to build a data structure describing the program. For example, the input file may be in a markup language such as XML (Extensible Markup Language). By contrast to computer languages such as C or Pascal, the result of processing a markup language input file is typically not executable code. Rather, the result of processing a markup language input file typically includes tagged text. For example, XML provides for the creation of customized tags, enabling the definition, transmission, validation, and interpretation of data between applications and between organizations. 
     FIG. 1  illustrates an example of an excerpt from an XML source file. The excerpt defines a table record with two row records. The text of the form &lt;X&gt; and &lt;/X&gt; are start and end tokens (tags), respectively, which indicate the start and end of a record. It can be seen from  FIG. 1  that the records may be nested such that tags are provided at various depths. More particularly, a subsequent start token may be provided before a matching end token is provided for a preceding start token. 
   Referring to the  FIG. 1  example, and taking the &lt;table&gt; token as being at depth  1 , the &lt;row&gt; token is at depth  2 , and the &lt;id&gt;, &lt;firstname&gt;, &lt;lastname&gt;, &lt;street&gt;, &lt;city&gt;, &lt;state&gt; and &lt;zip&gt; tokens are at depth  3 . The  FIG. 1  example is a relatively simple one. However, the structures may be arbitrarily complex, so long as the nesting rules are met (i.e., that an end token is provided matching the last provided start token, before any other end token is provided). 
     FIG. 2  illustrates the contents of a character array buffer, corresponding to the XML source file excerpt in  FIG. 1 . Conventionally, an XML stream is loaded into such a character array buffer, and the stream is parsed from the character buffer. 
   With reference to the pseudo code in  FIG. 3 , we now describe a conventional parsing flow, for parsing a markup language stream (using XML as a specific example). In the main XML parser, at step  1 , the XML stream is loaded into the character array buffer (such as is shown in  FIG. 2 ). At step  2 , the stream is processed until the start of a new element is detected. In this case, the start of the new element is a start tag, delimited by “&lt;” and “&gt;.” 
   At step  3 , the process_element( ) process (also shown in  FIG. 3 ) is called. Finally, at step  4 , processing continues until either the start of a new element is detected or processing of the source file is finished. If a new element is detected, then processing returns to step  3  (indicated by the step label “new_element”). 
   We now discuss the process_element process, with reference still to  FIG. 3 . As just described, the process_element process is called by the main XML parser program process. In addition, as will be described, the process_element process is also called recursively. 
   At step  1  of the process_element process, the start tag is read for the element being processed. At step  2  of the process_element process, the get_stringobject process is called to get a string object, from a symbol table, for the string. 
   The get_stringobject process will be described in greater detail below. At step  3  of the process_element process, the string object is pushed onto a stack. Finally, at step  4 , processing continues until a new element is detected, in which case the process_element process is called recursively, or the end of the element is detected. If the end of the element is detected, then the string object for the element is popped off the stack and processing returns to the calling program (which, it should be recalled, may be the process_element process itself). 
   We now describe the get_stringobject process, still with reference to  FIG. 3 . In the get_stringobject process, each character of the start string is checked to determine that it is a valid XML character according to the XML 1.0 specification. At step  2 , the symbol table is checked to determine whether there is already a string object for the start string. At step  3 , if there is already a string object for the start string in the symbol table, then the already-present string object is returned as the result of the get_stringobject process. Otherwise, a new string object is created in the symbol table for the start string, and the newly-created string object is returned as the result of the get_stringobject process. 
   Referring specifically to XML, but also relevant to other markup languages, there are at least two relatively “expensive” (i.e., that take lot of time and/or processing power) functions that the parser performs. Two such functions dealt with here are within the get_stringobject processing. One such expensive function is checking that each character of the start string is a valid XML character. Another expensive function is checking the symbol table to determine whether there is already a string object for the start string, particular as the number of string objects referenced in the symbol table increases. 
   SUMMARY 
   A computer-implemented method of parsing markup-language source data is described. The markup-language source data comprises a plurality of elements. A first portion of the elements is processed by interoperating with a symbol table to determine unique string objects associated with the elements of the first portion of the elements. A structure is recorded associated with the first portion of the elements collectively, including the determined unique string objects in association with the corresponding elements of the first portion. A second portion of the elements is processed, using the structure determined associated with the first portion of the elements, to determine the unique string objects associated with the elements of the second portion, without interoperating with the symbol table. 

   
     BRIEF DESCRIPTION OF FIGURES 
       FIG. 1  illustrates an input markup language source file. 
       FIG. 2  illustrates contents of a character array buffer for a portion of the  FIG. 1  input markup language source file. 
       FIG. 3  illustrates a conventional prior art parsing flow for a markup language source file. 
       FIG. 4  illustrates an array data structure useable to record a structure associated with processing a first portion of elements in an input markup language source file. 
       FIG. 5  illustrates an example of improved get_stringobject processing. 
   

   DETAILED DESCRIPTION 
   It is desirable to make markup language processing more efficient. In accordance with an aspect described herein, the string processing is streamlined, based on the property of many markup language source files that there are repeating structures of elements. Broadly speaking, by recognizing that elements are repeated in a particular pattern, some processing related to that pattern can be carried out only once, when the pattern is first encountered. 
     FIG. 4  illustrates a particular example of structure used to capture an initial instance of a pattern captured by the parser processing. The  FIG. 4  data structure is an array, but other suitable data structures may be employed, such as a linked list data structure.  FIG. 5  illustrates processing that refers to the captured initial instance to streamline subsequent encounters of the same pattern instance. 
   Referring first to  FIG. 5 , the pseudo code in this figure is an improved version of the conventional get_stringobject process. As can be seen from  FIG. 5 , the new get_stringobject process, when invoked with a start string, processes either in Stage  1  or Stage  2 . Stage  1  processing is used to carry out processing, typically “expensive” processing as discussed above in the Background, for what may be determined to be a first instance of a pattern of instances. Stage  2  processing is used to carry out processing of what are nominally subsequent encounters of the first instance. 
   Thus, referring to the Stage  1  processing, it can be seen that steps  102 ,  104  and  106   a  and  106   b  ( FIG. 5 ) are the same as steps  1 ,  2  and  3   a  and  b  in the conventional get_stringobject processing shown in  FIG. 3 . Step  106   c  processing populates a data structure, such as the  FIG. 4  array, with information of an initial instance. This includes saving an indication of the string object (for example, a link to the string object in the symbol table) in association with the start string. 
   At step  106   d , when a particular condition is met (indicative of what is nominally the end of a first pattern instance), it is indicated that further invocations of the get_stringobject processing are to be in Stage  2  (to carry out processing of what are nominally subsequent encounters of the first instance). That is, further invocations of the get_stringobject processing refer to the data structure populated in Stage  1 . 
   We now refer to the Stage  2  processing in  FIG. 5 . At step  202 , the next element to be read is predicted using the entries in the data structure. Put another way, assuming that the Stage  2  processing is for a subsequent processing of a pattern instance, the data structure is accessed in place of the expensive processing of the symbol table. At step  204 , the start tag string is compared to the predicted next element (result from step  202 ). 
   If there is a match at step  206 , then the number of characters from the character buffer can be skipped. That is, as a result, the processing to check each character of the start tag for validity with respect to the XML 1.0 specification, as well as the processing of the symbol table to check for and obtain the string object (and perhaps even create the string object), is replaced by a simple compare and simple access of the string object using the pointer in the data structure. At step  208 , if there is no match, then it is indicated that further invocations of the get_stringobject processing are to use Stage  1  processing, and the string object for the present start tag is processed using Stage  1  processing as well. 
   We now more particularly discuss what is meant, in one example, by a particular condition being meant so that subsequent invocations of the get_stringobject processing are to be in Stage  2 . Referring again to  FIG. 4 , this array data structure stores information about start element tokens in sequence as they are encountered. 
   In the  FIG. 4  example, position  0  includes the “table” token, indicated as being at depth  1 ; position  1  includes the “row” token, indicated as being at depth  2 ; position  2  includes the “id” token, indicated as being at depth  3 ; position  3  includes the “firstname” token, indicated as also being at depth  3 ; etc. 
   It is noted that depth increases when the elements are encountered. In addition, two variables are maintained: 
   
     
       
             
             
           
         
             
                 
                 
             
           
           
             
                 
               fLastDepth = depth of last start tag opened. 
             
             
                 
               fDepth = current depth 
             
             
                 
                 
             
           
        
       
     
   
   A decrease of depth means that a subtree has been read. The test for the particular condition which the parser uses as a signal to invoke Stage  2  processing includes 
   if (flastDepth&gt;fdepth &amp;&amp; fDepth&lt;=3){ 
   Thus, for example, when “firstname” is encountered, flastDepth=3, and firstname is also at depth  3 , so the condition is not met. The current element is added to the array data structure. (In one example, such processing will continue until twenty element have been encountered, which is the size of the array. The limit is configurable. That is, analysis stops if a pattern is not discerned within a set amount of encountered elements.) 
   According to the condition discussed above, the parser will invoke Stage  2  processing only when there is decrease in depth two times, adjacently. Thus, for example, Stage  2  processing would be invoked with a structure like: 
                                           &lt;a&gt;            &lt;b&gt;              &lt;c&gt; &lt;/c&gt;            &lt;/b&gt;            &lt;b&gt;             &lt;c&gt; &lt;/c&gt;            &lt;/b&gt;           &lt;/a&gt;                        
Note the decrease in depth two times, adjacently, at the end tokens for “c” and “b.”
 
   By contrast, Stage  2  processing would not be invoked with a structure like: 
   
     
       
             
             
           
         
             
                 
                 
             
           
           
             
                 
               &lt;a&gt; 
             
             
                 
                &lt;b&gt;&lt;/b&gt; 
             
             
                 
                &lt;b&gt;&lt;/b&gt; 
             
             
                 
                &lt;b&gt;&lt;/b&gt; 
             
             
                 
                &lt;b&gt;&lt;/b&gt; 
             
             
                 
               &lt;/a&gt; 
             
             
                 
                 
             
           
        
       
     
   
   Stage  2  processing also would not be invoked for a structure like: 
                                           &lt;table&gt;            &lt;row/&gt;            &lt;row&gt;            &lt;id&gt;0001&lt;/id&gt;            &lt;firstname&gt;Bob&lt;/firstname&gt;            &lt;lastname&gt;Aranow&lt;/lastname&gt;            &lt;street&gt;2 Any St.&lt;/street&gt;            &lt;city&gt;Anytown&lt;/city&gt;            &lt;state&gt;AL&lt;/state&gt;            &lt;zip&gt;22000&lt;/zip&gt;            &lt;/row&gt;            &lt;row&gt;            &lt;id&gt;0001&lt;/id&gt;            &lt;firstname&gt;Bob&lt;/firstname&gt;            &lt;lastname&gt;Aranow&lt;/lastname&gt;            &lt;street&gt;2 Any St.&lt;/street&gt;            &lt;city&gt;Anytown&lt;/city&gt;            &lt;state&gt;AL&lt;/state&gt;            &lt;zip&gt;22000&lt;/zip&gt;            &lt;/row&gt;           ...           ..           &lt;/table&gt;                        
In particular, it should be noted that the elements will be stored in the array data structure as “table”, “row”, “row”, “id”, “firstname” and “lastname.” Since two “row” elements are stored, the document structure is not repeated such that it is appropriate to invoke Stage  2  processing.
 
   In some examples, a stack data structure is used to track open start tags. Thus, for example, when a start tag is encountered, an indication of the start tag is pushed onto the stack data structure and, when an end tag is encountered, the start indication of the tag (to which that encountered end tag corresponds) is popped off the stack data structure. Thus, the contents of the stack data structure is dynamic such that, for example, when the parser encounters the first &lt;/id&gt; end tag ( FIG. 1  input source file) and before processing the &lt;/id&gt; end tag, the stack data structure will include indications of [table, row, id]. As another example, when the parser encounters the first &lt;firstname&gt; start tag (and after processing the &lt;firstname&gt; start tag), the stack data structure will include indications of [table, row, firstname]. 
   The start tag indications that are pushed onto the stack data structure are the indexes for the start tags an “initial instance” array like the  FIG. 4  example array. So, for example, the content of the stack data structure would be [0,1,2] when encountering and before processing the &lt;/id&gt; end tag. As another example, the content of the stack data structure would be [0,1,3] when encountering (and after processing) the &lt;firstname&gt; start tag. 
   The stack data structure may be referred to when going into “fallback mode” (e.g., step  208  of the NEW GET_STRINGOBJECT processing shown in  FIG. 5 ), that indicates “If no match, then indicate and revert to Stage  1  processing.” More particularly, the Stage  1  processing can refer to the stack data structure to know about the element start tags that have not yet been closed. (According to typical markup language specifications, such as XML 1.0, start tags should be closed by corresponding end tags.) 
   Using the described approach, markup language processing may be made more efficient, by recognizing repeating structures of elements and, based thereon, streamlining the string processing.