|
|
This module contains the procedures that generate the typing used to represent the abstract program tree that is used by the generated attribute evaluator.
Before we describe the procedures that generated the typing, we first want to make some remarks on our design choices.
In the (first) implementation of the attribute evaluator generator we decided to stay as close as possible to the rules as specified by the input grammar. For this reason we called this implementation the flat implementation. This resulted in one extra restriction on the input grammar, as described in [2.9].
The representation used to represent the abstract program tree should be space efficient. Because of this, we decided to specify a separate type for each node type and class given in the input grammar, instead of using a representation mechanism that applies to all kinds of node types. The class hierarchy is represented completely by defining a separate type for each class. On first sight, this might not seem to be as space efficient as collapsing the class hierarchy internally, which would require only one pointer between nodes. Problems arise, however, when the attributes are taken into account. Attributes can also be defined with classes in the middle of the class hierarchy. When using a collapsed representation, these attributes have to be stored elsewhere, which may lead to very complicated constructions.
We decided to store the attributes with the classes and the node type with which they are defined by the input grammar. This is the most straightforward and simple solution. This way of viewing the attributes differs from the way we used for calculating the dependencies, see [3.1.1]. However, this difference does not complicate the implementation of the generation procedures dramatically.
We decided not to store the one pass attributes in the tree, but implement them as parameters of the tree walking procedures.
Another decision to be made is, where to use pointers in the representation of the abstract program trees. At first sight one would expect pointers in the records that represent the right-hand sides of tree rules. But because these pointers could point to different kinds of objects we needed a kind of untyped pointer. Because of this, class definitions are defined using a variant record, where the variants are pointers to different types. The tag field is used to store which element of the class is applied.
When classes are used in the right-hand side of tree rules there is no need to introduce an extra pointer. Because of the termination restriction there is no need to introduce an extra pointer for node types used in the right-hand side of tree rules. To summarize, we see that there are no pointers used in the definition of the records that represent the tree rules, and pointers used in the definition of the records that represent the class definitions.
Another problem arises when we have elements in the right-hand side that are elements of a class which has attributes. These attributes have to be stored with that part of the right-hand side of the tree rule. We solved this problem by introducing an extra nested record type for these instances.
This module only exports the procedure gen types, which generates the whole typing for the abstract program tree for the generated attribute evaluator. This procedure has no parameters.
The typing consists of three parts. The first part is the definition of an enumeration type, to identify the different elements. This type is used as the type of the tag fields in the variant parts, which represent the class definitions. This part is generated by the procedure gen s elems type.
The second part is the definition of all the pointer types. For each element a pointer type is generated which points to the type representing the tree rule and class definition of that element. This part is generated by the procedure gen pointer types.
The third part is the definition of the types that represent the tree rule and class definition with each element. This part is generated by the procedure gen t types.
These three parts, with their generation procedures, are described in the following subsections.
The procedure gen s elems type generates the enumeration type s elems as the enumeration of the elements in the input grammar. The generated PASCAL typing has the following form:
s_elems = (<elem1>, <elem2>, ... <elemn>);
The procedure gen pointer types generates for each element in the input grammar a pointer type pointing to the representation of that element. The generated Pascal typing has the following form:
p_<elem1> = ^t_<elem1>; ... p_<elemn> = ^t_<elemn>;
The procedure gen t types generates for each element a record type representing the tree rule, the class definition and the attributes defined with the element. Whenever node types are used in the right-hand side of a tree rule, the record type representing this node type is used in the typing representing this tree rule. Because the types generated here can use each other, the order in which these record types are generated is important. Because the termination property holds, there is at least one possible order. The procedure gen t types repeatedly scans all the elements, and generates the record types when possible, until all the record types for the elements are generated. The local variable not printed contains the elements for which no record type has been generated. The function can be generated tests whether a record type uses only types that have already been declared in the generated typing.
The function can be generated tests whether the types used in the representation of a tree rule have already been generated. The tree rule for which the test is performed is pointed to by the first parameter tree list of type p tree list [bintree 1.7], and has a number of parts equal to the value of the second parameter nr of parts. The local variable not printed is used by this function, because it contains the elements for which no record type has been generated yet.
The procedure gen type of generates the record type for the element represented by the parameter elem nr only. The generated PASCAL typing for an element that has a tree rule, a class definition and attributes defined with it, has the following form:
t_<elemi> = RECORD
(* attributes : *)
..{attributes defined with this element}..
(* tree rule : *)
..{representation of the tree rule}..
(* class rule : *)
CASE k_ : s_elems OF
..{variants representing the elements of
the class definition}..
END;
Each of the tree parts (attributes, tree rule and class rule) can be absent, if it is not applicable. The representation of the attributes is generated by calling the local procedure gen attributes. The representation of the tree rule, if this element has a tree rule, is generated by calling the procedure gen tree rule. The representation of the class definition, if this element is a class, is generated by calling the procedure gen class rule.
The procedure gen attributes generates the typing needed to store the attributes as represented by the parameter attrs. For each attribute in this set a record field with associated type is generated, using the following format:
<attri> : <type of(attri)>;
The procedure gen tree rule generates the typing for the tree rule represented by the first parameter tree list of type t tree list [bintree 1.7], and with a number of parts equal to the value of the second parameter nr of part. This procedure generates a record field with typing for each part. The form of the typing depends on whether the element of the part has attributes defined by classes higher in the class hierarchy. As was explained in section 1, these attributes have to be stored with the part, using an extra record type. If there are no such attributes, the typing for the part has the following form:
<parti> : t_<elem of parti>;
However, if there are such attributes, the typing for the part has the following form:
<parti> : RECORD
(* attributes : *)
....
r_ : t_<elem of parti>
END;
The record fields which represent the attributes are generated by calling the procedure gen attributes.
This module uses declarations from the following modules:
definitions, screen, bintree, genpro.
The only procedure that is exported by this module is:
PROCEDURE gentypes;
This procedure generates the complete typing needed for the evaluator.
[ENVIRONMENT ('gtypes.pen'),
INHERIT ('definitions.pen',
'[-.screen]screen.pen',
'bintree.pen',
'onepassrel.pen',
'genpro.pen')]
MODULE gentypes;
[HIDDEN]
VAR
msg : text_info;
|
The s elems type, is the enumeration type of all the elements, and is used in the record definition of the classes.
PROCEDURE gen_s_elems_type;
VAR
nr ,
hold : integer;
BEGIN
enter_level('gen_s_elems_type);
gen_newline(1);
gen_('s_elems');
gen_tab(20);
gen_(' = (');
set_left_margin(hold);
FOR nr := 0 TO nr_of_elem
DO BEGIN
gen_(m_elem(nr));
IF nr <> nr_of_elem
THEN gen_(', ')
END;
gen_(');');
reset_left_margin(hold);
exit_level
END;
|
For every element a pointer type is generated.
PROCEDURE gen_pointer_types;
(* This procedure generates for every element the pointer type with prefix *)
(* p, of every element normal type with prefix t. *)
VAR
nr : integer;
BEGIN
enter_level('gen_pointer_types);
FOR nr := 0 TO nr_of_elem
DO BEGIN
gen_newline(1);
gen_('p_'+m_elem(nr));
gen_tab(20);
gen_(' = ^t_' + m_elem(nr) + ';');
END;
exit_level
END;
|
PROCEDURE gen_t_types;
(* This procedure generates for every element a record type, depending on *)
(* its definition. The order in which the types are generated depends on *)
(* whether there are tree rules with node_types. Those types should always *)
(* be generated first. No circularity can exist because that would imply *)
(* a non terminating grammar, which has been tested in the second pass. *)
VAR
elem_nr ,
hold : integer;
not_printed : elements;
FUNCTION can_be_generated(VAR tree_list : p_tree_list;
nr_of_parts : integer) : boolean;
(* This procedure tests whether the elements in the tree rule, *)
(* represented by tree_rule, all have been generated. *)
VAR
can_be : boolean;
part_nr : integer;
BEGIN
IF tree_list = NIL
THEN can_be_generated := TRUE
ELSE BEGIN
can_be := TRUE;
part_nr := 0;
WHILE (part_nr < nr_of_parts) AND can_be
DO BEGIN
part_nr := succ(part_nr);
can_be := NOT(tree_list^[part_nr]^.element^.elem_nr
IN not_printed)
END;
can_be_generated := can_be
END
END;
PROCEDURE gen_type_of(elem_nr : integer);
(* This procedure generates the record type with element elem_nr. The *)
(* layout can be described by : *)
(* *)
(* |RECORD *)
(* | <attributes(attrs[nor_gen])> *)
(* | <tree_rule(tree_rule)> *)
(* |<class_rule(class) OPTION> *)
(* |END *)
(* *)
VAR
hold : integer;
PROCEDURE gen_attributes(attrs : attributes);
(* This procedure generates the attributes associated with this element *)
(* in the record type. *)
VAR
attr_nr : integer;
BEGIN
enter_level('gen_attributes');
IF attrs <> []
THEN BEGIN
gen_newline(1);
gen_('(* attributes : *)');
attr_nr := start_nr;
REPEAT
next_attr(attr_nr, attrs);
gen_newline(1);
WITH attribute[attr_nr]^
DO BEGIN
gen_(name);
gen_tab(20);
gen_(' : ' + type_of_attr.type_name^.name + ';');
END
UNTIL attrs = []
END;
exit_level
END;
PROCEDURE gen_tree_rule(VAR tree_list : t_tree_list;
nr_of_part : integer);
(* This procedure generates the typing of a tree rule, represented by *)
(* tree_rule. *)
VAR
part_nr ,
hold : integer;
BEGIN
enter_level('gen_tree_rule');
gen_newline(1);
gen_('(* tree rule : *)');
FOR part_nr := 1 TO nr_of_part
DO BEGIN
WITH tree_list[part_nr]^,element^
DO BEGIN
gen_newline(1);
gen_(partname);
gen_tab(20);
gen_(' : ');
IF impattr_at[elem_nr] <> []
THEN BEGIN
set_left_margin(hold);
gen_keyw(k_record);
gen_attributes(impattr_at[elem_nr]);
gen_newline(1);
gen_('r_ : t_' + m_elem(elem_nr));
gen_keyw(k_end);
reset_left_margin(hold)
END
ELSE gen_('t_' + m_elem(elem_nr));
gen_(';');
END;
END;
exit_level
END;
PROCEDURE gen_class_rule(class : elements);
VAR
nr : integer;
BEGIN
enter_level('gen_class_rule');
gen_newline(1);
gen_('(* class rule : *)');
gen_keyw(k_s_end);
gen_newline(1);
gen_keyw(k_case);
gen_('k_ : s_elems OF');
nr := start_nr;
WHILE class <> []
DO BEGIN
next_elem(nr, class);
gen_newline(1);
WITH element[nr]^
DO BEGIN
gen_(name);
gen_tab(20);
gen_(' : (n_' + m_elem(nr) + ' : p_' + m_elem(nr) + ')');
IF class <> []
THEN gen_(';')
END
END;
exit_level
END;
BEGIN (* of gen_type_of *)
enter_level('gen_type_of);
writev(msg, 'elem : ', element[elem_nr]^.name);
add_level_info(msg);
gen_newline(1);
WITH element[elem_nr]^
DO BEGIN
gen_('t_' + name);
gen_tab(20);
gen_(' = ');
set_left_margin(hold);
gen_keyw(k_record);
gen_attributes(attr[nor_gen] - implone_pass[elem_nr]);
IF kind_of_rule = r_dire
THEN gen_tree_rule(tree_list^, nr_of_parts);
IF class_rule <> []
THEN gen_class_rule(class_rule);
gen_keyw(k_end);
gen_(';');
reset_left_margin(hold)
END;
exit_level
END;
BEGIN (* of gen_t_types *)
enter_level('gen_t_types);
not_printed := [0..nr_of_elem];
REPEAT
FOR elem_nr := 0 TO nr_of_elem
DO IF elem_nr IN not_printed
THEN WITH element[elem_nr]^
DO IF can_be_generated(tree_list, nr_of_parts)
THEN BEGIN
gen_type_of(elem_nr);
not_printed := not_printed - [elem_nr]
END
UNTIL not_printed = [];
exit_level
END;
|
PROCEDURE gentypes;
(* This procedure generates the complete typing needed for the evaluator. *)
BEGIN
enter_level('gentypes');
gen_newline(1);
gen_keyw(k_type);
gen_s_elems_type;
gen_pointer_types;
gen_t_types;
reset_left_margin(0);
exit_level
END;
END.
|
My life as a hacker | My home page