20.1 Progress report traverser

A progress report traverser is

• a linked list of the Earley items in a Earley set, in which
• one node is distinguished as the current node of the traverser.

The linked list has two sentinel nodes, one at the start of the linked list, and one at the end of the linked list. The two sentinel nodes do not correspond to Earley items so that, where n is the size of the Earley set, the linked list of its traverser contains n+2 nodes.

The sentinel node at the start of the linked list is called the start sentinel node or start sentinel. In a traverser for a non-empty Earley set, the start sentinel comes before the first Earley item. The sentinel node at the end of the linked list is called the end sentinel node or end sentinel. In a traverser for a non-empty Earley set, the end sentinel comes after the last Earley item.