Foundations of Software Testing: Fundamental Algorithms and Techniques

Test Generation

xy

p call

=

param

param function

foo

(a)

Start

1

2

3

f

t

End

(c)

Start

1

2

3

t

f

End

(b)

foo foo

’

Fig. 5.7 Syntax trees with identical function call nodes but different function CFGs.

(a) Syntax tree for nodes

n

and

n

1

, respectively in

G

and

G



.(b) CFG for foo

in P. (c) CFG for foo’ in

P



.

down recursively identifying corresponding nodes that differ in P and

P



. Only tests that traverse such nodes are selected.

While traversing the CFGs, two nodes n ∈ N and n



∈ N



are consid-

ered equivalent if the corresponding syntax trees are identical. Two syn-

tax trees are considered identical when their roots have the same labels

and the same corresponding descendants (see