|
|
This module contains the procedures that derive the dependency graph from the given attribute assignments. The graph itself is built by calling procedures from the Simple Multi-Pass Module [allsmp].
This module also contains the function that tests whether the given grammar is flat implementable, as defined in [2.9].
The boolean function flatimplementable returns TRUE when the grammar is flat implementable, otherwise FALSE. The procedure first makes the sets of right- and left-hand side elements by calling the local procedure make right left side elements. This procedure initializes (as a global side effect) the two global variables left side elements and right side elements [bintree 2.2]
When the right-hand side elements are known the procedure end always at is called for all right-hand side elements. The procedure end always at is the straightforward implementation of "end always at" in [2.9].
In [3.1.1] we defined the function "attr elem pairs of", that specified on which (attribute,element) pairs a given (attribute,element) pair is projected according to the flat implementation. The function projection is the implementation of this function. It returns the subset of the elements for a given pair that is equal to the clause "clos parents of and(E) union clos class(E)" in the formal definition. The first parameter attr nr contains the number of the attribute, and the second parameter elem nr contains the number of the element of the attribute pair.
In [3.1.1] we defined the set "all attr elem pairs" as the set of (attribute,element) pairs that form the nodes of the dependency graph. The set is implemented by assigning a unique number to each pair. This is also explained in [4.13]. The global variable number of is used to store the lowest number of all attribute element pairs with each element. The following two subsections explain how numbers are assigned to pairs, and once this is done, how the number assigned to a pair can be found.
The function make numbering for pairs tries to make a unique numbering for all the (attribute,element) pairs. The function returns FALSE when more pairs are found than the implementation allows, otherwise TRUE is returned. Pairs are numbered by calling the procedure make for for each element that has an indirect, direct or empty tree rule defined.
The procedure make for adds the pairs as nodes to the dependency graph by calling the procedure add a node [allsmp 2.1] for the attributes as represented by the parameter attrs, and the element with element number elem nr. The variable number of is also updated for the element with element number elem nr.
The function number of pair returns the number of the pair given by the parameters attr nr and elem nr. It makes use of the global variable number of.
The boolean function generate all dependencies tries to generate the dependency graph. When this is not possible, due to restrictions imposed by the implementation on the number of nodes of the dependency graph, the function returns FALSE, otherwise TRUE. The value returned is the same as the value returned by the function make numbering for pairs (see section 3.1). This procedure can be viewed as the implementation of the expression that is used to define the set "dependencies" in [3.1.2].
The function generates the dependencies that are introduced by each tree rule by calling the procedure dep lattr ass (see next section) after calling the local procedure make partlist. The procedure make partlist fills its second parameter with the representation of the part list [2.11.2] of the element as indicated by the value of the first parameter of the procedure. A slightly different implementation for the part list is chosen here, compared to that which is used in the Attribute Assignment Transformation Module [trans 3].
The global boolean variable with dep info [definitions 2.6] is used to determine whether information of the collected dependencies with each tree rule have to be printed or not.
The procedure dep lattr ass generates the dependencies for the attribute assignments pointed to by the first parameter lattr ass ptr of type plattr ass [bintree 1.5] within the context described by the second reference parameter partlist. The procedure calls either the procedure dep simp ass or dep sel ass for each assignment in the list of assignments pointed to by lattr ass ptr. This procedure is the implementation of the function "dep in AAS" in [3.1.2].
The procedure dep simp ass generates the dependencies of a simple attribute assignment. It initializes the global variables to attr, to elements and to part, which represents the nodes of the dependency graph to which the dependencies introduced by the expression on the right-hand side of the simple attribute assignment point. It also calls the procedure dep expr, see following subsection.
The procedure dep sel ass generates the dependencies of a case expression. For each alternative of the case expression the local procedure dep alter is called.
The procedure dep alter calls the procedure dep lattr ass recursively, with an updated partlist for each element in the selector represented by the first parameter selector.
The procedure dep expr generates the dependencies introduced by the expression pointed to by the first parameter expr ptr in the context described by the second reference parameter partlist. The procedure either calls the procedure dep simple expr, dep sem func or dep case expr depending on the kind of the expression. This procedure is the implementation of the function "dep in EXPR" in [3.1.2].
The procedure dep simple expr generates the dependencies from the nodes determined by the applied attribute occurrence to the nodes determined by the assigned attribute occurrence. These nodes are represented by the global variable to attr, to elements and to part, which are initialized in the procedure dep simp ass (see previous subsection). This is done by calling the procedure generate dependencies with the right arguments.
The procedure dep sem func generates the dependencies introduced by a semantic function expression, by calling the procedure dep expr recursively from all the argument expressions.
The procedure dep case expr generates the dependencies introduced by a case expression. This is done by calling the local procedure dep alter for each alternative of the case expression. The procedure dep alter generates the dependencies for the selector represented by the first parameter selector and the expression pointed to by the second parameter expr. For each element in the selector the procedure dep expr is called recursively with an updated part list.
The procedure generate dependencies adds the dependencies from the nodes represented by the parameters attr from and elements from to the nodes represented by the parameters attr to and elements to, using the restrictions determined by the part as represented by the parameters part from and part to. The kind of restriction is returned by the local function direction, which is the implementation of "direction" in [3.1.2]. The dependencies are added to the graph by calling the procedure add a dependency [allsmp 2.1].
This module uses the following modules:
definitions, perform, bintree, allsmp, listing.
The following functions are exported by this module:
FUNCTION flatimplementable : boolean;
This procedure tests whether the grammar is implementable according to the flat implementation. It is described in section 1
FUNCTION generate_all_dependencies : boolean;
This procedure generates the dependency graph, and returns the value TRUE whenever this was successful, otherwise the value FALSE is returned. See section 4, for a complete description.
[ENVIRONMENT ('depend.pen'),
INHERIT ('definitions.pen',
'perform.pen',
'bintree.pen',
'allsmp.pen',
'listing.pen')]MODULE depend;
(* MODULE: DEPEND *)
(* This module generates the dependencies, for a so called flat *)
(* implementation model. It includes a testing function whether it is *)
(* possible to make a flat implementation. *)
(* The generating process stores all the information in the data structure *)
(* of allsmp. This is done by the procedures : *)
(* initialize_smp_algorithm *)
(* add_a_node(nr, elem_nr, attr_nr : integer) *)
(* add_a_dependency(from, to_ : integer; dir : tdirection) *)
(* !!! WARNING !!! *)
(* The type partlist is defined different from the one used in TRANS. *)
[HIDDEN]
CONST
max_pairs = 255;
[HIDDEN]
TYPE
(* Begin of the declarations for the partlist *)
twhere = ARRAY[0..max_part_nr] OF ttr_ass;
tpartlist = ARRAY[0..max_part_nr] OF integer;
(* Begin of the declaration for the dependency generation *)
tlower = ARRAY[0..max_elem_nr] OF elements;
tnumber = ARRAY[0..max_elem_nr] OF integer;
(* VARIABLE DECLARATION *)
[HIDDEN]
VAR
(* local for this program *)
lower : tlower; (* lower_left_hand_side_elements *)
number_of : tnumber; (* start numbers for numbering of pairs *)
to_attr : integer; (* These variables are used as a parameter *)
to_elements : elements; (* mechanism between: dep_simp_ass, (ass) *)
to_part : integer; (* and dep_simple_expr where they are used.*)
number : integer;
|
FUNCTION flatimplementable : boolean;
(* This procedure tests whether the described grammar is implementable *)
(* using the socalled flat implementation. The test for this is : *)
(* ALL e IN right_hand_side_elements *)
(* ( end_always_at(e)) *)
(* WHERE end_always_at(e) *)
(* = e IN element_with_direct_tree_rule *)
(* OR (e NOT IN elements_with_indirect_tree_rule *)
(* AND ALL e' IN class(e) (end_always_at(e')) *)
(* ) *)
(* To do this test first the sets right_hand_side_elements and left_hand_ *)
(* side_elements are generated. Then the test is performed. *)
VAR
right_elem_nr : integer;
no_errors : boolean;
PROCEDURE make_right_left_side_elements;
(* This procedure makes the right hand side and the left hand side *)
(* elements, which are put in left_side_elements and right_side_elements *)
VAR
elem_nr : integer;
PROCEDURE make_from(tree_rule : ptree_rule);
(* This procedure finds all the right hand side elemets from the tree *)
(* rule. *)
BEGIN
WHILE tree_rule <> NIL
DO BEGIN
right_side_elements := right_side_elements
+ [tree_rule^.element^.elem_nr];
tree_rule := tree_rule^.rest
END
END;
BEGIN (* of make_right_left_side_element *)
left_side_elements := [];
right_side_elements := [root^.elem_nr];
FOR elem_nr := 0 TO nr_of_elem
DO WITH element[elem_nr]^
DO IF kind_of_rule IN [r_dire,r_empt]
THEN BEGIN
left_side_elements := left_side_elements + [elem_nr];
make_from(tree_rule)
END
END;
PROCEDURE print_error_message(elem_nr : integer);
(* This procedure prints an error message if the grammar is not flat *)
(* implementable. with an indication of the place where the error *)
(* occurred. *)
BEGIN
IF no_errors
THEN BEGIN
write(listing, 'GRAMMAR IS NOT FLAT IMPLEMENTABLE');
print_newline;
write(listing, 'for:');
print_newline(2);
no_errors := FALSE
END;
write(listing, element[elem_nr]^.name, ' in ',
element[right_elem_nr]^.name);
print_newline
END;
PROCEDURE end_always_at(start_nr : integer);
(* This procedure seeks whether this element ends at an element with an *)
(* indirect tree rule, and if so an error message is generated. *)
VAR
elem_of : integer;
class : elements;
BEGIN
WITH element[start_nr]^
DO IF kind_of_rule = r_indi
THEN print_error_message(start_nr)
ELSE IF NOT(start_nr IN left_side_elements)
THEN BEGIN
class := class_rule;
elem_of := start_nr;
WHILE class <> []
DO BEGIN
next_elem(elem_of, class);
end_always_at(elem_of)
END
END
END;
BEGIN (* of flatimplementable *)
perf_start_time(perf_3_fl_im);
make_right_left_side_elements;
no_errors := TRUE;
FOR right_elem_nr := 0 TO nr_of_elem
DO IF right_elem_nr IN right_side_elements
THEN end_always_at(right_elem_nr);
IF NOT no_errors
THEN print_newline(3);
flatimplementable := no_errors;
perf_end_time(perf_3_fl_im);
END;
|
(* This page deals with the projection from each attribute element pair on *)
(* pairs in the implementation. Which could be described with the *)
(* following formal description, where the function projection returns all *)
(* elements of the pairs in the implementation : *)
(* *)
(* DF projection(attr, elem) *)
(* = IF elem IN elements_with_indirect_tree_rule *)
(* THEN IF attr IN attr_of(elem) *)
(* THEN [ elem ] *)
(* ELSE projection(attr, parent_of(elem)) *)
(* ELSE IF elem IN elements_with_tree_production *)
(* THEN [ elem ] *)
(* ELSE clos_class_or_and(elem) *)
(* INTERSECTION left_hand_side_elements *)
[HIDDEN]
FUNCTION projection(attr_nr : integer; elem_nr : integer) : elements;
(* This function returns the non_empty set of elements, to which this *)
(* attribute element (attr_nr, elem_nr) pair is projected by the flat *)
(* implementation method. *)
VAR
par_nr : integer;
BEGIN
WITH element[elem_nr]^
DO IF kind_of_rule = r_indi
THEN IF attr_nr IN attr[nor_gen]
THEN projection := [elem_nr]
ELSE BEGIN
par_nr := start_nr;
REPEAT
REPEAT par_nr := succ(par_nr) UNTIL par_nr IN parent
UNTIL element[par_nr]^.kind_of_rule IN [r_indi, r_dire];
projection := projection(attr_nr, par_nr)
END
ELSE projection := (clos_class + [elem_nr]) * left_side_elements
END;
|
(* This page deals with the numbering of the attribute element pairs with a *)
(* unique number that can be used for the construction of the dependency *)
(* graph. Two things have to be done. First we have to assign a number to *)
(* each pair, and secondly we have to give a function that retrieves the *)
(* number for a given pair. *)
(* We choose for the representation where we assign a number to each element *)
(* which added with an order of the attribute in the attribute set of this *)
(* element gives a unique number, in such a way that the resulting numbering *)
(* is compact. *)
[HIDDEN]
FUNCTION make_numbering_for_pairs : boolean;
(* This function assigns the right number to the global variable number_of *)
(* for every element, that has not an undefined tree rule. The function *)
(* returns TRUE if the maximum possible pairs is not exceeded. *)
VAR
number ,
elem_nr : integer;
PROCEDURE make_for(attrs : attributes);
(* This procedure sets number_of to the right value for elem_nr, and adds *)
(* number with the number of attributes in attrs. As a side effect the *)
(* attributes are written to the dependency file as pairs with the *)
(* name of element elem_nr. *)
VAR
attr_nr : integer;
pair : tnode;
BEGIN
number_of[elem_nr] := number;
attr_nr := start_nr;
WHILE attrs <> []
DO BEGIN
next_attr(attr_nr, attrs);
add_a_node(number, elem_nr, attr_nr);
number := succ(number);
END
END;
BEGIN (* of mak_numbering_for_pairs *)
perf_start_time(perf_3_mk_nr);
number := 0;
FOR elem_nr := 0 TO nr_of_elem
DO WITH element[elem_nr]^
DO CASE kind_of_rule OF
r_dire ,
r_empt : make_for(attr[all_gen]);
r_indi : make_for(attr[nor_gen]);
r_undf : number_of[elem_nr] := error_nr
END;
make_numbering_for_pairs := number <= max_pairs;
perf_end_time(perf_3_mk_nr)
END;
[HIDDEN]
FUNCTION number_of_pair(attr_nr, elem_nr : integer) : integer;
(* This function returns the number associated with the attribute element *)
(* pair (elem_nr, attr_nr), using the start_number assigned to the element, *)
(* which is in the global variable number_of, and the order of the *)
(* attribute in the attribute set. *)
VAR
cur_attr_set : attributes;
number ,
a : integer;
BEGIN
WITH element[elem_nr]^
DO IF kind_of_rule = r_indi
THEN cur_attr_set := attr[nor_gen]
ELSE cur_attr_set := attr[all_gen];
number := number_of[elem_nr];
FOR a := 0 TO pred(attr_nr)
DO IF a IN cur_attr_set
THEN number := succ(number);
number_of_pair := number
END;
|
This page deals with the generation of the dependencies for given set of elements with their attributes and partnumbers.
[HIDDEN]
PROCEDURE generate_dependencies
(attr_from : integer; elements_from : elements; part_from : integer;
attr_to : integer; elements_to : elements; part_to : integer);
(* This procedure generates all the dependencies for all the pairs formed *)
(* by attr_from and elements_from to the pairs formed by attr_to and *)
(* elements_to, with the right restrictions on the direction, depending on *)
(* part_from and part_to. *)
VAR
elem_nr ,
from_elem_nr ,
to_elem_nr ,
from ,
to_ : integer;
dir : tdirection;
elements_between ,
helements_to : elements;
FUNCTION direction(part_from, part_to : integer): tdirection;
(* This function returns the restrictions on the direction for a *)
(* dependency from node part_from to node part_to, of a tree rule. *)
BEGIN
IF (part_from = main_part_nr)
OR (part_to = main_part_nr)
THEN direction := none
ELSE IF part_from = part_to
THEN direction := both
ELSE IF part_from < part_to
THEN direction := left
ELSE direction := right
END;
BEGIN (* of generate dependencies *)
dir :=direction(part_from, part_to);
IF part_from <> part_to
THEN BEGIN
from_elem_nr := start_nr;
WHILE elements_from <> []
DO BEGIN
next_elem(from_elem_nr, elements_from);
from := number_of_pair(attr_from, from_elem_nr);
helements_to := elements_to;
to_elem_nr := start_nr;
WHILE helements_to <> []
DO BEGIN
next_elem(to_elem_nr, helements_to);
to_ := number_of_pair(attr_to, to_elem_nr);
add_a_dependency(from, to_, dir)
END
END
END
ELSE BEGIN
elements_between := elements_from * elements_to;
elem_nr := start_nr;
WHILE elements_between <> []
DO BEGIN
next_elem(elem_nr, elements_between);
from := number_of_pair(attr_from, elem_nr);
to_ := number_of_pair(attr_to, elem_nr);
add_a_dependency(from, to_, dir)
END
END
END;
|
[HIDDEN]
PROCEDURE dep_expr(expr_ptr : pexpr; VAR partlist : tpartlist);
(* This procedure tests the visibility as described by dep_visibility_EXPR *)
(* with EXPR, pointed by expr_ptr, and partlist partlist. *)
PROCEDURE dep_simple_expr;
(* This procedure tests whether the attribute of this simple expression, *)
(* pointed to by expr_ptr is visible from element elem. *)
(* This procedure makes use of the global variables to_attr, to_elements *)
(* and to_part, which are assigned in dep_simp_ass. *)
BEGIN
WITH expr_ptr^,attr^
DO generate_dependencies(attr_nr,
projection(attr_nr, partlist[partnamenr]),
partnamenr,
to_attr, to_elements, to_part)
END;
PROCEDURE dep_sem_func(args : plexpr);
(* This procedure generates the dependencies for the arguments of the *)
(* function with the arguments args. *)
BEGIN
WHILE args <> NIL
DO BEGIN
dep_expr(args^.first,partlist);
args := args^.rest
END
END;
PROCEDURE dep_case_expr(partnamenr : integer; partlist : tpartlist);
(* This procedure generates the dependencies for the case expressions *)
(* pointed to by expr_ptr. The variable elem holds the element associated *)
(* with the partname of this case expressions. *)
VAR
alt_expr : plalt_expr;
PROCEDURE dep_alter(selectors : elements; expr : pexpr);
(* This procedure generates the dependencies for one alternative of a *)
(* case expression. *)
VAR
elem_nr : integer;
BEGIN
elem_nr := start_nr;
WHILE selectors <> []
DO BEGIN
next_elem(elem_nr, selectors);
partlist[partnamenr] := elem_nr;
dep_expr(expr, partlist)
END
END;
BEGIN (* dep_case_expr *)
WITH expr_ptr^
DO BEGIN
alt_expr := alter;
WHILE alt_expr <> NIL
DO BEGIN
WITH alt_expr^
DO dep_alter(selectors, expr);
alt_expr := alt_expr^.rest
END
END
END;
BEGIN (* of dep_expr *)
WITH expr_ptr^
DO CASE kind OF
e_atoc : dep_simple_expr;
e_func : dep_sem_func(args);
e_case : dep_case_expr(headpnnr, partlist)
END
END;
|
[HIDDEN]
PROCEDURE dep_lattr_ass(lattr_ass_ptr : plattr_ass;
VAR partlist : tpartlist);
(* This procedure generates all dependencies for the list of assignments *)
(* pointed to by lattr_ass_ptr. *)
PROCEDURE dep_simp_ass;
(* This procedure generates all dependencies for the case that the first *)
(* assignment of lattr_ass_ptr is a simple attribute assignment. *)
(* The global variables to_attr, to_element and to_part are set, which *)
(* are used in dep_simple_expression. *)
BEGIN
WITH lattr_ass_ptr^,attr^
DO BEGIN
to_attr := attr_nr;
to_elements := projection(attr_nr, partlist[partnamenr]);
to_part := partnamenr;
dep_expr(expr, partlist)
END
END;
PROCEDURE dep_sel_ass(gpartnamenr : integer; partlist : tpartlist);
(* This procedure generates all the dependencies for the first assignment *)
(* in the case this is a selective assignment. *)
VAR
alt_ass : plalt_ass;
PROCEDURE dep_alter(selector : elements;
lattr_ass_ptr : plattr_ass);
(* This procedure generates the dependencies form one alternative, with *)
(* the selector , and the list of attribute assignments, *)
(* pointed to by lattr_ass_ptr. *)
VAR
elem_nr : integer;
BEGIN (* of dep_alter *)
elem_nr := start_nr;
WHILE selector <> []
DO BEGIN
next_elem(elem_nr, selector);
partlist[gpartnamenr] := elem_nr;
dep_lattr_ass(lattr_ass_ptr, partlist)
END
END;
BEGIN (* of dep_sel_class *)
WITH lattr_ass_ptr^
DO BEGIN
alt_ass := alter;
WHILE alt_ass <> NIL
DO BEGIN
WITH alt_ass^
DO dep_alter(selectors, attr_ass);
alt_ass := alt_ass^.rest
END
END
END;
BEGIN (* of dep_lattr_ass *)
WHILE lattr_ass_ptr <> NIL
DO BEGIN
WITH lattr_ass_ptr^
DO CASE kind OF
a_simp : dep_simp_ass;
a_sele : dep_sel_ass(headpnnr, partlist)
END;
lattr_ass_ptr := lattr_ass_ptr^.rest
END
END;
|
FUNCTION generate_all_dependencies : boolean;
(* This procedure generates the dependencies for all the attribute *)
(* assignments. *)
VAR
elem_nr : integer;
partlist : tpartlist;
PROCEDURE make_partlist(elem_nr : integer; VAR partlist : tpartlist);
(* This procedure makes a partlist with element pointer elem_ptr. *)
VAR
partnamenr : integer;
walker : ptree_rule;
BEGIN
partnamenr := 0;
partlist[partnamenr] := elem_nr;
walker := element[elem_nr]^.tree_rule;
WHILE walker <> NIL
DO BEGIN
partnamenr := succ(partnamenr);
WITH walker^
DO partlist[partnamenr] := element^.elem_nr;
walker := walker^.rest
END
END;
BEGIN (* of generate_all_dependencies *)
(* INITIALIZATION *)
initialize_smp_algorithm;
(* NUMBERING OF THE PAIRS *)
IF with_dep_info
THEN BEGIN
write(listing, 'The attribute pairs are:');
print_newline(2)
END;
IF make_numbering_for_pairs
THEN BEGIN
(* GENERATION OF THE DEPENDENCIES *)
IF with_dep_info
THEN BEGIN
print_newline(2);
write(listing, 'The dependencies are:');
print_newline
END;
perf_start_time(perf_3_g_dep);
FOR elem_nr := 0 TO nr_of_elem
DO WITH element[elem_nr]^
DO IF kind_of_rule IN [r_dire, r_empt]
THEN BEGIN
IF with_dep_info
THEN BEGIN
print_newline;
write(listing, 'With element: ', name);
print_newline(2)
END;
make_partlist(elem_nr, partlist);
dep_lattr_ass(attr_ass, partlist)
END;
perf_end_time(perf_3_g_dep);
generate_all_dependencies := TRUE
END
ELSE generate_all_dependencies := FALSE
END;
END.
|
My life as a hacker | My home page