Patent US5557720A successfully refreshed from Google Patents.
US5557720A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of determining whether a document tree is weakly valid
Assignee: Xerox Corp
•
Filing: 1994-09-08
•
Granted: 1996-09-17
•
Expires: 2014-09-08
Abstract
Abstract Some document languages such as the Standard Generalized Markup Language (SGML) represent documents as trees with each node of the tree labelled with a tag and each node's immediate descendants taken in order having tags that satisfy a production corresponding to the parent's tag. Thus, a document is represented as a complete parse tree satisfying the production rules of a grammar. To simplify maintaining a valid document/parse tree at all stages, an efficient check is made whether a document is valid or can be extended to a valid document and furthermore to show how a document could be changed to be valid. A document can be extended to a valid document if is equal to a valid document with possibly some nodes deleted. External (leaf) nodes can just be deleted. Internal nodes are deleted by replacing the arc from the parent with multiple arcs (in the same order) from the parent to each of the children of the deleted node. A grammar is constructed from the given grammar that includes those documents that can be completed to a valid document and is called a gapped grammar. A method is provided to teach how a gapped grammar can be constructed from a grammar, a parser/checker is efficiently implemented.
Inventors
- 👤 Allen L. Brown, Jr.
- 👤 Sidney W. Marshall
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 10:02
CPC Classifications
G; G06; G06F; G06F40/00; G06F40/20; G06F40/205; G06F40/226; G06F40/10; G06F40/103; G06F40/117; G06F40/12; G06F40/14; G06F40/143; G06F40/166
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
110 words
A method for determining whether an editing step of a document tree results in a weakly valid document structure, the weakly valid document structure being a document structure that is extendable into a valid document structure that satisfies a grammar, the method comprising the steps of: producing the document tree having a plurality of nodes labelled with symbols of the grammar; examining selective nodes of the document tree to determine whether the selective nodes are weakly valid to extend into the valid document structure that satisfies the grammar; and performing the editing step to obtain the weakly valid document structure if the selective nodes are determined to be weakly valid.
Claim 2
Independent Claim
110 words
A method for determining whether an editing step of a document tree results in a weakly valid document structure, the weakly valid document structure being a document structure that is extendable into a valid document structure that satisfies a grammar, the method comprising the steps of: producing the document tree having a plurality of nodes labelled with symbols of the grammar; examining selective nodes of the document tree to determine whether the selective nodes are weakly valid to extend into the valid document structure that satisfies the grammar; and performing the editing step to obtain the weakly valid document structure if the selective nodes are determined to be weakly valid.
Claim 3
Dependent Claim
22 words
The method according to claim 1, further comprising determining whether a plurality of editing steps result in the weakly valid document structure.
Claim 4
Dependent Claim
41 words
The method according to claim 1, wherein the document tree is defined by a structured language, said method further comprising determining whether the document tree is extendable into the valid document structure by insertion of additional structural language in appropriate places.
Claim 5
Dependent Claim
18 words
The method according to claim 1, wherein a plurality of editing steps are performed in any desirable order.
Claim 6
Dependent Claim
18 words
The method according to claim 1, wherein said examining step comprises checking each node of the document tree.
Claim 7
Dependent Claim
32 words
The method according to claim 5, wherein said examining step comprises: checking, for each node in the document tree, whether descendants of the node are extendable into a legal sequence of descendants.
Claim 8
Dependent Claim
21 words
The method according to claim 6, wherein each node is checked to determine whether the node matches a corresponding gap grammar.
Claim 9
Dependent Claim
18 words
The method according to claim 7, wherein each gap grammar is represented by a corresponding finite state machine.
Claim 10
Dependent Claim
36 words
The method according to claim 8, wherein the document tree is determined to be weakly valid when names of children of each nonterminal node are accepted by the corresponding finite state machine of each nonterminal node.
Claim 11
Dependent Claim
16 words
The method according to claim 1, wherein only certain subtrees of the document tree are examined.
Claim 12
Dependent Claim
21 words
The method according to claim 10, wherein said subtrees comprise a parent, siblings and children of a particular newly inserted node.
Claim 13
Dependent Claim
24 words
The method according to claim 10, wherein said subtrees comprise a parent and new children of the parent of a particular newly deleted node.
Claim 14
Dependent Claim
54 words
The method according to claim 10, wherein said examining step comprises checking, for each new node in the document tree, whether descendants of the new node satisfy a corresponding gap grammar; and checking, for each parent node of a deleted or inserted node, whether descendants of the parent node satisfy the corresponding gap grammar.
Claim 15
Independent Claim
116 words
A method of determining whether a given document tree is a weakly-valid document tree of a given grammar, the weakly valid document tree being a document tree that is extendable into a valid document tree that satisfies the given grammar with only an insertion of additional nodes, the method comprising the steps of: constructing gap regular expressions for each nonterminal node of the given grammar; and checking each nonterminal node of the given document tree for children whose names form a string in a language of the corresponding gap regular expression to determine if the given document tree is a weakly-valid document tree that can be extended into the valid document tree that satisfies the grammar.
Claim 16
Independent Claim
116 words
A method of determining whether a given document tree is a weakly-valid document tree of a given grammar, the weakly valid document tree being a document tree that is extendable into a valid document tree that satisfies the given grammar with only an insertion of additional nodes, the method comprising the steps of: constructing gap regular expressions for each nonterminal node of the given grammar; and checking each nonterminal node of the given document tree for children whose names form a string in a language of the corresponding gap regular expression to determine if the given document tree is a weakly-valid document tree that can be extended into the valid document tree that satisfies the grammar.
Claim 17
Dependent Claim
19 words
The method according to claim 14, wherein each gap regular expression is represented by a corresponding finite state machine.
Claim 18
Dependent Claim
125 words
An editing method for determining whether an editing step of a document tree results in a weakly-valid document tree, the document tree having nodes labelled with symbols of grammar of the document tree, the weakly valid document tree being a document tree that is extendable into a valid document tree that satisfies the given grammar by additional structural changes, the method comprising the steps of: constructing gap regular expressions for each nonterminal node of the grammar; and checking each nonterminal node of the document tree for children whose names form a string in a language of the corresponding gap regular expression to determine if the document tree is a weakly-valid document tree that can be extended into the valid document tree that satisfies the grammar.
Claim 19
Dependent Claim
125 words
An editing method for determining whether an editing step of a document tree results in a weakly-valid document tree, the document tree having nodes labelled with symbols of grammar of the document tree, the weakly valid document tree being a document tree that is extendable into a valid document tree that satisfies the given grammar by additional structural changes, the method comprising the steps of: constructing gap regular expressions for each nonterminal node of the grammar; and checking each nonterminal node of the document tree for children whose names form a string in a language of the corresponding gap regular expression to determine if the document tree is a weakly-valid document tree that can be extended into the valid document tree that satisfies the grammar.
Claim 20
Dependent Claim
18 words
The editing method according to claim 16, wherein the gap regular expressions are represented by finite state machines.
Claim 21
Dependent Claim
22 words
The method according to claim 1, wherein the selective nodes are nodes having subchildren that have been changed in the editing step.
References Cited (Backward Citations)
US4429372A
Cited
US4723211A
Cited
US4831541A
Cited
US4905185A
Cited
US4891770A
Cited
US4887212A
Cited
US5179650A
Cited
US5130924A
Cited
US5099425A
Cited
US5060155A
Cited
US5113341A
Cited
US5185698A
Cited
US5079700A
Cited
US5140521A
Cited
US5293473A
Cited
US5276793A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-09-17 | 2000-03-18 | 2000-09-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-09-17 | 2004-03-18 | 2004-09-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-09-17 | 2008-03-18 | 2008-09-17 | $7700.00 | Window Closed / Lapsed |