Method of determining whether a document tree is weakly valid

Details Method of determining whether a document tree is weakly valid Method of determining whether a document tree is weakly valid

1994-09-08

1996-09-17

Nguyen, Phu K.

G06F 728

Patent

active

055577202

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.

REFERENCES:
patent: 4429372 (1984-01-01), Berry et al.
patent: 4723211 (1988-02-01), Barker et al.
patent: 4831541 (1989-05-01), Eshel
patent: 4887212 (1989-11-01), Zamora et al.
patent: 4891770 (1990-01-01), Hollett
patent: 4905185 (1990-02-01), Sakai
patent: 5060155 (1991-10-01), van Zuijlen
patent: 5079700 (1992-01-01), Kozoll et al.
patent: 5099425 (1992-03-01), Yuji et al.
patent: 5113341 (1992-05-01), Kozol et al.
patent: 5130924 (1992-07-01), Barker et al.
patent: 5140521 (1992-08-01), Kozol et al.
patent: 5179650 (1993-01-01), Fukui et al.
patent: 5185698 (1993-02-01), Hesse et al.
patent: 5276793 (1994-01-01), Borgendale et al.
patent: 5293473 (1994-03-01), Hesse et al.
McNaughton et al.; "Regular Expressions and State Graphs for Automata"; Sequential Machines--Selected Papers; Addison-Wesley Publishing Co. Inc., 1964; pp. 157-174.

Affiliated with

Also associated with

Rating

Method of determining whether a document tree is weakly valid does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of determining whether a document tree is weakly valid, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of determining whether a document tree is weakly valid will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-420788