5.  Language Theory

      The basic structure of the language is not a particularly original one. Equations are pictured as a set of ``boxes,'' pieced together in various ways. For example, something with a subscript is just a box followed by another box moved downward and shrunk by an appropriate amount. A fraction is just a box centered above another box, at the right altitude, with a line of correct length drawn between them.

      The grammar for the language is shown below. For purposes of exposition, we have collapsed some productions. In the original grammar, there are about 70 productions, but many of these are simple ones used only to guarantee that some keyword is recognized early enough in the parsing process. Symbols in capital letters are terminal symbols; lower case symbols are non-terminals, i.e., syntactic categories. The vertical bar | indicates an alternative; the brackets [ ] indicate optional material. A TEXT is a string of non-blank characters or any string inside double quotes; the other terminal symbols represent literal occurrences of the corresponding keyword.

eqn : box | eqn box
box : text | { eqn } | box OVER box | SQRT box | box SUB box | box SUP box | [ L | C | R ]PILE { list } | LEFT text eqn [ RIGHT text ] | box [ FROM box ] [ TO box ] | SIZE text box | [ROMAN | BOLD | ITALIC] box | box [HAT | BAR | DOT | DOTDOT | TILDE] | DEFINE text text
list : eqn | list ABOVE eqn
text : TEXT

      The grammar makes it obvious why there are few exceptions. For example, the observation that something can be replaced by a more complicated something in braces is implicit in the productions:

eqn : box | eqn box box : text | { eqn }

      Clearly, our grammar is highly ambiguous. What, for instance, do we do with the input

a over b over c ?

{a over b} over c

a over {b over c} ?

      To answer questions like this, the grammar is supplemented with a small set of rules that describe the precedence and associativity of operators. In particular, we specify (more or less arbitrarily) that over associates to the left, so the first alternative above is the one chosen. On the other hand, sub and sup bind to the right, because this is closer to standard mathematical practice. That is, we assume is , not .

      The precedence rules resolve the ambiguity in a construction like

a sup 2 over b

      Naturally, a user can always force a particular parsing by placing braces around expressions.

      The ambiguous grammar approach seems to be quite useful. The grammar we use is small enough to be easily understood, for it contains none of the productions that would be normally used for resolving ambiguity. Instead the supplemental information about precedence and associativity (also small enough to be understood) provides the compiler-compiler with the information it needs to make a fast, deterministic parser for the specific language we want. When the language is supplemented by the disambiguating rules, it is in fact LR(1) and thus easy to parse[5].

      The output code is generated as the input is scanned. Any time a production of the grammar is recognized, (potentially) some TROFF commands are output. For example, when the lexical analyzer reports that it has found a TEXT (i.e., a string of contiguous characters), we have recognized the production:

text : TEXT

      As another example, the translation associated with the production

box : box OVER box

Width of output box = slightly more than largest input width Height of output box = slightly more than sum of input heights Base of output box = slightly more than height of bottom input box String describing output box = move down; move right enough to center bottom box; draw bottom box (i.e., copy string for bottom box); move up; move left enough to center top box; draw top box (i.e., copy string for top box); move down and left; draw line full width; return to proper base line.

      With a grammar, it is usually clear how to extend the language. For instance, one of our users suggested a TENSOR operator, to make constructions like

Grammatically, this is easy: it is sufficient to add a production like

box : TENSOR { list }