Mihai Ciocoiu, Ştefan Bruda * GULiveR: Generalized Unification Based LR Parser for Natural Languages

algorithm recognizer(sentence, grammar) is
	initialize current-stack, next-stack;
	while next-stack is not empty do
		current-stack = next-stack;
		next-stack = empty;
		do all reduce actions from current-stack;
		if there are no more tokens to parse then
		   do all accept actions from current-stack;
		else
		   lexically analyze the current token;
		   do all shift actions from current-stack;
		end if;
	end while;
end algorithm;

algorithm shift(state, shift-head) is
	if state has reduce actions then
	   look into reduce-stack of next-stack for a top labeled 
    with state;
	else
	   look into shift-stack of next-stack for a top labeled 
           with state;
	end if;
	if a node was found then
	   link it with shift-head;
	else
	   construct a new leaf in next-stack corresponding 
	   to a shift action from shift-head to state;
	end if;
end algorithm;

Due to the difference between the nodes labeled with states and those corresponding to categories, and due to the fact that packing can occur at both kinds of nodes, splitting the reduction action in two algorithms has proven useful.

algorithm pass-over-state(rhs, state-top-branch = (state . structure-top-branches)) is
	if rhs then
	     if state is a packed node then
		  for each branch struct-top-branch in struct-top-branches do
		           pass-over-structure(rhs, structure-top-branch);
		  end for;
	     else
		  pass-over-structure(rhs, structure-top-branches);
	     end if;
	else
	     construct in current-stack the structure resulting from the reduce;
	end if;
end algorithm;

algorithm pass-over-structure(rhs, structure-top-branches = (structure . state-top-branches)) is
	rhs = (rest rhs);
	if structure is a packed node then
		for each branch state-top-branch in state-top-branches do
			 pass-over-state(rhs, state-top-branch);
		end for;
	else
		pass-over-state(rhs, state-top-branches);
	end if;
end algorithm;

algorithm reduce(reduce-head, rule-code) is
	rhs = the right member of rule-code production;
	pass-over-state(rhs, reduce-head);
end algorithm;

97