JPH0192836A - tree scanning method - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a tree scanning method that involves attribute propagation between nodes. The present invention relates to a tree scanning method that can improve the efficiency of tree scanning even when it is impossible to perform tree scanning at the time of scanning.

[Conventional technology]

A method of scanning tree-structured data and processing visits to individual nodes based on information about the nodes is frequently used in various software such as compilers.

The data to be scanned, for example, as shown in FIG.
The tree structure 200 has a main structure 200 consisting of branches 202 connecting the tree structure 200, and the node at the top of the nodes 201 of this tree structure 200 is called the root, and when no other contact is connected below a certain node. , the nodes of the hand are called leaves. Regarding the relationship between the nodes 201 connected by the branches 202, for example, a node y connected immediately below a certain node X is called a child of that node X, and the node X is called the parent of the node y.

Furthermore, there is an order relationship between nodes that share a parent, and the leftmost child and rightmost child of the parent node X are called the eldest child and the youngest child of the node X, respectively.

The node to the right of node X is called the node X's th node, and the node X is called the older brother of the node X.

Note that since these nodes form a tree structure, they hold the location of their first-born data and the location of their first child data.

Also, nodes where the eldest child or the th child does not exist hold a special value nil (n i l) in place of their location.

When traversing a tree with this structure, we use a depth-first search, that is, we start the tree from the root.

First, search downwards from the child closest to the person, and when a leaf is reached, return to the parent one step, and if there is a child in the leaf,
Continue searching for the corresponding number, and if there is no one, return to the parent,
This search includes, for each contact point, all of the destination order to be visited before visiting all the children of the node, the middle layer to be visited during the visit of the children, and the post-order to be visited after visiting all the children. There is a method of scanning the tree in order and sequentially arranging data corresponding to the visit order of the node according to the visit order.6 For example, as shown in Fig. 8(a), node R has three children. If the above method is used to perform a tree scan on the tree structure having the partial tree structure A to C and sequentially arrange the data, the result will be as shown in Figure (b). To,
Result Rz of tree scan (first order) to node R before partial tree structure A-C, result of tree scan (middle layer) to node R between partial tree structure A and partial tree structure B R2, the result Ra of the tree scan (middle layer) to the node R between the partial tree structure B and the partial tree structure C, and the tree scan (afterward) to the node R after the partial tree structure A-C. (order) results Ra are arranged sequentially.

Therefore, in tree scanning, the node currently targeted for main scanning has a state equal to the total number of its children plus one. This state is a scanning stage for one node, and is expressed by an integer from 0 to the total number of children of the node. In addition, each node has attributes at each scanning stage, that is, the contents R1 to R4 to be arranged sequentially, or the contents R1 to R4.
Information indicating R4 is provided.

Such a tree scanning method is particularly useful when it is possible to evaluate the attributes of all nodes at low cost before the start of the main scan, or when it is difficult to evaluate the attributes of all the nodes before the start of the main scan, or This applies to cases where it is possible to evaluate individual attributes according to the type of visit.

However, when the nodes depend on each other and it is necessary to scan the entire tree to evaluate the attributes of a certain node, or when the information required to evaluate the attributes is enormous.

- In cases where it is impossible to arrange the attributes of all nodes in one scan, the evaluation order of the attributes of each node is specified, and the evaluation order and the main scan order for each node in the main scan are If they do not match, each operation cannot be performed by applying such a method.

For example, 'algorithm child data structure = program, N
In the method described in ``, 1st, 2, Translated by Takuya Katayama, 1979, 1, Published by Japan Computer Association'', the entire tree is scanned starting from the root of this structure, and each node is visited in order, Processing is performed for each subsequent order.For this reason, -
If the number of nodes to be processed in one scan is limited,
In this scan, it was necessary to repeatedly scan the entire tree, including nodes that were not processed at all.

In the above-mentioned conventional technology, if the number of nodes to be processed in - times of scanning is limited, the entire tree is repeatedly scanned, which poses a problem in processing efficiency.

Also, no consideration is given to cases where processing of different nodes interfere with each other, for example, when processing results from visiting individual nodes are arranged in a sequential structure, and the The process was not easy.

Japanese Patent Application No. 61-280032 improves these problems and improves processing efficiency when multiple main scans are required, and even when the processing results of each scan interfere with each other. In order to provide a tree scanning method and apparatus capable of obtaining correct processing results, the method includes means for accumulating tree structure data composed of nodes, and each node has an attribute indicating the scanning stage in the tree structure. and a type that defines the evaluation order of the attributes on a node-by-node basis, and the evaluation results of attributes and properties corresponding to the scanning stage of each node of the tree structure data are sequentially arranged in the memory in depth-first search order. In a tree scanning device that performs processing in one step according to the evaluation order of attributes,
The above-mentioned memory is composed of two memories, which are of the same type, recognize a connected group of nodes as a subtree, and when scanning the root of the subtree, they write symbols indicating that they are at the start and end positions of the subtree. , respectively, are arranged sequentially in the preceding order and the subsequent order, and a symbol indicating the position in the middle of the subtree is placed in each leaf of the subtree, at the time of returning from scanning children of a type different from that type. means for performing a first process of sequentially arranging data in one of the two memories; the first processing means searches for data strings sequentially arranged for each type, and searches for data strings that do not belong to the type; When the start symbol, intermediate symbol, and end symbol of the tree are copied to the other of the two memories and the start symbol of the subtree belonging to the type is found,
means for instructing the start of the subtree scan, and upon finding an intermediate symbol and an end symbol, performing a second process for instructing the resumption of the subtree scan; a third means for scanning the subtree to which it belongs and expanding the attributes of the subtree to the other of the two memories; the first processing means expanding the sequential data string to the one memory; The second processing means sequentially searches the data string.

The third processing means receives the start instruction from the second processing means, starts scanning the subtree, and when detecting a node of a type different from that type, temporarily suspends the scanning, and the second processing means performs the following operations.
The sequential data string stored in one memory is searched again, and the third processing means resumes subtree scanning in response to the restart instruction from the second processing means, and in parallel with the scanning, searches for the relevant type. Performs processing to expand the attributes of the subtree to which it belongs onto the other memory.

[Problem that the invention seeks to solve]

The above conventional technology can improve processing efficiency when multiple main scans are required, but when attribute propagation occurs from a certain node to an ancestor, the node where the propagated attribute is generated and this reference No consideration is given to the case where the timing of evaluating nodes is different.

An object of the present invention is to provide a scanning method and apparatus that can propagate attributes even when non-scanning is performed at different timings and can obtain correct results.

[Means for solving problems]

The above purpose is to provide information to identify whether each node in the tree structure data is a propagation source or propagation destination of certain propagation information, and to
During the first process of sequentially arranging start symbols, intermediate symbols, and end symbols in one of the memories, a set of paths connecting the propagation source and the highest propagation destination of the propagation information is defined as the propagable area. When searching the area, assign an ordinal number to the occurrence class of the propagation source, secure a storage location for propagation information for the number of propagation sources for each area, and store the location information at the root of the propagable area. On the other hand, by setting the same information to a symbol indicating the start position when scanning the root of the subtree, the third process of scanning the subtree and expanding the attributes of the subtree to the other of the two memories can be performed. In this case, the propagation information storage location information stored in the root of the subtree is first retrieved and the subtree is searched, and when the propagation source node arrives, the attribute evaluation result of the node is searched for the propagation information storage location information of the same node in the propagation information storage location. This is achieved by setting the position corresponding to the ordinal number and obtaining the information necessary for contact evaluation from the propagation information storage location upon arrival at the propagation source node.

[Effect]

In the present invention, the node group that is the target of each scan is classified and colored, the node group in which nodes having the same number are connected is regarded as a subtree, and the subtree is managed, and each subtree is scanned and managed. They call each other in a Korchin style.

That is, a collection of subtrees is managed as a parenthesis structure with the root of each subtree as an identifier, and in order to manage the collection of subtrees, the parenthesis structure is copied during - times of scanning. During the copying, if a subtree of the current type appears, the copying is interrupted and scanning of the subtree is started, the processing result is reflected in the parenthesis structure, and the heterogeneous node is reached before the scanning of the first subtree is completed. Then, copying of the parenthesis structure of the corresponding part continues.

When multiple subtrees are included in the propagable area of certain attribute information, the location information of the propagation information storage location that stores the attribute evaluated by the propagation source is stored in advance at the root of the subtree in the same way as the root of the propagable area. Therefore, the propagation information evaluated and stored when scanning the subtree containing the propagation source can be propagated to the propagation destination when scanning the subtree containing the propagation destination via the propagation information storage location. becomes.

〔Example〕

An embodiment of the present invention will be described below with reference to the drawings.

FIG. 5 is an explanatory diagram of nodes and subtrees in one embodiment of the present invention, and FIG. 6 is an explanatory diagram of sequential data strings in one embodiment of the present invention.

In the main scanning method of this embodiment, in advance, as shown in FIG. 5(a),
The set of nodes that make up the tree to be scanned is
Classify each node according to the evaluation order, and divide the subsets by one-dot lines according to the classification into the node types A-C.
shall be. In addition, each node retains the name of the type to which each node belongs, and the tree to be scanned is as shown in Figure 5(b).
It is colored based on its type A-C.

Note that the subtrees that make up the tree structure are defined as follows.

(i) The root of the entire tree, or a node whose type is different from the parent type, is set as the root of the subtree to which it belongs.

(n) When the type of the child of a node belonging to a certain subtree matches the type of the parent, the child belongs to that subtree.

(■) A leaf or a node whose type of all children is different from its own type is set as a leaf of the subtree to which it belongs.

Therefore, according to the above definition, as shown in FIG. 5(b), the areas separated by dotted lines indicate the subtrees according to the above definition, and each subtree can be identified by the location of the root of each subtree. .

Furthermore, when evaluating node attributes, it may be necessary to refer to information held by descendants of the node. Such information is called propagation information, and the propagation information is propagated from the node that defines this value to the ancestor nodes that may refer to it.

Propagation information is classified into several types, and propagation is performed for each type. In other words, the definition and reference of a certain propagation information is
This is done by specifying the type name of the propagation information.

A node that defines one type of propagation information is called a propagation light of that propagation information, and a reference node is called a propagation destination.

Generally, there can be multiple ancestral propagation destinations for one propagation source. Also, there may be multiple propagation sources.

The propagable area of one propagation information of a certain node is the path from the propagation source to the propagation destination of the farthest ancestor. Further, the propagable area of one piece of propagation information is a set of propagable areas for individual propagation sources, and this is called a propagable area. FIG. 7 shows an example of the propagable area. The propagable area is a tree structure defined as follows.

(i) Let the propagation source be a leaf.

(it) The highest node among the propagation destinations is set as the root.

(iii) All nodes whose ancestors have propagation destinations and whose descendants have propagation sources belong to the tree structure.

In general, a propagable region may be (i) included in a certain subtree, or (if) included in multiple subtrees. (i)
In this case, the relevant propagation information is defined and referenced only when scanning that subtree. In the case of (3i), it is necessary to propagate the propagation information in a scan different from the scan that involves the definition of the propagation information.

A scan involving the definition of propagation information must be performed before a scan involving the reference thereof, and the evaluation order of each subtree shall satisfy this condition.

When the target tree is colored in this way, the main scan is first performed, and the images are scanned sequentially as shown in Figure 6 (,).

A partial tree is recognized by marks indicating the location of the scanned node, the type of the node, and the positional relationship between the node and the boundary of the area to which the node belongs.

When reaching a propagation source node for the first time for a certain propagation information, or for the first time in a descendant of a propagation source, this is recognized as the root of the propagable area for this propagation information, and the start address of the propagation information storage location is obtained while scanning the descendants. , along with the information that it is within the relevant propagation area. Also, at this time, a counter value for counting the propagation source nodes is set to O.

When the source of the propagation information is reached within the propagation area, the information that the information is within the propagation area and the counter value are temporarily saved as node information.

The same information is reset and the descendants are scanned. When the same propagation source is reached, the same information and the counter value are restored, and after storing the value as node information, the counter value is incremented by 1.

In this case, for nodes of a different type from the parent.

The node is recognized as a node of a new subtree in the prior order.

The start address of the propagation information storage location held from the propagation destination, the nine types of locations of the nodes, and data holding the start symbol (start symbol data) are placed at the end of the sequential data string.

Upon finishing scanning the propagable area and returning to the area,
An area corresponding to (dimension of one unit of propagation information) x (counter value) from the start address of the propagation information storage location is secured as the storage location.

In addition, when the scanning stage is i (i≧1) at a certain node, if the type of the i-th child is different from the type of that node, data holding the type and intermediate symbol (intermediate symbol data)
is placed at the end of the sequential data string.

Furthermore, in a certain subtree, the intermediate symbol data that appears last is deleted from the end, and at the root of that subtree,
At the beginning, data holding the type and end symbol (end symbol data) is placed at the end of the sequential data string.

By this recognition, a sequential data string having a structure as shown in FIG. 6(b) is developed from the tree structure shown in FIG. 5(b).

The sequential data string created in this way is, if the tree in Figure 5(b) is a tree whose units are subtrees indicating each type A-C, as shown in Figure 6(Q), this tree is the 6th tree. As shown in figure (d), it can be expressed using a parenthesis structure. Therefore, Fig. 6 (
The start symbol, end symbol, and intermediate symbol in the sequential data string in b) correspond to the left parenthesis, right parenthesis, and delimiter of this parenthesis structure, respectively.

Further, this sequential data string is called an initial sequential data string, and sequential data strings are searched in order from the youngest type according to the type indicating the evaluation order to obtain a target sequential data string.

Note that for the first type of search, the initial sequential data string is regarded as the primitive sequential data sequence, and for the second and subsequent types, the previous target sequential data sequence is regarded as the primitive sequential data sequence.

When searching such a primitive sequential data string and developing a target sequential data string, first, while sequentially searching from the beginning to the end of the primitive sequential data string, each data type is If it does not match the type, the data is placed at the end of the target sequential data string.

During the search, if start symbol data matching the type is reached, start instruction data including the start address of the propagation information storage location in the start symbol data is created, and a subtree is created from the location of the node held by that data. Start scanning, a node different from the relevant type appears, and interrupt the subtree scanning, or.

After waiting for the subtree scan to complete, the search continues from the next data.

Also, during the search, if intermediate symbol data or end symbol data that matches the type is reached, a node different from the type appears before reaching the intermediate symbol data or end symbol data, so the subtree scan that was interrupted at - is restarted. , Furthermore, after waiting for a node different from the relevant type to appear and the subtree scan to be interrupted or completed, the search continues from the next data. Note that if the subtree scan has been completed at the time of the instruction, the search continues from the next data.

In this way, in the process of searching for the relevant type of sequential data from the source sequential data string and obtaining the target sequential data string,
Starts a subtree traversal with the indicated node as the root, and for each node to be main traversed, if an attribute corresponding to that traversal stage is required, it is evaluated at that point, and its value is added to the target sequential data sequence. Place at the end.

At this time, the start address of the propagation information storage location in the start instruction data is held as location information of the current propagation information. It also generates a stack structure for correctly propagating current propagation information during subtree scanning. When a propagation source is reached in order of priority during scanning, the first address of the propagation information storage location up to that point is pushed onto the stack, and scanning is performed assuming that the propagation information will not be propagated for its descendants. Evaluate the attribute value of the propagation information, restore the first address of the propagation information storage location from the stack in the later layer, and write the evaluation result from the first address (dimension of one unit of propagation information) x
Store it at the offset position of (counter value),
At the propagation source, when performing attribute evaluations on the middle and back of the head,
The value of the propagation information storage location of any propagation source can be referenced from the current propagation information storage location start address and the counter value of the required propagation source.

For example, if the i-th child at a certain node does not belong to that subtree, the scan is interrupted immediately before the scan stage i and waits for an instruction.

In this case, if the sequential data is intermediate symbol data or end symbol data that matches the type, a restart instruction is issued and the corresponding subtree scan is restarted from the interrupted node scan stage i. Note that if there is no corresponding subtree scan, that is, if the subtree scan has already finished scanning.

Waiting for instructions again.

In the search for a primitive sequential data string, the end of processing the last data of the primitive sequential data string means the completion of the search for the primitive sequential data string for one type and the subtree scan, and if the next type exists, Purpose: To obtain the next type of sequential data by regarding the sequential data string as a primitive sequential data string.

The search for the primitive sequential data string starts from the beginning.

In addition, in the main scanning method of this embodiment, during scanning of one subtree, the type of a certain node does not match the type, so the scanning of one subtree is interrupted, and furthermore, the mark of the sequential data is an intermediate symbol or an end symbol. Therefore, when issuing a restart instruction and restarting a subtree scan that started from the intermediate symbol data at that point and the start symbol data corresponding to the end symbol data, the environment, nodes, and A location for holding information (subtree scanning information) indicating the position where subtree scanning is restarted, such as the subtree scanning stage and the scanning stage, that is, a subtree scanning information pointer, is managed in a stack structure. This subtree scan information pointer is used as information indicating the starting position of the corresponding subtree scan when instructing to restart the main scan. Therefore, when new start symbol data is reached, the subtree scan information pointer that was used up until then is pushed onto the stack.

When the terminal symbol data is reached, it is popped from the stack.

FIG. 1 is a block diagram of a tree scanning device according to an embodiment of the present invention.

The tree scanning device of this embodiment [1 is a main scanning control device 2゜initial main scanning circuit 3. Tree scanning information storage circuit 4. Tree structure storage circuit 5
．． Sequential data search circuit 62 partial water scanning management information storage circuit 72 partial tree scanning circuit 89 partial tree scanning information storage circuit 9. Sequential data read/write switching circuit 10. and sequential data storage circuits 11 and 12.

The tree structure storage circuit 5 stores tree structure data such as tree structure information 26 and attribute information 27 of each node in advance, and stores structure information such as the eldest child of a certain node and the second location, and each scanning stage of the node. For tree structure access 21.28 such as attribute information reference or update request, corresponding node information 22.29
Output.

When the main scan start signal 13 is input, the main scan control circuit 2 outputs an initial signal 17 to the sequential data output/write switching circuit 10, and further outputs a start signal 15 to the initial water scan circuit 3. 6 Further, when the type information 14 is inputted, the present scanning control circuit 2 outputs the data search circuit 6 if this input is performed after the output of the start signal 15 to the initial water scanning circuit 3, and the sequential data search circuit. Start signal 19 for 6
If the output is performed after the output of the end signal 16 ., the end signal 16 . Alternatively, when 20 is input, the switching signal 18 is output to the sequential data output/write switching circuit 10, and furthermore, the start signal 19 for the corresponding type of search is output to the sequential data search circuit 6.

When the initial signal 17 is input, the sequential data read/write switching circuit 10 allocates the sequential data storage circuit 11 as the storage location of the target sequential data string. Data storage circuit 1
1, and the read signal 36 to the sequential data read/write switching circuit 10 and the output from the sequential data reading/writing switching circuit 10. A certain channel of sequential data 37 is connected to a read signal 46 to the sequential data storage circuit 12 and a channel of sequential data 47 which is read data from the sequential data storage circuit 12, and the sequential data storage circuit 11 is connected.
In response, a reset signal 40 is output. Thereafter, each time the sequential data 25 is input, it is output as sequential data 41 written to the sequential data storage circuit 11.

Further, when the switching signal 18 is input, the sequential data read/write switching circuit 10 controls the input sequential data 25.35.
When the channel of the sequential data 41 written to the sequential data storage circuit 11 is connected, the channel of the input data 25° 35 is switched to the channel of the sequential data 45 written to the sequential data storage circuit 12. If the input data 25.35 channel is connected to the sequential data 45 channel written to the sequential data storage circuit 12, the input data 25.35 channel is connected to the sequential data storage circuit 12. 11
The channel of the sequential data 41 to be written to is switched and connected.

Furthermore, the read signal 36 and the sequential data search circuit 6
channel of sequential data 37 output to
6. When the channel of the sequential data 47 read from the sequential data storage circuit 12 is connected, the read signal 36 and the channel of the sequential data 37 output to the sequential data search circuit 6 are connected to the successive signal 42 . and sequential data channel 43 and connect to the sequential data channel.
A reset signal 44 is output to the data storage circuit 11.

Conversely, the read signal 42 and the sequential data 37 channel and the read signal 42 . and the channel of sequential data 43 are connected, the channel of successive signal 36 and sequential data 37 is switched and connected to the channel of read signal 46 and sequential data 47, and connected to sequential data storage circuit 12. , outputs a reset signal 44.

After that, the sequential data read/write switching circuit 10.

Every time the sequential data 35 is input, it is output as sequential data 42 or 46 written to the sequential data storage circuit 11 or 12 to which the channel is connected. Also, each time the successive signal 36 is input, the sequential data storage circuit 11 or 12 on the side to which the channel is connected is
is outputted as a read signal 42 or 46, and inputs sequential data 43 or 47 read from the sequential data storage circuit 11 or 12, respectively, and outputs it as output data '37.

The sequential data storage circuit 11.12 includes a storage section for sequentially arranging input data, and a pointer indicating the location of the data arranged at the end in the storage section, and receives a reset signal 40.44. Then, the pointer is set to the beginning of the storage section, and the sequential data 41 is written as write data.
．． When 45 is input, the current pointer is moved by 1 data,
Move forward and write the write data 4 to the location indicated by the pointer.
1°45 is stored, and when read signals 42 and 46 are input, sequential data 43°47 at the location indicated by the current pointer is output as read data, and the pointer is returned by one data.

These data are data composed of four fields: two types of nodes, a mark, and a first address of a propagation information storage location, or are attribute data. The node field holds the location of the node data, the type field holds the type of node, and the mark field holds the start symbol of the data.

Retains either an intermediate symbol or a terminal symbol.

Therefore, the data composed of the node field, type field, and mark field is information regarding the subtree of the type that has not yet been expanded, and the attribute data indicates the attribute information itself of the node that has already been expanded.

FIG. 2 is a flowchart of the initial sequential data string creation process of the initial main scanning circuit in one embodiment of the present invention. Note that MODE indicates the location of the current node at the time of scanning, and NODEI indicates the location of the child of the current node.

As shown in FIG. 1, the initial main scanning circuit 3 performs push and pop operations on the main scanning information storage circuit 4, and the main scanning information storage port M4 is opened by the button operation of the initial main scanning circuit 3. The save information 23 is input and accumulated at the end of the stack structure, and by pop operation of the initial main scanning circuit 3,
Extract the information at the end of the stack structure and return the return information 24
Output as .

As shown in FIG. 2, first, the main scanning control circuit 2 sends a start signal 1
5, the initial main scanning circuit 3 outputs this start signal 1.
5 is input, and the search starts from the root of the tree structure stored in the tree structure storage circuit 5.

If MODE is a child of a node that is not a propagable area for certain propagation information and is a propagation source node that refers to that propagation information (74), obtain the start address of the area that can be used as a storage location for propagation information. , this address is set as the current propagation information storage location start address 75), and if not, the propagation information storage location start address set by the ancestor is set as the current one.

If the MODE indicating the location of the current node in this main scan is the root, or if the type of MODE is different from the parent type, it is determined to be the root of the subtree60), and the current propagation information is Start symbol data including the first address of the storage location is created (61) and written into the target sequential data storage circuit 11 via the sequential data read/write switching circuit 10 (62).

Next, in order to scan the first child of descendants in order from the first child of that MODE, the current MODE, N0DEL.

The parent type and current propagation information storage location start address,
65) in the main scanning information storage circuit 4.

Reset the child information (66), 1abel 1
Returning to , it is determined whether the type of N0DE is equal to the type of the parent (60).

Also, if the root of the subtree does not exist (67
), if the end of the sequential data string is intermediate symbol data, the intermediate symbol data is deleted, and end symbol data is created and placed at the end of the sequential data string (68).

Furthermore, when returning from the child scan, the main scanning information storage circuit 4 is popped and the current information is restored (69).If there is no information to be popped, the process ends.

Also, if it is determined that the child's type is different from your own type (
70), create intermediate symbol data for that node 71), and sequentially through the data read/write switching circuit 10,
The target is written to the sequential data storage circuit 11 (72).

In this way, when writing of intermediate symbol data is completed, N
The number N0DE1 is set in 0DEI (73), the process returns to label 2, and it is determined whether MODEI is nil or not (64).

FIG. 3 is a flowchart of processing for expanding a source sequential data string into a target sequential data string in a sequential data search circuit according to an embodiment of the present invention. Note that the sequential data storage circuit 11
stores the primitive sequential data string, and the sequential data storage circuit 1
2 is assumed to store a sequential data string at the moment, and the passage through the sequential data read/write switching circuit 10 is not mentioned.

As shown in FIG. 1, the sequential data search circuit 6 performs a push operation on the subtree scanning management information storage circuit 7, and the subtree scanning management information storage circuit 7 inputs the save information 30 and creates a stack structure. is accumulated at the end of the data search circuit 6.
By pop operation.

Extract the information at the end of the stack structure and return the return information 31
Output as .

As shown in FIG. 3, first, when the sequential data search circuit 6 receives the start signal 19 from the main scanning control circuit 2, the sequential data search circuit 6 searches from the beginning of the primitive sequential data string in the sequential data storage circuit 11. Read (80, 93).

If the data to be read is empty data (81), the end signal 20 is output to the main scan control circuit 2, and the state waits for the start signal 19 from the main scan control circuit 2.

If there is data to read (81), check whether the value of the type field of that data matches the current type (
82), and if different, the data is sequentially written into the data storage circuit 12 (84).

If the value of the type field of the data matches the current type, first check the mark of the data (83)
.

If the mark field is a start symbol, the value (subtree scanning information pointer) indicating the location in the first subtree scanning information storage circuit 9 in the information for the current subtree scanning is saved as the save information 3.
0 to the subtree scanning management information storage circuit 7 85), and instructs the subtree scanning circuit 8 to start a new subtree scanning using the subtree scanning start signal 32 accompanied by the location of the node in the node field 86). , waits for the subtree scanning stop signal 34 from the subtree scanning circuit 8 (87). Note that this subtree scanning stop signal 34 is accompanied by a subtree scanning information pointer for scanning a new subtree, and the sequential data search circuit 6
temporarily holds the location of the current subtree scanning environment until it is written to the subtree scanning management information storage circuit 7.

After that, when the 1 subtree scanning circuit signal 34 is input, data is read out from the sequential data storage circuit 11 again (93
).

Furthermore, if the mark field is an intermediate symbol, the current subtree scanning information pointer 3 is sent to the subtree scanning circuit 8.
The subtree scanning restart signal 33 with 0 instructs restart of this subtree scanning 88).

It waits for the subtree scanning stop signal 34 from the subtree scanning circuit 8 (89). When the subtree scanning stop signal 34 is input in this way, data is sequentially read from the data storage circuit 11 again (93).

Furthermore, if the mark field is an end symbol, the subtree scanning stop signal from the subtree scanning circuit 8 is issued to instruct restart of the current subtree scanning, as in the case of an intermediate symbol (88, 89). 34 (91), then pops the latest subtree scanning information pointer 31 from the subtree scanning management information storage circuit 7 (92), and reads data from the sequential data storage circuit 11 again (93).

FIG. 4 is a flowchart of processing for expanding a tree structure into a target sequential data string in a subtree scanning circuit according to an embodiment of the present invention. Note that 9M0DE indicates the location of the current node at the time of scanning, MODEl indicates the location of the child of the current node, and 5TAGE indicates the scanning stage of N0DE.

As shown in FIG. 1, by the generation operation of the subtree scanning circuit 8,
The subtree scanning information storage circuit 9 inputs the generation signal 48, circulates the area corresponding to the new subtree, outputs the location (subtree scanning information pointer 49) to the subtree scanning circuit 8, and stores one part. By the push operation of the tree scanning circuit 8, the save information 38 is input, and the save information 38 is accumulated at the end of the stack structure in the area designated by the subtree scanning information pointer, and by the pop operation of the subtree scanning circuit 8. , Similarly, the information at the end of the stack structure on the designated area is extracted and output as restoration information 39.

As shown in FIG. 4, when the subtree scanning circuit 8 receives a start signal 32 accompanied by the location of the node and the first address of the propagation information storage location from the sequential data search circuit 6, the subtree scanning circuit 8 converts the first address of the propagation information storage location to the current one. The node is set as the start address of the propagation information storage location, and the tree structure in the tree structure storage circuit 5 is scanned with that node as the root. In this case, the subtree scanning circuit 8
outputs the generation signal 48 to the subtree scanning information storage circuit 9 and inputs the subtree scanning information pointer 49 (100,
101).

If N0DE is a propagation light of a certain propagation information and the first address of the propagation information storage location is assigned, this should be interpreted as the root of the propagation possible area of this propagation information.
), while saving the current propagation information storage location start address to the stack structure in the subtree scanning information storage circuit 9 (11
6), Set the propagation information storage location start address of this node as the current propagation information storage location start address (117
).

In addition, if N0DE is the propagation light of a certain propagation information, after evaluating the information, the result is transferred from the current propagation information storage location start address (dimensions of 1 unit of propagation information)
It is stored at a position incremented by (counter value of the node) (119).

If the type of MODE is different from the relevant type (102), the subtree scanning stop signal 3 accompanied by the subtree scanning information pointer
4 is output to the sequential data search circuit 6 and the operation is interrupted (103). When the subtree scan restart signal 33 is input from the sequential data search circuit 6, the subtree scan resume signal 33 is output to the sequential data search circuit 6. The scanning information pointer is set as a pointer indicating the current area on the subtree scanning information storage circuit 9, and the operation is restarted (104).

Also, if the type of MODE matches the relevant type (10
2) Write the attribute of N0DE at 5TAGE=O as sequential data 50 to the sequential data storage circuit 12 (106, 106), and further.

The first child of MODE is set in N0DEI (107).

If N0DEI is not n1lt'(108'), N0D
Currently (
7) Push MODE, N0DEI, and 5TAGE into the current area of the subtree scanning information storage circuit 9.
9), reset the child information (110), and again, 1
Returning to abel 1, it is determined whether the type of MODE matches the current type (102).

If N0DE is nil (108), when returning from child operation, pop from the current area on the subtree scanning information storage circuit 9 and restore the current information (111).
.

In this case, if there is no data to pop (112), scanning of this subtree is completed, the area indicated by the 1 partial main scanning information pointer is abandoned, and a subtree scanning stop signal 34 is sent to the sequential data search circuit 6. Output subtree scanning start signal 3
2. Alternatively, it waits for the subtree scanning restart signal 33.

Also, if there is return information 39 (112), its 5TAG
Own add E (113), write sequential data 50 indicating the attribute of N0DE in that 5TAGE to the sequential data storage circuit 12 (114), set NoDEL to N0DEL in order to perform the second scan, and write (11
5), again.

Return to 1abel 2 and check whether MODE is nil (108). If the area indicated by the subtree scan information pointer accompanying the subtree scan restart signal 33 has already been abandoned, execute one or more processes. It outputs the subtree scanning stop signal 34 without doing anything, and waits for the subtree scanning start signal 32 or the subtree scanning restart signal 33.

〔Effect of the invention〕

According to the present invention, in the main scan for processing tree-structured data, if it is impossible to process nodes in the order in which they are scanned and multiple scans are required, in each scan, the target node Since only the periphery of the image is scanned, processing efficiency can be improved.

In addition, even if the information required to process each node cannot be stored all at once, it is not possible to handle the problem with multiple scans. Nodal processing results can be obtained.

At this time, since it has a mechanism for propagating a specific attribute value of a certain node to the ancestors of that node, it can also be applied to the main scan that involves the propagation of composite attributes.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of a tree scanning device according to an embodiment of the present invention, FIG. 2 is a flowchart of an initial sequential data string creation process of an initial tree scanning circuit according to an embodiment of the present invention, and FIG. 3 is a block diagram of a tree scanning device according to an embodiment of the present invention. FIG. 4 is a flowchart of an expansion process from a source sequential data string to a target sequential data string according to an embodiment of the present invention; FIG. The figure is an explanatory diagram of nodes and subtrees in one embodiment of the present invention. Fig. 6 is an explanatory diagram of a sequential data string in an embodiment of the present invention, Fig. 7 is an explanatory diagram of a propagable area, Fig. 8 is an explanatory diagram of operations on tree-structured data, and Fig. 9 is a subtree and propagation diagram. A related explanatory diagram of possible regions, FIG. 10 is an explanatory diagram of a tree structure. 1... Tree scanning device, 2... Main scanning control circuit, 3...
・Initial tree scanning circuit, 4...Main scanning information storage circuit, 5.
...Tree structure storage circuit, 6...Sequential data search circuit, 7
... Subtree scanning management information storage circuit, 8... Subtree scanning circuit, 9... Subtree scanning information storage circuit, 10...
Sequential data output/write switching circuit, 11.12... Sequential data accumulation circuit, 13... Main scan start signal, 14...
・Type information. 15.19...Start signal, 16.20...End signal. 17...Initial signal, 18...Switching signal, 21.28
...Tree structure access, 22.29...Node information, 2
3゜30.38...Evacuation information, 24,31,39...
・Return information, 25, 35, 37, 41, 43, 45°4
7.50... Sequential data, 26... Tree structure information, 2
7... Attribute information, 32... Subtree scanning start signal, 3
3... Subtree scanning restart signal, 34... Subtree scanning stop signal, 36, 42, 46... Read signal, 40° 44
...Reset signal, 48...Generation signal 5.49...
・Subtree scanning information pointer, 200...Tree structure, 20
1 Rin 5 Zu Mourning) Yesterday, Se, Me 1 book (Su type 1' J) PELT +7: iq f=
Ljri7A, B, C field, g, , Shabetsu stone play 6 Fertilization (shi) Kaya 6 Figure (dunuL> (A(C(B),βC14,C,A)n)(tonn6(
ump r honbuki lotus paste

Claims (1)

[Claims] 1. A means for storing tree structure data composed of nodes is provided, and if i is an integer greater than or equal to 1 and less than or equal to the total number of children of the node, the node is stored before scanning the first child of the node. , or has an attribute indicating the scanning stage in the tree structure that is after the scanning of the i-th child, and a type that defines the evaluation order of the attribute for each node, and When performing the process of sequentially arranging the evaluation results of the corresponding attributes in memory in depth-first search order according to the evaluation order of the attributes, the attributes held by a certain node are compared to the attributes of the ancestors of the node. In the tree scanning device that needs to be referenced in the evaluation, the memory is composed of two memories, the types are the same, and the connected node group is recognized as a subtree,
In addition, a propagation source node that generates propagation information that is a propagation target is taken as a leaf, and a set of paths connecting this node and propagation destination nodes that refer to the propagation information that no longer refer to the propagation information in their ancestors is defined as It is recognized as a propagable area related to the propagation information, secures a propagation information storage location for the number of propagation source nodes in the area for each area, stores the location information at the root of the propagable area, and stores the location information at the root of each subtree. When scanning, a symbol indicating that the subtree is at the start position and an end position of the subtree holding the propagation information storage location information held by the root of the propagable area of the nearest ancestor of the root, and a symbol indicating that it is at the end position, Each leaf of the subtree is arranged sequentially in the order of the first and second order, and a symbol indicating that it is located in the middle of the subtree is placed in each leaf of the subtree.
Upon returning from scanning a child of a type different from this type, the 2
means for sequentially arranging data strings in one of the memories; a first processing means for searching data strings sequentially arranged for each type; The start symbol, the middle symbol, and the end symbol of the tree are
When the start symbol of the subtree belonging to the type is found, the start of scanning of the subtree is instructed, and when the intermediate symbol and the end symbol are found, the subtree is copied to the other of the two memories. means for performing a second process for instructing resumption of scanning, and scanning the subtree belonging to the type according to the instruction from the second processing means, and storing the attributes of the subtree in the other of the two memories. a third means for performing a process of expanding;
The processing means develops the sequential data string in the one memory, the second processing means searches for the sequential data string, and the third processing means receives the start instruction from the second processing means. , starts scanning the subtree, and when a node of a type different from the type is detected, the scanning is temporarily interrupted, and the second processing means again reads the sequential data string stored in the one memory. The third processing means searches for the second
restarting the subtree scanning according to the restart instruction from the processing means;
In parallel with the scanning, the attributes of the subtrees belonging to the type are
A tree scanning method characterized by performing a process of expanding onto the other memory.