<< Prev | - Up - | Next >> |
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.
%% 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
<< Prev | - Up - | Next >> |