We will examine how parsing proceeds for a grammar that only describes the y-axis line and its tick marks and does so in a very simple way. When a grammar is entered into the system, a Lisp defgrammar macro expands the form into one that includes an additional defrule macro, applied to each rule structure. When the defrule forms expand, they define the CLOS classes for each non-terminal as well as the goal predicates for the search and the generator functions needed. These macros act as the parser generators. Once they have been applied, the parsing process then acts as a top-down tree-search.

**A simple grammar with three rules:**

;;; ****************** < X-Ticks > *************** ( Y-Ticks -> Ticks Y-Line (Y-Line) (Ticks (touch Y-Line '?) :constraints (> (size Ticks) 2))) ;;; ****************** < X-Line > *************** ( Y-Line -> Line (:constraints (vertp Line) (long Line))) ;;; ****************** < Ticks > *************** ( Ticks -> Set(Line) (:element-constraints (horizp Line) (short Line)))

The parse is assumed to be started at the top node, Y-Ticks. Parsing proceeds by a depth-first search to discover and build elements that satisfy the various geometric constraints. The order of the search is dictated by the order of the constituents in the body of the rule (not in the order of the constituents in the "->" production).

- In the Y-Ticks rule, the Y-Line constituent is searched for first.
There are no specific restrictions on the Y-Line search included
in this Y-Ticks rule.

- In the Y-Line rule the Line primitive is the only constituent,
and it must obey the constraints that it be vertical and long.

- Returning to the Y-Ticks rule, Ticks are searched for next. The
expression "
`(touch Y-Line '?)`" is a*context generator*. The set of all elements in the diagram that obey this constraint is created and the Ticks constituent rule is then entered with this context restriction -- Ticks members can only be chosen from the set of elements in the diagram that touch the long vertical line found by the Y-Line rule. The context is propagated to a constituent rule as an*inherited attribute*.

- The Ticks rule is then entered. Ticks is a
*set*of Line primitives. The elements of the set are chosen from the context inherited from the Y-Ticks rule, as explained in step 3. The elements of this set are further filtered by constraining every one of them to be both*short*and*horizontal*. Any subset of the y tick marks would satisfy this rule. But our algorithm attempts to choose the*maximal*set of elements that satisfy the rule. In this way, a single rule can return twenty tick marks or a hundred data points in one step. In the Y-Ticks rule, an acceptable set of ticks must have greater than 2 members, the constraint "`:constraints (> (size Ticks) 2))`".

Our grammars, because of the way they are designed and operate,
are called *Context-based Constraint Grammars*. It is essentially an Attributed Multiset Grammar, but its use
of *context* is new. A rule inherits a context specified in its parent that
restricts the set of items within which the rule is allowed to
search for a solution. This successive narrowing of the search
set helps to make the parsing process more efficient. Parsing
generates a set of all distinct solutions that satisfy the constraints.
In the example above, the set is a singleton. In addition, the
same element can be reused or *shared* by various parts of a single solution, see the discussion of sharing.

When the parse is complete we can highlight the elements in the
Diagram Viewer that make up the Y-Ticks structure, as shown on
the right. Note that this simple grammar also identifies the top
and bottom sides of a data point as tick marks. This is avoided
in our more complex grammars by requiring that a tick mark not be a line that participates in a polygon. |

Next: Parsing runs with timing |

Back to Index page |