5.4.2 Building Parse Trees

Our recognizer only returns a list of recognized categories. It would be nicer if it returned a list of parse trees. We will represent a parse tree as a record whose label is the recognized category. For example, the parse tree for [the man] can be represented by:

np(det(the) n(man))

and for [john sees the man] by:

s(np(pn(john)) vp(vt(sees) np(det(the) n(man))))

In order to apply rule np -> det n to the sequence of trees [det(the) n(man)], it is necessary to modify IsPrefix to check the labels of the trees against the categories of the rule's body (exercise). It is also necessary to modify Infer to replace the matched subsequence by a new parse tree instead of just by the recognized category:

proc {Infer Prefix Suffix Rule}
   %% does the rule apply here?
   if {IsPrefix Rule.subcat Suffix} then Args Rest Tree in 
      {List.takeDrop Suffix {Length Rule.subcat} Args Rest}
      %% assemble new parse tree
      Tree={List.toTuple Rule.cat Args}
      %% add the conclusion to the agenda
      {Agenda.push {Append {Reverse Prefix} Tree|Rest}}
   end 
   %% rewritings for the rest of the sequence
   case Suffix
   of nil then skip 
   [] H|then {Infer H|Prefix T Rule}
   end 
end

The library procedure List.takeDrop combines the functionality of List.take and List.drop:

{List.takeDrop L N PREFIX SUFFIX}

binds PREFIX to the list of the N first elements of L and SUFFIX to the rest of L. A parser that avoids redundant derivations and produces parse trees will return the following two trees for [john sees the man with the telescope], thus properly accounting for PP attachment ambiguity:

[s(np(pn(john))  
   vp(vt(sees)  
      np(np(det(the) n(man))  
         pp(prep(with) np(det(the) n(telescope))))))  
 s(np(pn(john))  
   vp(vp(vt(sees) np(det(the) n(man)))  
      pp(prep(with) np(det(the) n(telescope)))))]


Denys Duchier, Claire Gardent and Joachim Niehren
Version 1.3.99 (20050412)