Method and apparatus for parsing source code using prefix analysis5812853Abstract A method and apparatus for processing source code in a language processing system with improved parsing based on prefix analysis. A method in accordance with the present invention includes the steps of identifying a previously-parsed prefix of a source code translation unit; creating a parser in a parser state corresponding to the identified prefix; and parsing a remaining portion of the translation unit after the prefix using the parser in the parser state corresponding to the prefix. In one embodiment of the invention, the step of creating a parser includes retrieving stored level-one subtrees corresponding to the top-level statements in the prefix. The level-one subtrees corresponding to the prefix may be stored in the form of a prefix tree along with the text of the top-level source code statements represented by the prefix and a parser delta indicating the effect of the code statements on the parser state. Claims We claim: Description BACKGROUND OF THE INVENTION
______________________________________
#include <X.h>
void f() {
// . . .
______________________________________
After this source code file is preprocessed and parsed, the definition of function f() might change. If the file is then parsed again, the prefix of the translation unit corresponding to the macro-expansion of X.h will often be the same, and will thus have been previously parsed. Further, if at a later time the following source code file is preprocessed and parsed:
______________________________________
#include <X.h>
void g() {
// . . .
______________________________________
the translation unit prefix for the latter source code file will often be the same as that of the former. The parsing of the present invention exploits such common prefixes in a significantly more efficient manner than, for example, the prior art precompiled header techniques. The present invention is based in part on recognition that it is very difficult to determine before preprocessing whether a set of source code has been previously parsed. Many of the problems of prior art techniques, such as precompiled header files, stem from a failure to recognize and address this difficulty. In accordance with the present invention, this difficulty is overcome by, for example, first completely preprocessing the source code to be parsed, and then performing prefix analysis to determine if any portion of the preprocessed source code has been previously parsed. In the embodiments described below, it will be assumed that top-level source code statements in the translation unit correspond to level-one subtrees in the parse tree of the translation unit. There will thus be an a priori correspondence between top-level statements and portions of the parse tree. For example, the parse tree for the following translation unit:
______________________________________
class T {
// . . .
};
void add1 (int& n) {
++n;
extern int i;
______________________________________
includes three level-one subtrees, corresponding to the definition of T, the definition of add1, and the declaration of i. It will be readily understood by those skilled in the art, however, that the present invention may also be implemented using parse trees for which top-level source code statements are represented by lower level subtrees. For example, an a priori correspondence between top-level source code statements and portions of the parse tree could be achieved by assigning level-two subtrees to certain top-level statements. FIGS. 3(a) and 3(b) illustrate an exemplary sequence of steps for generating a parse tree in accordance with the present invention. Referring to FIG. 3(a), an input source code file 120 is preprocessed in the manner previously described to generate a translation unit 122. A prefix 124 of the translation unit 122 is then identified as having been previously parsed. As used herein, a prefix refers to an initial portion of a translation unit. The remainder 126 of the translation unit 122 is a portion which has not been previously parsed. For maximum efficiency, the prefix 124 should be the longest prefix of the translation unit 122 which is the same as a prefix of a translation unit previously parsed. Such a prefix will be referred to herein as a maximal prefix. The process of identifying a maximal or near-maximal prefix will be referred to herein as prefix analysis. The process of utilizing an identified prefix to reduce parse time will be referred to herein as prefix optimization. A partial parse tree 128 with root node 130 is then created by retrieving the level-one subtrees 132 corresponding to a previous parsing of the prefix 124. The partial parse tree 128 may be stored in, for example, the memory 26 or secondary storage 28 of FIG. 1 as a data structure referred to as a prefix tree and described in greater detail below. Referring now to FIG. 3(b), a complete parse tree 140 for the translation unit 122 is generated by using a parser in a state corresponding to the prefix 124 to parse the remainder 126 of the translation unit 122. A parser in a state corresponding to a prefix refers to a parser in a state it would be in after parsing that prefix. This parser then generates the level-one subtrees 144 corresponding to the remainder 126 of the translation unit 122. The complete parse tree 140 is generated by adding the level-one subtrees 144 for the remainder 126 to the level-one subtrees 132 for the prefix 124. FIG. 4 shows a flow diagram of the exemplary parsing method of the present invention described above in conjunction with FIGS. 3(a) and (b). The exemplary parsing method includes the following steps: (1) preprocessing the source code (operation block 150); (2) identifying the maximal prefix of the resulting translation unit corresponding to top-level source code statements that have been previously parsed (operation block 154); (3) creating a parser in the parser state that the parser would be in after parsing the portion of the translation unit corresponding to the maximal prefix (operation block 158); (4) parsing the remaining source code in the translation unit using the parser created in step (3) (operation block 162); and (5) storing the results of the parsing for use in subsequent repetitions of the parsing method (operation block 168). The parser state which is determined in operation block 158 of the exemplary parsing method of FIG. 4 will be described in greater detail below. It should be noted that performing the prefix analysis on the code after preprocessing eliminates the need for users to track header file dependencies. A tradeoff is that the parser always preprocesses all source code, even the source code for prefixes that have already been parsed. As will be demonstrated below, the use of a fast preprocessor can substantially reduce the time spent preprocessing in the above exemplary method. It should also be noted that to determine the maximal prefix in operation block 154, it may be necessary to use a data structure which is stored across a number of executions of the parsing method. Such a data structure is described in detail below. In alternative embodiments, a near-maximal prefix or a prefix of a shorter length could be identified instead of a maximal prefix. The exemplary method of the present invention also has the desirable property that if a comment is changed after a given set of source code has been parsed, a subsequent parse of that source code is performed very quickly, because changing a comment typically does not affect the text of the corresponding translation unit. This is due to the fact that in certain programming languages, such as C and C++, preprocessing generally replaces each comment with a single space. The parser state will now be described in greater detail. The following description will use s to designate a sequence of top-level source code statements. The parser state after s is defined herein as the minimal amount of information needed to create a parser that will correctly parse any source code following s. The step of creating a parser in a particular state thus generally involves retrieving the corresponding information from, for example, memory 26 or secondary storage 28 of FIG. 1. It should be noted that this definition of parser state depends on the type of parse trees being generated. For the type of parse trees typically generated in most programming environments, the parser state includes information about the names declared in s. For example, the parser state after parsing the following C++ source code:
______________________________________
class T {
public:
void f();
};
void add1 (int& n) {
float g;
++n:
extern int i;
______________________________________
might include the following information: Type names T, add1, and i are declared at global scope; nontype name f is declared in T's inner scope. The parser state need not include any information about the names n or g in the above code because nothing about these names can affect the parsing of any source code following the exemplary sequence of code statements. If s is expressed as the concatenation of the top-level source code statements s.sub.1, s.sub.2, . . . , s.sub.n, then the parser state after s is (.DELTA..sub.n.sup.o . . . .sup.o .DELTA..sub.2.sup.o .DELTA..sub.1) (0) where (0) is the initial parser state and the parser delta .DELTA..sub.1 represents the effect of s.sub.i on any given parser state. For example, the following is the parser delta for the definition of T shown in the above code: Add type name T to the global scope; add nontype name f to T's inner scope. A parser in the state after s can be created by first creating a parser in the initial state and then applying all the parser deltas to that parser. An exemplary data structure for storing information about previously-parsed code will now be described. This data structure is referred to herein as a prefix tree. In the prefix tree of the present invention, each node other than the root node represents a top-level source code statement. The path from the root node of the prefix tree to any other node therein represents the translation unit formed by concatenating the source code statements represented by the nodes along that path. The path from the root node to itself represents the empty translation unit. Each node n in an exemplary prefix tree contains the following information: TEXT.sub.n --the text of the top-level statements s represented by node n TREE.sub.n --the level-one subtree that represents s .DELTA..sub.n --the parser delta for s FIG. 5 shows an exemplary prefix tree 180 for the sequence of C++ source code statements listed in the above discussion of parser state. The prefix tree 180 shows only the values of TEXT.sub.n. FIG. 6 shows an exemplary prefix tree 190 for the following translation unit, showing only the values of TEXT.sub.n :
______________________________________
class T {
public:
void f();
};
class U {
public:
void g();
};
______________________________________
The actual number of prefix trees used, and which prefix trees are used by a particular parser, will generally depend upon the programming environment in which the parser is used. However, if the same prefix tree is used for a series of parses, the prefix tree may grow arbitrarily large. It would therefore be potentially inefficient to read the entire prefix tree at the start of every parse that uses it. This problem is solved in accordance with the present invention by using, for example, a disk-based prefix tree in which only the nodes which must be examined in a particular parse are read in from disk or other secondary storage for that parse. To further improve the parsing efficiency of the present invention, the prefix trees can be stored in a compressed form. For example, to minimize the time spent reading the TEXT.sub.n information for all the nodes that must be examined while parsing, TEXT.sub.n can be stored in compressed form. One possible technique for achieving high compression involves using a compressor in the state s resulting from having compressed all the ancestors of node n, starting from the root node. Unfortunately, this technique may adversely affect the efficiency of the parsing method. For example, in the exemplary parsing method of the present invention, it might be necessary to decompress all the children of a given node. If each child was compressed using a compressor in state s, it will then be necessary to set the state of a decompressor to s for each child. For many compression techniques, it is difficult to efficiently set the state of a decompressor to a noninitial state s. An alternative technique for compressing the prefix trees of the present invention involves compressing each TEXT.sub.n individually. Unfortunately, because the average size of a top-level statement in well-written C++ code is small (typically about 200 characters), compressing each TEXT.sub.n individually might not achieve a sufficiently high compression rate. Another alternative compression technique involves altering the definition of a prefix tree to allow every node in the prefix tree to represent a contiguous sequence of top-level statements. For example, every node could represent as many top-level statements as is necessary to give the tree the property that no node has only one child. Thus, if a given node had only one child, that child could be merged with the given node. When attempting to identify the longest prefix that has already been parsed, if a prefix ends within a sequence of statements represented by a node, that node can be split before continuing the prefix analysis. Such an approach may be difficult to implement efficiently, however. First, when a node is examined, one cannot simply read in the entire compressed text stored at that node, because there would usually be no upper bound on the size of that text. Instead, fixed-size portions of the compressed text could be read in one at a time, decompressing each portion as it is read in. In addition, the process of splitting a node may be problematic. For example, assume a given node n representing the decompressed text a=a.sub.1 a.sub.2 is to be split between a.sub.1 and a.sub.2, and that c represents the compression of a. The compressions c.sub.1 and c.sub.2 of a.sub.1 and a.sub.2, respectively, must then be computed. Computing c.sub.1 is typically not difficult because c.sub.1 is simply a prefix of c. The compression c.sub.2, however, is in general not the remaining suffix of c. To compute c.sub.2 one might first compute the uncompressed a.sub.2, and then compress it. However, computing a.sub.2 requires reading in from memory or secondary storage the entire compressed text stored at n, which, as previously stated, might be inefficient. A preferred compression approach, which addresses many of the above-identified compression problems, may be implemented as follows. Every node in the prefix tree is used to represent a contiguous sequence of some constant number k of top-level source code statements. It should be noted that for any node representing the end of a translation unit, it might be necessary to represent fewer than k source code statements at that node. One suitable value of k is 50. Existing fast compression algorithms can be used to efficiently compress about 50 top-level statements to achieve up to about a 70% compression rate in practice. This rate is approximately that achieved in practice by compressing the entire translation unit at once. Allowing each prefix tree node to represent up to 50 top-level source code statements may mean that the maximal previously-parsed prefix might not be found using the exemplary method described above. Instead, the method might find a prefix of top-level statements that contains at most 50 statements fewer than the maximal prefix. However, assuming a constant upper bound on the number of characters in a top-level statement, the parsing of the present invention will still produce a near-maximal prefix. In addition, representing 50 statements per node might reduce several constant factor overheads in a practical implementation of the above-described exemplary parsing method. Of course, values of k other than 50 may also be used. Exemplary techniques for parsing a given translation unit prefix will now be described. To construct the nodes in the prefix tree, a function is needed that can parse at most k top-level statements from the text remaining in a given translation unit. Such a function can then be called repeatedly in order to parse the entire translation unit. More specifically, define s as a sequence of top-level statements, P as a parser in the state after s, and e as a text string. Assume that e, when parsed in the context of s, is error free, and define t as the first k statements in e. A function parseprefix(P, e) may be used which returns the triple (len, T, .DELTA.), where len is the number of characters in t, T is the prefix tree representing t, and .DELTA. is the parser delta for t. The function parseprefix(P, e) may be implemented in any of a number of ways to return these values. Furthermore, when the function parseprefix(P, e) returns, P is in the state after the concatenation of s and t. For illustrative purposes, the remainder of this description will assume that e, when parsed in the context of s, is error free. It will be readily apparent to those skilled in the art that the present invention also encompasses translation units which do not conform to this assumption. The above-described parsing may be implemented using the following set of exemplary processing steps:
______________________________________
parse (t, T) is
1 e .rarw. macro-expansion of t
2 P .rarw. parser in initial state
3 n .rarw. root of T
4 while e is not the empty string
5 if there is a child m of n such that TEXT.sub.m is a
prefix of e
6 apply .DELTA..sub.m to P
7 remove the prefix TEXT.sub.m from e
8 n .rarw. m
9 else
10 (len, T, .DELTA.) .rarw. parseprefix(P, e)
11 create a new node m = (e.sub.0..len-1, T, .DELTA.)
12 make m a child of n
13 remove the prefix TEXT.sub.m from e
14 n .rarw. m
15 return n
______________________________________
The operation of the above exemplary implementation is as follows. First a given translation unit is macro-expanded, or preprocessed, and then a parser in the initial state is created. The function parse(t, T) then begins at the root of the prefix tree T and proceeds down the tree. At each node in the prefix tree, the function looks for a child whose text matches a prefix of the text e remaining in the translation unit. If there is such a child, the function moves to it, strips that prefix from the remaining text, and applies the parser delta to the parser. If there is no such child, the function parse(t, T) calls the function parseprefix(P, e) to parse a prefix of the remaining test. The function parse(t, T) then creates a prefix tree node with the information returned by the function parseprefix(P, e), makes it a child of the current node, and moves to that child. The function parse(t, T) is completed when there is no more text remaining in the translation unit. As mentioned above, a preferred embodiment of the present invention reads from disk or other secondary storage only those nodes of the prefix tree that must be examined, which in the function parse(t, T) occurs on line 5. In addition, the memory used to hold a node should generally be freed as soon as the function leaves that node on lines 8 and 14. In the above detailed implementation of parse(t, T), the entire translation unit generally must be expanded in memory. If it is not feasible to expand the entire translation unit in memory, the translation unit could be expanded into a file. Such an approach might increase the time spent by the function parse(t, T) in performing file input and output. Alternatively, the translation unit could be expanded in memory one piece at a time, in a manner well-known in the art. It should be noted that the above implementation of the parsing method returns the last node visited in the prefix tree. Given a node n in a prefix tree, the parse tree of the corresponding translation unit can be reconstituted, or reconstructed, using the following exemplary function:
______________________________________
reconstitute (n) is
R .rarw. root of an empty parse tree
while parent(n) .noteq.nil
for each level-one subtree t associated with n in
reverse order
make t the leftmost child of R
n .rarw. parent (n)
return R
______________________________________
The operation of the exemplary function reconstitute(n) is as follows. First a parse tree is created consisting only of a root node. Then beginning at a given node n the function proceeds up the parse tree. At each node, copies of the level-one subtrees associated with that node are retrieved, and then spliced into, or added to, the parse tree under construction. It is important to ensure that the level-one subtrees are spliced in the correct order. The complexity of the above exemplary processing steps parse(t, T) will now be analyzed. Running time will be considered first. The time required to preprocess a given translation unit is defined as O(L), where L is the number of characters in the macro-expanded translation unit, and the notation O() designates "on the order of" the quantity enclosed in the parentheses. The function parseprefix(P, e) runs in time O(len), where len is the first value in the triple (len, T, .DELTA.) returned by parseprefix(P, e). The time needed to apply parse delta .DELTA..sub.m to parser P is assumed to be proportional to the number of characters in TEXT.sub.m. A node m in a prefix tree is examined if the value of TEXT.sub.m is examined on line 5 of parse(t, T). X.sub.1 is defined as the number of nodes examined by the processing steps, and X.sub.2 as the maximum number of characters in any top-level source code statement contained in the translation unit being parsed or represented anywhere in the prefix tree. X.sub.3 is defined as the sum of all the values of len returned by calls to the function parseprefix(P, e). It should be noted that the modifications to the variable e in parse(t, T) can be implemented with constant-time index manipulations. If this is the case, the worst-case running time of parse(t, T) is O(L+X.sub.1 X.sub.2 +X.sub.3)=O(L+X.sub.1 X.sub.2). In practice, both X.sub.1 and X.sub.2 are typically bounded by a constant. Therefore, the running time of parse(t, T) may be expressed as O(L), or O(X.sub.3) not counting preprocessing time. This result is asymptotically optimal for a parsing method that always preprocesses the entire translation unit. The memory space required for storing parsing results will now be considered. The memory space needed to hold the prefix tree T and parser delta .DELTA. returned by parseprefix(P, e) are given by O(len), where len is the first value in the triple (len, T, .DELTA.) returned by parseprefix(P, e). If, immediately before lines 8 and 14 of parse(t, T), the memory space needed to hold the node pointed to by n is freed, then the space used by parse(t, T) in the worst case is O(L+X.sub.2). If file-based or one-piece-at-a-time macro expansion as explained above is also used, then the space used by parse(t, T) is O(X.sub.2), which for well-written code is generally the asymptotically optimal O(X.sub.3) . A stored prefix tree might be shared by many executions of the parse(t, T) and reconstitute(n) functions. In general, however, only one execution at a time should access the prefix tree. To prevent conflicts, the well-known technique of explicitly locking and unlocking the file containing the stored prefix tree may be used. Alternatively, the prefix tree could be stored in a database, thereby providing serialization of accesses without having to do explicit locking. More specifically, the code for parse(t, T) might be modified as follows:
______________________________________
parse(t,T) is
begin read-write transaction
// . . .
commit transaction
______________________________________
It should be noted that using a database may adversely affect the efficiency of the parsing method. In many databases, the memory used to hold a retrieved object cannot be freed until the current transaction is committed or aborted. Thus, in the function parse(t, T) the memory used to hold a node may not be freed as soon as the function leaves that node. One way to solve this problem is to commit and restart the transaction after examining every k nodes, for some constant k. There are several problems with this approach, however. First, it might be difficult to implement. Second, the resulting processing steps might be noticeably slower. Finally, the resulting processing steps serialize incorrectly--that is, it is possible for two overlapping executions e.sub.1 and e.sub.2 of parse(t, T) to have an effect that is different than the effect of executing e.sub.1 followed by e.sub.2 or e.sub.2 followed by e.sub.1. The performance results of an exemplary implementation of the present invention will now be described. The parsing method described in detail above was incorporated into a language processing system including an existing C++ parser running on a Sun IPX workstation. The existing parser produces ALF trees as described in the above-cited article by R. Murray. For comparison purposes, the parser was profiled and optimized with the prefix optimization of the present invention both turned off and turned on. The parser operated on a number of source code files which, when macro-expanded, produced translation units of varying sizes. Each source code file was first (1) parsed with the prefix analysis optimization turned off, then (2) parsed with the optimization turned on, and then (3) parsed again with the optimization turned on. FIG. 7 shows the performance results in the form of a plot of parse time as a function of translation unit size. The plot is intended to illustrate relative improvement in parse time, and therefore the vertical axis does not include specific time units. The translation unit size is specified in Kchar, or thousands of characters. It should be noted that the first time that a file is parsed with the prefix optimization of the present invention turned on, the parser is slower than with the optimization turned off. This behavior is as expected in that with the optimization turned on, the parser must spend extra time building and storing the prefix tree. The second time a file is parsed with the optimization turned on, however, the parse time is significantly less than that of either of the previous parses. The parser determines by using the stored prefix tree that none of the translation unit needs to be parsed again. In this example, for large translation units on the order of 470 Kchar, the first parse with the optimization turned on is about 15-18% slower than parsing with the optimization turned off, and the second parse with the optimization turned on is about 80-82% faster than parsing with the optimization turned off. FIG. 8 shows the performance results in the form of a plot of parse time as a function of common prefix length. The plot shows the effect on parse time if a change is made somewhere in the translation unit, and then the translation unit is parsed again with the optimization turned on. To generate this plot, a file that produced a large (470 Kchar) translation unit was chosen, one noncommentary change to the code was made in a file that was directly or indirectly included by the chosen file, and the chosen file was then reparsed. The plot of FIG. 8 shows the resulting parse time as a function of the distance, in thousands of characters, of the change from the beginning, or top, of the translation unit. This distance corresponds to the common prefix length. As in FIG. 7, the plot is intended to show relative improvement in parse time, and therefore no specific time units are shown on the vertical axis. Notice that the parse time varies with the common prefix length. This result is as expected in that the farther the change from the beginning of the translation unit, the less code the parser actually has to parse. In particular, if the change is made in the file specified to the parser, rather than one of the included files, reparsing is very fast. FIGS. 7 and 8 demonstrate that the parsing of the present invention can result in a substantial decrease in the time required to parse a given source code file. The present invention may be implemented as an apparatus which includes, for example, a preprocessor, means for identifying a previously-parsed prefix of a translation unit, and a parser in a parser state corresponding to the prefix. The means for identifying a prefix may be, for example, a computer or other digital data processor programmed to provide the above-described exemplary prefix identification operations. The apparatus may also include means for storing parsing results to be used for subsequent parsing. These means for storing may include, for example, the memory 26 or secondary storage 28 of FIG. 1. It should be understood that the above-described embodiments of the present invention are exemplary only. Many variations may be made in the arrangements shown, including, for example, the type of programming language, the type of parse trees or other structures generated by the parser, the manner of storing parse trees for previously-parsed prefixes, the application in which the parsing is used, and the hardware used to implement the parsing. These and other alternatives and variations will be readily apparent to those skilled in the art, and the present invention is therefore limited only by the appended claims.
|
Same subclass Same class Consider this |
||||||||||