System and method for analyzing programmed equations5410701Abstract A system for the automated analysis of programmed statements, that define parameters and that define equations involving the parameters, includes a method for determining the precedence according to which the statements are to be evaluated. The method includes the steps of determining the number of dependencies associated with each parameter according to the program statements, the step of identifying each dependency associated with each parameter as defined by the program statements, the step of decrementing the dependency quantity of each variable associated with a variable having a zero dependency quantity, and the step of evaluating each parameter that has a non-zero dependency quantity prior to the decrementing step and for which the dependency quantity has been decremented to zero. Claims I claim: Description BACKGROUND
TABLE I
______________________________________
E = 20 (i)
C = F + G (ii)
A = B + C (iii)
B = D + E (iv)
D = 10 (v)
F = 30 (vi)
G = 50 (vii)
______________________________________
The program expressions in Table I are elementary in context and of simplified syntax, and are provided only for illustration. The invention typically is practiced with programs containing far more complex statements and with hundreds if not many thousands or more expressions, rather than the illustrative seven in Table 1. The symbol table representation of FIG. 2 includes a first, leftmost column 20 that contains each lexeme identified in the expressions of Table I and listed in the order in which they occur in the stated expressions. The second column 22 of the symbol table, from the left, identifies the number of dependencies of each lexeme that is a variable. For example, the expression (i) in Table I specifies that the lexeme (E) is not variable, and the next expression (ii) identifies the lexeme (C) as being a variable dependent on two other lexemes. This information is summarized in the second column of the illustrated symbol table of FIG. 2. The third column 24 from the left of the FIG. 2 table, designated Unresolved Dependencies, initially has the same information as the preceding column, headed "Variable Dependencies". The Unresolved Dependencies information in this third column changes during execution of the flow diagramming tool, as discussed below. The fourth column 26 from the left in the illustrated table of FIG. 2 represents the graph nodes and arcs of the designated lexemes. The nodes represent model parameters, such as variables or constants, and each arc represents a relationship between two model parameters as specified by the target program. The arcs are considered to originate from the dependent parameter and to terminate at the independent parameter. Typically, the memory location for each graph node is allocated dynamically and the pointers to the node associated with a symbol, for all symbols whose type is "variable" or "constant" are stored within the symbol table entry. Also, the memory for each arc is dynamically allocated and pointers to the arc are stored within the node structure. The graph node data structure preferably used in the practice of the invention principally contains the following fields: a pointer to the parameter's symbol table entry; a pointer to a linked list of arcs emanating from the node; and the number of dependencies associated with the node, and therefore the number of arcs emanating from the node. Similarly, the arc structure principally contains the following fields: a pointer to the next arc emanating from the same node, if any, and a pointer to the node associated with the destination symbol, i.e. the symbol representing the independent parameter. The remaining two columns 28 and 30 of the FIG. 2 table, i.e. the rightmost two columns, designate respectively the destinations and origins of this arc structure. FIG. 3 illustrates a syntax tree that the flow diagram tool represented in FIG. 1 creates upon executing the lexical analysis and parsing phases 12 and 14, for the illustrative listing of program expressions in Table 1. The program statements in Table 1 are listed not in the sequential order conventionally needed for evaluation. This is because the flow diagramming tool of FIG. 1 is able to establish precedence among programmed expressions independent and irrespective of the sequence in which they appear in the listing. The conventional evaluation of the Table 1 group of expressions proceeds through the list in sequential order, starting with expression (i) and proceeding to expression (vii). Upon encountering the second expression, i.e. expression (ii), the conventional evaluation would determine that the variable parameter (C) has a value of (0), because no other none zero values have previously been specified in the listing for the parameters (F) and (G) on which the parameter (B) depends. Similarly, upon encountering expression (iii), conventional evaluation would determine that (A) is equal to (0), because no prior non-zero values have been defined for the variable parameters (B) or (C) on which it depends. The same conventional evaluation would result for equation (iv). The precedence establishing feature of the flow diagram tool of FIG. 1, on the other hand, evaluates the list of expressions in Table I only after establishing the precedence, i.e. the logically sequential order, according to which the expressions are to be evaluated. The flow diagramming tool 10 of FIG. 1 executes these operations in the precedence evaluation phase 16. The precedence evaluation phase 16, FIG. 1, of the illustrated flow diagramming tool determines the precedence of the programmed statements independent of the sequence in which they are written or listed. The precedence evaluation phase performs this operation in response to the context of the programmed statements. Further, this phase 16 of the illustrated flow diagramming tool can evaluate the programmed statements according to the precedential order which it determines. More particularly, the precedence evaluation phase 16 in accordance with the invention determines, for each programmed statement such as each statement in Table I, the number of dependencies associated with each variable lexeme. A second step is to identify the specific dependencies for each variable lexeme. Both items of information are entered in the symbol table, as represented for example by the leftmost second and fifth columns 22 and 28, in FIG. 2. A third step of the precedence evaluation phase is to evaluate each dependency and to report the resultant resolution to all variables that depend on it. The precedence evaluation phase continues this operation, in a repetitive manner, until all dependencies are resolved and all resultant information is reported to other variables. The precedence evaluation phase can then compute or otherwise evaluate any variable. With specific reference to the illustrative list of program expressions in Table I, columns 22 and 28 of the table of FIG. 2 report the results of the foregoing first and second steps. That is, column 22 reports the results of the dependency determining first step, and column 28 reports the identification of the specific dependencies according to the second step. In performing the third step, the illustrated precedence evaluation phase 16 examines the Unresolved Dependencies of the program variables as entered in the symbol table column 24 of FIG. 2. A comparison with the Variable Dependencies entries in column 22 shows that the Unresolved Dependencies, column 24, are identical at the start of this third step. For each parameter associated with an entry having zero Unresolved Dependencies, the system identifies all other parameters that depend on the former parameter and decrements their respective number of Unresolved Dependencies. Thus, in a first iteration of the third step, the precedence evaluation routine examines the entries in the symbol table, in sequence, and determines that the parameter (E) has zero Unresolved Dependencies. The routine then determines that the parameter (E) is a factor in determining the parameter (B), pursuant to the statement (iv) in Table I and as listed in the Table 2 column 30 of arc origins. In response to this information, the routine decrements by one the number of unresolved dependencies, in column 24, assigned in the symbol table to the parameter (B). Continuing the first iteration through the symbol table, the parameter (D) is the next one having zero variable dependencies and hence zero unresolved dependencies in column 24. The parameter (B) depends on that parameter, per listing statement (iv) in Table I and column 30 of FIG. 2. Accordingly, the number of unresolved dependencies assigned to the parameter (B) is again decremented, and accordingly now has the value zero. The further examination of the symbol table shows that the parameter (F) has zero variable dependencies, and that the variable (C) depends on that parameter, per program statement (ii). The number of unresolved dependencies assigned to the parameter (C) is accordingly decremented by one, from the initial value two to one. Further examination of the symbol table, FIG. 2, recognizes that the parameter (G) has zero variable dependencies and that the parameter (C) depends on that parameter, per equation (ii). The number of unresolved dependencies assigned to the parameter (C) is accordingly decremented by one, to a zero value. FIG. 4 repeats columns 20 and 24 of FIG. 2, and further shows, in column 24', the number of unresolved dependencies remaining for the symbol table of FIG. 2 after this first iteration of the third step of the precedence evaluation phase. As shown in that column 24', only the parameter (A) has a non-zero number of unresolved dependencies. The routine for precedence evaluation again traverses the unresolved dependency entries in the symbol table and determines which parameters now designated as having zero unresolved dependencies previously had a non-zero number of unresolved dependencies. A comparison of the FIG. 4 columns 24 and 24' shows that these are parameters (C) and (D). In response, the routine determines that the parameter (C) is involved is in the evaluation of parameter(A) and accordingly decrements by one the number of unresolved dependencies assigned to parameter (A). In response to the parameter (B) now having zero unresolved dependencies whereas in the prior iteration it had a non-zero value, and in response to the dependency of the parameter (A) on that parameter (B), the routine decrements by one the number of unresolved dependencies assigned to the parameter (A). At this juncture in the illustrated example, all parameters entered in the symbol table have zero unresolved dependencies, as reported in column 24" of FIG. 4. Moreover, the parameter (A) is the last one to be evaluated in this manner, and it can now be evaluated, in accordance with statement (iii) of the Table I listing. The precedence evaluation phase 16 can execute the evaluation, and uses the previously determined evaluations of the parameters (C) and (B), of which (A) is a function in accordance with statement (iii). The following Table II sets forth a pseudo-code statement of the algorithms for establishing precedence in accordance with the steps discussed above. As apparent from the foregoing discussion and set forth in the Table II pseudo-code representation, it is seen that the precedence establishing sequence employs three nested loops of operations.
TABLE II
______________________________________
EstablishPrecedences
SymbolTableSize:= 1111;
FROM Bucket:= 1 TO Bucket:= SymbolTableSize DO
BEGIN
CurSymTabEntry:= SymbolTable[Bucket];
WHILE (CurSymTabEntry NULL)
BEGIN
CurEquation = CurSymTabEntry.fwdarw.Equation;
WHILE (CurEquation NULL)
BEGIN
GraphEquation (CurEquation);
CurEquation = CurEquation.fwdarw.Next;
END;
CurSymTabEntry = CurSymTabEntry.fwdarw.Next;
END;
END;
GraphEquation
IF (Symbol on LHS of Equation has a Node (Entry.fwdarw.Node))
THEN BEGIN
DestinationHeader = Entry.fwdarw.Node;
END
ELSE BEGIN
Allocate memory for and initialize the Node structure
`Destination Header`;
END;
Call AuxGraphInitVals
AuxGraphEquation (DestinationGraphNode,
EquationSyntaxTree)
DependentParameter =
DestinationGraphNode.fwdarw.Symbol.fwdarw.Name,
IndependentParameter =
EquationSyntaxTree.fwdarw.Symbol.fwdarw.Name;
IF (DependentParameter = IndependentParameter)
RETURN;
AuxGraphEquation (DestinationGraphNode,
EquationSyntaxTree.fwdarw.LSon);
AuxGraphEquation (DestinationGraphNode,
EquationSyntaxTree.fwdarw.RSon);
IF (EquationSyntaxTree.fwdarw.Symbol.fwdarw.
Type == FUNCTION)
THEN.BEGIN
FOR I FROM 1 TO NumberOfArgumentsTo
Function) DO
AuxGraphEquation (DestinationGraphNode,
EquationSyntaxTree.fwdarw.Node[I]);
END
ELSE IF (EquationSyntaxTree.fwdarw.Symbol.fwdarw.Type I=
VARIABLE)
RETURN;
IF (Graph Node already exists for the
independent parameter)
THEN Assign it to SourceGraphNode
ELSE Create a SourceGraphNode;
Call FindArc to check if the relationship between the
dependent parameter and the independent parameter has
already been established. If so RETURN. If not create a
new arc and establish the precedences.
______________________________________
With further reference to the flow chart of FIG. 1, upon completion of the precedence establishing phase 16, the illustrated flow diagramming tool proceeds to the output phase 18. In an illustrated embodiment of this output phase, and in view of the fact that all precedences have been established for the statements of the target program, the flow diagramming tool traverses the symbol table of FIG. 2 to identify the entry in column 20 associated with the parameter that is of interest to the user, in response to a user designation. The output phase uses the precedence information stored in the symbol table and creates a flow diagram using, for example, the algorithm set forth below in Table III, in the same pseudo-code of Table II.
TABLE III
______________________________________
Display Graph (ParameterName, TraversalDepth)
______________________________________
Look up the symbol table for the entry associated with the
specified parameter
Identify the number of parameters on which ParameterName
is dependent
IF (ParameterName is not dependent on any parameters) OR
(Traversal depth has been exceeded)
THEN BEGIN
Draw ParameterOnScreen (ParameterName);
RETURN;
END;
Call DisplayGraph recursively for each parameter on which
ParameterName is dependent.
______________________________________
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction of copyrighted portions of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, and otherwise reserves all copyright rights whatsoever. It will thus be seen that the objects set forth above, among those made apparent from the preceding description, are efficiently attained. Since certain changes may be made in the above method without departing from the scope of the invention, it is intended that all matter contained in the above description or shown in the accompanying drawings be interpreted as illustrative and not in a limiting sense. It is also to be understood that the following claims are intended to cover all generic and specific features of the invention herein described, and all statements of the scope of the invention which, as a matter of language, might be said to fall therebetween. Appendix The following Appendix presents program listings for the following computer program files. These files implement a flow diagramming tool as described above in accordance with the ACCESS programming language as available under license from Devonrue Ltd. of Boston, Mass. That programming language is similar to the well-known PASCAL and C computer languages and to the DYNAMO language of Pugh-Roberts Associates. A brief description of the programming files in this Appendix follows.
______________________________________
File Name Purpose
______________________________________
doc.h Header file containing type
definitions, data structure
definitions and constant
definitions used for graphically
displaying the tree structures
using OSF/Motif.
local.sub.-- fns.c
Contains functions necessary for
graphically displaying the tree
structures using OSF/Motif.
functions.c Contains support functions used by
the flow diagramming tool.
common.sub.-- graph.c
Contains functions used for
reordering the equations.
local.sub.-- graph.c
Contains functions used in
handling Macro calls in the model
equations file.
access.h Header file containing type
definitions data structure
definitions and constant
definitions used by the lexical
analyzer and the parser.
access.1 "lex" specification for the
lexical analyzer. This file is
used as input by "lex" whose
output is the "C" source code for
the lexical analyzer.
support.sub.-- fns.c
Contains support functions used by
the lexical analyzer and the
parser.
access.y "yacc" specification for the
parser. This file is used as
input by "yacc" whose output is
the "C" source code for the
parser.
compatability.h
contains code that permits porting
of code between UNIX locations
supplied by different vendors
______________________________________
##SPC1##
|
Same subclass Same class Consider this |
||||||||||