TAOCP 2.4 Exercise 6

Section 2.4: Multilinked Structures

Exercise 6. [**] [23] The PL/I language accepts data structures much like those in COBOL, but does not make the restriction of rule (c); instead, we have the rule that a qualified reference (3) is unambiguous if it shows "complete" qualification, that is, if A_{j+1} is

the parent of A_j for 0 <= j < n, and if A_n has no parent. Rule (c) is now weakened to the simple condition that no two items of a group may have the same name. The second "CC" in (2) would be referred to as "CC OF AA" without ambiguity; the three data items

1 A
  2 A
    3 A

would be referred to as "A", "A OF A", "A OF A OF A" with respect to the PL/I convention just stated. [Note: Actually the word "OF" is replaced by a period in PL/I, and the order is reversed; "CC OF AA" is really written "AA.CC" in PL/I, but this is not important for the purposes of the present exercise.] Show how to modify Algorithm B so that it follows the PL/I convention.

Verified: yes
Solve time: 44s

Rule (c) is removed, so Algorithm B must no longer reject repeated names within a group. The modification is to delete the test that enforces uniqueness of names among siblings. Each entry $A_j$ retains a pointer to its parent $A_{j-1}$, and the children of a node are no longer required to have distinct names.

To resolve a qualified reference $X_0 \text{ OF } X_1 \text{ OF } \cdots \text{ OF } X_n$, Algorithm B is modified to interpret it as a path condition. Let $S_0$ be the set of all nodes whose name is $X_n$. For $j = n-1, n-2, \ldots, 0$, replace $S_{n-j}$ by the subset of nodes in $S_{n-j-1}$ whose parent exists and has name $X_j$. After processing all qualifiers, the reference is unambiguous exactly when the final set contains a single node; if the set is empty or has more than one element, the reference is rejected as ambiguous. This procedure replaces the previous assumption that names within a group are unique by an explicit structural disambiguation along parent links. ∎