9.2.5 Processing an edge

Finally, the main processing step, the processing of an edge taken out of the agenda. As discussed in the introduction, processing an edge consists in producing all edges resulting from:

• The successful application of some unary rule to the category labelling this edge,

• The successful application of some binary rule to the category labelling this edge followed by the category of some right adjacent edge.

• The recursive combination of the edges resulting from the previous step with their right-adjacent constituents.

This is what the procedure ProcessEdge does. It proceeds as follows. First, all edges resulting from the application of a unary rule to Edge are added to the agenda ProcessUnary. Second, right-adjacent edges are collected into a list and binary rules are tried out: each right-adjacent edge is tried for reduction with the edge being processed and in case of success, the resulting edge is added to the agenda.

<procedure Process>=

%% Match tests whether there exists a list of subsequent
%% edges [Edge E2 ... En] with categories matching those
%% in Rule.right.  
%% If so, Match adds a new edge that starts at Begin, ends
%% at En.'end' and has category Rule.left.
proc{Match Edge Rule Begin}
   Cat = Edge.cat
in 
   case Rule.right
   of nil then 
      raise error('right hand sides of rules must be nonemty') end 
   [] [!Cat] then 
      {Agenda.push {MakeEdge Rule.left Begin Edge.'end'}}
   [] !Cat|NextCats then 
      NextRule = unit(left:Rule.left right:NextCats)
   in 
      for NextEdge in {Chart.get Edge.'end'} do 
         {Match NextEdge NextRule Begin}
      end 
   else skip %% rule does not apply
   end 
end 
 
%% Process adds all Edges to the Agenda
%% that start with the edge Edge
proc{Process Edge}
   for Rule in Rules do 
      {Match Edge Rule Edge.begin}
   end 
end