Browse Prior Art Database

Tool to Measure the Size of Program Change Disclosure Number: IPCOM000174496D
Original Publication Date: 2008-Sep-10
Included in the Prior Art Database: 2008-Sep-10
Document File: 2 page(s) / 28K

Publishing Venue



To accurately size a software project, one requires a method for measuring the complexity (usually understood in terms of "size") of the software project. For making modifications in existing software, one requires a way to measure the complexity of the modification. It is typical for developers to estimate the time required for a new project based on the time required for previous projects of similar complexity. To measure change, developers often use "lines of code," but this is known to be an inaccurate measure and the number of lines of code are not directly related to program complexity. An additional benefit of measuring program complexity is that one can make estimates of the amount of testing required for a software change. For simple changes, less testing is required. For more complex changes, more testing is required. Abstract Syntax Trees (AST) are commonly used in text formatters, parsers, compilers, and detecting plagiarism. This article discusses a method for measuring the size of a program by using it's AST representation.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 55% of the total text.

Page 1 of 2

Tool to Measure the Size of Program Change

Roughly, the procedure to compare two ASTs works in a top-down fashion by comparing first the root of each tree and then the subtrees. Also, during the comparison the invention constructs correspondence between the symbol tables for the two trees. The end result is that invention shows the total size complexity of the difference between the two programs, in terms of actual logic and not merely lines of code. The process is insensitive to comments, formatting changes, and other non-logical changes to the source code file.

The algorithm has a recursive step which is:





1, AST


Here AST

_1 and AST

_2 are the 2 syntax trees that will be compared.

The argument "SCT" is the "symbol correspondence table," which is a list of pairs. The first element from each pair is a symbol from AST

_1, and the second is the

corresponding symbol from AST



_STEP proceeds by comparing the

root node of AST

_1 and AST

_2. If the root nodes are equal, then the result of



STEP(SCT, left


1), left


1)) +



_STEP(SCT, right



_1), right(subtree(AST



If the root nodes are not equal and both root nodes are not symbols, then the result of RECURSIVE

_STEP is one more than the above quantity.

If the root notes are both symbols (even if they are equal) then check SCT to see if there is a correspondence between the two symbols. If there is not (and if neither symbol is in the list of pairs already), then add it, so that from now on consider both of these symbols to be "the same." This prevents confusion based on variable names, rather than actual program structure.

The entire algorithm is:



_set, AST1, AST2), where AST1 and AST2 are the abs...