JP2722465B2 - Data conversion method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Industrial applications]   According to the present invention, the structure of the data conversion device is based on the conversion rule.
Regarding the conversion method from structure data to structure data, especially
A program based on conversion rules given from outside the processing system.
Language conversion, language conversion such as compiler, programming language
Suitable for interpreters, symbolic execution, automatic theorem proofs, etc.
Data conversion method. [Conventional technology]   Programming language interpreter, compiler, translation
Language conversion of translation, symbol execution, automatic theorem proof, etc.
In many cases, data conversion is performed by using structured data as an intermediary. An example
For example, in the case of a compiler, input statements that are character strings
Is converted to an analytic tree represented by this structure, and this tree structure
Perform semantic analysis, optimization, and code generation for structural data
And convert it to the target machine language. This process is input
Converting the given symbol string according to a given rule; and
Can be considered. Conventionally, a device that performs such conversion
Are often designed based on conversion rules.
The design had to be changed every time the rules were different.   In contrast, conversion devices that do not depend on individual conversion rules
One example is a parser generator. Parser Genere
Is a syntax that performs parsing based on the grammar entered.
Generate an analyzer.   In parsing, the grammar is usually a grammar rule or rewriting.
A set P of relations called rules, production rules, etc., and terminal symbols
And a set N of non-terminal symbols and a start symbol s
Is described. The grammar rule consists of the left and right sides,
Indicates that the symbol string on the left side is rewritten to the symbol string on the right side.
You. Non-terminal symbols are grammatical rules or rewriting rules described above,
Rewriting by a set of relations P called rules
The terminal symbol can be rewritten by the above set P.
It is a sign that cannot be obtained. The starting symbol s is a special non-
Is a terminal symbol, and if the input sentence conforms to the grammar,
By applying the above set P, the input sentence can be rewritten.
Can be.   One of the basic classes of grammar is context-free grammar.
You. The context-free grammar is defined as a grammar rule belonging to the set P
One non-terminal symbol on the left side, zero or more terminals on the right side, non-terminal
A sequence of terminal symbols and a restricted grammar, that is, each grammar rule
The rule is   A → a A∈N, a∈ (NUT)^* It is a grammar expressed as here,( )^*Is the responsibility of the set
Represents zero or more columns of meaning elements.   In general, the syntax used by traditional parser generators is
It is a grammar rule with strong restrictions. Statement like this
The cost of simplifying the parser is the structure of the sentence.
Description, that is, the analytic tree structure cannot be set freely
Has difficulties. In particular, grammars with recursive structures are notably described.
Receive about.   In contrast, DCG (Definite Clause Grammar)
Write the grammar in context-free grammar and write the grammar rules
og program and executed by Prolog processing system
Performs a syntax analysis. The details of the above DCG
Is F. Pereira and D. Warren, Definite Clause Grammar
s for Language Analysis-A Survey of the Formali
sm a Comparison with Augmented Transition Network
s, Artificial Intelligence, vol. 13, pp. 231-278 (198
0), and here is an overview. Less than
Below, start the predicate symbol with a lowercase letter and the variable symbol with an uppercase letter.
Expressed as an English character string.   DCG expresses grammar as a set of first-order predicate logic clauses
I do. Following this interpretation, parse a sentence in a language
This proves the theorem under an axiomatic system that describes a language.
Is interpreted as In addition, a set of clauses is a program
According to the notion that this theorem proves automatically
It can be carried out. In that sense, the grammar described in DCG
Is also axiom-based under first-order predicate logic, and
It can be executed as a Prolog program. This blog
Running the ram generates a top-down parser for that language
It is.   The DCG notation extends the notation of context-free grammar in two ways:
It is a stretch. (1) Allow nonterminals to have arguments. Example: Context-free grammar np DCG np (X, S) (2) List of nonterminals and terminal symbols on the right side of the grammar rules
Not only can you write procedure calls. Example: Context-free grammar name → NAME DCG name (name (W))                 → [W], {is_name (W)}   Here, NAME appearing on the right side of the context-free grammar is
Number, a specific string belonging to the lexical category of the name.
Express. {Is_name (W)} on the right side of DCG is
Calling a predicate is_name (W) that returns a true value if it is a name
Represents   For example, sentence (s (NP, VP), S0, S)   → noun_phrase (NP, S0, S1),     verb_phrase (VP, S1, S). (However, S0, S1, S represent the position in the word string) A series of grammar rules and dictionaries starting with are given as DCG
When input text [Every, man, loves, mary] In contrast, the grammar rules and dictionary are
Executed sentence (theta, [every, man, loves, mary], []) Becomes true. Where theta is a term s (np (det (every), n (man), rel (nil)), vp (tv
(Loves), np (name (mary))) Which is equivalent to a parse tree.   The DCG also allows the following description: (1) Condition can be given using procedure call
You. Example: date (D, M)   → month (M), [D],     {Integer (D), 0 <D, D <32}.   In this example, the date M / D is a phrase representing the year.
(M) followed by the grammar D
Predicate that is true if D is an integer
(D), a predicate 0 <D that is true when D is positive, and D is 32
Call the predicate D <32, which is true when less than, and let D be 0
Constrains to an integer greater than 32. (2) Using arguments to carry context-sensitive information
You can strike.   In this example, noun_phrase, verb_phrase,
Add an argument N to carry the number to the affected nonterminal
And noun_phras the given number singular, plural in the dictionary
e, transport to verb_phrase. noun_phrase, verb_phrase
The number carried by is matched at the sentence level and matches
Predicate sentence is true only if   In summary, DCG has the following features. (1) A grammar that extends the context-free grammar. (2) By executing it as a Prolog program,
Generate a sentence analyzer. (3) The result of the parsing is the final
A term given as an argument to the end symbol, and how to give the argument
Can give different output terms than just a parse tree.
It is possible. (4) Procedure calls can be described in grammar rules
You. (5) grammar rules that depend on the context can be described
You. [Problems to be solved by the invention]   The DCG described above introduces arguments to the grammar description and
Parse tree from input sentence
You can freely give the grammar that is the conversion rule to
A conversion system that does not depend on individual conversion rules can be configured.
Functioned. However, DCG converts input sentences to parse trees.
For the purpose of conversion, from structure data to structure data
In order to convert to, the structure data of the input
Expand to a string and convert it from string to structure data
Must be processed. This allows the number of components
Such as the structural information originally held by the input data is lost,
Conversion efficiency deteriorates.   The present invention has been made in view of the above circumstances,
However, the above-mentioned problem in the conventional technology is solved.
Can be freely given and given conversion rules, given
Data conversion based on the conversion rules
An object of the present invention is to provide a structure data conversion method. [Means for solving the problem]   SUMMARY OF THE INVENTION The above object of the present invention is to provide a structure data conversion method based on a conversion rule.
Data conversion method to convert data into structure data
Classify the substructures of the structure into classes,
The structure is described by the relationship between the classes,
Conversion that describes the output structure in association with the class
Provision of rules storage means to input structure data to be converted
To analyze the structure data to be converted,
Classifying into the rule class and the structure data to be output
Step for associating the data with the conversion rule class
Data conversion method characterized by having
Achieved.   Here, the class of the partial structure described above is used in the grammar description.
Corresponds to a non-terminal, but the non-terminal applies grammar rules
Generates a string by
Differs in that a structure is generated by applying a transformation rule
Things. [Action]   The class of the substructure is
Input structure for classifying sets into substructures
Is described using the above class, and the output structure is
By describing in association with the
Write conversion rules easily without losing structure information
be able to. At this time, the input structure is
Classes are part of the relationship between the classes described in the rule.
A structure that is derived by expanding to the structure class
Structs reduce the classes of substructures in reverse, and
A structure obtained by combining the structures associated with the class
is there.   Even in the data conversion process, through the substructure class
Analyze structure data and classify it into conversion rule classes
Follow the steps and description of the structure associated with the class.
Conversion by the step of forming a structure
The conversion of the structural information described in the conversion rules
Calculate directly, and duplicate calculation for partial structure
And efficient processing can be performed. 〔Example〕   Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
You.   FIG. 2 shows a structure data conversion processing system according to the present invention.
It is a functional block diagram of a program. In the figure, 1-3 are processing
4-8 show the functional configuration of the processing system
I have. That is, 1 is a conversion rule and 2 is input data.
Both are inputs to the processing system. 3 is data conversion
Is the output data obtained by performing
You.   4 analyzes the given conversion rules and converts them into internal representations
A conversion rule analysis unit that outputs to a conversion rule storage unit 7 described below;
5 selects a conversion rule to be given to a pattern matching unit 6 described later.
To control the formation of intermediate structures and output data.
The match match control unit 6 receives the input data and the conversion rule described above.
Rules, conversion rules, and patterns related to pattern matching of intermediate structures.
A turn match part, and 7 is one of the conversion rules described above.
8 is a conversion rule storage unit for storing an internal expression,
At the same time as remembering the information obtained during the conversion process
An inter-structure storage unit.   Next, the structure data is represented by terms, and the function of the present invention is shown as an example.
Show. Terms use function symbols, which are constant symbols with arguments
Therefore, it is defined as follows. (I) The function symbol of the 0 argument is a term. (Ii) f is a function symbol with n arguments, and r1, r2, and ‥‥ rn are terms
Where f (r1, r2, ‥‥ rn) is a term.   The term including the variable is defined as
Is defined as (I) A function symbol of 0 argument is a term including a variable. (Ii) Variable symbols are terms that include variables. (Iii) g is a function symbol with m arguments, and s1, s2, and ‥‥ sm are variables
G (s1, s2, ‥‥ sm) includes variables
Term.   The term including the class identifier is divided into function symbols, variable symbols,
It is defined as the term on the resource identifier as follows. (I) The function symbol of 0 argument is a term including a class identifier.
You. (Ii) A variable symbol is a term that includes a class identifier. (Iii) The class identifier is a term including the class identifier. (Iv) h is a function symbol with n arguments, and t1, t2, and ‥‥ tn are classes
If the term contains an identifier, h (1t, t2, ‥‥ tn) is the class
This is a term that includes a resource identifier.   Class using the class of the substructure that composes it
Then, it is defined as follows. <Class definition> Class identifier == term containing class identifier   Uppercase letter of class identifier prefixed with #, variable symbol _
Uppercase letters, function symbols in lowercase strings and alphanumeric characters
Sometimes the structure represented by the following five class definitions
The structure will be described.   # A == f (#B, #C) ‥‥ (a)   # B == i ‥‥ (b)   # B == j ‥‥ (c)   # C == u ‥‥ (d)   # C == v ‥‥ (e)   The above (a) indicates whether #A is a function symbol f and classes #B and #C.
(B) and (c) show the class B
Is a function symbol i or j, and (d),
(E) states that class C is a function symbol u or v
Shown respectively.   In other words, each class is a set of terms,   # A = {f (i, u), f (i, v), f (j, u), f (j, v)}   # B = {i, j}   # C = {u, v} Is represented.   When the input data is f (i, u), its structure is
Is analyzed as follows. (1) f (i, u) and #A are pattern matched, and #B, #C
For i and u respectively. (2) i and #B are pattern matched, and the above matches
Select (b). (3) Pattern matching between u and #C, and matching
Select (d).   At this time, the class identifier #A is a starting point of the processing.
Such a class identifier is hereinafter referred to as a start symbol.   As described above, in the present invention, the output structure is
Write it in association with the class. Here, the structure to output
Is a term that includes a variable, and a term that includes a variable in the class identifier.
Indicates the association followed by Information obtained during the conversion process
By replacing the variable symbol of the term containing the variable with the term.
Is stored.   Add the output structure to the above class definition example.
Consider an example of a conversion rule such as   #A [add (_X, _Y)]     == f (#B [_X], #C [_Y]) ‥‥ (a ′)   #B [zero]     == i ‥‥ (b ′)   #B [one]     == j ‥‥ (c ′)   #C [two]     == u ‥‥ (d ')   #C [three]     == v ‥‥ (e ')   Data conversion is performed according to the following procedure. (1) Pattern matching between input data f (i, u) and #A
And (a ') is selected, and at the same time, i,
Bind u. (2) i and #B are pattern matched and matched
(B ') is combined with #B on the right side of (a'). (3) The term of (b ') connecting the variable _X of (a')
Replace with zero. (4) u and #C are pattern matched and matched
(D ') is combined with #C on the right side of (a'). (5) The term of (d ') connecting the variable _Y of (a')
Replace with two. (6) Use the obtained term add (zero, two) as output data
You.   Here, binding of class identifier and input data, variables and output
Force data bindings are recorded at the nodes of the intermediate structure.   FIGS. 1A to 1D show basic processing operations of the present invention.
It is a flowchart shown.   FIG. 1 (a) is a main flow of the conversion rule analysis,
This processing is performed by the conversion rule analysis unit 4. Conversion rule analyzer 4
Reads conversion rule 1 and the start symbol, given them.
Take (step 20) and clean the structure according to the class identifier.
Classify as lath and mark the class corresponding to the start symbol
(Step 202). Conversion rules are converted to internal representation for each class
After making changes, analyze the relationships between classes and check
(Step 203), and stored in the conversion rule storage unit 7.
Output (Step 204).   FIG. 1B is a main flow of the data conversion.
Regarding data input / output and activation of pattern match control unit 5
You. Given input data, this data conversion processing system
Reads it (step 301) and creates an intermediate structure
A node serving as a starting point is generated in the storage unit 8, and an initial environment is recorded.
And obtains a start symbol from the conversion rule storage unit 7 (step 30).
2) Call procedure 1 with the node as an argument (step
303). If Procedure 1 succeeds (Step 30
4), the output data recorded on the node generated in step 302
The data is obtained (step 305) and output (step 306).
Otherwise, output a syntax error in the input data
(Step 307).   FIG. 1 (c) shows step 303 in FIG. 1 (b).
This is a processing flow of a procedure 1, in which the processing is performed by using the pattern
This is performed by the match control unit 5. The argument of procedure 1 is an intermediate structure
Class identifier and data from the given node.
(Step 401), and from the conversion rule storage 7,
Get a conversion rule with the class identifier of
402). If such a conversion rule is obtained (Step 4
03), using the conversion rules and the data obtained in step 401 above
Procedure 2 is read as an argument (step 404).
Return to Step 402. For all such conversion rules
Processing ended, procedure 2 failed for all of them
If not (step 405), return failure (step 406),
Otherwise, success is returned (step 407).   FIG. 1 (d) shows the procedure 2 of the procedure 2 shown in the step 404.
This is a processing flow.
6 does. The arguments for procedure 2 above are the conversion rules and the input data.
Pattern mapping between argument conversion rules and data.
(Step 501) If there is no match (Step 50
2), return failure (step 509).   If they match, the intermediate structure storage unit 8 is checked (
Step 503), Class identification on the right side of the matching conversion rule
If there is no node with a child and data pair, create a node.
(Step 504). Write the current environment at the node
Recording (step 505). The rules included on the right side of the conversion rule
For all class identifiers (step 506),
Procedure 1 is called with the point as an argument (step 507),
If procedure 1 is successful (step 508), the next class
The processing of the resource identifier is performed (step 506). If on the way
If at least one fails, a failure is returned (step 509).   The processing shown in FIG. 1B is performed in advance in the form of a conversion table.
You may make it input what was made.   The present invention can be implemented in hardware or software.
Therefore, it can also be implemented. In the following description
Describes an embodiment using software.   FIG. 3 is an example of information stored in the conversion rule storage unit 7.
You. FIG. 4 shows information stored in the intermediate structure storage unit 8.
This is an example. In FIG. 4, 71 is a node of the intermediate structure.
It is the details of. Here, the flag indicates that the node
True if all subnode sequences succeeded in pattern matching,
Otherwise, false. 72 is the leaf of the intermediate structure
73 is the details of the subnode. The subnode is the left of the relationship
Binding between the class identifier or variable symbol of the edge and the input data
Express. 74 is the details of the node connection information. Node connection information
Represents the connection between the nodes of the intermediate structure using a list structure.
I forgot.   FIGS. 6 (a) to 6 (e) show processing procedures according to an embodiment of the present invention.
It is a flowchart which shows the detail of a sequence.   FIG. 6A is a flowchart of a main routine.
Yes, input / output of data and activation of pattern match control unit 5
I do. That is, the input data is read (step 90).
1) Generate special starting nodes and subnodes (step
(Step 902), the environment is initialized (Step 903). Ma
Further, a start symbol is obtained from the conversion rule storage unit 7, and the start symbol,
Input data and subnodes generated in step 902 described above
The procedure 1 is read by using the
Continue 1 to evaluate output data under the environment set as a node
(Step 905), and output (Step 906).   FIG. 6 (b) is a flowchart of the procedure 1 described above.
You. Procedure 1 converts the class identifier, input data, and subnodes
Performs a pattern match as an argument. First, conversion rules
Conversion rule with class identifier of argument on left side from storage unit 7
(Step 1001), there is no corresponding conversion rule
If (step 1002) return, if not
Stores the argument data from the intermediate structure storage unit 8 in the first element
Search for a node (step 1003), if it does not exist
If the second element of the conversion rule, data, and subnodes are arguments,
Call procedure 2 (step 1004) and go to step 1001
Return. If the above node exists,
If the pointer to the point is in the pointer set to the parent subnode
If (step 1005), go back to step 1001, otherwise
If so, a pointer to the subnode is added to the set (step 100).
6) If the node flag is true (step 1007),
To step 1001, otherwise the nodes and subnodes as arguments
And call procedure 4 (step 1008), step 1001
Return to   FIG. 6C is a flowchart of the procedure 2 above.
You. Procedure 2 consists of the term containing the class identifier, the input data,
Using the nodes as arguments, the generation of intermediate structure nodes and the
Matching term including input identifier and input data, subsection
Generate points. First, a node is generated (step 110).
1) Pattern match the second element of the conversion rule with the node
(Step 1102). If the pattern match fails
Step 1103) Return, if successful, enter the conversion rules
Check whether the pattern includes a class identifier (step 110)
4) If not, use procedure 3 with nodes as arguments
Call (step 1105), otherwise create subnodes
(Step 1106), the generated sub-nodes and their first and third sub-nodes
Procedure 1 is called with the element as an argument (step 110)
7).   FIG. 6D is a flowchart of the procedure 3.
Procedure 3 uses the nodes of the intermediate structure as arguments
Generate information and combine nodes. First, set the node flag
true (step 1201), and the parent sub-clause starts from the second element of the node
Points are obtained (step 1202). If parent subnode does not exist
Return (step 1203) and, if it exists, the node
The pointer to the parent and the fifth element of the parent subnode as a set
Generate joint information (step 1204) and connect the nodes of the parent subnodes.
In addition to the joint information (step 1205), the sixth element of the parent subnode
The next parent subnode is obtained from (step 1206). Next parent subclause
If a point exists (step 1207), the obtained subnode and its
Procedure 1 is called with the first and third elements of
Step 1208), and return to step 1202. Otherwise, parent
Procedure 3 using the parent node traced from the subnode of
Call (step 1209) and return to step 1202.   FIG. 6E is a flowchart of the procedure 4 described above.
You. Procedure 4 takes the nodes and subnodes of the intermediate structure as arguments
Then, node connection information is generated and nodes are shared. First,
Generate node connection information from arguments, nodes and subnodes (step
1301), in addition to the node connection information of the fifth element of the subnode,
(Step 1202), the next subnode is obtained from the sixth element of the subnode.
Obtain (step 1203). If the next subnode exists
(Step 1304) Subtracting the obtained subnode and its first and third elements
Procedure 1 is called as the count (step 1305).
If the node does not exist, subtract the parent node followed from the subnode.
Procedure 3 is called as the number (step 1306).   FIG. 5 shows an example of the conversion rule,
It is a figure showing the internal expression of an inter-structure. Processing of this embodiment
In order to help the understanding, a supplementary explanation is given below using FIG.
Do.   61 (1) to 61 (5) are converted by the conversion rule analysis unit 4
This is the conversion rule that has been analyzed.
Is attached, and 61 (1) is changed to 61 (2) and 61 (3) from #B.
Chains from 61 (1) to 61 (4), 61 (5)
Is chained by #C.   71 (1) is the top level when classifying structures into classes.
The main routine calls this a sub-node
Generated in step 902 together with (1), # A, f (i, u), 73
Call procedure 1 with (1) as an argument (step 90)
Four). Procedure 1 is a transformation having #A on the left side in step 1001.
Find the replacement rule 61 (1) and find f (# B, # C), f (i, u),
Call procedure 2 with 73 (1) as an argument (step 10)
04). Procedure 2 generates node 71 (2) (step 11).
01), pattern matching between f (#B, #C) and f (i, u)
(Step 1102). By this pattern match, #B
And i, #C and u match, so 73 (2) and 73 (3)
Is generated (step 1106), and the sixth element of 73 (2) is
Procedure 1 using #B and i, 73 (2) as arguments
Is called (step 1107).   Procedure 1 is a conversion rule 61 having #B as the first element.
(2), 61 (3) is searched (step 1001), i, i, 73
For each of the set (2) and the set i, j, 73 (2),
Procedure 2 is called (step 1004). i, j, 73 (2) is subtracted
Procedure 2 called as a function generates node 72 (2)
(Step 1101), i and j are pattern matched,
(Step 1102) Since there is no match, the procedure returns to Procedure 1.   On the other hand, the procedure called with i, i, 73 (2) as an argument
2 generates a node 72 (1) (step 1101), i and i
Is pattern matched (step 1102)
Call procedure 3 with 72 (1) as an argument (step 11)
05). Procedure 3 sets the flag of 72 (1) to true (step
Steps 1201) and 73 (2) are obtained from the second element of 72 (1) (step 1201).
Step 1202), 5th element of 72 (1) and 73 (2) (initial value
Is nil) and generates 74 (2) to form the fifth of 73 (2).
Element (steps 1204 and 1205), the sixth element of 73 (2)
73 (3) is obtained (step 1206), #C and u, 73 (3)
Procedure 1 is called by using as an argument (step 1208).   Here, the same as performed for #B and i, 73 (2)
Perform processing, generate 72 (4), 72 (3), and convert 74 (3)
The connection is made to 73 (3) through the connection (step 1205). 73 (3)
Is the nil (step 1207), so the 73 (3)
Procedure 3 is called using the second element 71 (2) as an argument.
(Step 1209). Procedure 3 sets the flag of 71 (2)
Set true (step 1201), and obtain 73 (1) (step 12)
02) and 74 (1) are generated as the fifth element of 73 (1).
Steps 1205) and 73 (1) are 71 because the sixth element is nil
Procedure 3 is called using (1) as an argument (step 120).
9). Procedure 3 sets the flag of 71 (2) to true and sets 73
(1) is obtained (steps 1201 and 1202), and 74 (1) is generated.
(Step 1204) As the fifth element of 73 (1) (Step 1204)
1205), 73 (1) continues nil because the sixth element is nil
Procedure 3 is called as the count. Procedure 3 is 71 (1)
Set the flag to true and get the parent subnode from the second element of 71 (1)
(Step 1202), but because it is nil (step 1203)
The procedure returns to procedure 3 on the sending side. Procedure 3 of the caller is 71
Since the processing of the parent subnode of (2) is completed, the calling side
Return to procedure 3. In this way, procedures are released one after another.
Then, control transfers to step 905 of the main routine.   Step 905 is the output of the top-level node 71 (1).
The pattern_X is converted into the subnode 73 (1) and the node connection information 74 (1).
Through the output pattern of the node 71 (2) add (_X, _Y)
And bind. Here, it is connected to the sub node through the node connection information.
Although there are generally multiple nodes that match, the
Constrain each of the force patterns and the output pattern of the parent node.
Bundle 71 (1) output pattern and 71 (2) output pattern
Variable symbol of the output pattern of 71 (2)
_X is the output path of node 72 (1) via subnode 73 (2).
At turn zero, the variable symbol _Y goes through subnode 73 (3)
Bound to the output pattern two at node 72 (3).   As a result of these bindings, all variable symbols are replaced.
The term add (zero, two) is created. The processing system must use this term
Output (step 906), and the conversion process ends.   In the present embodiment, the node connection information is aggregated.
A plurality of intermediate structures are superimposed and represented
The memory size occupied by the structure has been reduced.   The internal expressions shown in FIGS. 4 and 3 are logically equivalent.
Instead of another expression, such as a list expression, a table
It can also be implemented using expressions such as Also, in FIG.
The pointer to the input data identifies the input data and
Replacement with other information that has enough information for the match
Can be. The same applies to other information. In addition, multiple
If there is no need to represent the intermediate structure of
No node connection information is required.   The processes shown in FIGS. 1A to 1E are sequentially performed.
Or in parallel.   The present invention can be used to represent abstract data types.
You. Two data types SEQITEM, VECT defined as follows
This is shown by taking OR as an example. sort: SEQITEM operations: nlsq → SEQITEM            apdl ITEM, SEQITEM → SEQITEM            car SEQITEM → ITEM            cdr SEQITEM → SEQITEM            isnil SEQITEM → BOOLEAN laws: car (apdl (_i, _s)) = _i            cdr (apdl (_i, _s)) = _s            isnil (nlaq) = true            isnil (apdl (_i, _s)) = false sort: VECTOR operations: emptyv → VECTOR            assign VECTOR, INDEX, ITEM                                   → VECTOR            read VECTOR, INDEX → ITEM laws: read (emptyv, _ix) = undefined            : read (assign (_v, _ix1, _i), _ ix2)               = If _ix1 = _ix2                 then _i                 else read (_v, _ix2)   The implementation of the data type SEQITEM by VECTOR is shown in the following table.
Be forgotten. d_SEQITEM(Nlsq) = emptyv d_{ITEM SEQITEM SEQITEM}(Apdl (_i, _s))   = <Assign (vector (_s), size (_s) + 1, _i), size
(_S) +1> d_{SEQITEM ITEM}(Car (_s))   = Read (vector (_s), size (_s)) d_{SEQITEM SEQITEM}(Cdr (_s))   = <Vector (_s), size (_s) -1>   In the present embodiment, this is given as the following conversion rule.
You.   #SEQITEM [_s]     == # SZDVCT [_s]   #SZDVCT [<_ v, _ix>]     == <# VECTOR [_v], #INDEX [_iv]>   #SZDVCT [<emptyv, zero>]     == nlsq   #SZDVCT [<assign (_v, _ix + 1, _i), _ ix + 1>]     == apdl (#ITEM [_i], #SEQITEM [<_ v, _ix
>])   #ITEM [read (_v, _ix)]     == car (#SEQITEM [<_ v, _ix>]   #SZDVCT [<_ v, _ix-1>]     == cdr (#SEQITEM [<_v, _ix>]   Expression as input data car (cdr (cdr (apdl (C, apdl (B, apdl (A, ni
l)))))) And this conversion rule gives the expression read (   <Assign (     <Assign (       <Assign (         <Emptyv, 1>       1, A), 1>,     2, B), 2>,   3, C), 3> , 1) Is converted to   The present invention can be used to implement algebraically described specifications.
Can be. Abstract data types are algebraic specifications of data types
So, taking SEQITEM as an example,
You. laws is expressed as follows in the conversion rules of this embodiment.
It is.   #SEQITEM [nlsq]     == nlsq   #SEQITEM [apdl (_i, _s)]     == apdl (#ITEM [_i], #SEQITEM [_s])   #ITEM [_i]     == car (apdl (#ITEM [_i], #SEQITEM [_
s]))   #EXP [_s]     = Cdr (apdl (#ITEM [_i], #SEQITEM [_s]))   #BOOLEAN [true]     == isnil (nlsq)   #BOOLEAN [false]     == isnil (apdl (_i, _s))   #EXP [apdl (_e)]     == apdl (#EXP [_e]   #ITEM [car (_e)]     = Car (#EXP [_e])   #EXP [cdr (_e)]     == cdr (#EXP [_e])   By repeatedly applying this conversion rule, the expression car (cdr (cdr (apdl (C, apdl (B, apdl (A, ni
l)))))) Is   car (cdr (apdl (B, apdl (A, nil))))   car (apdl (A, nil))   A Is converted to In this embodiment, the steps of the main routine are executed.
By repeating steps 902-095,
Can be realized.   The conversion rule of this embodiment is also implemented by another notation.
be able to. An example is shown below. <Conversion rules> → List of <Class definition> <Operation rules> <Class definition> → Class identifier → Term containing class identifier <Operation rules> → == terms including variables {list of <binding expressions>} <Binding type> →   Term including variable == class identifier   The following is an example of the conversion rule described in this notation.
You.   # SEQITEM → # SZDVCT     == _ x ｛_X == # SZDVCT｝   # SZDVCT → <# VECTOR, # INDEX>     == <_ v, _ix> ｛_V == # VECTOR, _ix == # INDEX｝   # SZDVCT → nlsq     == <empty, zero>   # SZDVCT → apdl (# ITEM, # SEQITEM)     == <assign (_v, _ix + 1, _i), _ ix + 1> {_I == # ITEM, <_ v, _ix> == # SEQITEM}   # ITEM → car (#SEQITEM)     == read (_v, _ix) ｛<_V, _ix> == # SEQITEM｝   # SZDVCT → cdr (#SEQITEM)     == <_ v, _ix-1> ｛<_V, _ix> == # SEQITEM｝   The above rules are also applied to the conversion rules described in this way.
Only conform to the notation of the conversion rule
Conversion can be performed without changing other processes
You. 〔The invention's effect〕   As described above, according to the present invention, the conversion rule
Data conversion method for converting structure data to structure data
Classifies the substructures of a structure into classes
Is described by the relationship between the above classes
In both cases, the structure to be output is described in association with the class.
Storage means for the conversion rules to be
Data, and analyze the structure data to be converted.
Classifying into a conversion rule class;
Reconstruct the structure data by associating it with the conversion rule class
DCG
Without losing the structural information of the structure as in
Can be given freely, and based on given conversion rules,
Structure data conversion that can perform data conversion efficiently
It has a remarkable effect that the method can be realized.
You.

BRIEF DESCRIPTION OF THE DRAWINGS FIGS. 1 (a) to 1 (d) are flowcharts showing basic processing operations of the present invention, FIG. 2 is a functional block diagram of a structure data conversion processing system according to the present invention, and FIG. FIG. 4 and FIG. 4 are diagrams showing the internal representation method of the information of the embodiment, FIG. 5 is a diagram showing a specific example of the internal representation of the information, and FIGS. 6 (a) to 6 (e) show the processing procedure of the embodiment. It is a flowchart which shows details. 1: Conversion rule, 2: Input data, 3: Output data, 4: Conversion rule analysis unit, 5: Pattern match control unit, 6: Pattern match unit, 7: Conversion rule storage unit, 8: Intermediate structure storage unit.

Claims (1)

(57) [Claims] In a data conversion method for performing conversion between structure data formed by explicit connection of partial structures based on a conversion rule, a partial structure of a structure is classified into a class, and an input structure is inter-class Storage means for storing a conversion rule that describes a structure to be output in association with the class, inputs structure data to be converted, and stores the structure data to be converted with the conversion rule A data conversion method, comprising: collating and analyzing into a class; and reconstructing output structure data based on the conversion rule class. 2. Analyzing the structure data to be converted, performing pattern matching between the input structure data and the conversion rule, and comparing a partial structure of the input structure data with the class; Forming an intermediate structure having a class as a node based on the relationship between the classes described in the rules, and recording a result of the pattern matching on a node of the intermediate structure, the structure data to be output Reconstructing the pattern matching results recorded on the intermediate structure, the step of applying to the description of the structure associated with the corresponding class, the recorded on the intermediate structure 2. The data conversion method according to claim 1, further comprising the step of: combining the application results to form structure data.