Method and apparatus for an equation editor
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The invention relates to computerized wordprocessing technology and specifically, to a process and apparatus carried out on a digital computer for creating and editing mathematical equations in printed documents. 
     &#34;Wordprocessing&#34; involves the use of a digital computer to manipulate printed characters in creating and editing documents. Such documents can be displayed electronically on a computer display screen or printed on hardcopy. This patent application was created using a wordprocessing program (&#34;wordprocessor&#34;). Manipulation of data in the form of printed characters is, indeed, a fundamental tool for human interaction with computers. Input devices such as keyboards provide the mechanism for feeding information to the computer, while output devices, such as video display terminals and printers, provide the mechanisms for viewing the results. Wordprocessors are a fundamental and vital tool of modern business. 
     Wordprocessors range in functionality from simple &#34;text editors,&#34; which do no more than reproduce on the display screen the user&#39;s keyboard input, to sophisticated &#34;desktop publishers,&#34; which enable the user to create, display, and print sophisticated, publication quality documents. An &#34;equation editor&#34; is a method implemented in software that is used to create and edit mathematical equations and which may be a component of a wordprocessor. Mathematicians, economists, businesspersons, and others who frequently utilize mathematical equations often need to incorporate those equations into printed documents such as reports, articles, and other papers. Incorporating complex mathematical equations into standard textual documents for printing has long been a difficult or even impossible undertaking. Because equations contain many non-standard characters and because those characters are often formatted in a complex manner, they are far more difficult to create and print than standard text. 
     The ability to create and manipulate equations in documents with an equation editor is partially constrained by the keyboard. Standard computer keyboards contain a character set including the letters &#34;a&#34; through &#34;z&#34;, numbers &#34;0&#34; through &#34;9&#34;, various commonly used characters such as commas, periods, semicolons, and apostrophes, cursor control keys such as &#34;Page Up&#34;, &#34;Page Down&#34;, and arrow keys, and ten or twelve special function keys. Standard computer keyboards do not contain many unique characters or symbols frequently used in mathematical equations. Therefore, unlike ordinary text, equations cannot be typed directly into documents using only keyboard characters. For example, while a simple equation such as can be created directly from keyboard characters, a more complex equation such as ##EQU1## cannot be created directly from keyboard characters. Thus, the incorporation of equations into documents created with a wordprocessor requires the use of at least two components: (1) a form of textual description of equations and (2) a &#34;formatter&#34; to translate the textual description into the actual printed form of the equation. For example, even a simple equation such as ##EQU2## cannot be typed directly from the keyboard and therefore must be created using a textual description such as &#34;a OVER b&#34; which can be translated and printed in its equation form. An equation such as ##EQU3## can be created using a textual description such as &#34;FUNC f&#39;(x)=lim--(h→0) {(FUNC f(x+h)-FUNC f(x)}OVER h}&#34;. 
     A sophisticated equation editor also automatically formats equations, performing such tasks as automatic sizing of equation elements such as the root sign or the horizontal separator for division, and the vertical extension of &#34;delimiters&#34; (growing parentheses, brackets) around the sub-equations they enclose. For example, in the equations ##EQU4## the equation editor adjusts the size of the square root sign and the parentheses to fit the equation inside. By automatically performing these awkward and time-consuming tasks, the equation editor frees the user to perform other less tedious tasks. 
     2. Brief Description of Prior Art 
     Prior art equation editors, such as TeX, Microsoft Word for the Apple MacIntosh computer and for the Microsoft Windows environment, Lotus Manuscript and EQN for Unix systems all include a method for describing equations textually and an equation formatter for translating the textual description into the printed form of the equation. However, prior art equation editors provide neither an editing methodology which allows the efficiency and flexibility of the present invention in creating textual descriptions of equations nor a window in the same display interface to display the final printed form of the equation at the same time as its textual description is being edited. The present invention uniquely combines multiple equation editing components into a single user interface, including an editing window for manipulating the textual description of an equation, a display window for viewing the printed form of the equation, and a palette window for selecting characters and commands used in describing the equation. 
     SUMMARY OF THE INVENTION 
     A method and apparatus carried out on a digital computer for creating and editing mathematical equations in a printed document is disclosed. This invention allows the user of a wordprocessor to create and edit mathematical equations in an efficient and flexible manner through use of a user interface which includes an editing window, a display window, and a palette window. The editing window allows the user to input a textual description of the equation, the palette window provides an alternative method of entering the textual description of the equation by displaying the characters and commands that may be used, and the display window displays the equation as it appears in its final printed form. 
     This invention also provides several methods for creating the textual description of the equation including direct textual input of keyboard characters, pre-defined key sequences for extended characters (non-ASCII characters), commands for printing and formatting unique mathematical symbols, and selection of input from the palette window. 
     Finally, this invention enables the user to view an equation in the display window from 25% to 1000% of its actual printed size and to easily move the entire equation to different locations in the document. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 provides an overview of the equation editor system. 
     FIG. 2 is the multi-window equation editor user interface. 
    
    
     DESCRIPTION OF AN ILLUSTRATIVE EMBODIMENT 
     While this invention can be carried out on most digital computers, this description is confined to implementation on an IBM PC or compatible computer which uses a microprocessor in the Intel 8086/8088 family of microprocessors (e.g., 80286, 80386) and the DOS operating system. Also, while the invention can be implemented independently as a separate computer program, the preferred embodiment is implemented as a component of a wordprocessor. 
     Equations are created in a document by using a combination of characters, mathematical symbols, and commands. Commands are entered into the textual description of an equation in order to generate equation structures and mathematical symbols that cannot be generated directly by the keyboard. For example, the command &#34;SQRT&#34; is used in the textual description &#34;SQRT x&#34; to generate the square root symbol ##EQU5## and the commands SUM, FROM, TO, INF, and SUP are used in the textual description &#34;SUM FROM {k=0} TO INF×SUP k&#34; to generate the summation equation: ##EQU6## 
     FIG. 1 provides an overview of the equation editor system. A computer containing a microprocessor 21 with memory 22 and an I/O circuit 23 for handling data input and output executes the equation editor application program 24. The user interface of the equation editor application is displayed on the display monitor 25. The user enters the textual description of an equation through the input device 26. The I/O circuit 23 retrieves the input and places it in memory 22 for the equation editor application program 24 to process. The equation editor application 24 lexically scans and parses the textual description (see below) and generates data for printing the equation which is sent by the microprocessor 21 through the I/O circuit 23 to be displayed on the display monitor 25. Alternatively, data for the printed form of the equation may be sent through the I/O circuit 23 to a printer 28 for printing in a document. The textual description of the equation may also be sent through the I/O device 23 to the storage device 27 for permanent storage. 
     Referring to FIG. 2, the equation editor includes three separate &#34;windows&#34; in a single display screen: an editing window 1 for manipulating the textual description of an equation, a palette window 2 for selecting characters and commands used in editing the equation, and a display window 3 for displaying the printed form of the equation. A &#34;window&#34; is a discrete part of the display screen with a function different from the remainder of the display screen. Only one window may be accessed at a time and the user may switch control among the three windows by pressing pre-defined keys. In the preferred embodiment, the user may switch control from the editing window to the palette window by pressing the F5 key and from the editing window to the display window by pressing &#34;Control-F3&#34; (&#34;Control&#34; and F3 keys pressed simultaneously). The user may then switch back to the editing window from either the display window or the palette window by pressing the F7 key. Other keys could be used to switch control among windows; the present set was chosen because of their similarity with keystrokes utilized in the wordprocessor of which the preferred embodiment of the present invention is a part. Alternatively, if a &#34;mouse&#34; device is attached to the computer, it can be used to activate each of the windows. 
     The editing window 1 is used to edit the textual description of an equation, which is present in the editing window at all times while an equation is being edited. The textual description of the equation is stored in memory during the equation editing process. When the user terminates the equation editor session, the textual description is stored in a file as part of the wordprocessing document on a storage medium such as a magnetic disk. If the user wishes to edit the equation at a later time, the textual description is simply read out of the file and into memory to allow further modification. This textual description then serves as the &#34;source code&#34;  describing the equation. The process of converting the textual description into its printed equation form is described below in the section discussing the display window. 
     This invention provides a new and extremely flexible method for editing the textual description of an equation. First, a textual description can be created through the normal input mode by typing characters directly from the keyboard. For example, the equation &#34;a+b&#34; could be input using only characters found on a standard keyboard. Second, in the preferred embodiment, characters which are recognized by the wordprocessor but are not found on a standard keyboard, called &#34;extended characters,&#34; can be inserted into the textual description of an equation through a pre-defined sequence of keystrokes. FIG. 2 contains a list of extended character sets in the preferred embodiment. Each extended character is represented by a pair of numbers, the first indicating the &#34;character set&#34; to which the extended character belongs, and the second representing the number of the character within the character set. For example, the greek letter alpha (&#34;α&#34;) can be inserted into the textual description of the equation in the editing window by typing the key sequence &#34;Control-2,8,1&#34;, where &#34;Control-2&#34; indicates that an extended character follows, &#34;8&#34; indicates the extended character set number, and &#34;1&#34; indicates the number of the character within the set. Third, the invention provides the user with the option of inserting extended characters into the equation by typing the name of the character. For example, in the preferred embodiment, the greek letter &#34;α&#34; can be inserted into the equation by typing &#34;alpha&#34; into the textual description of the equation. 
     Referring to FIG. 2, the palette window 2 provides an alternative method for inserting extended characters and keywords into the textual description of an equation. The user can access the palette window from the editing window by pressing a pre-defined key (F5 in the currently preferred embodiment). The preferred embodiment of the palette window contains eight separate &#34;menus,&#34; each with a list of characters or keywords that may be selected and inserted into the textual description of the equation. FIG. 4 contains a list of the contents of the palette window menus, each containing a unique group of characters or keywords. A particular menu may be selected by pressing the &#34;Page Down&#34; key to display the next menu or the &#34;Page Up&#34; key to select the previous menu in the sequence of eight palette menus. 
     The keywords in the palette menus represent commands used by the equation editor in creating various forms of equations. For example, the keyword &#34;OVER&#34; directs the equation editor to create a fraction by drawing a horizontal line between the designated numerator and denominator, &#34;SQRT&#34; directs the equation editor to create a square root symbol, and &#34;INT&#34; directs the equation editor to create an integral symbol. 
     The characters and keywords in each menu of the palette window may be viewed by using the arrow keys to move to the next item in the menu. In the preferred embodiment, the characters and keywords are highlighted in reverse video, one at a time, as the arrow keys are pressed. A keyword or the text form of a character, e.g., &#34;alpha,&#34; may be selected and inserted into the textual description by pressing the &#34;Enter&#34; key when the desired character or command is highlighted in the palette window. Alternatively, the character form, e.g., &#34;α,&#34; may be selected and inserted into the textual description by pressing &#34;Control-Enter.&#34; 
     The palette entries are specified in a file stored on a disk or other storage means, called the &#34;QRS file&#34; in the preferred embodiment. This file also provides the keywords recognized by the equation lexical scanner/parser, described below. 
     The palette window also serves as a visual aid to inexperienced users. When the palette window is activated, a message is displayed at the bottom of the screen describing in some detail the keyword that will be inserted into the textual description when the symbol or command highlighted is selected. Thus, a major purpose of the palette window is to provide a learning tool whereby the user has the flexibility to choose the method most applicable to his style or experience with the wordprocessor. The new user, being unfamiliar with equation editing commands and seldom-used mathematical characters, will likely use the palette as his principal mode of entry. By providing on-screen display of many available commands and characters, the palette window reduces the need to resort to written documentation, which is advantageous in the keyboard-intensive task of wordprocessing. For example, rather than entering the Greek letter &#34;α&#34; into the textual description directly from within the editing window by typing either the word &#34;alpha&#34; or the extended character sequence &#34;Control-2,8,1&#34;, the new user might access the palette window, find the &#34;α&#34; character and enter it from the palette. When he becomes familiar enough with the character or command, he will eventually enter it directly from the editing window. 
     Referring to FIG. 2, the third window in the equation editor is the display window 3. The display window displays equations as they appear in their final printed form. At any time while the textual description of an equation is being edited in the editing window, the equation may be displayed in the display window in its current for by pressing a pre-defined key, e.g., F9 or &#34;Control-F3&#34; in the currently preferred embodiment. The equation is displayed by using a combination of lexical scanning, parsing, and display techniques well known in the art, as follows. 
     First, the textual description of the equation in memory is lexically scanned, i.e., it is dissected into a sequence of &#34;tokens&#34; of which the equation editor grammar is composed. Tokens consist of all keywords, characters, and extended characters that may be used to construct the textual description of an equation, e.g., &#34;ROOT&#34;, &#34;SUP&#34;, &#34;ALPHA&#34;, &#34;+&#34;, &#34;-&#34;, &#34;x&#34;, &#34;y&#34;, &#34;z&#34;, &#34;α&#34; and &#34;β&#34;. In the preferred embodiment, the equation editor grammar is composed of the ASCII keyboard characters, the extended characters in Table 1, and the keywords representing commands and symbols shown in Table 2. Each token in the equation editor grammar has a unique value which is stored in a file called the &#34;QRS file.&#34; The lexical scanner matches each token with its corresponding value found in the QRS file and passes the value to the parser. Thus, for example, for each valid keyword in the textual description, the lexical scanner locates its corresponding value in the QRS file and when a match is found passes the unique value assigned to the keyword in the QRS file to the parser. If the scanner encounters a token which is an extended character, it passes the extended character value contained in the QRS file to the parser. Thus, if the token &#34;alpha&#34; is encountered in the textual description, the scanner will look up and find &#34;alpha&#34; in the QRS file and cause the return of &#34;8,1, &#34; which is the extended character value of the alpha symbol, α, in the Greek character set. 
     Next, after the lexical scanner returns the character and keyword values of the textual description to the parser, the parser generates a binary tree-type data structure describing the equation to be built in memory according to a set of grammar rules. The use of such grammar rules in the likes of compilers, interpreters and language translators is well known in the computer art. The equation editor grammar rules essentially define all sequences of tokens from which an equation can be properly constructed. Thus, for example, a textual description of the form &#34;a+b&#34; would be recognized by the grammar rules as valid while &#34;ab+&#34; would not be valid. 
     After the full textual description has been scanned, the tree is complete (if the textual description contained no syntax errors). Each node of the tree data structure is then analyzed and formatted with regards to the appearance, font, placement (i.e., (x,y) location), and actual symbols to output. For example, if a node contained a &#34;SQRT&#34; command, information pertaining to the size and placement of the square root symbol would be determined and stored. Finally, after each node has been analyzed and the format information stored, the tree is traversed again to output the individual text nodes in their correct position and appearance either in the display window or on paper. 
     While the displayed equation is initially presented in a default size, e.g., 500% of its size on a printed page in the currently preferred embodiment, it may be viewed in the display window in scaled sizes ranging from 25% to 1000% of the actual printed size by pressing the &#34;Page Down&#34; key to decrease its size in 25% increments and pressing the &#34;Page Up&#34; key to increase its size in 25% increments. The displayed equation may also be moved relative to the display window (&#34;panned&#34;) by pressing the arrow key which points in the desired direction of the move. Scaling and panning of the displayed equation are accomplished by modifying the graphical screen coordinates of the displayed equation using a combination of display techniques well known in the art, as follows. 
     The scaling and panning of the equation is called a transformation and is described by either a 3×3 transformation matrix or an equivalent set of calculations describing the (x,y) coordinate locations of the equation in the display. To change the view of the equation, the transformation matrix or calculations associated with the equation are recalculated according to the desired panning or scaling of the displayed equation. The use of transformation matrices to scale and pan graphically displayed data is a technique well known in the art. 
     As an example, referring again to FIG. 2, the equation ##EQU7## can be created and displayed as follows. While in the editing window of the equation editor, the user would first type &#34;FUNC&#34; to indicate that the letter to follow is to be printed in &#34;function&#34; format (non-italicized). Alternatively, the user could select the &#34;FUNC&#34; command from the palette window command menu. Next, since the characters in &#34;f(x)=&#34; are all keyboard characters, they are simply typed into the editing window directly from the keyboard. The square root symbol is created by either typing &#34;SQRT&#34; or selecting it from the palette window. Next, the textual description of the expression inside the square root symbol ##EQU8## can be created by typing &#34;{×SUP 2 OVER {2 alpha)}.&#34; Brackets are used to group the expressions. Of course, the &#34;OVER&#34; command can also be entered by selecting it from the palette window, the &#34;x SUP 2&#34; can also be inserted by using the &#34; &#34; character, e.g., &#34;x 2&#34;, and &#34;α&#34; can also be inserted into the equation by typing the extended character code &#34;Control-2,8,1&#34; or selecting it from the palette window. 
     After entering the textual description for this equation, the printed form of the equation can be displayed in the display window above the editing window by pressing a pre-defined key, e.g., F9 or &#34;Control-F3&#34; in the preferred embodiment. The display is created by sending the display data contained in the binary tree-type data structure, described above, to the computer&#39;s display memory to be displayed on the computer screen. 
     While displaying the equation, its textual description can be modified to change the appearance of the equation if desired. For example, &#34;alpha&#34; can be replaced by &#34;beta&#34; by simply moving the cursor in the editing window and inserting beta into the textual description of the equation as &#34;FUNC f(x)=SQRT {x 2 OVER {2 beta}&#34; to produce the equation ##EQU9## Thus, when &#34;alpha&#34; is replaced by &#34;beta,&#34; the tree-type data structure describing the equation is recreated from the changed textual description of the equation so that &#34;α&#34; is replaced by &#34;β&#34; in the display. 
     The present invention thus uniquely combines multiple equation editing components into a single user interface, including an editing window for manipulating the textual description of an equation, a display window for viewing the printed form of the equation, and a palette window for selecting symbols and commands used in editing the equation. This invention presents a uniquely efficient and flexible method for creating and editing mathematical equations in printed documents. ##SPC1##