Next: Formula Straightening
Up: Formula Processor Details
Previous: The ``Nothing Inside'' Test
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
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.