Method and Apparatus for Displaying Text Including Context Sensitive Information Derived From Parse Tree

1. Field of Invention

This invention relates to the field of context sensitive text displays. In particular, this invention relates to determining the display characteristics of text efficiently from the parse node containing the text in a parse derived from the text.

2. Description of Background Art

Computers have long been used to display text to humans to facilitate editing and understanding. Typically, a human using a computer to manipulate or view a block of text. For purposes of illustration, a block of text will be assumed to be simply an array of characters.

In a modern computer text editor or text display tool, displaying text on a computer screen involves several steps. First, the tool needs to identify where in the text array the display should begin. This amounts to having an integer that indicates the starting position in the array. This information can be provided to the tool from the human being by keystrokes indicating a line number or a scroll bar indicating the relative position in the file. Next, the tool needs to "paint" the screen with the characters. Conceptually, the tool gets a character at the indexed point, determines the screen display characteristics, such as color, font, size, or format, associated with that character at that point in the text array, and provides that information to the graphical display hardware. The computer then increments the index and repeats the process with the next character.

Conventional text editors require the user to specify the display characteristics associated with particular points in the text without regard to what the particular text is or "means." However, in certain applications, the text may have context that the computer could use to determine the display characteristics. For example, computer programs are written in computer languages like C, Pascal, or Cobol. A program written in computer language has text strings within it that have a particular meaning or significance, such as keywords like "if", "else", or "while". A more sophisticated text display tool could use this context-sensitive information within the text to define the display characteristics of the text. Borland's C++ development environment for DOS machines provides a text editor that, for example, displays keywords with one color and comments in another color.

Using the context of the text to determine the display characteristics presents computational performance problems. The user wants to see the text displayed on the computer screen displayed promptly. However, setting the display characteristics as a function of the context requires that the computer compute the context. That computation can be done at the time the display is requested, or, alternatively, the context computation could be performed at some other, earlier time and the result stored. At the time the display is requested, the computer has to perform some computation either directly or by finding a previous result. This computation takes time. If this time is too long, then the text will not be displayed promptly, thus frustrating the user. Economically viable context-sensitive text displays therefore must efficiently store and compute the context.

A review of the process of extracting context out of certain kinds of text will clarify the problems a context-sensitive display has. One place that context extraction occurs is in the process of generating executable machine code from the text of a computer program written in a high level language. This process is called compilation. Compilation involves several steps: lexical analysis, parsing, code generation, and optimization. Only lexical analysis and parsing are relevant for purposes of displaying context sensitive information Lexical analysis involves breaking the text into distinct, non-overlapping text strings in accordance with the rules of a specified language. These non-overlapping objects are referred to as tokens. The lexical analyzer can characterize some of these text strings because the text matches a keyword, or is a number or a symbol such as "&". Lexical analysis is computationally fast because it relies only on "local" information to determine where the next token begins and ends.

After the lexical analyzer breaks the text into tokens, a parser converts the entire sequence of tokens into a parse tree that describes the computer program's structure. From this parse tree, the code generator can create blocks of executable code corresponding to the nodes of the parse tree. The code generator can then link the blocks together to make an executable program. An optimizer can then look for improvements to make in each block to reduce the amount of memory required to store the executable code or to decrease the run time of the executable code. The nature and mathematical structure of compilers is described in Compilers Principles, Techniques and Tools, by Alfred Aho, Ravi Sethi, and Jeffrey Ullman, 1986, ISBN 0-201-10088-6 which is hereby incorporated by reference. The steps for building a compiler are shown in Introduction to Compiler Construction with UNIX by Axel T. Schreiner and H. George Friedman, Jr., published by Prentice-Hall, 1985, ISBN 0-13-474396-2, which is hereby incorporated by reference.

If it is only desired to modify the display characteristics of the text depending solely on information that can be obtained "locally" from a lexical analyzer, then a text display tool can perform lexical analysis at the time it scans the text for the display. For common computer languages, this would allow the display tool to paint different keywords in different colors without a noticeable performance problem. However, this may not produce enough information for the user.

Changing the display characteristics of the text in accordance with information associated with the corresponding parts of a parse tree can be very useful. However, because constructing a parse tree requires processing all of the text, a tool using the parse tree to determine the display characteristics of the text will probably not be able to compute the entire parse tree every time the display needs to be changed. Therefore, such a display tool will generally require that the parse tree be generated once and stored, and then accessed when the need arises. However, conventional parse trees occupy significant amounts of memory, and require a substantial amount of time to build.

The memory requirements of a conventional parse tree are straight-forward to compute. Consider a text block consisting of N characters. Experience has shown that a file of N characters will generate a parse tree with N/4 nodes. A conventional parse tree which has nodes with a data structure written in C could be declared as follows:

This data structure provides a pointer to the parent node, a pointer to an array of pointers to the children of the node, an integer for counting the number of children, pointers for indicating where, in the text block, the text that generated this node begins and ends, and an integer to indicate what number node this is. In a conventional, 32 bit machine, each node will require one word for the parent pointer, one word to point at the array of children, one word for the child.sub.-- count, one word each for start.sub.-- position and end.sub.-- position, and one word for parse.sub.-- tree.sub.-- id. In addition, each node will require an additional word in its parent's array of children. Therefore, each parse node will require 7 words of memory. Therefore, this conventional tree structure will require 7N/4 words to store the parse tree for an N character file. In a conventional machine, there are 4 bytes per word, thus making the conventional data structure consume 7N bytes.

This invention provides a compact and easily accessed data structure for representing a parse tree associated with a block of text, and efficiently allowing text associated with a particular parse nodes to be displayed in a manner specified by the parse node. Linking the display characteristics of text with the parse tree associated with the text is particularly useful in viewing the results of circuit analysis for circuits created by synthesis from the same text.

A parse tree consists of one or more parse nodes in a tree configuration. Each parse node has associated with it subordinate parse nodes or a particular contiguous group of characters within the text block. The data structure of this invention represents the parse tree as an array of elements, with each element represented by two bits. The index to this array is related to the position in the text block.

Using two bits for each element provides for four kinds of elements. One element represents the beginning of a parse node, called TREE.sub.-- START. Another element represents the end of a parse node, called TREE.sub.-- END. Another element represents the existence of a single character, called TREE.sub.-- CHAR. To make the parse array more compact, the fourth element represents a fixed number of sequential characters, called the block size. The fourth element is called TREE.sub.-- BLOCK. In this invention, using the fourth element to represent four characters works well.

Generating the parse array representation from a conventional tree representation can be done by recursively traversing the conventional tree. A TREE.sub.-- START is written every time a child node is accessed. A TREE.sub.-- END is written every time a parent node is accessed to after accessing a child node. TREE.sub.-- BLOCKs and TREE.sub.-- CHARs are written to reflect the size of the text string found at the node. (See the function "ve.sub.-- write.sub.-- paren.sub.-- tree" in Appendix A for an example.)

Constructing a conventional tree representation from the parse array can be done by sequentially marching through the parse array, keeping a stack of parse nodes, and keeping a current index into the text array. When a TREE.sub.-- START symbol is encountered, a new node is created, made a child of the current node on the top of the stack, and pushed onto the stack. When a TREE.sub.-- CHAR or TREE.sub.-- BLOCK symbol is encountered, the appropriate number of characters beginning with the current index in the text array is assigned to the node at the top of the stack. When a TREE.sub.-- END symbol is encountered, the stack is popped. (See the function "tree.sub.-- convert.sub.-- to.sub.-- full" in Appendix A for an example.)

Estimating the size of the parse array offers insight into the value of the invention. Each node in the parse tree will require a TREE.sub.-- START symbol and a TREE.sub.-- END symbol. These symbols each require 2 bits, so, with 8 bits per byte, each node will therefore require 1/2 byte. If the file has N characters, and tends to have N/4 nodes, then the node symbols will require (1/2) *N/4=N/8 bytes. If no compression is used, then there needs to be storage space for an additional N symbols to store the representation of the characters. In this situation, each character requires 2 bits to store, thus the parse array requires N/4 bytes to store the character representation in an uncompressed form. However, experience has shown that using the TREE.sub.-- BLOCK symbol to represent 4 characters halves the character storage requirement to N/8 bytes. Therefore, the parse array requires N/8 bytes for the node markers, and N/8 bytes for the text, thus requiring N/4 bytes for the entire parse array, compared to the 7N bytes for the conventional approach. The parse array therefore reduces the memory required by a factor of 28 over a conventional parse tree. The reduced memory usage also leads to reduced access times, and therefore a faster performing display tool. In addition, this data structure can be loaded directly from permanent storage, such as a file, because it does not contain pointers. This makes the loading time very small, and initialization very fast.

One disadvantage to using any parse tree to guide the selection of display characteristics is that it is necessary to traverse the parse tree to get to the point in the parse tree that corresponds to the portion of text that needs to be displayed. However, this invention helps reduce this computation by creating a table that is keyed to the line number in the text file. This table stores a copy of the stack created by traversing the parse tree to the point in the text file corresponding to the end of the particular line. To further reduce storage requirements, a stack only needs to be saved every several text lines. (Every 16 lines works well.) When it comes time to get information from the parse tree, it is only necessary to get a copy of the stack corresponding to the nearest preceding recorded line, and continue traversing the parse tree from there.

FIG. 1. A parse tree showing the text corresponding to the nodes.

FIG. 2. A textual representation of the parse tree of FIG. 1 in accordance with the present invention.

FIG. 3. A binary representation of the parse tree of FIG. 1 in accordance with the present invention.

FIG. 4. A flow chart showing a method of setting the display characteristic of the text as a function of the parse node containing that text.

FIG. 5. A flow chart showing a method of obtaining the initial parse node corresponding to a particular point in the text array.

FIG. 6. A generalized diagram showing relationships between parse node, program text and electronic structures created from the text.

FIG. 7. A diagram of a general purpose computer system.

The present invention comprises a novel method and provides a novel structure for compactly storing a parse tree and using that parse tree to change the display characteristics of the associated text efficiently. The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the preferred embodiment will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the invention. Thus, the present invention is not intended to be limited to the embodiment shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.

FIG. 7 is a simplified block diagram illustrating a general purpose programmable computer system, generally indicated at 200, which may be used in conjunction with a first embodiment of the present invention. In the presently preferred embodiment, a Sun Microsystems SPARC Workstation is used. Of course, a wide variety of computer systems may be used, including without limitation, workstations running the UNIX system, IBM compatible personal computer systems running the DOS operating system, and the Apple Macintosh computer system running the Apple System 7 operating system. FIG. 7 shows one of several common architectures for such a system. Referring to FIG. 7, such computer systems may include a central processing unit (CPU) 202 for executing instructions and performing calculations, a bus bridge 204 coupled to the CPU 202 by a local bus 206, a memory 208 for storing data and instructions coupled to the bus bridge 204 by memory bus 210, a high speed input/output (I/O) bus 212 coupled to the bus bridge 204, and I/O devices 214 coupled to the high speed I/O bus 212. As is known in the art, the various buses provide for communication among system components. The I/O devices 214 preferably include a manually operated keyboard and a mouse or other selecting device for input, a CRT or other computer display monitor for output, and a disk drive or other storage device for non-volatile storage of data and program instructions. The operating system typically controls the above-identified components and provides a user interface. The user interface is preferably a graphical user interface which includes windows and menus that may be controlled by the keyboard or selecting device. Of course, as will be readily apparent to one of ordinary skill in the art, other computer systems and architectures are readily adapted for use with embodiments of the present invention.

The present invention advantageously uses the fact that parse node information has been linked to automated design display technology. For example, netlist data structures may retain links to parse nodes generated from HDL code used to produce such structures. Moreover, graphical display tools used to illustrate features or performance of such structures also may contain links to the parse nodes generated from HDL code. See, for example, commonly assigned U.S. patent application Ser. No. 08/417,147, filed Apr. 3, 1995, which is expressly incorporated herein by this reference.

Referring to FIG. 6, there is provided an overview which illustrates where the mechanisms of the present invention fit within the overall process of using parse nodes to create electronic or software-based structures. HDL text 2000 is created by a user. At compile time, a parse tree 2002 is created. Nodes on the parse tree correspond to portions of the HDL text. Nodes of the parse tree also correspond, for example, to cells 2004-2016 within a netlist 2018 and, for example, to portions 2020, 2022, of a display image 2024 used to analyze the netlist. Arc 2003 indicates that cell 2004 was created from parse node 2005. A netlist may retain references, such as arc 2026, to a parse node used to create netlist nodes and nets. Similarly, electronic structures within the display tool also may have references, such as arc 2028, to a parse node used to create netlist cells or nets analyzed in the display.

The mechanism of the present invention advantageously provides a two-way link between parse node information and text. See, for example, two-way link 2030 which can be created through the mechanism of the present invention. It should be appreciated that a parse tree, once created, often is not saved. Nevertheless, as explained above, electronic structures such as a netlist cell or computer display information may retain references to the parse nodes of the parse tree after the tree has been discarded. The mechanism of the present invention permits linkages between text and electronic structures based upon retained parse node information.

Appendix A contains a C program listing describing the data structure of the present invention and methods of manipulating the data structure to obtain display characteristics of the associated text. The procedures beginning with "xm" or "Xt" or "topLevelShellWidgetClass" involve the graphical user interface, and are described in "The X Window System: Programming and Applications with XT, COSF/Motif edition", by Douglas Young, published by Prentice-Hall in 1990 with ISBN 013-497074-8, which is hereby incorporated by reference. Basic data structure manipulations such as hash tables and stacks are described in "Introduction to Algorithms" by Thomas Cormen, Charles Leiserson and Ronald Rivest, by the MIT Press in 1990 with ISBN 0-07-013143-0, which is hereby incorporated by reference.

The routine "os.sub.-- show.sub.-- stat" merely gathers computer performance statistics and is not functionally related to the parse array operations. "Error.sub.-- if" is based on the "assert" macro commonly used in C programs. "Error.sub.-- if" causes the program to terminate if a specified condition is true, and continue if the condition is false.

The program listing in appendix A along with its comments and the library references are hereby incorporated by reference into the specification.

FIG. 1 illustrates a parse tree associated with some text. The parse tree consists of nodes 100, 101, 102, 103, 104, 105, and 106. The characters 1 through 13 represent generic characters. Characters 1, 2, 3, 4, 5 and 6 are associated with node 102. Characters 7 and 8 are associated with node 103. Characters 9, 10 and 11 are associated with node 105 and characters 12 and 13 are associated with node 106.

FIG. 2 illustrates a text representation of the parse tree using "{" to mark the beginning of a node and "}" to mark the end of a node. For example, left brace 30 and right brace 40 together contain all of the text and nodes associated with node 100. Left brace 31 and right brace 41 demarcate the text and nodes associated with node 101. Left brace 32 and right brace 42 demarcate the text associated with node 102. Left brace 33 and right brace 43 demarcate the text associated with node 103. Left brace 34 and right brace 44 demarcate the text associated and nodes with node 104. Left brace 35 and right brace 45 demarcate the text associated with node 105. Left brace 36 and right brace 46 demarcate the text associated with node 106. One alternative embodiment of the present invention is to rewrite the text data structure with a brace or equivalent symbol inserted into the text.

The left braces serve as begin markers which denote the beginning of information encompassed by a parse node. The right braces serve as end markers which denote the end of information encompassed by a parse node. Begin and end markers are grouped in sets: a left brace in a set denotes the beginning of information encompassed by a parse node. A right brace in the same set denotes the end of information encompassed by a parse node.

FIG. 3 illustrates the use of a parse array 150 to store a representation of the parse tree using the text representation of FIG. 2 as a guide. Parse array 150 is really an array of bits divided into bit pairs 200 through 223. Each bit pair is used to represent a symbol. In one embodiment, the beginning of node is denoted with the TREE.sub.-- START symbol, and that symbol has a value of "00". The TREE.sub.-- START symbol is a begin marker. The TREE.sub.-- END symbol has value "01" and is used to demarcate the end of a node. The TREE.sub.-- END symbol is an end marker. The TREE.sub.-- CHAR symbol has value "10" and is used to demarcate a single character. The TREE.sub.-- CHAR symbol is a character marker. The TREE.sub.-- BLOCK symbol has value "11" is used to demarcate a group of 4 characters.

Using this encoding, the parse tree of FIG. 1 begins with the "00" to denote the beginning of the node 100, as shown with bit pair 200. The next two bits are set to "00" to denote the beginning of node 101, as shown with bit pair 201. Bit pair 202 holds "00" to denote the beginning of node 103.

Note that node 103 has 6 characters associated with it. One embodiment of the invention would use the value "11" in bit pair 203 to note the presence of characters 1, 2, 3, and 4, while bit pairs 204 and 205 each hold a "10" to mark a place for characters 5 and 6 respectively. Other compression schemes could be used to store the character count.

Bit pair 206 holds the value "01" to mark the end of node 102.

It can be very useful to associate an unique identification number with a particular node in a parse tree. A conventional parse tree often allocates an entire word in the data structure to hold that information. However, the parse array provides that information indirectly. The identification number of the node at a particular point in the parse array is the number of TREE.sub.-- START symbols to the "left" of the TREE.sub.-- START symbol corresponding to the particular point. For example, to determine the node identification number for the node containing bit pair 215 of FIG. 3, back up to the TREE.sub.-- START symbol demarcating the boundary of the node containing bit pair 215. This is bit pair 213. Then and count the number of TREE.sub.-- START symbols preceding bit pair 213. In this case, there are 5, namely bit pairs 200, 201, 202, 207, and 212. Therefore, the node corresponding to bit pair 213 is uniquely identified as node number 5.

Of course, if the request for bit pair identification is made at a point where a TREE.sub.-- START symbol is already located, it is not necessary to back up.

Constructing the parse array from a conventional parse tree can be done as follows. Define an index and a tree pointer. Set the index to zero, and the tree pointer to the root node. At a particular node, write all unwritten characters up to the start of the node, write the TREE.sub.-- START symbol into the parse array, and increment the index. Recursively apply this start symbol/character rule for each child node. If there are no more children, write all the unwritten characters up to the end of the node, then write the TREE.sub.-- END symbol into the parse array, increment the index, and return to processing the parent node. See "ve.sub.-- write.sub.-- paren.sub.-- tree" in Appendix A for an example.

Constructing a conventional parse tree from the parse array can be done as follows. Define a stack pointer, a text index, and a parse array index. Set the text index and the parse array index to zero.

If the symbol in the parse array at the parse array index is the TREE.sub.-- START symbol, create a new parse node. The new parse node should be made a child of the node at the current stack pointer, if there is anything on the stack pointer. Push the new node onto the top of the stack, and increment the parse array index, and process the next symbol.

If the symbol in the parse array at the parse array index is a TREE.sub.-- BLOCK or TREE.sub.-- CHAR, then associate the appropriate number of characters in text block beginning with the text index with the parse node on top of the stack. Increment the text index and the parse array index appropriately.

If the symbol in the parse array at the parse array index is the TREE.sub.-- END symbol, then pop the parse node on the top of the stack, and increment the parse array index. See "tree.sub.-- convert.sub.-- to.sub.-- full" in Appendix A for an example.

A variety of information can be attached to a parse tree that is useful to guide the selection of the display characteristics. One way to do this is to allow another component of a system to define the display characteristic for every parse node. By using an unique identification number associated with every parse node, the display tool can look up or compute the appropriate display characteristic for that node.

For example, in conjunction with circuit analysis and as described in U.S. application Ser. No. 08/417,147 by Gregory et al filed on Apr. 3, 1995, it is possible to determine the circuit characteristics associated with a particular piece of source text. For example, it might be useful to have the text corresponding to the critical path of the circuit displayed in red while all other parts are displayed in black. A database and analysis tools can be used to identify the parts of the parse tree that are on the critical path. The display tool can then inquire about the status of a particular node, and use that to select the color for the text corresponding to that node.

The process for determining the display characteristics of the text associated with a particular node is shown in FIG. 4. This section provides a general and simple explanation of the process. Later sections identify modifications that can be made to decrease execution time. The process begins at step 1001 where the human interface portion of the software identifies the place in the text where the user wants the display to begin. This amounts to computing an index into the text array.

Step 1002 finds the parse node containing the starting point of the text. In particular, step 1002 involves traversing the parse tree and keeping track of how many characters in the text have been covered as well as keeping track of the current parse node. When the number of characters covered equals or exceeds the index value, then the current parse node is the parse node containing the particular text point. FIG. 5 shows a conceptually straight-forward approach to this process.

Step 1101 of FIG. 5 involves initializing a character count, the parse array index, and the current node id to zero and creating a stack.

Step 1102 involves identifying the bit pair in the parse array at the location specified by the parse array index.

If the symbol identified in step 1102 is the TREE.sub.-- START symbol, then push the current node id onto the stack and increment the value of the current node id as shown in step 1103.

If the symbol identified in step 1102 is the TREE.sub.-- END symbol, then pop the value on top of the stack into the current node id as shown in step 1104.

If the symbol identified in step 1102 is the TREE.sub.-- BLOCK symbol, then increment the character count by the number of characters represented by the TREE.sub.-- BLOCK symbol as shown in step 1106. In one embodiment, this is four characters.

If the symbol identified in step 1102 is the TREE.sub.-- CHAR symbol, then increment the character count by 1, as shown in step 1105.

After incrementing the character count in steps 1106 or 1105, determine if the parse tree has been parsed far enough by comparing the character count with the index into the text array as shown in step 1107. If the tree has been parsed far enough, stop this process and go to step 1002 of FIG. 4. To proceed efficiently in the process of FIG. 4, it useful to keep the variables and stack computed in FIG. 5 intact.

If the parse tree has not been traversed far enough, increment the parse array index as indicated by step 1108, and return to step 1102.

After identifying the appropriate parse node from the process in FIG. 5, then it is necessary to obtain the display characteristic associated with the current parse node. This is done through a data base or a look-up table in step 1003 of FIG. 4.

In step 1004, the character is painted onto the screen with the characteristic established in step 1003.

In step 1005, the next character is identified by incrementing the character index by one. In step 1006 it is determined whether the display block has been completed. If it has, then stop the process. Otherwise, determine if the next character belongs to the current parse node, as shown in step 1008. If the current bit pair referred to by the parse array index is a TREE.sub.-- BLOCK, and the new character is part of that block, then the character is within the same parse node, and the painting continues in step 1004. If the block has been exceeded or the current bit pair is a TREE.sub.-- CHAR, then the parse array index needs to be incremented to obtain a new current bit pair. If the new current bit pair is a TREE.sub.-- BLOCK or a TREE.sub.-- CHAR, then the new character is part of the current parse node, and painting continues in step 1004. If the new current bit pair is a TREE.sub.-- END, then the parse node changes in step 1009.

Adjusting the current parse node requires adjusting the stack formed in step 1002 and the current parse node and incrementing the parse array index until the parse array index refers to bit pair that is a TREE.sub.-- BLOCK or a TREE.sub.-- CHAR. Adjusting the stack involves popping the top of the stacking into the current parse node when a TREE.sub.-- END is encountered and pushing the current parse node onto the stack when a TREE.sub.-- START is encountered. After a new parse node is identified, the display characteristic is determined in step 1003.

The processes shown in FIG. 4 and FIG. 5 assumed that the text was stored as an array. The techniques shown can be trivially modified for other text data structures. For example, another approach to storing text is to have an array of pointers with each pointer referring to a block of text with each block of text ending with a new line character. Using this or another data structure requires modifying the character incrementing step 1005 of FIG. 4, and step 1105 and step 1106 of FIG. 5.

The processes shown in FIG. 4 and FIG. 5 require traversing the parse tree from the beginning of the text block to identify current parse node. This can require much computational effort. One way to improve performance in step 1002 is to create a storage mechanism that can retrieve the parse tree traversal state as a function of the text display index. This can be done efficiently by observing a few characteristics of the text display and the parse tree traversal state.

The process in FIG. 5 manipulates several variables, namely the character count, the parse array index, the current node, and the stack as the computer marches through the parse array. Together, this information specifies the state of traversing the parse tree. Conceptually, the process in FIG. 5 specifies a parse tree traversal state for every character in the text array. For example, see the type definition for "tree.sub.-- gen" in Appendix A. In principle, with some adjustments for the compaction performed using the TREE.sub.-- BLOCK symbol, one could store this state in step 1107, and create a look-up table that would hold the state for each character in the text array. Then the process of FIG. 5 could be replaced by looking data up. This would result in a very fast access time. Unfortunately, a table for every character would occupy a great deal of memory and take a long time to create.

However, an intermediate approach could work where the state at step 1107 is stored for every fixed number of characters. For example, the state could be stored in a table every 256 characters. At the initialization step 1101, a table index could be computed by dividing the text index by 256 and truncating, and the various variables initialized to the value stored in the corresponding table entry. This way, the process in FIG. 5 would only need to parse the tree for no more than an additional 255 characters.

The state storing scheme could also be modified to deal with line numbers instead of the number of characters. In step 1001, the user interface could provide a line number in the file where the display is to start. The parse tree traversal state of step 1107 could be stored every several lines in a table. Experience has indicated that storing every 16 lines works well. At the initialization step 1101, a table index could be computed from the line index, and the initial parse tree traversal state set to the values found in the table.

The parse tree traversal method shown in FIG. 5 proceeds with one symbol in the parse array at a time. Determining the correct symbol from the parse array directly would require many machine instructions for massaging the bits in the array to identify the symbol, and process it accordingly. An alternate method that takes advantage of the compact nature of the representation processes four symbols concurrently by using a look-up table to determine the appropriate actions required to process the symbols contained in a byte of storage. In particular, the function "tree.sub.-- build.sub.-- expanded.sub.-- array" on data input converts a byte's worth of parse array to a short list of symbols. The function "tree.sub.-- gen.sub.-- next" uses this converted representation to proceed through the parse array efficiently. A similar approach could be used where the parse tree is traversed in step 1009 of FIG. 4. ##SPC1##