Method in a structure editor5493678Abstract The present invention relates to a method for providing improved editing capability in a structure editor, and more particularly for syntax-directed editors. A set of methods provide an approach to selecting arbitrary nodes from within a tree, and using those arbitrarily selected groups of nodes in otherwise conventional editing operations such as move, copy, delete, collect, and the like. In syntax-directed editors, the present invention provides a way of maintaining syntax while these novel and highly flexible editing operations are performed. Claims We claim: Description BACKGROUND OF THE INVENTION
______________________________________
scopeSubtree
given a node (e.g. indicated by the pointing
device), add it and all its descendents to
the set of nodes that makes up the scope; if
the given node was in the scope set to begin
with, however, remove it and its children
from the scope set.
scopeNode given a node, add it to the scope; if it was
already in the scope set, remove it from the
set instead.
scopeRange
given two nodes, find the smallest sequence
of siblings (siblings are nodes that share a
common parent and one is the next node after
the other in the sequence of nodes under that
parent), including the subtrees under that
sequence that contains the two nodes and, if
the first node of the two was previously in
the scope set then remove that sequence of
subtrees from the scope set, otherwise add it
to the set.
______________________________________
The generalized target of the preferred embodiment is specified as a node and a relationship to that node. The scope is copied or moved to the target and inserted according to the specified relationship. The relationships are:
______________________________________
Left As a sibling of the target node.
Right As a sibling of the target node.
Around As the parent of the target node.
Within As a child of the target node, such that all
the the target nodes children are now
children of the new node(s).
______________________________________
The method of the preferred embodiment of the present invention provides for move, copy, insert, and delete operations given an arbitrary set of nodes (the scope), and (for move, copy and insert) also provides specification of a generalized target. The generalized target allows for making complex changes to the tree in one natural step that, under prior art methods, required two steps. The generalized scope allows very powerful editing operations that may be considered intuitive and yet required many counter-intuitive operations in other methods. A concept involved in the preferred embodiment is that of nodes being simply connected. A group of nodes is simply connected if simple connections exist between the nodes such that by starting at one node all other nodes can be reached by crossing one or more simple connections. A simple connection is a pointer from one node to another. At the highest level, the method involves breaking move, copy, insert, and delete into the following three steps: 1. Collect Subtrees: collect the list of subtrees that can be made from the scope, 2. Delete: delete the nodes that make up the scope, and 3. Paste: paste the list of subtrees at the target location. The paste operation uses the generalized target, while the collecting of subtrees and deletion of scoped nodes involves flexible scoping. Basic move, copy, delete, and insert operations are performed by combining one or more of the above steps. These basic operations are best demonstrated through examples illustrated by the figures. FIG. 2a shows a tree 200 with eight nodes (202, 204, 206, 208, 210, 212, 214, 216) selected for inclusion in the scope of a subsequent operation. (These scoped nodes are indicated by an asterisk.) Collecting the scope produces the three element list of subtrees shown in FIG. 2b (220, 222, 224); where the prime (e.g. G2'and 216') indicates that this is a copy of the original node. (When the collect and delete operations are combined into one step, the actual nodes are collected rather than copied.) Deleting the scope results in the structure 230 shown in FIG. 3. Selecting element E2 209 in FIG. 3 as the node and "Around" as the relationship of a generalized target, pasting the scope according to the generalized target results in the structure 232 shown in FIG. 4. The end result of a Collect Subtrees, combined with a Delete, followed by a Paste is a move of the scoped nodes, maintaining their relative ordering in both dimensions (ancestorhood and left to right sibling relations), to the target location. If the Delete is not done, the result is a copy operation. If only the Delete is done, then a delete operation is the result. Finally, if a node is created external to the tree (not based on the scope) and then Pasted, the result is an insert of that node into the tree. The preferred embodiment of a flexible scope editing method according to the present invention will now be described. The description presents a specification language used in the disclosure of the steps of the method. This is followed by a description of utility functions or methods used by the preferred embodiment, base functions, based on the utility functions, and main functions describing the principle steps of the method for flexible scope editing. Following the main functions is the description of an extension to the preferred embodiment incorporating syntax rules and syntax checking for valid structures. A description of the utility functions, data, base functions and main functions of this extension to the preferred embodiment are then described. In particular, the main functions of the extension provide graft and replace functions that ensure all syntax rules are observed. 2. Specification Language A simple specification language is used throughout this document for illustrating detailed steps of the present invention. Functions implementing the present invention are presented including a description of the function, definition of the inputs and outputs of the function, and method steps necessary to perform the function. This language allows the following statements:
______________________________________
assignment
Simple assignments of the form x = y are
allowed.
If/Otherwise
A test is phrased in English together with
standard relationship operators like "=,"
"<=" . . . If the test results are true, the
statements in the if clause are executed. If
the test result is false, the statements in
the Otherwise clause are executed.
Case Expression of
A choice is made between several mutually
exclusive values of an expression. The
statements under the value that matches the
expression are executed.
While Execute a number of statements for as long as
a certain condition is true.
Return Returns from a subroutine successfully.
Fail Returns from a subroutine unsuccessfully.
Returns changes made in the routine to the
condition they were in on entry.
______________________________________
Unless success or failure is explicitly tested for, a routine that fails implies that the calling routine fails as well. If success or failure is explicitly tested for, then alternative processing based on the state tested will occur when a specific call fails. Comments are enclosed in square brackets. Variables need not be declared, and are not considered to be initialized to any particular value. Variables have a type (integer vs. string, for example) associated with them by the way they are used. Subroutines are specified as having a name and input or output parameters with the parameters enclosed in parentheses following the same. Subroutines may have the same name as other subroutines and are distinguished by the type and number of parameters provided to the subroutine. 3. Utility Functions Used in the Preferred Embodiment It is assumed that the following basic operations are available to implement the preferred embodiment and are provided, for example, by conventional utility functions: I. Functions for manipulating trees. Tree manipulation is a well understood field, as long as the operations are restricted to the simple ones listed here:
______________________________________
graft Insert a list of subtrees as "leaves" of
a node, after a specific child of that
node (the null child indicates that the
operation is to be done before the first
child). This operation may fail due to
syntax checking in a syntax-directed
editor. The method of the preferred
embodiment is designed so that if graft
checks syntax, the method will build
syntactically correct trees. The method
will work, however, whether graft checks
syntax or not.
(An extension of the preferred
embodiment which provides a method of
checking syntax within a graft operation
is presented below, after description of
the move, copy, insert and delete
operations of the preferred embodiment.)
replace Disconnect an inclusive range of
subtrees from a given parent node, and
then replace it with a list of subtrees.
Replace may fail due to syntax checking
in a syntax directed editor. The method
is designed so that if replace checks
syntax, the method will build
syntactically correct trees. The method
will work, however, whether replace
checks syntax or not.
(A method of checking syntax within a a
replace operation is presented below,
after description of the move, copy,
insert and delete operations of the
preferred embodiment.)
copyNode Form a new childless node that is
identical to a given node.
destroyNode Mark a node so that is can be destroyed
at the end of a delet operation.
The method does not make assumptions
about the fate of children of a
destroyed node.
createNode Create a childless node of a given type.
In a simple structured editor all nodes
are of the same type.
copySubtree Create a new subtree that is identical
to a given subtree.
destroySubtree
Mark all nodes in a subtree so that they
can be destroyed at the end of a delete
operation.
getParent Return the parent node of a given node
or null if the node has no parent.
getFirstChild
Return the first child of a given node,
or null if the node is childless.
getLastChild
Return the last child of a given node,
or null if the node is childless.
getRightSibling
Return the right hand sibling of a
node, or null if the node is the last
child of its parent.
getLeftSibling
Return the left hand sibling of a node,
or null if the node is the first child
of its parent.
getFirstLeaf
Given a subtree, return the first leaf
(childless node) within that subtree.
Return null if the root of the subtree
has no children.
getNextLeaf Given a subtree and a leaf node, return
the next leaf node in that subtree, or
null if there are no further leaves
around.
getSubtreeNodes
Add to a set the nodes within a
subtree.
______________________________________
II. Functions for manipulating sets, specifically sets of nodes.
______________________________________
create Create a new empty set.
copy Create a new empty set that is a copy of
some existing set.
destroy Remove an existing set completely.
insert Insert an item into the set.
delete Delete an item from the set.
query Determine if an item is in a set.
makeEmpty Make a given set empty.
isEmpty Determine if a given set is empty.
getFirst Return an item in the set. May be any
arbitrary item.
getNext Given an item, return an arbitrary item
in the set that hasn't been returned
since the last getFirst. If there are
none left, then return null.
difference Remove from one set those elements which
it has in common with a second set.
______________________________________
III. Functions for manipulating lists of items, specifically lists of subtrees.
______________________________________
create Create a new empty list.
destroy Destroy a list completely.
append Add an item to the end of a list.
prepend Add an item to the beginning of a list.
getFirst Return the first item on the list.
getNext Given a list and an item in the list,
return the next item in the list, or
null if the item given is the last.
______________________________________
4. Base Function Definitions Definitions of subroutines used to describe the steps of the method of the preferred embodiment of the present invention follow. I. findFirstScoped(root, scope, scopeUnder, node): Given the root of a subtree (the top-most node in that subtree), a set of node identifiers indicating the nodes in the scope, a set of node identifiers indicating which nodes have descendants that are in the scope, return the first node in the subtree that is contained in the scope, where "first" in this case is recursively defined as the leftmost child of the root of the given subtree if that child is in the scope, or if not, the first scoped node in the leftmost subtree of the root of the given subtree, or if there is none, apply the preceding tests to the remaining children of the root of the given subtree, and if no children remain before the first scoped node is discovered then there is no scoped node below the root of the given subtree. Returning to the previous example, described with reference to FIGS. 2-4, the scope set is B1, B3, C2, E1, F1, F2, G1, and G2 (nodes 202, 204, 206, 208, 210, 212, 214, 216). The scopeUnder set (those nodes which have descendents in the scope set) contains A1, B1, B3, B4, C2 and D2 (nodes 201, 202, 204, 205, 206, 213). The function findFirstScoped given B1 202 as the root of the subtree, returns C2 206 as the first scoped node. If B2 203 is specified as the root, the function returns null (there are no scoped nodes below B2). If B3 204 is specified, the function returns G1 214.
______________________________________
Inputs:
root The node under which the first node in the
scope is desired
scope The set of nodes that are in the scope
scopeUnder The set of nodes that are parents of scoped
nodes
Outputs:
node The first scoped node according to the
definition.
______________________________________
Method 1. If query(scopeUnder,root) is true [there are scoped nodes under the root] a. child=getFirstChild(root) b. While child is not null [there are still children to look under] 1) If query(scope,child) is true [the child is in the scope] a) node =child [child is the first scoped node] b) return 2) Otherwise [the child is not in the scope, so find the first scoped node under it] a) findFirstScoped(child, scope, scopeUnder, node) [find the first scoped node under the child] b) If node is not null [we found a scoped node] i. Return [node is the first scoped node under root, so we're done] c) Otherwise [didn't find the first node under this child of root] i. child=getRightSibling(child) [try next child of root] c. node=null [couldn't find a first child anywhere] d. Return. 2. Otherwise [there aren't any scoped nodes under this one] a. node=null [No first subtree under that node] II. findNextScoped(root, scope, scopeUnder, prev, node): Given the root of a subtree, a scope set, a scopeUnder set, and a previous node, return the next scoped node under that root. Assuming the example tree in FIG. 2a, given root B1 202 and the previous node C2 206, the next node is null. Given root B3 204 and previous node G1 214, the next node is G2 216.
______________________________________
Inputs:
root The node under which the next node in the
scope is desired
scope The set of nodes that are in the scope
scopeUnder
The set of nodes that have scoped nodes
beneath them
prev The node that we want to find the next scoped
node after
Outputs:
node The next scoped node according to the
definition
______________________________________
Method 1. While prev is different from root [there must be something more to search for] a. rsib=getRightSibling(prev) b. While rsib is not null [there are still siblings to try] 1. If query(scope,rsib) is true [the sibling is in the scope] a) node=rsib [sibling is the next scoped node] b) Return 2. Otherwise [the sibling is not in the scope, so find the first scoped node under it] a) findFirstScoped(rsib, scope, scopeUnder,node) [find the first scoped node under the sibling] b) If node is not null [found a scoped node] i. Return [node is the next scoped node under root after prev, so we're done] c) Otherwise [didn't find the first node after this sibling of prev] i. rsib=getRightSibling(rsib) [try next sibling] c. prev=getParent(prev) [couldn't find a first child anywhere next to prev, so try prev's parent] 2. node=null [reached root without finding a scoped node, so there can't be any after prev] 3. Return III. getFirstSubtree(root,scope,scopeUnder,compSubtrees,sub,top): Given a root node for a subtree, a scope set, a scopeUnder set, and a completely scoped subtrees set, return a new copy of the first collected subtree formed of all the scoped nodes under root, and the top node identifier in the original tree of the subtree that was copied. Assuming the example tree in FIGS. 2a and 2b, given B1 202, return the new "sub"tree starting with C2 206' and C2 206.
______________________________________
Inputs:
root The node under which the first scoped subtree
is desired
scope The set of nodes that are in the scope
scopeUnder
The set of nodes that have scoped nodes
beneath them.
compSubtrees
The set of nodes whose subtrees are made up
entirely of scoped nodes.
Outputs:
sub The first new subtree found
top The old node that is the top of the first
scoped subtree
______________________________________
Method 1. findFirstScoped(root,scope,scopeUnder,top) [grab the top of the first subtree] 2. If top is null [didn't find a scoped node, so there can't be any subtrees] a. sub=null [no subtree] b. Return 3. Otherwise [found a top for the subtree, so collect the subtrees underneath it] a. If query(compSubtrees,top) [see if a complete subtree is scoped] 1) copySubtree(top,sub) [copy a complete subtree] b. Otherwise [the entire subtree under top is not scoped. Collect the pieces of the subtree that are scoped] 1) sub=copyNode(top) [make a new copy of the top scoped node] 2) create(list) [get a list to collect the subtrees into] 3) addSubtrees(top, scope, scopeUnder, compSubtrees, list) 4) If isEmpty(list) [no subtrees to collect] a) Return [sub is all the subtree there is] 5) Otherwise a) graft(sub, null, list, status) [put the list of subtrees onto sub as the first bunch] b) destroy(list) [don't need the list anymore] c) Return IV. getNextSubtree(root,scope,scopeUnder,compSubtrees,Prev,sub, top): Given a root node for a subtree, a scope set, a scopeUnder set, a completely scoped subtrees set, and a previous node identifier return a new copy of the next collected subtree formed of all the scoped nodes under root after prev, and the top node identifier in the original tree of the subtree was copied. Assuming the example tree in FIGS. 2a and 2b, given B3 as root and G1 214 as prev, the routine returns the new "sub"tree starting with G2 216', and G2 216. Or, given B1 202 as root and C2 206 as prev, the routine returns null as the subtree and as top.
______________________________________
Inputs:
root The node under which the first scoped subtree
is desired
scope The set of nodes that are in the scope
scopeUnder
The set of nodes that have scoped nodes
beneath them
compSubtrees
The set of nodes whose subtrees are made up
entirely of scoped nodes
prev The node that is the top of the previous
subtree
Outputs:
sub The next new subtree found after prev
top The old node that is the next scoped subtree
top after prev
______________________________________
Method 1. findNextScoped(root, scope,scopeUnder,prev,top) [grab the top of the next subtree] 2. If top is null [didn't find a scoped node, so there can't be any subtrees left] a. sub=null[no subtree] b. Return 3. Otherwise [found a top for the subtree, so collect the subtrees underneath it] a. If query(compSubtrees,top) [see if a complete subtree is scoped] 1) copySubtree(top,sub) [copy a complete subtree] b. Otherwise [the entire subtree under top is not scoped. Collect the pieces of the subtree that are scoped] 1) sub=copyNode(top) [make a new copy of the top scoped node] 2) create(list) [get a list to collect the subtrees into] 3) addSubtrees(top, scope, scopeUnder, compSubtree, list) 4) If isEmpty(list) [no subtrees to collect] a) Return [sub is all the subtree there is] 5) Otherwise a) graft(sub, null, list, status) [put the list of subtrees onto sub as the first bunch] b) destroy(list) [don't need the list anymore] c) Return V. addSubtrees(root,scope,scopeUnder,compSubtrees, list): Given a root node for a given subtree, a scope set, a scopeUnder set, a completely scoped subtrees set, and a list of subtrees, append to the list the subtrees under root that are collected from the nodes that are scoped. Assuming the example tree in FIGS. 2a and 2b, given B1 202 and an empty list, the routine returns the list containing the subtree topped by C2 206'. Given B2 203 and an empty list, it returns the empty list. Given B3 204 and an empty list, it returns the list containing G1 214' and G2 216'.
______________________________________
Inputs:
root The node under which the subtrees are to be
collected
scope The set of nodes in the scope
scopeUnder
The set of nodes that have scoped nodes
beneath them
compSubtrees
The set of nodes whose subtrees are made up
entirely of scoped nodes
list The list to which the new subtrees are added
Outputs:
list The list to which the new subtrees are added
______________________________________
Method 1. getFirstSubtree(root, scope, scopeUnder, compSubtrees, sub, top) [grab the top of the first subtree] 2. While sub is not null [there are still some subtrees left] a. append(list, sub) [add the subtree to the list] b. getNextSubtree(root, scope, scopeUnder, compSubtrees, top, sub, top) [get the next subtrees to add] VI. buildScopeUnder(scope,scopeUnder): Given a scope set, return the set of nodes that have scoped nodes beneath them. See the example under findFirstScoped for sample inputs and outputs.
______________________________________
Inputs:
scope The set of nodes that are in the scope
Outputs:
scopeUnder The set of nodes that have scoped nodes
beneath them
______________________________________
Method 1. node=getFirst(scope) [pick a node from the scope] 2. While node is not null [there are still nodes in the scope] a. parent=getParent(node) b. While parent is not null and the query(scopeUnder,parent) is not true [there are parents left to add that haven't been added before] 1) insert(scopeUnder,parent) [add the node to the set] 2) parent=getParent(parent) [get the next parent to add] c. node=getNext(scope) [next arbitrary node to pull from the scope] VII. collectTrees(tree,scope,compSubtrees,list): Given the root node of a complete tree, a set of node identifiers that are in the scope, and a set of completely scoped subtrees, return a list of copied subtrees collected from the nodes in the scope. Assuming the example tree in FIGS. 2a and 2b, given the tree based off node A1 201, and the set containing B1 202, B3 203, C2 206, E1 208, F1 210, F2 212, G1 214, and G2 216 as the scope, the routine returns the list containing subtrees 202, 222, 224, below nodes B1' 202, B3' 204 and E1' 208, in that order
______________________________________
Inputs:
______________________________________
tree The root of the tree from which to collect
the subtrees
scope The set of nodes in the scope
compSubtrees
The set of nodes whose subtrees are made up
entirely of scoped nodes
list The list to which the new subtrees are added
______________________________________
Method 1. Create(scopeUnder) [create a set to hold the nodes that have a scoped node under them] 2. buildScopeUnder(scope,scopeUnder) [create the scopeUnder set] 3. addSubtrees(tree, scope, scopeUnder, compSubtrees, list) [get the subtrees into the list] VIII. deleteConnected(node,scope,compSubtrees,list): Given a node that is scoped in a tree, a set of scoped node identifiers, a set of completely scoped subtrees, and a list of subtrees, delete the scoped nodes that are connected to the identified node, and the node itself, return the scope set minus the nodes that were deleted, and append any orphan subtrees to the list (an orphan subtree is a subtree whose parent has been deleted). Assuming the example tree 200 in FIG. 2a, given node B1 202, the routine deletes B1 202, C2 206, F1 210, and F2 212, and return the list unchanged. Given node B3 204, the routine deletes B3 204, and adds nodes D1 211 and D2 213 to the end of the list.
______________________________________
Inputs:
node The node from which to start deleting
scope The set of nodes in the scope
compSubtrees
The set of nodes whose subtrees are made up
entirely of scoped nodes
list The list to which are added the subtrees left
after the scoped nodes are deleted
Outputs:
scope The set of nodes in the scope
list The list to which are added the subtrees left
after the scoped nodes are deleted
______________________________________
Method 1. If query(compSubtrees,node) [see if a complete subtree is scoped] a. If getFirstChild(node) is null [see if the subtree consists only of the node] 1) delete(scope, node) [the node has no children. Remove it from the scope using a simple delete] 2) destroyNode(node) b. Otherwise [there is more than one node in the subtree] 1) create(subtreeNodes) [create a set to hold the nodes in the subtree] 2) getSubtreeNodes(node, subtreeNodes) [get the set of nodes within the subtree] 3) difference(scope, subtreeNodes) [remove the nodes from the scope] 4) destroy(subtreeNodes) 5) destroySubtree(node) [delete the subtree] 2. Otherwise a. delete(scope, node) [remove this node from the scope] b. child=getFirstChild(node) [get the child of node] c. While child is not null [there are still children left] 1) If query(scope, child) is true [child is in the scope] a) deleteConnected(child, scope, compSubtrees,list) [recurse to delete the nodes connected to the child and add to list] 2) Otherwise [child is not in the scope] a) append(list,child) [add the leftover node to the leftover node list] 3) child=getRightSibling(child) [get the next child] d. destroyNode(node) [destroy the deleted node] IX. deleteTrees(tree,scope,compSubtrees): Given the root of an entire tree, a set of scoped node identifiers to attempt to delete, and a set of completely scoped subtrees, delete the nodes identified in the scope set from the tree, and return the empty set.
______________________________________
Inputs:
tree The root of the tree from which to delete
scope The set of nodes in the scope
compSubtrees
The set of nodes whose subtrees are made up
entirely of scoped nodes
Outputs:
scope The set of nodes that are left in the scope
(none following a delete)
______________________________________
Method 1. create(orphanList) [create the list for the children of deleted nodes] 2. While isEmpty(scope) is not true [there are still nodes to delete] a. node=getFirst(scope) [get a node to start with] b. parent=getParent(node) [get the parent node] c. While parent is not null and then query(scope, parent) is true [ascend to top of nodes to delete] 1) node=parent [node wasn't the topmost] 2) parent=getParent(node) d. If parent is null [the root was scoped and to be deleted] 1) Fail [it is illegal to delete the root, so fail] e. lastToReplace=getLastChild(parent) f. while not query(scope, lastToReplace) [find the last child that is scoped] 1) lastToReplace=getLeftSibling(lastToReplace) g. firstToReplace=getFirstChild(parent) h. while not query(scope, firstToReplace) [find the first child that is scoped] 1) firstToReplace=getRightSibling(firstToReplace) i. child=firstToReplace j. prevChild=null k. While prevChild not lastToReplace [loop through the range between the first scoped child and the last scoped child of parent. Delete nodes in scope and collect orphaned subtrees that must be adopted by parent] 1) if query(scope,child) [see if the child is scoped] a) deleteConnected(child, scope, compSubtrees,orphanList) [delete scoped nodes under child and including child. Collect orphaned subtrees] 2) Otherwise [the child is not scoped] a) append(orphanList,child) [add the child to the list of nodes that will replace the range of nodes between firstToReplace and lastToReplace] 3) prevChild=child 4) child=getRightSibling(child) l. replace(parent, firstToReplace, lastToReplace, orphanList, status) [replace the nodes between firstToReplace and lastToReplace with the nodes in orphanList] m. makeEmpty(orphanList) [clean up the list of orphans] 3. destroy(orphanList) X. removeScoped(root, scope, scopeUnder, compSubtrees, unremovedList): Given a scoped root node for a given subtree, a scope set, a scopeUnder set, a completely scoped subtrees set, and a list of unremoved subtrees, append to the list of unremoved subtrees any subtrees under root which are not removed, and remove all scoped nodes under root from the tree 200. Assuming the example tree in FIG. 2a, given B1 202 and an empty unremoved list, the routine returns C1 207 in the unremoved list and removes B1 202, C2 206, F1 210, and F2 212. Given B3 204 and an empty removed list, it returns D1 211 and D2 213, and removes B3 204, G1 214, and G2 216.
______________________________________
Inputs:
root The node under which scoped nodes are to be
removed
scope The set of nodes that are in the scope
scopeUnder The set of nodes that have scoped nodes
beneath them
compSubtrees
The set of nodes whose subtrees are made up
entirely of scoped nodes
unremovedList
The list to which unremoved subtrees are
added
Outputs:
scope The set of nodes in the scope
unremovedList
The list to which the new unremoved subtrees
have been added
______________________________________
Method 1. Ifquery(compSubtrees, root) [see if the entire subtree is scoped. If so, only update the scope] a. if getFirstChild(root) is null [see if the subtree consists only of root] 1) delete(scope, root) [the root has no children. Remove it from the scope using a simple delete] b. Otherwise [there is more than one node in the subtree] 1) create(subtreeNodes) [create a set to hold the nodes in the subtree] 2) getSubtreeNodes(root, subtreeNodes) [get the set of nodes within the subtree] 3) difference(scope, subtreeNodes) [remove the nodes from the scope] 4) destroy(subtreeNodes) 2. Otherwise a. delete(scope, root) [remove this node from the scope] b. create(removedList) [create a list that will hold subtrees that have been removed under root. After these subtrees have been collected, they will be connected to root] c. lastToReplace=getLastChild(root) d. while lastToReplace not null and then query(scope, lastToReplace) [find the last child that is not scoped] 1) lastToReplace=getLeftSibling(lastToReplace) e. If lastToReplace not null [lastToReplace will be null if all children are scoped, in which case, no children will be replaced] 1) firstToReplace=getFirstChild(root) 2) while query(scope, firstToReplace) [find the first child that is not scoped] a) firstToReplace=getRightSibling(firstToReplace) f. child=getFirstChild(root) g. replaceRange=false h. While child not null 1) If query(scope, child) [see if child scoped] a) removeScoped(child, scope, scopeUnder, compSubtrees, unremovedList) [recurse to remove connected scoped nodes] b) If replaceRange=true [see if within the range of children that are being replaced] i. append(removedList, child) [the child should be connected to root when all done. Add it to the list of children that will be reconnected] 2) Otherwise a) if child=lastToReplace i. replaceRange=false [no longer in the range of children that will be replaced] b) Otherwise i. replaceRange=true [in the range of children that needs to be replaced] c) If query(scopeUnder, child) [see if descendants of child are scoped] i. removeSubtrees(child, scope, scopeUnder, compSubtrees, removedList) [remove scoped nodes and collect removed subtrees to be connected to the root] d) append(unremovedList, child) [since the child isn't removed, add it to the list of unremoved subtrees] 3) child=getRightSibling(child) [handle next child] i. If lastToReplace not null [only do the replace if root has at least one unscoped child] 1) replace(root, firstToReplace, lastToReplace, removedList) [replace the children of root with the list of removed nodes, thus creating a removed subtree] j. destroy(removedList) XI. removeimmediate(root, firstScopedChild, scope, scopeUnder, compSubtrees, list): Given an unscoped root node that has scoped children, the first scoped child of the root, a scope set, a scopeUnder set, a completely scoped subtrees set, and a list of subtrees, append to the list the subtrees under root that are collected from scoped nodes below and to the right of the first scoped child, and remove the scoped nodes from under root. Assuming the example tree 200 in FIG. 2, given A1 201, B1 202 and an empty list, the routine returns the list containing B1 202, B3 204, and E1 208, and delete B1 202, B3 203, C2 206, E1 208, F1 210, F2 212, G1 214, and G2 216. Given D2 213, G1 214 and an empty list, return the list containing G1 214 and G2 216, and delete G1 214 and G2 216 from the tree.
______________________________________
Inputs:
root The node from under which the subtrees
are to be removed
firstScopedChild
The firstScopedChild below root that is
scoped
scope The set of nodes that are in the scope
scopeUnder The set of nodes that have scoped nodes
beneath them
compSubtrees
The set of nodes whose subtrees are made up
entirely of scoped nodes
list The list to which the new subtrees will be
added
Outputs:
scope The set of nodes that are in the scope
list The list to which the new subtrees have been
added
______________________________________
Method 1. create(unremovedList) [create a list which will hold subtrees that will not be removed from the tree, but that must be collected] 2. lastToReplace=getLastChild(root) 3. while not query(scope, lastToReplace) [find the last child that is scoped] a. lastToReplace=getLeftSibling(lastToReplace) 4. child=firstScopedChild 5. replaceRange=false 6. while child not null [loop through children. Remove scoped nodes under each child] a. If query(scope, child) [child is scoped?] 1) if child=lastToReplace a) replaceRange=false [no longer in the range of children that will be replaced] 2) Otherwise a) replaceRange=true [in the range of children that needs to be replaced] 3) removeScoped(child, scope, scopeUnder, compSubtrees, unremovedList) [remove the scoped node, and all of its scoped descendants. Append all unremoved subtrees to the list] 4) append(list,child) [add child to the list of removed subtrees] b. Otherwise 1) If query(scopeUnder, child) [child has scoped descendants?] a) removeSubtrees(child, scope, scopeUnder, compSubtrees, list) [remove the scoped descendants] 2) If replaceRange=true [see if in the range of children that is being replaced] a) append(unremovedList, child) [reinsert this child under the parent once done removing children] c. child=getRightSibling(child) [handle next child] 7. replace(root, firstScopedChild, lastToReplace, unremovedList) [replace the range of children which contained scoped children with all unremoved subtrees from that range] 8. destroy(unremovedList) XII. removeSubtrees(root, scope, scopeUnder, compSubtrees, list): Given an unscoped root node for a given subtree, a scope set, a scopeUnder set, a completely scoped subtrees set, and a list of subtrees, append to the list the subtrees under root that are collected from scoped nodes, and remove the scoped nodes from under root. Assuming the example tree 200 in FIG. 2, given B2 203 and an empty list, the routine returns an empty list. Given D2 213 and an empty list, it returns a list containing G1 214 and G2 216, and deletes G1 214 and G2 216 from the tree.
______________________________________
Inputs:
root The node from under which the subtrees are to
be removed
scope The set of nodes that are in the scope
scopeUnder
The set of nodes that have scoped nodes
beneath them
compSubtrees
The set of nodes whose subtrees are made up
entirely of scoped nodes
list The list to which the new subtrees will be
added
Outputs:
scope The set of nodes that are left in the scope
(none following a remove)
list The list to which the new subtrees have been
added.
______________________________________
Method 1. getFirstScoped(root, scope, scopeUnder, top) [grab the top of the first subtree] 2. While top is not null [there are still some subtrees left] a. parent=getParent(top) b. removeImmediate(parent, top, scope, scopeUnder, compSubtrees, list) [remove remaining scoped descendants of parent and update list] c. Otherwise 1) getNextScoped(root, scope, scopeUnder, parent, top) [get the next subtree to add, start searching at parent because top (along with all other scoped descendants of parent) was removed] XIII. removeTrees(tree, scope, compSubtrees, list): Given the root of an entire tree, a set of node identifiers to try to remove, and a set of completely scoped subtrees, return a list of subtrees collected from scoped nodes, and delete the scoped nodes from the tree. removeTrees performs the same function as a call to collectTrees followed by a call to deleteTrees, but removeTrees is more efficient. Assuming the example tree 200 in FIG. 2, given the tree based off A1 201, and the set containing nodes B1 202, B3 204, C2 206, E1 208, F1 210, F2 212, G1 214, and G2 216 as the scope, the routine returns the list containing subtrees C2 206, B3 203, and E1 208, in that order, and delete B1 202, B3 204, C2 206, E1 208, F1 210, F2 212, G1 214, and G2 216 from the tree.
______________________________________
Inputs:
tree The root of the tree from which to remove
trees
scope The set of nodes that are in the scope
compSubtrees
The set of nodes whose subtrees are made up
entirely of scoped nodes
Outputs:
scope The set of nodes that are left in the scope
(none following a remove)
list The list of subtrees removed from the tree
______________________________________
Method 1. create(scopeUnder) [create a set to hold the nodes that have a scoped node under them] 2. buildScopeUnder(scope, scopeUnder) [create the scopeUnder set] 3. if query(scope,tree][see if the top node is scoped] a. parent=getParent(tree) [the node is scoped. Get its parent] b. if parent is null [see if the tree is the root] 1) Fail [cannot remove the root] c. create(unremovedList) d. removeScoped(tree, scope, scopeUnder, compSubtrees, unremovedList) [remove the top node and its scoped descendants, and return the list of unremoved subtrees] e. replace(parent, tree, tree, unremovedList, status) [replace tree with the unremoved subtrees] f. append(list, tree) [put tree in the list of removed subtrees] f. destroy(unremovedList) 4. Otherwise a. removeSubtrees(tree, scope, scopeUnder, compSubtrees, list) [the top node is not scoped. Remove the subtrees and put then into the list] XIV. insertLeft(node,list): Insert a list of subtrees to the left of a given node in a tree.
______________________________________
Inputs:
______________________________________
node The node to insert to the left of
list The list of subtrees to insert
______________________________________
Method 1. parent=getParent(node) [find the parent of the node] 2. prev=getLeftSibling(node) [determine node after which to insert] 3. graft(parent,prev,list,status) [insert the trees] XV. insertRight(node,list): Insert a list of subtrees to the right of a given node in a tree.
______________________________________
Inputs:
______________________________________
node The node to insert to the right of
list The list of trees to insert
______________________________________
Method 1. parent=getParent(node) [find the parent of the node] 2. graft(parent,node,list,status) [insert the trees] XVI. insertAround(node,list): Insert a list of subtrees as a child of the parent of a given node with that node as a child of one of the leaves of one of the subtrees in the list. The leaf chosen is the first leaf into which the given node fits.
______________________________________
Inputs:
______________________________________
node The node to insert around
list The list of trees to insert
______________________________________
Method 1. parent=getParent(node) [find the parent of the node] 2. prev=getLeftSibling(node) [determine node after which to insert] 3. create(childList) [dummy list for grafting] 4. append(childList,node) [store node for later graft] 5. replace(parent,node,node,list, status) [remove the node and replace it with the list] 6. tree=getFirst(list) 7. while tree is not null [iterate through the trees in the list] a. leaf=getFirstLeaf(tree) b. while leaf is not null [iterate through the leaves on the tree] 1) graft(leaf,null,childList,status) 2) If status=ok a) return [successful insert around] 3) left=getNextLeaf(tree,leaf) [try next leaf] c. tree=getNext(list,tree) [try next tree] 8. fail [no more trees to try, unsuccessful] XVII.insertWithin(node,list): Insert a list of subtrees as the children of a given node with the children of that node as the children of one of the leaves of one of the subtrees in the list. The leaf chosen is the first leaf into which the children fit.
______________________________________
Inputs:
______________________________________
node The node to insert within
list The list of trees to insert
______________________________________
Method 1. parent=node [find the parent to insert within] 2. create(childList) 3. node=getFirstChild(node) [find out the first child] 4. While node is not null [scan through children] a. append(childList,node) [remember child] b. node=getRightSibling(node) [next child] 5. replace(parent, getFirstChild(parent), getLastChild(Parent), list, status) [replace all of the children with the list] 6. tree=getFirst(list) 7. While tree is not null [iterate through the trees in the list] a. leaf=getFirstLeaf(tree) b. while leaf is not null [iterate through the leaves on the tree] 1) graft(leaf,null,childList,status) 2) If status=ok a) Return [successful insert within] 3) leaf=getNextLeaf(tree,leaf) [try next leaf] c. tree=getNext(list,tree) [try next tree] 8. fail [no more trees to try, unsuccessful] XVIII. insertTrees(node,relation,list): Given a target node, a relation to that target node, and a list of subtrees to insert, insert the subtrees in relation to the target node.
______________________________________
Inputs:
______________________________________
node The node to insert within
relation The target relation to the node
list The list of trees to insert
______________________________________
Method 1. Case relation of a. left 1) insertLeft(node,list) b. right 1) insertRight(node.list) c. around 1) insertAround(node,list) d. within 1) insertWithin(node,list) XIX. checkcompSubtree(node, scope, compSubtrees, alreadyChecked): Given a node, a scope set, a set of nodes which are already known to have completely scoped subtrees, and a set of nodes which have already been checked for completed scoped subtrees, indicate if the subtree under the node is made up entirely of scoped nodes.
______________________________________
Inputs:
node The root of the subtree that is to be checked
scope The set of nodes in the scope
compSubtrees
The set of nodes already known to
have subtrees made up entirely of scoped
nodes.
alreadyChecked
The set of nodes within scope which have
already been checked by checkCompSubtree
Outputs:
compSubtrees
The set of nodes which are known to have
subtrees made up entirely of scoped nodes.
alreadyChecked
The set of nodes within scope which have been
checked by checkCompSubtree
______________________________________
Method 1. If query(scope,node) [see is node is in the scope] a. if query(alreadyChecked,node) [see if checkCompSubtree has already checked this node] 1) return b. Insert(alreadyChecked,node) [add node to the set of nodes checkCompSubtree has checked] c. child=getFirstChild(node) d. While child is not null [loop while there are still children of node] 1) checkCompSubtree(child, scope, compSubtrees,AlreadyChecked) [check to see if the subtree under child is entirely scoped, and add node to compSubtrees if it is] 2) not query(compSubtrees,child) a) return 3) child=getRightSibling(child) [check next child] e. insert(compSubtrees,node) [since the node is scoped, and all its children subtrees are scoped, the node's subtree is scoped] XX. buildcompSubtrees(scope, compSubtrees): Given a scope set, return the set of nodes which are the roots of subtrees made up entirely of scoped nodes. Determine which subtrees are entirely scoped because the collectTrees, removeTrees and deleteTrees operations can take shortcuts when working with complete subtrees. Assuming the example tree 200 in FIG. 2, this set of nodes contains C2 206, F1 210, F2 212, G1 214, G2 216 and E1 208.
______________________________________
Inputs:
scope The set of nodes in the scope
Outputs:
compSubtrees
The set of nodes whose subtrees are made up
entirely of scoped nodes.
______________________________________
Method 1. create(alreadyChecked) [Initialize set of nodes that have been checked for complete subtrees] 2. node=getFirst(scope) [pick a node from the scope] 3. While node is not null [loop while there are still nodes in the scope] a. checkCompSubtree(node,scope,compSubtrees, alreadyChecked) [check to see if the subtree under node is completely scoped, and add node to compSubtrees if it is] b. node=getNext(scope) [next arbitrary node to pull from the scope] 4. destroy(alreadyChecked) 5. Main Functions The following functions are defined using the preceding subroutines. These functions provide the high level view of the generalized structure editing operations: delete; copy; move; insert. FIG. 11 illustrates the process flow described below. The discussion concentrates on the processes for manipulating the data; the user interaction required to specify the scope 502, type of operation 504, target node, and relationship to the target node are not discussed. A. Delete(tree,scope): Delete a scope from a tree (Step 506).
______________________________________
Inputs:
tree The root of the tree to start deleting
scope The set of nodes in the scope
Outputs:
scope The set of nodes that are left in the scope [none
following a delete]
______________________________________
Method 1. create(compSubtrees) [create set for nodes whose subtrees are completely scoped] 2. buildCompSubtrees(scope, compSubtrees) [build the set of nodes whose subtrees are completely scoped] 3. deleteTrees(tree, scope, compSubtrees) 506 [delete the trees] 4. destroy(compSubtrees) B. Copy(tree,scope,node,relation): Copy a scope to a target location (Steps 508, 514, 517).
______________________________________
Inputs:
tree The root of the tree from which to start deleting
scope The set of nodes in the scope
node The target node
relation The target relation to the node
Outputs:
scope The set of nodes that are left in the scope [none
following a copy]
______________________________________
Method 1. create(treeList) [the list of trees that make up the scope] 2. create(compSubtrees) [create set for nodes whose subtrees are completely scoped] 3. buildCompSubtrees(scope, compSubtrees) 508 [build the set of nodes whose subtrees are completely scoped] 4. collectTrees(tree, scope, compSubtrees, treeList) 514 [collect the subtrees that are scoped] 5. insertTrees(node, relation treeList) 516 [insert the collected trees at the target] 6. makeEmpty(scope) [clear scope] 7. destroy(compSubtrees) 8. destroy(treeList) C. Move (tree,scope,node,relation): Move a scope to a target location (Steps 510, 518, 520).
______________________________________
Inputs:
tree The root of the tree from which to start deleting
scope The set of nodes in the scope
node The target node
relation The target relation to the node
Outputs:
scope The set of nodes left in the scope [none
following a move]
______________________________________
Method 1. create(treeList) [the list of trees that make up the scope] 2. create(compSubtrees) [create set for nodes whose subtrees are completely scoped] 3. buildCompSubtrees(scope, compSubtrees) 510 [build the set of nodes whose subtrees are completely scoped] 4. removeTrees(tree, scope, compSubtrees, treeList) 518 [collect the subtrees that are scoped, and delete them from the tree] 5. insertTrees(node, relation, treeList) 520 [insert the collected subtrees at the target] 6. destroy(compSubtrees) 7. destroy(treeList) D. Insert(tree,node,relation,nodeType): Insert a new node of a given type at a target location (Steps 512, 522).
______________________________________
Inputs:
______________________________________
tree The root of the tree to start deleting from
node The node to insert within
relation The target relation to to the node
nodeType The type of node to create
______________________________________
Method 1. create(treeList) [the list of trees that make up the scope] 2. createNode(newNode,nodeType) 512 [create the node with the appropriate type] 3. append(treeList,newNode] 4. insertTrees(node,relation,treeList) 522 5. destroy(treeList) 6. Extension to Preferred Embodiment Although many editing systems for manipulating tree structured data have been developed, the inventors are aware of no prior art for manipulating n-ary trees and enforcing syntax rules on such a tree. This extension of the preferred embodiment will now be described. In the prior art, trees manipulated by syntax directed editors take the form of a direct rendition of the Backus Naur Form (BNF) structure into an internal tree. BNF is a means of specifying the valid relationships within a set of data. BNF was developed to define the legitimate sequences that could be recognized as belonging to some language. The use of trees to represent intermediate stages of parsing the language came later. BNF consists of rules known as productions. Each production has a left-hand side and a right-hand side, separated by some delimiter, commonly an arrow or the string "::=". The left-hand side consists of a single word. (This is not always the case. The most general description of BNF allows for sequences on both sides of the production. This feature is considered to be too difficult to use in real systems, however, and is unnecessary for formal languages such as programming languages.) This word is a non-terminal. The right-hand side consists of a sequence of zero or more words, which may be non-terminals or terminals. Terminal words never appear on the left-hand side of productions. If a node in the tree is generated for each non-terminal word, then the right-hand sides of productions having that non-terminal as its left-hand side define the legitimate children for that node. A non-terminal word may appear as the left-hand side of more than one production. The right-hand sides do not have to be equivalent in this case. This means that a single type of node may have different types of children at different times. A non-terminal word may appear in both the left- and right-hand sides of a production, or more deeply nested within the dependencies of the grammar. This recursion is the way that sequences are expressed in BNF. For example, statements::=statement statements::=statements statement statement::=ifStatement statement::=whileStatement ifStatement::=`IF` condition `THEN` statement ifStatement::=`IF` condition `THEN` statement `ELSE` statement whileStatement::=`WHILE` condition `DO` statements `END` defines a sequence a statements recursively. Note that the sequence of statements defined here may not be zero length. It is inefficient to write the rules for a complete language in simple BNF. BNF is commonly extended to allow for a concise expression of the rules. The extensions include the use of a vertical bar, ".vertline.", to indicate a choice amongst terminals and non-terminals, square brackets, "[]", to indicate optional terminals or non-terminals, and curly braces, "{}", to indicate a 0 to n length sequence of terminals or non-terminals (where n is any positive integer). Definitions of the exact meaning of these extensions differ from implementation to implementation. As an example, the six productions above can be replaced by: statements::=statement {statement} statement::=ifStatement .vertline. whileStatement ifStatement::=`IF` condition `THEN` statement [`ELSE` statement] whileStatement::=`WHILE` condition `DO` statements `END` These extensions do not extend the expressive power of BNF, but merely make it more convenient to write. The transformation from these extensions to simple BNF is trivial. For this reason, extensions to BNF are colloquially known as "syntactic sugar," because they make the syntax of BNF easier to swallow. A tree built in such a way that each and every node in the tree represents a specific instance of some production in simple BNF is known as a parse tree. A parse tree representing a valid sequence of statements using the simple grammar presented herein is shown generally at 300 (e.g. 304, 306, 308, 310, 312, 314) in FIG. 5. Note the number of intermediate nodes used. In the prior art of which the inventors are aware, trees manipulated by syntax directed editors take the form of a direct rendition of the simple BNF structure into an internal tree. This requires each type of node in the tree to have a fixed number of children. The preferred embodiment of the present invention allows nodes to have a variable number of children, and removes the need for intermediate nodes by maintaining the tree in a form that is directly equivalent to the extended BNF. In addition, certain nodes that are intermediates in the extended BNF need not be present in the tree. Using this improved tree representation, the previous simple grammar can be represented as shown generally at 350 in FIG. 6. Note that many fewer nodes are required for this representation. The more nodes employed as intermediate "backbones" to sequences, the less storage available for the data that users of syntax-directed editors are interested in, i.e. the lowest level statements themselves. In addition, in large, complex languages such as Ada programming language, the number of intermediate productions needed to define common language constructs is quite large. The manipulation of all these nodes takes time resulting in an editor with slow response times to user actions. The basic concept behind this extension to the preferred embodiment, i.e., a method of maintaining syntactic correctness in a structure editor (thus making it a syntax-directed editor), is the use of "sockets". A socket defines the types of nodes and relationships that can be associated with a given node. This embodiment maintains an n-ary tree representing the data and relationships: In other words each node may have an arbitrary number of other nodes related to it. Each node (or more precisely, each type of node) has a fixed number of sockets or allowable relations. However, any number of nodes satisfying the socket criteria may be associated with the given node via that socket. The following example grammar will be used to help explain the concept socket `.vertline.`, `[]` and `{}` mean the same thing in this grammar as they do in extended BNF. Since this grammar is only used for tree manipulation, non-terminals are not shown.
______________________________________
block ::= {DECLARE} {statement}
DECLARE ::= VARPART TYPEPART
VARPART ::=
TYPEPART ::=
statement ::= IFSTATEMENT
WHILESTATEMENT
IFSTATEMENT ::= CONDITION THENPART
[ELSEPART]
CONDITION ::=
THENPART ::= {statement}
ELSEPART ::= {statement}
WHILESTATEMENT ::= CONDITION nullorblock
nullorblock ::= NULLSTATEMENT block
NULLSTATEMENT ::=
______________________________________
Each right hand side non-terminal word represents a socket associated with the left hand side. Each socket has two attributes defined in a language definition table. The two attributes are the socket type, which determines how many nodes may connect to it, and the connection rule for that socket, which determines which other node types may connect to that socket. All nodes of a node type (defined by a left-hand side) share the same definitions of their sockets. The valid types for sockets are:
______________________________________
required
Nodes matching the connection rule must be
connected to the socket at all times. Required
sockets are represented in the grammar as right
hand side non-terminal words with no `{ }` or `[ ]`
around them. For example, the DECLARE production
has two required sockets, VARPART and
TYPEPART.
optional
Nodes matching the connection rule may be
connected to the socket, or it may be empty.
There can be at most one set of connections made
to an optional socket. Optional sockets are
represented in the grammar as right hand side
non-terminals with `[ ]` around them. For example,
the IFSTATEMENT production has an optional
socket, [ELSEPART].
n-ary Nodes matching the connection rule may be
connected to this socket, or it may be empty.
There is no limit to the number of sets of
connections which can be made to an n-ary socket.
N-ary sockets are represented in the grammar as
right hand side non-terminals with `{ }` around
them. For example, the block production has two
n-ary sockets, {DECLARE} and {statement}.
______________________________________
Each socket has a single connection rule attribute determined by the production which defines the non-terminal word represented by the socket. The connection rule defines the nature of the connections allowed. There are only four types of connection rules, two simple types and two complex types. The simple types are:
______________________________________
construct
Construct rules define the basic language
constructs, i.e. words or phrases that would
appear during the use of the language, as
contrasted with definitions of language
abstractions or intermediate definitions.
Construct rules are defined by the language
specification. Construct rules are the only rules
that define nodes actually represented in a tree.
In the example grammar, construct rules are
identified by uppercase non-terminal words
(DECLARE, VARPART, TYPEPART, . . .)
When a socket contains a construct connector rule
name, it means that a node defined by a construct
connector rule should be inserted under the socket.
For example the IFSTATEMENT node contains
three sockets with construct connection rules, one
for CONDITION, one for THENPART, and an
optional one for ELSEPART. (Node 4 of FIG. 7
is an IFSTATEMENT and contains three sockets
4-1, 4-2, and 4-3.)
The type of a node is given the same name as the
construct rule that defines its structure. For
example, a node defined by the IFSTATEMENT
rule has a node type of IFSTATEMENT.
connectorSet
A connector set rule allows a node of one of
many connection rule types to connect to a socket.
(Note that if the socket has type required or
optional then the maximum number of nodes
that may ever be connected to that socket is one,
not one of each kind.) Connector set rules appear
in the example grammar as:
1hs ::= rh1 rh2 rh3 rh4 . . .
where all the "rhx"s are single required sockets
having a construct rule type. In the example
grammar, the only connector set is `statement`.
`nullorblock` is not a connector set because
`block` is not a construct rule. `block` is not a
connector set because it has more than one socket
on its right hand side, because `DECLARE` and
`statement` are not required sockets, and because
`statement` is not a construct rule.
Connector sets can be implemented in the language
definition tables as a bit array containing bit
positions for each construct rule by assigning
each construct rule an integer value. A one is
placed in the respective bit position for each
construct rule that the connector set rule
references, and other bits are set to 0. The
parsing algorithm can then check whether a given
construct rule is within a connector set by doing
a very rapid bit array lookup. Connector sets
represent language abstractions or intermediate
nodes in standard BNF.
______________________________________
Complex connection rule types are more costly to process during editing. However, they are much rarer in language definitions. The two preceding rules are quite efficient, and cover over 90% of the cases in real languages. In a test case grammar for a language similar to the Ada Programming Language, 97% of the connection rules were construct rules or connector set rules. When these simple rule types are used with the methods described below, child nodes can be grafted into a parent node with very few table lookups per child node. The following complex connection rule types provide a mechanism for nested sockets within a single socket. These connection rules define a fairly standard parser, with the different rule types allowing different efficiencies to be obtained.
______________________________________
connector
A connector is similar to a connector set, except
that matching connection rule types are not
limited to construct rules. Like connector set
rules, connector rules appear in the example
grammar as:
1hs ::= rh1 rh2 rh3 rh4 . . .
The difference is that each "rhx" does not have to
be a single required socket with a construct rule.
It can also be a sinqle required socket having a
connection rule type of connector set, connector,
or ordered connector. In the example grammar,
`nullorblock` is a connector rule.
ordered An ordered connector rule divides a
connector
socket into subsockets. Each subsocket may be of
any type and have any type of connection rule.
The ` ` BNF symbol is not allowed in the ordered
connector rules, i.e. there may not be alternative
definitions of subsets. In the example grammar,
`block` is an ordered connector rule.
______________________________________
The methods of the present invention define how these construction rules may be maintained through editing operations involving graft and replace, which use lists or ranges of subtrees. The following examples show the results of a graft operation and a replace operation. The examples are based on the example grammar with the initial tree represented as shown in FIG. 7. Starting with this tree, a list containing an IFSTATEMENT and a WHILESTATEMENT is grafted under node 9 and after node 11. The result is shown in FIG. 8. FIG. 9 shows the results of replacing nodes 3 and 4, under node 1, with the IFSTATEMENT and a WHILESTATEMENT. FIG. 10 shows a tabular form of the information contained in the example grammar, as well as implementations of the preferred embodiment of the present invention. It will be used to walk through the above graft and replace operations (shown in FIGS. 12 and 13 respectively). There is one row in the table for every production in the grammar (e.g. "BLOCK" 402). Each production rule is assigned a rule number 403, and a rule name 405. The "Rule Type" column tells which type of rule each production is. The "Children Complex?" column 432 indicates whether connector or ordered connector rules are used as a connection rule for any of the sockets of a construct rule. If so, the children connecting to that socket are complex (True), if not, they are not complex (False). The "Children Complex?" field is used to determine whether a fast but inflexible graft or replace algorithm can be used (no complex children), or if a slower more flexible algorithm must be used. The "Number of sockets" column 434 tells how many sockets are defined for a construct, connector, or ordered connector rule. The "Sockets or Bit array" column 436 for construct, connector, and ordered connector rules contains a list of sockets. Each socket consists of a socket type (e.g. 440) (required (r), optional (o), or n-ary (n)) and a connection rule number (e.g. 442). The "Sockets or Bit array" column for connector set rules contains a bit array (e.g. 444). The bit array consists of one bit for each rule (numbered 0 through n, the number of rules). A 1 value in a bit indicates that a node defined by the corresponding rule can be connected. In FIG. 10, rule 4 410, the bits corresponding to the IFSTATEMENT rule (bit number 5 446) and WHILESTATEMENT rule (bit number 9 448) are set to 1. The steps involved in the graft operation discussed above, namely grafting an IFSTATEMENT and WHILESTATEMENT under node 9 and after node 11 of FIG. 7 resulting in the structure shown in FIG. 8 are (see FIG. 12): 1. Determine (Step 530) from the production definition, FIG. 10, that THENPART node 9 does not have complex children (complex children is false). This means the fast graft algorithm 532 can be used. (The fast algorithm only checks whether if the new children fit into the target socket. The slower algorithm checks all the children of the node to whether any of them need to be moved from one socket to another.) 2. Determine 534 whether the socket containing node 11 (the one being "inserted after") is n-ary. If so, the new nodes can be inserted, otherwise the graft fails since the socket is already occupied. 3. Determine 534 whether the connection rule for the socket allows the insertion of the types of nodes being grafted. The socket of node 9 is a "statement" socket (connection rule 4), which has a connector set connection rule type. The bit array associated with the rule 4 connector set specifies that IFSTATEMENT and WHILESTATEMENT nodes can be connected to this socket. The first node being inserted (node 15) is an IFSTATEMENT node. The second node (node 16) is a WHILESTATEMENT node. Thus both nodes can be inserted into the socket. 4. Insert the nodes into the socket. The steps involved in replacing FIG. 7 nodes 3 and 4 with the IFSTATEMENT and WHILESTATEMENT resulting in FIG. 9 are: 1. Determine whether (WHILESTATEMENT node 1) has complex children. If so, the slower algorithm must be used. (The slower algorithm checks all the children of the node to see if any of them need to move from one socket to another.) 2. Build childrenList containing CONDITION node 2, IFSTATEMENT node 15, WHILESTATEMENT node 16, and WHILESTATEMENT node 5. These are the nodes which will become the new children of node 1 after the replace. 3. Determine whether CONDITION node 2 will fit into the first socket of WHILESTATEMENT node 1. It will because the first socket of a WHILESTATEMENT is a required socket connecting to a CONDITION construct. This fills the first socket of node 1. 4. Since node 1 has only one remaining socket, an attempt is made to insert nodes 15, 16, and 5 into the second socket. The connection rule for this socket is rule 10, nullorblock. Since nullorblock is a connector construction rule type, an attempt is made to insert the new nodes into each of its virtual sockets until one is found into which it can be inserted correctly. (A connector rule's sockets are called virtual sockets because they do not correspond to sockets in the resulting tree.) a. The first virtual socket of nullorblock is construct rule 11 NULLSTATEMENT. Since the next node to be inserted, IFSTATEMENT node 15, is not a NULLSTATEMENT, this test fails. b. The next virtual socket of nullorblock is an ordered connector rule 0, block. Parsing for an ordered connector rule is very similar to parsing for a construct rule. Movement is from left to right through the ordered connector's virtual sockets, with nodes being inserted along the way. 1) The first virtual socket of rule 0, block, is n-ary with a connection rule DECLARE. Since the next node, IFSTATEMENT node 15, is not a DECLARE, it cannot be inserted in the virtual socket. But, the test does not fail, because n-ary sockets can have 0 children. 2) The second socket of block is n-ary with a connection or rule of statement. statement is a connector set rule type that accepts either IFSTATEMENT or WHILESTATEMENT. Since the next three nodes (nodes 15, 16, and 5) are all IFSTATEMENTs or WHILESTATEMENTs, they are valid within this virtual socket. The parse is now finished and it has been determined how to connect nodes 2, 15, 16, and 5 to the sockets of node 1. 5. Remove all children from the sockets of WHILESTATEMENT node 1. 6. Connect CONDITION node 2 to the first socket of WHILESTATEMENT node 1, and connect IFSTATEMENT and WHILESTATEMENT nodes 15, 16, and 5 to the second socket of WHILESTATEMENT node 1. 7. Utility Functions Used by the Extension to the Preferred Embodiment It is assumed that the following basic operations are available through utility functions: Functions for manipulating trees. Tree manipulation is a well understood field. The operations are restricted to the simple ones listed here:
______________________________________
getFirstChild
Returns the first child of a given node,
or null if the node is childless.
getLastChild Returns the last child of a given node,
or null if the node is childless.
getRightSibling
Returns the right-hand sibling of a
node, or null if the node is the last
child of its parent.
getLeftSibling
Returns the left-hand sibling of a node,
or null if the node is the first child
of its parent.
insertNode Insert a node under a parent node and
after a left sibling.
removeNode Remove a node from under a parent node.
______________________________________
Functions for manipulating lists of items, specifically subtrees.
______________________________________
create Create a new empty list.
destroy Destroy a list completely.
append Add an item to the end of a list.
prepend Add an item to the beginning of the
list.
getFirst Return the first item on the list.
getNext Given a list and an item in the list,
return the next item in the list, or
null if the item given is the last.
______________________________________
These functions are all well defined and well known throughout the industry. 8. Data Needed for the Extension to the Preferred Embodiment Nodes require two pieces of associated data: a node type and a socket number. The node type defines the type of node, such as an IFSTATEMENT node or a WHILESTATEMENT node. The socket number identifies the socket of its parent occupied by a particular node. The method uses the node type of each node and the type of its parent to assign nodes to sockets. If a node cannot be assigned to a socket then the operation fails. The node type field (which is the same as the connection rule that defines the node) is an index into the language definition table array. The socket field is an integer, indicating the socket to which the node is currently assigned. The following operations are provided to manipulate the node data.
______________________________________
getNodeType Given a node, return its type.
getParentSocket
Given a node, return the socket it has
been assigned to.
setParentSocket
Given a node and a socket index,
assign that node to that socket. This
functions does not check that the
sockets are assigned in order amongst
the children; it is the responsibility
of graft and prune operations to do
that.
______________________________________
The Language Definition Table is an array of structures, indexed by connection rule number (which, when associated with nodes, is called the node type. The two terms will be used interchangeably in this discussion.) Note that only the connection rules with a construct connection rule type will actually be assigned to nodes. The other rules are used in the socket assignment process as connection rules. The data contained within the structures is different for each type of connection rule. The type of connection rule is always present in this structure, namely construct, connector set, connector, or ordered connector. The following function returns the type of connection rule for a given connection rule number.
______________________________________
getRuleType
Given a connection rule number, return the
type of that connection rule.
______________________________________
If the rule is a connector set type, a bitmap representing the valid construct node types for this connector set is contained in the rest of the structure. The following routine is defined to extract data from a connectorSet entry.
______________________________________
inConnSet Given a node type that indexes to a connector
set and a node type to test, return true if
the node type to test is in the set of node
types that are valid, otherwise, return
false.
______________________________________
If the rule type is anything other than a connector set, then the structure contains the number of sockets defined for this rule and a list of socket descriptors. These are interpreted differently, however, based on the rule type. Each socket descriptor has a socket type field (required, optional, or n-ary) and a connection rule number that defines the connection rule used for that socket. The following functions are defined for extracting data from these entries.
______________________________________
getNumSockets
Given a node type, return the number of
sockets associated with that entry. This
number may be zero.
getSocketType
Given a node type and a socket index, return
the type of socket that is referenced by that
index (required, optional, or nary).
getRule Given a node type and a socket index, return
the connection rule that is specified for
that socket.
______________________________________
In addition to the above functions, if the table entry is for a construct rule, the table contains an indication of whether any of the sockets of the construct use connector or ordered connector rules. This information is available because the graft and replace algorithms can take short cuts when connector and ordered connector rules are not used.
______________________________________
complexChildren
Given a node type, return whether a
complex connection rule (connector rule or
ordered connector rule) is used as the
connection rule for any socket of that node
type.
______________________________________
9. Base Function Definitions for the Extension to the Preferred Embodiment Definitions of subroutines used to describe the extension to the method of the preferred embodiment follow. I. parseSocket(parentType, socket, child, children, status): Parse subtrees from a list of subtrees to see if they will fit under a socket. parseSocket decides what type of connection rule is associated with the socket and branches to the appropriate routine.
______________________________________
Inputs:
parentType The type of the parent node to attempt to
parse the children under.
socket The socket to attempt to parse the
children under.
child A subtree top from the children list. child
is the first subtree top that to parse under
the socket.
children The list of subtrees to parse.
Outputs:
status Indicates whether the operation succeeded.
It will fail if the children cannot be
parsed according to the syntax rules of the
grammar.
child A subtree top from the children list. Child
is the next subtree top that should be
parsed.
______________________________________
Method 1. Case getRuleType(getRule(parentType, socket)) [execute the proper type of parse depending on which type of rule defines the socket] a. Construct rule 1) parseConstruct(parentType, socket, child, children, status) b. Connector Set rule 1) parseConnSet(parentType, socket, child, children, status) c. Connector rule 1) parseConn(parentType, socket, child, children, status) d. Ordered connector rule 1) parseOrdConn(parentType, socket, child, children, status) II. parseConstruct(parentType, socket, child, children, status): Parse children of a specific construct type under a socket.
______________________________________
Inputs:
parentType
The type of the parent node to parse the
children under.
socket The socket to parse the children under.
child A subtree top from the children list. child is
the first subtree top to parse under the socket.
Outputs:
status Indicates whether the operation succeeded. It
will fail if the children cannot be parsed
according to the syntax rules of the grammar.
child A subtree top from the children list. Child is
the next subtree top that should be parsed.
______________________________________
Method 1. Case getSocketType(parentType, socket) [do the correct type of parse depending on whether the socket is required, optional, or n-ary] a. required 1) if child is null [there is no child available to put into the required socket] a) status=syntax error 2) otherwise a) if getNodeType(child)=getRule(parentType, socket) [See if the child node has the same type as the rule specified for the socket] i. status=ok [this part of the parse succeeded] ii. child=getNext(children, child) [prepare to parse the next child] b) otherwise i. status=syntax error [wrong type of socket] b. optional 1) if child is not null a) if getNodeType(child)=getRule(parentType, socket) [See if the child node has the same type as the rule specified for the socket] i. child=getNext(children, child) [prepare to parse the next child] 2) status=ok [optional sockets can be empty, so they never cause failure] c. n-ary 1) n-aryDone=false 2) while n-aryDone is false a) if child is null i. n-aryDone is true b) otherwise i. if getNodeType(child)=getRule(parentType,socket) [See if the child node has the same type as the rule specified for the socket] i) child=getNext(children, child) [prepare to parse the next child] ii. otherwise i) n-aryDone=true 3) status=ok [n-ary sockets can be empty, so they never cause failure] III. parseConnset(parentType, socket, child, children, status): Parse children according to the syntax defined in a connector set rule. Connector set rules consist of a set of construct rule numbers which are valid within a socket. Parsing is very simple: Determine whether the type of the next child is one of the valid construct rule numbers defined in the connector set.
______________________________________
Inputs:
parentType
The type of the parent node to attempt to
parse the children under.
socket The socket to attempt to parse the
children under.
child A subtree top from the children list. Child
is the first subtree top to attempt to parse
under the socket.
children The list of subtrees to parse.
Outputs:
status Indicates whether the operation succeeded.
It will fail if the children cannot be parsed
according to the syntax rules of the grammar.
child A subtree top from the children list. Child
is the next subtree top that should be
parsed.
______________________________________
Method 1. Case getSocketType(parentType, socket) [do the correct type of parse depending on whether the socket is required, optional, or n-ary] a. required 1) if child is null a) status=syntax error 2) otherwise a) if inConnSet(getRule parentType, socket), getNodeType(child)) i. status=ok [this part of the parse succeeded] ii. child=getNext(children, child) [prepare to parse the next child] b) otherwise i. status=syntax error b. optional 1) if not child is null a) if inConnSet(getRule(parentType, socket), getNodeType(child)) i. child=getNext(children, child) [prepare to parse the next child] 2) status=ok [optional sockets can be empty, so they never cause failure] c. n-ary 1) n-aryDone=false 2) while n-aryDone is false a) if child is null i. n-aryDone is true b) otherwise i. if inConnSet(getRule(parentType, socket), getNodeType(child)) i) child=getNext(children, child) [prepare to parse the next child] ii. otherwise i) n-aryDone=true 3) status=ok [n-ary sockets can be empty, so they never cause failure] IV. parseConn(parentType, socket, child, children, status): Parse children according to the syntax defined in a connector rule. Connector rules consist of a list of virtual sockets. (Since connector rules do not define nodes in the tree, the virtual sockets only define the possible syntaxes the children can have, and do not define actual sockets to which nodes will be connected.) The children are parsed into only one of these virtual sockets. Each virtual socket is tried from the first to the last, until one is found under which the children can be parsed.
______________________________________
Inputs:
parentType
the type of the parent node to try to
parse the children under.
socket The socket to try to parse the
children under.
child A subtree top from the children list. child
is the first subtree top to try to parse
under the socket.
children The list of subtrees to parse.
Outputs:
status Indicates whether the operation succeeded.
It fails if the children cannot be parsed
according to the syntax rules of the grammar.
child A subtree top from the children list. Child
is the next subtree top that should be
parsed.
______________________________________
Method 1. connParentType=getRule(parentType, socket) [set an index into the table entry for the connector rule. This is passed to the routine that parses children under each connector rule virtual socket] 2. Case getSocketType(parentType, socket) [do the correct type of parse depending on whether the socket is required, optional, or n-ary] a. required or optional 1) status=syntax error [initialize status for a while loop] 2) connSocket=1 3) While connSocket<=getNumSockets(connParentType) and status is syntax error [try to parse under each virtual socket until either virtual sockets are run out of or until a virtual socket parses without a syntax error] a) connChild=[create a local copy of child so parseSocket won't update child when status is not ok. child is only updated when it is known that a group of children has been parsed correctly within a virtual socket] b) parseSocket(connParentType, connSocket, connChild, children, status) [try to parse under the virtual socket] c) connSocket=connSocket+1 4) if status is ok a) child=connChild [get ready to parse the next child] 5) otherwise a) if getSocketType(parentType, socket) is optional i. status=ok [the optional socket is empty] b. n-ary 1) n-aryDone=false 2) while n-aryDone is false a) status=syntax error [initialize status for while loop] b) connSocket=1 c) While connSocket<=getNumSockets(connParentType) and status is syntax error [try to parse with each virtual socket until either virtual sockets are run out of or until a virtual socket parses without a syntax error] i. connChild=child [make a local copy of child so parseSocket won't update child when status is not ok. Update child only when it is known that a group of children has been parsed correctly within a virtual socket] ii. parseSocket(connParentType, connSocket, connChild, children, status) [try to parse under the virtual socket] iii. connSocket=connSocket+1 d) If status is not ok or connChild=child i. n-aryDone=true e) otherwise i. child=connChild [prepare to parse the next child] 3) status=ok [n-ary sockets can be empty, so they never cause failure] V. parseOrdConn(parentType, socket, child, children, status): Parse children according the syntax defined in an ordered connector rule. Ordered connector rules consist of a list of virtual sockets (Since ordered co | ||||||