Program Modules
The relations → and ⇒ are defined over the set of functions of a program.
• A → B means that the function A directly calls the function B;
• A ⇒ B means that the function A calls the function B (directly or indirectly).
In addition, it is known that:
• ifA→BthenA⇒B
• ifA⇒BandB⇒CthenA⇒C
A computer aided software engineering system is able to group the functions of a program into modules according to the following rules:
- IfA⇒BandB⇒AthenthefunctionsAandBaregroupedinthesamemodule. 2. Any two functions which do not satisfy (1) must be in different modules.
Write a program that is able to modularize a program according to the rules (1) and (2) given above.
Input
The program reads sets of data from a text file. Each set of data stands for a different program to be modularized and has the format:
(Fun1 Fun11 ...Fun1n1) (Fun2 Fun21 ...Fun2n2)...(Funm Funm1 ...Funmnm).
where F uni and F unij , i = 1, m, j = 1, nj , m, nj ≥ 0, are letters (case sensitive) designating names of functions. The meaning of the term (Funi Funi1 ... Funini), ni ≥ 0, is: Funi → Funij, j = 1,nj. The data set is ended by a dot. Spaces, tabs and line breaks are used freely in the input. Input data are correct, i.e. each data set contains exactly one term (F un F un1 . . . F unn ), for each F un of the program encoded by the data set, and Funi ̸= Funj for i ̸= j, i,j = 1,n.
Output
The result of the program is on standard output. For each data set the program lists the function names of each computed module, one module per line. The names of the functions of a module are listed in ascending lexicographic order and are separated by single spaces. The modules are listed ascendingly according to the lexicographic order of their first component (function name). The output for the data set is followed by an empty line.
Note: The example below shows an input file, which contains three data sets, and the corresponding output.
The first data set stands for an empty set of functions and the corresponding output is an empty line. For the second data set there are two singleton modules ‘a’ and ‘b’, whereas for the third data set there are three modules ‘a b e’, ‘c’ and ‘d’.
2/2 Sample Input
.
(a a) (a b) (b).
(a b c) (b a e) (c d)
(d d) (e b).
Sample Output
a b
abe c
d