Marking a Derivation Tree

Given a derivation tree t of a generated sentence s, we can mark the places where the ambiguity occurs as follows. If s is ambiguous it can be parsed in several ways, giving rise to a set of derivation trees . We now compare t with the set of trees T in a top-down fashion. If for a given node label in t there are several possible labels at the corresponding nodes in T then we have found an ambiguous spot, and the corresponding node in t is marked.

Thus, in the previous example of structural ambiguity we may first generate sentence (25) above. After checking whether this sentence is ambiguous we obtain, as a result, the marked derivation tree of that sentence. A marked node in such a tree relates to an ambiguity. The relevant part of the resulting derivation tree of the example above may be the tree in figure 5.7.

 
Figure 5.7:  Marked derivation tree

We will define a procedure MARK that marks the generated tree given the trees found by the parser. Marking a node will be done by adding the feature MARKED with value YES in addition to features and . If a node has been marked then scanning of its subtree will stop, i.e., the nodes of a subtree with a marked root will not be marked. Thus, the definition of the procedure MARK is as follows:

mark(t(L,Ds,n),Set):-
    root_same(L,Set),!,
    get_ds(Set,DsSet),
    mark_ds(Ds,DsSet).
mark(t(L,Ds,y),Set).

root_same(L,[]).
root_same(L,[t(L,_,_)|T]):-
    root_same(L,T).

mark_ds([],[]).
mark_ds([H|T],[Hs|Ts]):-
    mark(H,Hs), mark_ds(T,Ts).

get_ds([t(_,[],_)|_],[]).
get_ds(Set,[H|T]):-
    get_f(Set,Set2,H),
    get_ds(Set2,T).

get_f([],[],[]).
get_f([t(_,[H3|B],_)|T],
      [t(_,B,_)|T2],[H3|T3]):-
    get_f(T,T2,T3).

mark(Tree, TreeSet):
 if root_same(label(Tree),TreeSet)
   then mark_ds(dtrs(Tree),get_ds(TreeSet))
   else
    return mark_node(Tree).

root_same(Label,TreeSet):
 if empty(TreeSet)
   then return true
  else
   if equal(Label,label(first(TreeSet)))
    then root_same(Label,rest(TreeSet))
     else return false.

We first compare the rule names of each root node of trees in the set of parsed trees TreeSet with the rule name of the root node of the generated tree Tree, using the function ROOT_SAME. If all are the same (i.e., the same rule has been applied during generation and parsing), we conclude that no ambiguity has occurred at that level so we scan the next level of the trees in parallel, using the function MARK_DS, where the function call DTRS(TREE) just returns the daughter trees of Tree, and the call GET_DS(TREESET) returns a list containing all daughter trees of all trees in TreeSet preserving the relative order. More precisely, we return a list of lists where the i-th list contains the i-th daughter of each tree in TreeSet. Within the function MARK_DS the function MARK is called recursively on each daughter tree of Tree.

If, however, the root nodes are not equal, we return the Tree after having marked the root node of Tree using the function MARK_NODE. This function destructively adds the feature MARKED with value YES.