Method of automatically evaluating source language logic condition sets and of compiling machine executable instructions directly therefrom

• US 4,309,756 A
• Filed: 11/28/1973
• Issued: 01/05/1982
• Est. Priority Date: 02/17/1971
• Status: Expired due to Term

• Current Assignee: CA Management, Inc. (Broadcom, Inc.)
• Original Assignee: Robert I. Beckler
• Inventors: Beckler, Robert I.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US05/419,496
• Time in Patent Office: 2,960 Days
• Field of Search: 444/1, 340/172.5, 364/300
• US Class Current: 717/155
• CPC Class Codes: G06F 3/0489 using dedicated keyboard keys or combinations thereof
• CPC Class Codes: G06F 8/41 Compilation

Abstract

A method for use under program control in a digital computer for automatically evaluating compiler level language logic condition sets and for compiling machine executable instructions directly therefrom is disclosed. More specifically, a unique method of constructing an array of novel logical linkages is described which permits an especially rapid direct compilation of an efficient and optimum-sized set of machine executable instructions without constructing the usual logic decision tables or going through an extra assembly level language step as is the case with most prior compilers. Rather, the method described generates an array of so-called primary link codes representing logical interrelationships or links between successive source deck cards in a condition set while also generating an associated array of so-called secondary link codes representing logical interrelationships or links between successive entries on the same source deck card in a condition set. These arrays are formed in such a manner that a simple analysis in terms of increasing/decreasing values of the primary and secondary link codes permits direct compilation of machine executable instructions from a computed array of incremental addresses for each term of the condition set. Further, the resulting set of machine instructions is near optimum in terms of both the core storage area utilized and the object program execution time.

Claims

1. A method to be carried out within a digital computer under programmed control for automatically evaluating a logic condition set composed of query statements connected by logical connectors and expressed in high level computer program source statements and for automatically compiling a compact and efficient set of machine executable instructions corresponding thereto, said method comprising the steps of:

constructing an array of logical linkage codes having at least one entry for each query statement in the condition set with the value of successive entries in the array being assigned in dependence upon the particular type of logical connector adjoining the respectively associated query statement,

scanning the resulting array of logical linkage codes in a predetermined order and comparing the values of adjacent entries to determine relative ordering therebetween, and

computing the necessary addresses for insertion in branch instructions included within said set of machine instructions in dependence upon said relative ordering.

2. A method as in claim 1 further comprising the steps of:

performing said set of machine executable instructions in skeleton form with a subset of at least one compare, one conditional branch and one unconditional branch instruction corresponding to each query statement and with address arguments for the branch instructions being intialized to correspond to the address of the compare instruction of its associated subset, and wherein

said computing step comprises;

constructing an array of good incremental addresses with each entry corresponding to a particular subset of instructions and with the value of each entry being calculated in dependence upon said relative ordering of corresponding adjacent linkage array entries,

constructing an array of bad incremental addresses with each entry corresponding to a particular subset of instructions and with the value of each entry being calculated in dependence upon said relative ordering of corresponding adjacent linkage array entries,

incrementing the address arguments of said conditional branch instructions with the value of the corresponding entry in the array of good incremental addresses, and

incrementing the address arguments of said unconditional branch instructions with the value of the corresponding entry in the array of bad incremental addresses.

3. A method to be performed by a digital computer under programmed control for automatically evaluating a logic condition set composed of query statements connected by logical connectors expressed in high level language computer program source statements and for automatically compiling a compact and efficient set of machine executable instructions corresponding thereto, each of said query statements comprising two terms corresponding to data fields and a relational operator relating the two fields such that an evaluation of the stated relation will provide a true or false result,

said method comprising the steps of:

generating a primary link array of linkage codes with at least one entry for each query statement and with the value of successive entries in the array being sequentially assigned starting from a predetermined value for the initial entry and increasing only when the first logical connector in a newly encountered source statement is effectively considered an AND connector,

generating a secondary link array corresponding to said primary link array of linkage codes with at least one entry for each query statement and with the value of successive entries in the array being sequentially assigned starting from a predetermined value for the initial entry and being increased only when an effective AND connector is encountered between query statements on the same source statement and being reset to the predetermined initial value each time a new source statement is encountered within said condition set,

scanning the resulting primary and secondary link arrays in reverse order and comparing values of adjacent entries in each array to determine the relative ordering therebetween, and

computing addresses for insertion in said set of machine instructions in dependence upon said relative ordering.

4. A method as in claim 3 further comprising the steps of:

generating said set of machine instructions in skeleton form with a subset of one compare, one conditional branch and one unconditional branch instruction corresponding to each entry in said primary link array and with address arguments for the branch instructions being initialized to correspond to that particular subset of instructions, and wherein said computing step comprises;

generating during said scanning step an array of good incremental addresses with each array entry corresponding to a particular subset of instructions and with the value of each entry being calculated in dependence upon said relative ordering of corresponding adjacent primary and secondary link array entries,

generating during said scanning step an array of bad incremental addresses with each array entry corresponding to a particular subset of instructions and with the value of each entry being calculated in dependence upon said relative ordering of corresponding adjacent primary and secondary link array entries,

determining which query statements are mandatory for the condition set and setting the corresponding entries in said array of bad incremental addresses to indicate a predetermined flunk address,

incrementing the address arguments of said conditional branch instructions with the value of the corresponding entry in the array of good incremental addresses,

incrementing the address arguments of said unconditional branch instructions with the value of the corresponding entry in the array of bad incremental addresses provided it is not the predetermined flunk address, and

replacing the address argument of said unconditional branch instruction with the predetermined flunk address if the corresponding entry in the array of bad incremental addresses has been set to so indicate.

5. A method as in claim 4 wherein the incremental address entries in said arrays of good and bad incremental addresses are multiples of a predetermined constant X corresponding to the number of computer storage positions normally occupies by each of said subject of instructions.

6. A method as in claim 5 wherein said scanning step comprises at least one reverse ordered scan and wherein:

said generating an array of good incremental addresses step is performed during at least one of said reverse ordered scans wherein the last entry in this array is set at 1X and other entries are also set at 1X if the corresponding secondary link array entry is higher than the just previous secondary link array entry or if the corresponding primary link array entry is less than the next suceeding primary link array entry;

otherwise, the entries are set at (M+1)X where M is the number of equal primary link array entries occurring just after the currently corresponding primary link entry, and

said generating an array of bad incremental addresses step is performed duringat least one of said reverse ordered scans wherein the entires corresponding to the highest level for any given primary link array entries are set to indicate said flunk address and other entries in said bad address array are also set to indicate the flunk address if the corresponding secondary link array entry is less than the next higher level secondary link array entry and the next higher level bad address array entry is already set to indicate a flunk address;

otherwise, the entries are set at (M+1)X where M is the number of adjacent higher level entries not set to indicate the flunk address.

7. A method as in claim 5 wherein said generating an array of good incremental addresses step comprises:

a first reverse ordered scan of the primary link array wherein all good address array entries are initialized by successively increasing the entry value by 1X until the corresponding primary link array entry decreases whereupon the good address entry is reset to begin again at 1X, and

a second reverse ordered scan of the secondary link array wherein all good address array entries are reset to 1X if the corresponding secondary link array entry is greater than the next lower ordered secondary link array entry.

8. A method as in claim 7 wherein said generating an array of bad incremental addresses step comprises:

a third reverse ordered scan of the primary link array wherein all bad address array entries are initialized by setting the last entry to indicate the flunk address and all other bad address array entries are similarly set if the corresponding primary link array entry is less than the next higher ordered primary link array entry;

otherwise the bad address array entries are initialized at 1X, and

a fourth reverse ordered scan of the secondary link array wherein all bad address array entries are incremented by 1X from the next higher ordered entry provided that the corresponding secondary link array entry is less than the next higher ordered secondary link array entry and provided that the next higher ordered bad address array entry has not been set to indicate the flunk address.

9. The new use of general purpose electronic data processor for automatically evaluating a logic condition set composed of query statements connected by logical connectors and expressed in high level computer program source statements and for automatically compiling a compact and efficient set of machine executable instructions corresponding thereto, said new use comprising the steps of:

constructing an array of logical linkage codes having at least one entry for each query statement in the condition set with the value of successive entries in the array being assigned in dependence upon the particular type of logical connector adjoining the respectively associated query statement,

scanning the resulting array of logical linkage codes in a predetermined order and comparing the values of adjacent entries to determine relative ordering therebetween, and

computing the necessary addresses for insertion in branch instructions included within said set of machine instructions in dependence upon said relative ordering.

10. The method of claim 9 further comprising the steps of:

performing said set of machine executable instructions in skeleton form with a subset of at least one compare, one conditional branch and one unconditional branch instruction corresponding to each query statement and with address arguments for the branch instructions being initialized to correspond to the address of the compare instruction of its associated subset, and wherein

said computing step comprises;

constructing an array of good incremental addresses with each entry corresponding to a particular subset of instructions and with the value of each entry being calculated in dependence upon said relative ordering of corresponding adjacent linkage array entries,

constructing an array of bad incremental addresses with each entry corresponding to a particular subset of instructions and with the value of each entry being calculated in dependence upon said relative ordering of corresponding adjacent linkage array entries,

incrementing the address arguments of said conditional branch instructions with the value of the corresponding entry in the array of good incremental addresses, and

incrementing the address arguments of said unconditional branch instructions with the value of the corresponding entry in the array of bad incremental addresses.

11. The new use of a general purpose electronic data processor for automatically evaluating a logic condition set composed of query statements connected by logical connectors expressed in high level language computer program source statements and for automatically compiling a compact and efficient set of machine executable instructions corresponding thereto, each of said query statements comprising two terms corresponding to data fields and a relational operator relating the two fields such that an evaluation of the stated relation will provide a true or false result,

said new use comprising the steps of:

generating a primary link array of linkage codes with at least one entry for each query statement and with the value of successive entries in the array being sequentially assigned starting from a predetermined value for the initial entry and increasing only when the first logical connector in a newly encountered source statement is effectively considered an AND connector,

generating a secondary link array corresponding to said primary link array of linkage codes with at least one entry for each query statement and with the value of successive entries in the array being sequentially assigned starting from a predetermined value for the initial entry and being increased only when an effective AND connector is encountered between query statements on the same source statement and being reset to the predetermined initial value each time a new source statement is encountered within said condition set,

scanning the resulting primary and secondary link arrays in reverse order and comparing values of adjacent entries in each array to determine the relative ordering therebetween, and

computing addresses for insertion in said set of machine instructions in dependence upon said relative ordering.

12. The method of claim 11 further comprising the steps of:

generating said set of machine instructions in skeleton form with a subset of one compare, one conditional branch and one unconditional branch instruction corresponding to each entry in said primary link array and with address arguments for the branch instructions being initialized to correspond to that particular subset of instructions, and wherein said computing step comprises;

generating during said scanning step an array of good incremental addresses with each array entry corresponding to a particular subset of instructions and with the value of each entry being calculated in dependence upon said relative ordering of corresponding adjacent primary and secondary link array entries,

generating during said scanning step an array of bad incremental addresses with each array entry corresponding to a particular subset of instructions and with the value of each entry being calculated in dependence upon said relative ordering of corresponding adjacent primary and secondary link array entries,

determining which query statements are mandatory for the condition set and setting the corresponding entries in said array of bad incremental addresses to indicate a predetermined flunk address,

incrementing the address arguments of said conditional branch instructions with the value of the corresponding entry in the array of good incremental addresses,

incrementing the address arguments of said unconditional branch instructions with the value of the corresponding entry in the array of bad incremental addresses provided it is not the predetermined flunk address, and

replacing the address arguments of said unconditional branch instructions with the predetermined flunk address if the corresponding entry in the array of bad incremental addresses has been set to so indicate.

13. The method of claim 12 wherein the incremental address entries in said arrays of good and bad incremental addresses are multiples of a predetermined constant X corresponding to the number of computer storage positions normally occupied by each of said subset of instructions.

14. The method of claim 13 wherein said scanning step comprises at least one reverse ordered scan and wherein:

said generating an array of good incremental addresses step is performed during at least one of said reverse ordered scans wherein the last entry in this array is set at 1X and other entries are also set at 1X if the corresponding secondary link array entry is higher than the just previous secondary link array entry or if the corresponding primary link array entry is less than the next succeeding primary link array entry;

otherwise, the entries are set at (M±

1)X where M is the number of equal primary link array entries occurring just after the currently corresponding primary link entry, and

said generating an array of bad incremental addresses step is performed during at least one of said reverse ordered scans wherein the entries corresponding to the highest level for any given primary link array entries are set to indicate said flunk address and other entries in said bad address array are also set to indicate the flunk address if the corresponding secondary link array entry is less than the next higher level secondary link array entry and the next higher level bad address array entry is already set to indicate a flunk address;

otherwise, the entries are set at (M±

1)X wherein M is the number of adjacent higher level entries not set to indicate the flunk address.

15. The method of claim 14 wherein said generating an array of good incremental addresses step comprises:

a first reverse ordered scan of the primary link array wherein all good address array entries are initialized by successively increasing the entry value by 1X until the corresponding primary link array entry decreases whereupon the good address entry is reset to begin again at 1X, and

a second reverse ordered scan of the secondary link array wherein all good address array entries are reset to 1X if the corresponding secondary link array entry is greater than the next lower ordered secondary link array entry.

16. The method of claim 15 wherein said generating an array of bad incremental addresses step comprises:

a third reverse ordered scan of the primary link array wherein all bad address arrray entries are initialized by setting the last entry to indicate the flunk address and all other bad address array entries are similarly set if the corresponding primary link array entry is less than the next higher ordered primary link array entry;

otherwise the bad address array entries are initialized at 1X, and

a fourth reverse ordered scan of the secondary link array wherein all bad address array entries are incremented by 1X from the next higher ordered entry provided that the corresponding secondary link array entry is less than the next higher ordered secondary link array entry and provided that the next higher ordered bad address array entry has not been set to indicate the flunk address.

17. A digital computer under programmed control for automatically evaluating a logic condition set composed of query statements connected by logical connectors and expressed in high level computer program source statements and for automatically compiling a compact and efficient set of machine executable instructions corresponding thereto, said computer comprising:

means for constructing an array of logical linkage codes having at least one entry for each query statement in the condition set with the value of successive entries in the array being assigned in dependence upon the particular type of logical connector adjoining the respectively associated query statement,

means for scanning the resulting array of logical linkage codes in a predetermined order and comparing the values of adjacent entries to determine relative ordering therebetween, and

means for computing the necessary addresses for insertion in branch instructions included within said set of machine instructions in dependence upon said relative ordering.

18. A computer as in claim 17 further comprising:

means for performing said set of machine executable instructions in skeleton form with a subset of at least one compare, one conditional branch and one unconditional branch instruction corresponding to each query statement and with address arguments for the branch instructions being initialized to correspond to the address of the compare instruction of its associated subset, and wherein

said means for computing comprises;

means for constructing an array of good incremental addresses with each entry corresponding to a particular subset of instructions and with the value of each entry being calculated in dependence upon said relative ordering of corresponding adjacent linkage array entries,

means for constructing an array of bad incremental addresses with each entry corresponding to a particular subset of instructions and with the value of each entry being calculated in dependence upon said relative ordering of corresponding adjacent linkage array entries,

means for incrementing the address arguments of said conditional branch instructions with the value of the corresponding entry in the array of good incremental addresses, and

means for incrementing the address arguments of said unconditional branch instructions with the value of the corresponding entry in the array of bad incremental addresses.

19. A digital computer under programmed control for automatically evaluating a logic condition set composed of query statements connected by logical connectors expressed in high level language computer program source statements and for automatically compiling a compact and efficient set of machine executable instructions corresponding thereto, each of said query statements comprising two terms corresponding to data fields and a relational operator relating the two fields such that an evaluation of the stated relation will provide a true or false result,

said computer comprising:

means generating a primary link array of linkage codes with at least one entry for each query statement and with the value of successive entries in the array being sequentially assigned starting from a predetermined value for the initial entry and increasing only when the first logical connector in a newly encountered source statement is effectively considered an AND connector,

means for generating a secondary link array corresponding to said primary link array of linkage codes with at least one entry for each query statement and with the value of successive entries in the array being sequentially assigned starting from a predetermined value for the initial entry and being increased only when an effective AND connector is encountered between query statements on the same source statement and being reset to the predetermined initial value each time a new source statement is encountered within said condition set,

means for scanning the resulting primary and secondary link arrays in reverse order and comparing values of adjacent entries in each array to determine the relative ordering therebetween, and

means for computing addresses for insertion in said set of machine instructions in dependence upon said relative ordering.

20. A computer as in claim 19 further comprising:

means for generating said set of machine instructions in skeleton form with a subset of one compare, one conditional branch and one unconditional branch instruction corresponding to each entry in said primary link array and with address arguments for the branch instructions being initialized to correspond to that particular subset of instructions, and wherein said computing step comprises;

means for generating during said scanning step an array of good incremental addresses with each array entry corresponding to a particular subset of instructions and with the value of each entry being calculated in dependence upon said relative ordering of corresponding adjacent primary and secondary link array entries,

means for generating during said scanning step an array of bad incremental addresses with each array entry corresponding to a particular subset of instructions and with the value of each entry being calculated in dependence upon said relative ordering of corresponding adjacent primary and secondary link array entries,

means for determining which query statements are mandatory for the condition set and setting the corresponding entries in said array of bad incremental addresses to indicate a predetermined flunk address,

means for incrementing the address arguments of said conditional branch instructions with the value of the corresponding entry in the array of good incremental addresses,

means for incrementing the address arguments of said unconditional branch instructions with the value of the corresponding entry in the array of bad incremental addresses provided it is not the predetermined flunk address, and

means for replacing the address arguments of said unconditional branch instructions with the predetermined flunk address if the corresponding entry in the array of bad incremental addresses has been set to so indicate.

21. A computer as in claim 20 wherein the incremental address entries in said arrays of good and bad incremental addresses are multiples of a predetermined constant X corresponding to the number of computer storage positions normally occupied by each of said subset of instructions.

22. A computer as in claim 21 wherein said means for scanning comprises means for performing at least one reverse ordered scan and wherein:

said means for generating an array of good incremental addresses is active during at least one of said reverse ordered scans wherein the last entry in this array is set at 1X and other entries are also set at 1X if the corresponding secondary link array entry is higher than the just previous secondary link array entry or if the corresponding primary link array entry is less than the next succeeding primary link array entry;

otherwise, the entries are set at (M+1)X where M is the number of equal primary link array entries occurring just after the currently corresponding primary link entry, and

said means for generating an array of bad incremental addresses step is active during at least one of said reverse ordered scans wherein the entries corresponding to the highest level for any given primary link array entries are set to indicate said flunk address and other entries in said bad address array are also set to indicate the flunk address if the corresponding secondary link array entry is less than the next higher level secondary link array entry and the next higher level bad address array entry is already set to indicate a flunk address;

otherwise, the entries are set at (M+1)X where M is the number of adjacent higher level entries not set to indicate the flunk address.

23. A computer as in claim 21 wherein said means for generating an array of good incremental addresses step comprises:

means for performing a first reverse ordered scan of the primary link array wherein all good address array entries are initialized by successively increasing the entry value by 1X until the corresponding primary link array entry decreases whereupon the good address entry is reset to begin again at 1X, and

means for performing a second reverse ordered scan of the secondary link array wherein all good address array entries are reset to 1X if the corresponding secondary link array entry is greater than the next lower ordered secondary link array entry.

24. A computer as in claim 23 wherein said means for generating an array of bad incremental addresses step comprises:

means for performing a third reverse ordered scan of the primary link array wherein all bad address array entries are initialized by setting the last entry to indicate the flunk address and all other bad address array entries are similarly set if the corresponding primary link array entry is less than the next higher ordered primary link array entry;

otherwise the bad address array entries are initialized at 1X, and

means for performing a fourth reverse ordered scan of the secondary link array wherein all bad address array entries are incremented by 1X from the next higher ordered entry provided that the corresponding secondary link array entry is less than the next higher ordered secondary link array entry and provided that the next higher ordered bad address array entry has not been set to indicate the flunk address.