Parser Implementation

The graph rewriting parser uses two main data structures: a labelled directed graph and a priority queue. A graph is represented within the system using:

• an adjacency matrix, that allows for quick adjacency tests.

• a collection of nodes, each having a number of attributes that store the identity of the node, its lexical class, and the position of its bounding box on the input area.

• a collection of arcs which store, in addition to which nodes they link, information about geometric relationship between these nodes.

The priority queue is implemented as a doubly linked list, the items in the list ordered by their score. Each item in the queue holds a copy of the formula graph, along with additional information about the state of the formula processing at that point.