JP2904112B2 - Automatic program synthesizer - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an automatic program synthesizing technique for synthesizing a program by repeatedly converting a program specification expressed in a tree structure based on a plurality of rewriting rules.

[0002]

2. Description of the Related Art A type of automatic program synthesizing system uses a structure of a subtree for performing conversion in a program specification on a left side and a set of rewriting rules defining a structure after conversion of the subtree on a right side. There is an apparatus that automatically generates a program by repeating conversion of a program specification represented by a tree structure having function symbols as nodes. If there are a plurality of parts that can be rewritten according to the rewriting rules in the program specification to be rewritten, the strategy to determine which one is to be rewritten preferentially is the part closest to the root and the leftmost part in the tree structure of the program specification. There is a leftmost outermost strategy that rewrites the part and a leftmost innermost strategy that rewrites the part closest to the leaf and the leftmost part. In the present invention, the latter leftmost innermost strategy is used. It is intended for automatic program synthesizers.

FIG. 2 shows an example of a program specification expressed in a tree structure, FIG. 3 shows an example of a set of rewrite rules, and FIG. 4 shows a diagram in which those rewrite rules are expressed in a tree structure. Here, lowercase alphanumeric characters represent function symbols, and uppercase alphanumeric characters represent variables. FIG. 5 corresponds to FIGS.
2 shows a process of repeating the conversion of the program specifications shown in FIG. 2 using the rewriting rules shown in FIG. The conversion in the conventional automatic program synthesizer proceeds as follows.

[0004] In the leftmost innermost strategy, rewriting is performed from the leftmost innermost part (the part closest to the leaf and the leftmost part) of the program specification. Therefore, first, a rewrite rule having a subtree conforming to the leftmost innermost part of the program specification of FIG. 2 on the left side is searched from the rewrite rule set shown in FIGS.
Is obtained based on the leftmost innermost part of the program specification and the contents of the right side part of the rule 33, and executes “rewrite1” shown in FIG. Rewrite the innermost part.

[0005] Next, a rewrite rule having a subtree conforming to the leftmost innermost part of the rewritten program specification on the left side is searched from the rewrite rule set, and a rewrite rule 31 having a left side 502 shown in FIG. Then, based on the leftmost innermost part of the program specification and the contents of the rule 31, “rewrite 2” shown in FIG. 5 is executed to rewrite the leftmost part of the program specification again.

Next, a rewrite rule having a subtree conforming to the leftmost innermost part of the rewritten program specification on the left side is searched from the rewrite rule set, and a rewrite rule 32 having a left side portion 503 in FIG. Then, based on the leftmost innermost part of the program specification and the contents of the rule 32, “Rewrite 3” shown in FIG. 5 is executed, and the leftmost part of the program specification is rewritten again.

Next, a rewrite rule having a subtree matching the leftmost innermost part of the rewritten program input specification on the left side is searched from the rewrite rule set, and 501 in FIG.
Is obtained, and based on the leftmost innermost part of the program specification and the contents of the rule 33, "rewrite 4" shown in FIG. 5 is executed, and the leftmost innermost part of the program input specification is rewritten again. . Then, since the rewritten program specification is in the normal form in which no further rewriting is performed, the rewriting is terminated.

[0008]

As described above, in the conventional apparatus, a program specification expressed in a tree structure is rewritten using a rewrite rule, and when a new tree structure is generated, the program is rewritten from the tree structure again. Applicable rules were selected from the rewrite rules in the rule set. For this reason,
Even when it is decisive that the structure generated by the rewrite rule is directly rewritten by another rewrite rule, the rewrite rule must always be selected again, resulting in a slow rewrite process. There is. Here, there is a case where it is decisive that the structure generated by the rewrite rules is directly rewritten by another rewrite rule. Each rewrite rule is created by considering all the other rewrite rules. It is difficult to keep in mind that the rewriting rule set is added to the existing rewriting rule set in order to enhance the rewriting rule set, and the rule itself is used for debugging etc. The main factor is that it is created in a format that is easy for people to understand.

Therefore, an object of the present invention is to analyze a set of rewrite rules in advance so that a tree structure generated after applying a certain rewrite rule may be rewritten by another rewrite rule in the set of rewrite rules. In such a case, it is possible to reduce the cost required to select a rewrite rule applicable to a rewritable part by allowing the rewrite rule to be directly rewritten without selecting the rewrite rule again, thereby improving the speed of the program synthesizing process. .

As an apparatus for improving the efficiency of rewriting as in the present invention, Japanese Patent Laid-Open No.
No. 2,510,662. In this conventional technique, a set of rewriting rules is analyzed in advance to obtain a set of function symbols that are candidates for rewriting. Function symbols that are not included in this set are not originally subjected to conversion. Such a function symbol is marked in advance, and when searching for a rewritable portion in the program specification, the marked portion is excluded from the search range. This prior art aims to improve efficiency by narrowing a search range in a program specification.
On the other hand, the present invention aims at improving efficiency by reducing the frequency of selecting rewrite rules, and both have the same purpose, but differ in the approach to achieve it.

[0011]

When the leftmost innermost strategy is adopted, among the rewrite rules included in the set of rewrite rules, the function symbol appearing on the right side of the rewrite rules is the same as the own rewrite rule or another rewrite rule. If it is the same as the outermost function symbol of the subtree defined on the left side (function symbol at the position closest to the root), the subtree rewritten by the rewriting rule immediately follows its own rewriting rule or Rewriting may be performed again according to the other rewriting rules. Therefore, in the present invention, a set of rewrite rules is analyzed in advance to identify rewrite rules having the above-described relationship, and a tree structure generated after application of a certain rewrite rule is replaced with another rewrite rule in the set of rewrite rules. If there is a possibility that the rewriting rule is rewritten, the rewriting rule is directly rewritten without selecting the rewriting rule again.

[0012]

That is , according to the present invention, a function symbol is defined by using a set of rewrite rules defining the structure of a subtree for performing conversion in a program specification on the left side and a structure after conversion of the subtree on the right side. In a program automatic synthesizer that generates a program by repeating the conversion of a program specification expressed in a tree structure with nodes, a set of rewrite rules is input, and the outermost function symbols of the subtrees defined on the left side are the same. For each group of rewrite rules that is, based on the subtree structure to be converted given by the caller as an argument, it is determined which rewrite rule of the rewrite rule of the group matches the subtree to be converted, and is matched. outermost function of the defined partial tree on the left side portion of one of the rewrite rules of its own group and other groups in the portion of the tree that is defined on the right side portion corresponding to the left side portion When the symbol exists, the rewriting function corresponding to the existing outermost function symbol is called with the structure of the converted subtree based on the definition of the right side as an argument, and the return value is returned to the caller. If there is no such outermost function symbol, a rewrite rule compiling unit that generates a rewrite function that returns the structure of the subtree after conversion based on the definition of the right side to the caller as a return value, and a program specification to be converted The rewrite function corresponding to the outermost function symbol of the subtree is called with the structure of the conversion target subtree searched based on the leftmost innermost strategy as the argument, and the returned converted subtree structure And a rewriting device that repeats the process of rewriting the conversion target subtree until there is no more convertible subtree.

Further, according to the present invention, the rewriting rule compiling unit analyzes the rewriting rules included in the set of the rewriting rules input by the outermost function symbol registration unit on the left side, the rewriting rule registration unit, and analyzes the left side portion of the rewriting rules. The type of the outermost function symbol registered in the subtree is registered in the leftmost outermost function symbol registration unit, and the input rewrite rules are grouped for each type of the outermost function symbol, and are registered in the rewrite rule registration unit. Whether the rewriting rule analysis unit to be registered and the subtree defined on the right side of the rewriting rule registered in the rewriting rule registration unit include a function symbol of the type registered in the leftmost outermost function symbol registration unit. For each group of rewrite rules registered in the rewrite rule registration unit, the call Based on the conversion target subtree structure given as an argument from the source, it is determined which rewriting rule of the corresponding group matches the left side of the conversion rule with the conversion target subtree, and a mark is placed on the right side corresponding to the matching left side. When is marked, the rewrite function corresponding to the function symbol with the mark is called using the structure of the subtree after conversion based on the definition of the right side as an argument, and the return value is returned to the caller, and the mark is returned. And a rewrite function generation unit that generates a rewrite function that returns the structure of the subtree after conversion based on the definition of the right-hand side to the caller as a return value.

[0015]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, embodiments of the present invention will be described in detail with reference to the drawings.

Referring to FIG. 1, an automatic program synthesizing apparatus 10 according to one embodiment of the present invention is an apparatus for generating a program 23 by repeatedly converting a program specification 22 using a rewrite rule set 24. An input unit 11, a rewrite device 12, a program output unit 13, a rewrite function storage unit 14, a rewrite rule compiling unit 15, and a rewrite rule set input unit 21 are provided.

An automatic program synthesizing apparatus 10 according to the present embodiment.
Are roughly divided into a part for generating a rewrite function from the rewrite rule set 24 and a part for generating a program 23 from the program specification 22 using the generated rewrite function. Hereinafter, the former part will be described first, and then the latter part will be described.

The part for generating a rewrite function from the rewrite rule set 24 includes a rewrite rule set input unit 21 for inputting the rewrite rule set 24, and a rewrite rule compiling unit 15 for generating a rewrite function from the input rewrite rule set 24. , And a rewriting function storage unit 14 for storing the generated rewriting function.

FIG. 3 shows an example of the rewrite rule set 24. FIG. 4 shows a tree structure of each of the rewrite rules 31 to 33 in the rewrite rule set 24 of FIG. In FIGS. 3 and 4, lowercase alphanumeric characters indicate function symbols, and uppercase alphanumeric characters indicate variables.
Each of the rewrite rules 31 to 33 is, as shown in FIG.
It is composed of a left side, a right side, and a symbol (arrow) connecting them. The left side defines the structure of the subtree to be converted in the program specification, and the right side defines the structure after conversion of the subtree.

If the rewrite rule set 24 of this example is applied as it is, the selection of the rewrite rule becomes redundant with respect to the leftmost innermost portion which becomes a (X, 1) or a (X, 0) in the program specification. That is, if the leftmost part in the program specification is a (X, 1), the rewriting rule 31 is selected and converted into a (X, 0). Since the conversion for the leftmost innermost part is performed, next, the rewriting rule 32 is selected, the leftmost part is converted to b (X), the rewriting rule 33 is selected, and finally converted to X. This is because the rewriting rule is selected twice. Similarly, the leftmost innermost part of the program specification is
If a (X, 0), the rewriting rule 32 and the rewriting rule 33 are selected in this order and are finally converted to X, and a total of two rewriting rule selections are required. Therefore, in this embodiment, in order to eliminate such redundancy, the leftmost innermost part in the program specification is a (X, 1) or a.
If (X, 0), a rewrite function that immediately returns X as the conversion result is generated based on the rewrite rule set 24. This generation is performed by the rewrite rule compiling unit 15.

As shown in FIG. 1, the rewriting rule compiling section 15 includes a rewriting function generating section 16, a left side outermost function symbol registration section 17, a right side mark section 18, a rewriting rule registration section 19, a rewriting rule analysis section And a unit 20.

The leftmost outermost function symbol registration unit 17 is a part that holds the type of the outermost function symbol of the subtree defined on the left side of the rewriting rules 31 to 33 included in the rewriting rule set 24. The writing is performed by the analysis unit 20 and is referred to by the rewriting function generation unit 16. Here, the outermost function symbol of the subtree means a function symbol at a position closest to the root of the subtree.
In the case of 32, it is a, and in the case of the rewriting rule 33, it is b.

The rewrite rule registration unit 19 is a unit that holds the rewrite rules 31 to 33 included in the rewrite rule set 24 by grouping them according to the type of the outermost function symbol on the left side. The writing is performed, referenced and marked by the right side mark unit 18, and referenced by the rewrite function generation unit 16.

The rewrite rule analysis unit 20 inputs the rewrite rule set 24 through the rewrite rule set input unit 21, analyzes the rewrite rules 31 to 33 included in the input rewrite rule set 24, and defines the rewrite rules 31 to 33 on the left side of the rewrite rule. Means for registering the type of the outermost function symbol obtained in the subtree in the leftmost outermost function symbol registration unit 17, and grouping the inputted rewriting rules for each type of the outermost function symbol and registering them in the rewriting rule registration unit 19 It is.

The right side mark section 18 has a function symbol of the type registered in the left side outermost function symbol registration section 17 in a subtree defined on the right side of the rewrite rule registered in the rewrite rule registration section 19. This is a means for checking whether or not the function symbol exists on the right side of the function symbol.

The rewriting function generator 16 generates, for each group of rewriting rules registered in the rewriting rule
One rewrite function is generated, and the rewrite function storage unit 1
4 means. The generated rewrite function is
Based on the following function, that is, based on the subtree structure to be converted given by the caller as an argument, it is determined which rewrite rule of the relevant group matches the subtree to be converted, and the left side to be matched is determined. If the outermost function symbol of the subtree defined on the left side of the rewriting rule of the own group or another group exists in the subtree defined on the right side corresponding to Calls the rewrite function corresponding to the existing outermost function symbol with the structure of the subtree as an argument, returns the return value to the caller, and if there is no such outermost function symbol, the It has a function to return the structure of the subtree after conversion to the caller as a return value.

FIG. 6 is a flowchart showing a processing example of the rewriting rule compiling unit 15. Hereinafter, the operation of the rewrite rule compiling unit 15 will be described with reference to FIGS.

In the initial state, the contents of the leftmost outermost function symbol registration unit 17 and the rewrite rule registration unit 19 have been cleared. At the time of compiling, first, the rewrite rule analysis unit 20 inputs the rewrite rule set 24 through the rewrite rule set input unit 21 (S1).

Next, for each of the rewrite rules included in the input rewrite rule set 24, steps S2 to S5
Is performed. First, it is checked whether or not the outermost function symbol on the left side of the rewriting rule (leftmost outermost function symbol) is registered in the leftmost outermost function symbol registration unit 17 (S3). Later (S4),
The rewriting rule is registered in the rewriting rule registration unit 19 in association with the leftmost outermost function symbol (S5). On the other hand,
If the leftmost outermost function symbol of the rewriting rule has already been registered in the leftmost outermost function symbol registration unit 17, the process proceeds to step S
Step 4 is skipped and the current rewrite rule is registered in the rewrite rule registration unit 19 in association with the leftmost outermost function symbol (S5). When the above processing is repeated for all the rewrite rules (YES in S6), the processing of rewrite rule analysis unit 20 ends. At this time, all the types of the outermost function symbols of the subtree defined on the left side of the rewrite rule included in the rewrite rule set 24 are registered in the leftmost outermost function symbol registration unit 17. 19, all the rewrite rules are grouped and registered for each type of the leftmost outermost function symbol.

Next, the right side mark section 18 performs the processing of steps S7 to S9 for each rewrite rule registered in the rewrite rule registration section 19. First, it is checked whether or not a function symbol registered in the leftmost outermost function symbol registration unit 17 exists on the right side of the rewriting rule (S
8) If present, mark the existing function symbol on the rewriting rule registration unit 19 (S9). On the other hand, if it does not exist, the marking process is not performed. When the above processing is repeated for all the rewriting rules (YES in S10), the processing of the right side mark unit 18 ends. At this point, among the rewrite rules stored in the rewrite rule registration unit 19, the outermost subtree defined on the left side of the rewrite rule of the own group or another group is included in the subtree defined on the right side. For a rewrite rule having the same function symbol as the function symbol, the function symbol is marked.

Next, the generation of the rewrite function by the rewrite function generation unit 16 and the storage in the rewrite function storage unit 14 are executed (S11).

FIG. 7 is a flowchart showing details of step S11 in FIG. Hereinafter, the operation of the rewrite function generator 16 will be described with reference to FIGS.

The rewriting function generating section 16 executes steps S21 to S30 for each function symbol registered in the leftmost outermost function symbol registering section 17, thereby generating a rewriting function corresponding to the function symbol.

First, attention is paid to one function symbol registered in the leftmost outermost function symbol registration unit 17 (S21), a corresponding rewriting function name is generated, and a rewriting function skeleton is generated (S22). Next, all the rewriting rules associated with the function symbol are input from the rewriting rule registration unit 19 (S23), and the processes of steps S24 to S28 are executed for each rewriting rule.

First, paying attention to one rewrite rule (S2
4) From the left side, a program fragment for performing pattern matching as necessary is generated in the skeleton part (S25).
A program fragment for performing a pattern match is composed of a program part for performing a pattern match in accordance with the structure of a subtree defined on the left side, and a program part for performing a process of substituting variables appearing on the left side. Next, a program fragment that returns the structure of the rewritten subtree when the pattern matches is generated, but the program fragment to be created differs depending on whether or not there is a mark on the right side.
It is determined whether or not there is a mark on the right side of the currently focused rewrite rule, and the processing is divided (S26).

If there is a mark on the right side, the rewriting function corresponding to the function symbol with the mark is called using the structure of the subtree after conversion based on the definition of the right side as an argument, and the return value is called by the caller. Is generated in the skeleton part (S28).

On the other hand, when there is no mark on the right side, a program fragment for returning the structure of the subtree after conversion based on the definition of the right side to the caller as a return value is generated in the skeleton section (S27).

The above processing is executed for all the rewrite rules input in step S23, that is, for the rewrite rules having the same outermost function on the left side (S29).
One rewrite function corresponding to the leftmost outermost function is generated and stored in the rewrite function storage unit 14 (S3).
0).

When the above processing is completed for all the function symbol units registered in the leftmost outermost function symbol registration unit 17 (S31), the rewriting function storage unit 14 stores each leftmost outermost function symbol in the rewriting function storage unit 14. Since the corresponding rewriting function has been stored, the processing of the rewriting function generator 16 ends.

FIG. 8 shows the rewrite rule set 2 illustrated in FIG.
4 shows an example of the contents of the leftmost outermost function symbol registration unit 17 and the rewrite rule registration unit 19 after the rewrite rule analysis unit 20 and the right-side mark unit 18 of the rewrite rule compilation unit 15 have performed the processing for No. 4. . 3 shown in FIG.
Since two rewriting rules 31 to 33 have two types of outermost function symbols on the left side, a and b, two of a and b are registered in the leftmost outermost function symbol registration unit 17 as shown in FIG. Is done. Also, since the rewriting rules 31 and 32 have a as the rewriting rule 33 and the rewriting rule 33 have b as the outermost function on the left side,
On the rewriting rule registration unit 19, the rewriting rules 31 and 32 are registered as a group 81 having the leftmost outermost function a, and the rewriting rule 33 is registered as a group 82 having the leftmost outermost function b. Furthermore, rewriting rule 3
Since the function symbols a registered in the leftmost outermost function symbol registration unit 17 exist on the right side of 1 and 32, FIG.
Each is marked as shown in FIG.

FIG. 9 shows an example of the rewrite function stored in the rewrite function storage unit 14. The rewrite function in this example is
It is generated by the rewriting function generator 16 based on the contents of the leftmost outermost function symbol registration unit 17 and the rewriting rule registration unit 19 illustrated in FIG. 8, and both are generated as one function in the C language. Among them, the rewrite function 91 is composed of two rewrite rules 31 belonging to the group 81 registered in the rewrite rule registration unit 19 in FIG.
The rewriting function 92 is a function for rewriting the function symbol a generated based on the function symbol 32, and the rewriting function 92 is a function for rewriting the function symbol b generated based on one rewriting rule 33 belonging to the group 82.

The rewriting function 91 is given variables X and Y as arguments. Since the structure of the left side of the rewrite rule 31 is (X, 1), a program fragment “if (Y == 1)” for checking whether the variable Y is 1 or not is used as an if statement for performing the pattern matching. , A program fragment “rerun a (X,
0) ". If the latter program fragment is not marked, the program fragment that returns the converted subtree structure “a (X, 0)” to the caller as a return value based on the structure on the right side of the rewrite rule 31 However, when the mark is attached, as shown in this example, the rewriting function 91 corresponding to the function symbol a is used as an argument with the structure of the subtree after conversion based on the definition of the right side (in this example, Is a program fragment that directly calls itself) and returns its return value to the caller. Similarly, since the structure on the left side of the rewrite rule 32 is (X, 0),
As an if statement for performing the pattern matching, a program fragment “if (Y == 0)” for checking whether the variable Y is 0,
A program fragment “r” that describes the processing when the variable Y is 0
etrun b (X). " This latter program fragment is a program fragment that returns the subtree structure “b (X)” after conversion based on the structure on the right side of the rewrite rule 32 as a return value to the caller when no mark is attached. Is marked, as shown in this example, the rewriting function 92 corresponding to the function symbol a is directly called with the structure of the converted subtree based on the definition of the right side as an argument, and the returned value is Will be returned to the caller. When the variable Y is neither 1 nor 0, a program fragment “return NULL” is added so that a NULL value indicating that rewriting has failed can be returned to the caller.

On the other hand, the rewriting function 92 is given a variable X as an argument. In this case, since there is no need for pattern matching, a program fragment (return X) for returning the variable X to the caller is described.

Next, referring to FIG. 1, the program 2
3 will be described. This part includes a specification input unit 11, a rewriting device 12, a program output unit 13, and a rewriting function storage unit 14.

FIG. 10 is a flowchart showing a processing example of the rewriting device 12. The operation will be described below with reference to FIGS.

The rewriting device 12 firstly receives the specification input unit 1
Then, the program specification 22 is input through the step S1 and is developed therein (S41). Next, a rewrite function corresponding to the outermost function symbol of the subtree is called using the structure of the conversion target subtree searched based on the leftmost innermost strategy for the program specification 22 (S44). Then, the conversion target subtree is rewritten based on the structure of the returned converted subtree (S45), and the process returns to step S42 to search for the conversion target subtree again based on the leftmost innermost strategy. The above processing is repeated until there is no more rewritable part (S43), and the result after conversion at the time when there is no more rewritable part is output through the program output unit 13 as an automatically generated result program (S46).

For example, when the rewriting functions 91 and 92 shown in FIG. 9 are stored in the rewriting function storage unit 14 and the program specification 22 illustrated in FIG. 2 is input, the rewriting device 12 first The rewriting function 92 corresponding to the function symbol b appearing at the leftmost innermost position is called using the variable X = 1 as an argument. Since the rewriting function 92 returns the variable X as it is, as shown in FIG.
Rewrites the leftmost innermost part into a variable X. That is, rewriting like “rewriting 1” in FIG. 5 is performed.

Next, the rewriting device 12 rewrites a rewriting function 91 (hereinafter, referred to as a rewriting function) corresponding to the function symbol a appearing at the leftmost innermost position.
(Referred to as a first function) with variables X = 1 and Y = 1 as arguments. As shown in FIG. 9, when the variable Y is 1, the rewriting function 91, which is the first function, uses the variables X = 1 and Y = 0 as arguments, that is, the rewriting function 91 (that is, itself; hereafter the second function).
Function is called directly. This called second
Since the variable Y is 0 in the rewriting function 91, the rewriting function 92 is directly called with the variable X = 1 as an argument. In the called rewriting function 92, the variable X = 1 is returned as it is to the caller's second function, and the second function returns it to the first function, and
The first function, the rewriting function 91, returns it to the calling rewriting device 12. As a result, the rewriting device 12 obtains X = 1 as the structure of the converted subtree, and rewrites the leftmost innermost part to X = 1. This corresponds to “Rewrite 5” shown in FIG. In other words, “rewrite 2”, “rewrite 3”, and “rewrite 4”, which were conventionally required, can be completed by one “rewrite 5”.

[0049]

As described above, according to the present invention, when a program is generated by rewriting a program specification having a tree structure using a set of rewrite rules, the rewrite rule set must be analyzed in advance. Thus, when a tree structure generated after applying a certain rewrite rule may be rewritten by another rewrite rule in the set of rewrite rules, the rewrite device can directly rewrite the rewrite rule without selecting it again. The cost required for selecting a rewrite rule applicable to a rewritable portion can be reduced, and high-speed rewrite, that is, a program can be generated.

[Brief description of the drawings]

FIG. 1 is a block diagram of an automatic program synthesizing apparatus according to an embodiment of the present invention.

FIG. 2 is a diagram showing an example of a program specification.

FIG. 3 is a diagram illustrating an example of a rewrite rule set.

4 is a diagram showing each rewrite rule included in the rewrite rule set of FIG. 3 in a tree structure.

FIG. 5 is an explanatory diagram of a process of repeating conversion of a program specification according to a rewriting rule.

FIG. 6 is a flowchart illustrating a processing example of a rewriting rule compiling unit;

FIG. 7 is a flowchart showing a detailed process of step 11 in FIG. 6;

FIG. 8 is a diagram showing an example of registered contents of a leftmost outermost function symbol registration unit and a rewrite rule registration unit.

FIG. 9 is a diagram illustrating an example of a rewrite function stored in a rewrite function storage unit.

FIG. 10 is a flowchart illustrating a processing example of a rewriting device.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 10 ... Automatic program synthesis apparatus 11 ... Specification input part 12 ... Rewriting apparatus 13 ... Program output part 14 ... Rewriting function storage part 15 ... Rewriting rule compilation part 16 ... Rewriting function generation part 17 ... Left side outermost function symbol registration part 18 ... Right side Marking section 19: Rewriting rule registration section 20: Rewriting rule analysis section 21: Rewriting rule set input section 22: Program specification 23: Program 24: Rewriting rule set

Claims (2)

(57) [Claims] 1. A function symbol is defined by using a set of rewrite rules defining a structure of a subtree for performing conversion in a program specification on a left side and a structure after conversion of the subtree on a right side. In an automatic program synthesizer that generates a program by repeatedly converting a program specification expressed in a tree structure, a set of rewrite rules is input, and a rewrite rule in which the outermost function symbol of the subtree defined on the left side is the same For each group of, based on the conversion target subtree structure given by the argument from the caller, determine which rewrite rule of the group of the left side of the group matches the conversion target subtree, and
If the outermost function symbol of the subtree defined on the left side of either the own group or the other group 's rewrite rule exists in the subtree defined on the right side corresponding to the matching left side, the right side When the rewrite function corresponding to the existing outermost function symbol is called using the structure of the subtree after the conversion based on the definition of the argument as an argument and the return value is returned to the caller, and such an outermost function symbol does not exist Is a rewrite rule compile unit that generates a rewrite function that returns the structure of the subtree after conversion based on the definition of the right side to the caller as a return value, and a leftmost innermost strategy for the program specification to be converted. The rewriting function corresponding to the outermost function symbol of the subtree is called by using the subtree searched based on the argument as an argument, and the structure of the returned subtree is converted to An automatic program synthesizing device, comprising: a rewriting device that repeats the process of rewriting the conversion target subtree based on the conversion target subtree until there is no more convertible subtree. 2. The rewriting rule compiling unit analyzes a rewriting rule included in a set of input rewriting rules, a leftmost outermost function symbol registration unit, a rewriting rule registration unit, and defines a rewriting rule on the left side of the rewriting rule. The type of the outermost function symbol registered in the subtree is registered in the outermost function symbol registration unit on the left side, and the input rewrite rules are grouped for each type of the outermost function symbol and registered in the rewrite rule registration unit. A rule analysis unit, and determines whether or not a function symbol of the type registered in the leftmost outermost function symbol registration unit exists in a subtree defined on the right side of the rewrite rule registered in the rewrite rule registration unit. The right-side mark part that checks and marks the existing function symbol on the right-side part, and for each rewrite rule group registered in the rewrite rule registration part, Left portion of any rewrite rule of the group is to determine matches the conversion source target subtree based on the converted partial tree structure given by the argument,
In addition, when a mark is attached to the right side corresponding to the matching left side, the rewriting function corresponding to the function symbol with the mark is used as an argument with the structure of the converted subtree based on the definition of the right side. Generates a rewrite function that calls and returns the return value to the caller, and if it is not marked, returns the structure of the subtree after conversion based on the definition of the right-hand side as the return value to the caller program automatic synthesizer according to claim 1, comprising a part.