5.1 Visually Notated Context-Free Grammars

A context-free grammar is a 4-tuple consisting of a terminal vocabulary, a non-termininal vocabulary, a start symbol, and a set of productions (or rules). The terminal vocabulary is the set of all simple (atomic) visual objects that might be found in an expression to be parsed, and the non-terminal vocabulary is the set of symbols used to represent combinations of terminals and non-terminals. The start symbol is the non-terminal which is the name of the topmost entity being parsed (for instance, ``S'' for sentence). A production has a non-terminal on the left hand side, and a combination of terminals and non-terminals on the right hand side.

The first three parts of a context-free grammar have been implicitly expressed in the visual representation of the productions, which we call the Visual Grammar Notation. Thus in the grammar for bar charts (Figure 5), the start-symbol is the symbol on the left hand side of the topmost rule, i.e., *bar-chart*. Terminals are visual literals appearing only on the right hand side, such as the bar and the horizontal line. Non-terminals are symbols that appear on the left hand side of rules, such as *bar-chart* and *bar-list*.

5.2 A Spatial Parser Which Uses Visual Grammars

The function spatial-parse takes two inputs: a region of space and a visual grammar. It then tries to parse whatever objects are in the region using the grammar. As used by spatial-parse, the rules or productions in a visual grammar are visual in two ways: first they are `about' visual matters; and second they are themselves spatial objects whose spatiality is integral to their functioning as rules.

Each rule is a spatial template, showing the parser where to search spatially for the members of the expression (i.e., where members should be according to that production). In addition, the rule shows what kind of object is acceptable at a location. This can be by example, as with the bar chart bar literal in Figure 5. Testing for acceptable literals can also be by pattern matcher-like predication (textlinep and ?). And finally, each rule expresses the target tree structure to be returned in the parse for its kind of expression.

When a spatial rule is applied to a region of space, either a visual object is returned or the parse fails. In the case of success, the visual object is a copy of the objects in the region put into a pattern with its members in the proper tree structure (as described by the grammar). In the case of failure, the parser gives up unless there are any other rules of the same name as yet untried in the grammar, in which case it tries the next one in top-down order.* Having two rules with the same name permits termination of recursion, an important feature of context-free grammars. For example, because the second rule in the bar chart grammar defines the non-terminal *bar-list* recursively, the grammar can handle bar charts with an arbitrary number of bars. The recursive rule keeps succeeding until there is just one bar left, in which case it fails and the simple rule is tried, which succeeds and terminates the parsing of the *bar-list*.

*Because the parser calls itself recursively, even if the invocation of a rule finally fails many levels down, control will return back to the originating level where any other rules of the same name will be tried.