Modified Grammars

 One technique is to take an existing one dimensional grammar that parses 1D strings, and modify it so that it incorporates checks of the geometric relationships between symbols. This technique is only applicable to online input as time is used to order the symbols before parsing. This is the approach used by Littin .

Littin uses a SLR(1) parsing technique, with additional tests for checking the geometric relationship between tokens. He does this by first building a SLR(1) parser then extending it where necessary to include these geometric tests.

To enable the use of this modified SLR(1) parser, the input has to be ordered correctly: the user has to enter the symbols for a formulae in a predefined order. For example,

$$\frac{a+b}{c-d}$$

has to be entered in the order a, +, b, -- , c, -, d. For some formulae there are a number of possible orders, but this only occurs when a symbol has both a subscript and superscript. The user is then able to decide whether to write the subscript or superscript first. Editing of the formula during and after entry is limited to the deletion or alteration of the most recently written symbol.

Permitting the user to enter symbols in an arbitrary order would mean that this type of grammar could not be used. He justifies this restriction through the fact that people tend to enter formulae in a fairly standard order, which he informally verified by observing several people writing a number of formulae. Although this assumption is reasonable, if users want to be able to go back later and edit their formulae, they are unable to. Littin has created a formula entry system, rather than a formula editing system.

The modification to the SLR(1) grammar adds geometric tests which check that the symbols are in the correct locations. Tolerance for the sloppiness of handwritten input is implemented by putting a threshold on the distance symbols can appear from their expected locations.

One major advantage of SLR(1) parsing is its time and space efficiency. Littin shows the computational complexity of his system to be O(g), where g is the number of symbols in the input formula.

.

Littin uses a SLR(1) parsing technique, with additional tests for checking the geometric relationship between tokens. He does this by first building a SLR(1) parser then extending it where necessary to include these geometric tests.

To enable the use of this modified SLR(1) parser, the input has to be ordered correctly: the user has to enter the symbols for a formulae in a predefined order. For example,

$$\frac{a+b}{c-d}$$

has to be entered in the order a, +, b, -- , c, -, d. For some formulae there are a number of possible orders, but this only occurs when a symbol has both a subscript and superscript. The user is then able to decide whether to write the subscript or superscript first. Editing of the formula during and after entry is limited to the deletion or alteration of the most recently written symbol.

Permitting the user to enter symbols in an arbitrary order would mean that this type of grammar could not be used. He justifies this restriction through the fact that people tend to enter formulae in a fairly standard order, which he informally verified by observing several people writing a number of formulae. Although this assumption is reasonable, if users want to be able to go back later and edit their formulae, they are unable to. Littin has created a formula entry system, rather than a formula editing system.

The modification to the SLR(1) grammar adds geometric tests which check that the symbols are in the correct locations. Tolerance for the sloppiness of handwritten input is implemented by putting a threshold on the distance symbols can appear from their expected locations.

One major advantage of SLR(1) parsing is its time and space efficiency. Littin shows the computational complexity of his system to be O(g), where g is the number of symbols in the input formula.