US5321606A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data transforming method using externally provided transformation rules
Assignee: Hitachi Ltd
•
Filing: 1988-05-18
•
Granted: 1994-06-14
•
Expires: 2008-05-18
Abstract
Abstract In transformation from a symbol string to a term, transformation rules received describe structures of input symbol strings in the form of a context-free grammar, and include structures of output terms as arguments of terminal symbols and non-terminal symbols. An inputted symbol string is analyzed by reduction processing based on the structures of input symbol strings described in the transformation rules, and an intermediate tree is formed. A term for output is produced in accordance with the structures of output terms shown in the arguments of the terminal symbols and the non-terminal symbols corresponding to the structure of the inputted symbol string. Transformation of structured data is performed in like manner using transformation rules which describe structures of input data in terms of relations between classes of partial structures, and includes structures of output data as arguments of class identifiers.
Inventors
- 👤 Hironobu Kuruma
- 👤 Koichi Yamano
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 11:51
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/42; G06F8/427; G06F40/00; G06F40/20; G06F40/205; G06F40/211; G06F40/40; G06F40/55
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
193 words
A method performed in a data processing system for transforming a symbol string to a term in accordance with transformation rules, input to said data processing system, comprising the steps of: storing one or more transformation rules which describe syntactic structures of input symbol strings using context-free grammar notation, said transformation rules including descriptions of structures of output terms, said descriptions of structures of output terms being linked in a predetermined notational form with terminal symbols and non-terminal symbols used in said context-free grammar notation; inputting a symbol string; analyzing the syntactic structure of said inputted symbol string by reduction processing in which a non-terminal symbol is sought which can be rewritten, by applying said transformation rules, into said inputted symbol string, thereby determining terminal symbols and non-symbol symbols that represent syntactic structures of said inputted symbol string; and producing a term to be outputted based on said descriptions of structures of output terms linked with said terminal symbols and non-terminal symbols that represent syntactic structure of said inputted symbol string; said term being a group of symbols having a tree structure corresponding to said analyzed syntactic structure of said inputted symbol string.
Claim 2
Independent Claim
193 words
A method performed in a data processing system for transforming a symbol string to a term in accordance with transformation rules, input to said data processing system, comprising the steps of: storing one or more transformation rules which describe syntactic structures of input symbol strings using context-free grammar notation, said transformation rules including descriptions of structures of output terms, said descriptions of structures of output terms being linked in a predetermined notational form with terminal symbols and non-terminal symbols used in said context-free grammar notation; inputting a symbol string; analyzing the syntactic structure of said inputted symbol string by reduction processing in which a non-terminal symbol is sought which can be rewritten, by applying said transformation rules, into said inputted symbol string, thereby determining terminal symbols and non-symbol symbols that represent syntactic structures of said inputted symbol string; and producing a term to be outputted based on said descriptions of structures of output terms linked with said terminal symbols and non-terminal symbols that represent syntactic structure of said inputted symbol string; said term being a group of symbols having a tree structure corresponding to said analyzed syntactic structure of said inputted symbol string.
Claim 3
Dependent Claim
19 words
The method as claimed in claim 1, wherein said reduction processing is performed in accordance with Earley's parsing algorithms.
Claim 4
Dependent Claim
55 words
The method as claimed in claim 1, wherein said analyzing step includes steps of: performing pattern matching of said inputted symbol string and said transformation rules; forming an intermediate tree having said non-terminal symbols as nodes and said terminal symbols as leaves; and recording results of said pattern matching in said nodes and said leaves.
Claim 5
Dependent Claim
71 words
The method as claimed in claim 3, wherein said descriptions of structures of output terms include variables, and said producing step includes a step of substituting said results of pattern matching recorded in the nodes and the leaves for the variables in the descriptions of structures of output terms linked with said non-terminal symbols in the nodes and said terminal symbols in the leaves, thereby forming said term to be outputted.
Claim 6
Dependent Claim
41 words
The method as claimed in claim 4, wherein said step of forming an intermediate tree includes a step of producing a node connector which interlinks a plurality of nodes corresponding to the same transformation rule to form a set of nodes.
Claim 7
Dependent Claim
40 words
The method as claimed in claim 5, wherein said step of forming an intermediate tree includes a step of producing a node-set constructor which interlinks said sets of nodes of a plurality of intermediate trees to superpose said intermediate trees.
Claim 8
Dependent Claim
78 words
The method as claimed in claim 3, wherein said storing step includes a step of producing from each of said transformation rules transformation rule elements each including the non-terminal symbol on the left side thereof and a different factor on the right side thereof, said pattern matching is performed with respect to each of said transformation rule elements, and said step of forming an intermediate tree produces said nodes and said leaves corresponding to said transformation rule elements.
Claim 9
Dependent Claim
27 words
The method as claimed in claim 1, wherein said descriptions of structures of output terms are provided as arguments of said non-terminal symbols and said terminal symbols.
Claim 10
Independent Claim
195 words
A method performed in a data processing system for transforming structured data to differently-structured data in accordance with transformation rules input to said system, comprising the steps of: storing one or more transformation rules which classify structures and partial structures of input data into classes by assigning class identifiers respectively to the structures and partial structures, and describe the structures of input data using class identifiers assigned to the partial structures, and include descriptions of structures of output data, said descriptions of structures of output data being linked in a predetermined notational form with said class identifiers; inputting structured data; analyzing the structure of said inputted structured data to classify the structure and partial structures of said inputted structured data into classes based on said transformation rules, by seeking class identifiers assigned to the structure and partial structures of said inputted structured data; and producing structured data to be outputted based on the descriptions of the structures of output data linked with class identifiers assigned to the structure and partial structures of said inputted structured data; said inputted structured data and said output structured data having tree structures corresponding to syntactic structures of symbol strings.
Claim 11
Independent Claim
195 words
A method performed in a data processing system for transforming structured data to differently-structured data in accordance with transformation rules input to said system, comprising the steps of: storing one or more transformation rules which classify structures and partial structures of input data into classes by assigning class identifiers respectively to the structures and partial structures, and describe the structures of input data using class identifiers assigned to the partial structures, and include descriptions of structures of output data, said descriptions of structures of output data being linked in a predetermined notational form with said class identifiers; inputting structured data; analyzing the structure of said inputted structured data to classify the structure and partial structures of said inputted structured data into classes based on said transformation rules, by seeking class identifiers assigned to the structure and partial structures of said inputted structured data; and producing structured data to be outputted based on the descriptions of the structures of output data linked with class identifiers assigned to the structure and partial structures of said inputted structured data; said inputted structured data and said output structured data having tree structures corresponding to syntactic structures of symbol strings.
Claim 12
Dependent Claim
93 words
The method as claimed in claim 9, wherein said analyzing step includes steps of: performing pattern matching of said inputted structured data and said transformation rules; classifying the structure and partial structures of said in putted structured data into said classes by establishing correspondence of the structure and partial structures of said inputted structured data to the class identifiers; forming a tree-structured intermediate structure having as nodes the class identifiers that correspond to the structure and partial structures of said inputted structured data; and recording results of said pattern matching in said nodes.
Claim 13
Dependent Claim
62 words
The method as claimed in claim 10, wherein said descriptions of structures of output data includes variables, and said producing step includes a step of substituting said results of pattern matching recorded in said nodes for the variables in the descriptions of structures of output data linked with said class identifiers in the nodes, thereby forming said structured data to be outputted.
Claim 14
Dependent Claim
42 words
The method as claimed in claim 11, wherein said step of forming an intermediate structure includes a step of producing a node connector which interlinks nodes of a plurality of intermediate trees using one node in common to superpose said intermediate trees.
Claim 15
Dependent Claim
34 words
The method as claimed in claim 9, wherein said classes are identified in said transformation rules by respective class identifiers, and said descriptions of output data are provided in association with said class identifiers.
References Cited (Backward Citations)
US4374408A
Cited
US4641264A
Cited
US4599691A
Cited
US4463423A
Cited
US4734848A
Cited
US4811400A
Cited
US5083268A
Cited
US4887212A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-06-13 | 1997-12-13 | 1998-06-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-06-13 | 2001-12-13 | 2002-06-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-06-13 | 2005-12-13 | 2006-06-14 | $7700.00 | Window Closed / Lapsed |