Deriving path expressions recursively

Program representation plays an important role in software engineering, because it is used by the tools supporting software life cycle activities. To represent a program's control structure, the donünator tree and the implied tree, derived from the program's ddgraph, can be profitably used. In fact, thanks to their recursive structure, these trees are especially statable for designing very simple and efficient algorithms for program path analysis, which is widely used in measurement and testing activities. In particular, this paper presents a recursive algorithm PE for computing path expressions from the dominator and the implied trees. The algorithm proposed is of interest to program comprehension for two reasons: representation of programs by path expressions is widely applied, e.g., to testing, data flow analysis and development of complexity metrics. More in general, an algorithm as PE, which computes path expressions from flowgraphs, can be used to solve many lands of path problems.