Pseudocode for the checker algorithm

Notation: x U= y means: x = x union y

Input: Grammar in normal form.

states = {};
worklist = terminals;
while worklist != {} do
  w = head(worklist);
  worklist = tail(worklist);
  s = compute_state(w);
  if !(s in states) then
    check(s);
    states U= {s};
    for op in unaries do
      worklist U= {op(s)};
    for op,s1 in binaries x states do
      worklist U= {op(s,s1),op(s1,s)}; //note: op(s,s) twice
    //cater for ternary ops if you allow them
//where to use representers instead of full-blown states?

// for binary operator, analogous for other arities
State compute_state(op(left, right)) // operator and child states
                                               // (one for each operand) */
{
  // create representer states to cut away irrelevant information
  rleft  = project(op,left);
  rright = project(op, right);
  op_nts = {nt|nt can derive op(_,_)};
  State.Itemsets = {};
  for paying_nts in powerset(op_nts) do
    for l in rleft.itemsets do
      for r in rright.itemsets do
	for nt in op_nts
          items[nt].cost=inf;
          items[nt].rules={};
        for all rules p with operator op do
          p is of form <nt: op(ntl, ntr), cost>
	  children_cost = l[ntl].cost+r[ntr].cost;
          if nt in paying_nts then
            items[nt]=update_item(items[nt],cost+children_cost,p);
          else if children_cost=0 then
            // something else is paying for the nt and its children
            items[nt]=update_item(items[nt],0,p);
      	repeat
      	  for all chain rules p
      	    p is of form <nt: nt1, cost>
      	    if nt in paying_nts then
      	      items[nt]=update_item(items[nt],cost+items[nt1].cost,p);
            else if items[nt1].cost=0
      	      items[nt]=update_item(items[nt],0,p);
	while some item changed in the last iteration;
	itemsets[paying_nts,l,r] = items.
  // Ignored the following:
  // The paper says: However, if a rule is not among the optimal
  // rules for any partial-cost itemsets where the cost of the
  // rule counts, it is not used for producing a zero-cost item,
  // either (this avoids some spurious errors and warnings when
  // checking).
	items = normalize_items(items);
        itemset.fullcost = (paying_nts=op_nts) and l.fullcost and r.fullcost;
	State.Itemsets U= {itemset};
  return State;
}

// compute representer states.
// see Function Project of TOPLAS 1995, p. 470
State project_state(Operator op, State s)
{
  ps.Itemsets = {};
  for i in State.Itemsets do
    ps.Itemsets U= {project_itemset(op,i)};
  return ps;
}

Itemset project_itemset(Operator op, Itemset i)
{
  pi = {};
  for n in nonterminals do
    if there is a rule <m: op(...,n,...)> then
      pi.items[n].cost = i.items[n].cost;
  normalize_items(pi.items);
  pi.fullcost = i.fullcost;
  return pState;
}

// normalize cost; delta+something is represented as
// 1+something, so all the checks above work nicely.
Item[] normalize_items(Item items[])
{
  mincost = min(items[*].cost);
  if mincost>0
    for i in items do
      i.cost -= mincost-1;
  return items;
}

Item update_item(Item item,Cost cost,Rule p)
{
  if cost<item.cost then
    item.cost=cost;
    item.rules={p};
  else if cost=item.cost then
    item.rules U= {p};
  return item;
}

check(State s)
{
  for n in nonterminals do
    if intersection(s.itemsets[*].items[n].rules) = {} then
      error "no optimal rule for "n" in "s;
    for r in s.itemsets.items[n].rules do
      if fullcost_itemset(s).items[n] is not subset of r then
        warning "not all tree-optimal rules are DAG-optimal for "n" in "s;
}