|
|
This document describes the body of the program which calls all the other procedures.
The program is divided into five main passes. The first pass is preceded by initialization (section 2), and the last pass is followed by finalization (section 8). All the passes may not be executed in all cases—for example, if a pass fails, or if the user elects not to proceed, then the following passes will be skipped.
In the first pass the input file is scanned and parsed. During parsing type checking is performed, see section 3
The second pass is entered on request by the user. In this pass the global semantic restrictions are tested. These apply to the definition of the rules (section 4.1) and the attribute declarations (section 4.2). The restrictions on the attribute assignments are tested when these are internally transformed (section 4.3). These transformed attribute assignments are used in the fifth pass.
In the third pass it is first checked whether the abstract tree grammar, as described in the input, can be implemented according to the flat implementation method. If this is possible the dependency graph is generated. During the generation it is possible that the number of attribute-element pairs exceeds the limit set by the current implementation. When this happens the rest of the passes are aborted. See section 5
In the fourth pass the Simple Multi-Pass algorithm is applied to the dependency graph. If there exists more than one solution, the best solution is chosen. See section 6
The fifth pass is entered on request by the user. In this pass the Pascal object program is generated using the SMP-solution. This program evaluates the attributes according to the attribute assignments. See section 7
We present an outline of the program, according to the above description:
initialization;
pass1 - scanning and parsing the input;
pass2 - IF user wants to proceed
THEN
testing the grammar;
calculating the attributes;
testing and transforming
the attribute assignments;
IF no errors detected in attribute assignments
THEN
pass3 - IF if input is flat implementable
THEN
generate dependencies;
IF number of pairs required within
implementation limits
THEN
pass4 - apply SMP-algorithm to dependency graph;
IF an SMP-solution is found
THEN
pass5 - IF user wants generation
THEN generation of evaluator
finalization
In the following sections we describe each of the five passes, as well as the initialization and finalization.
The procedure add screen info [screen 2.1.3] is used to update the current pass name displayed on the terminal. The procedure write elapsed time [screen 2.1.2] is used to update the elapsed run time as displayed by the screen module.
In the initialization phase a number of modules used by the main program are initialized. The following modules are initialized : the screen module (by calling the procedure initialize screen [screen 2.1.1]), the error module (procedure init errors [errors 1]), the binary tree module (procedure init tree [bintree 3.1]) and the performance analysis module (procedure perf init [perform 1]).
In the first pass the entire input is read [scanner] and checked (parsed) for grammatical correctness [parser]. During the parsing a number of type checks are performed, and errors are written to a listing file [listing]. The input is stored in the binary tree [bintree].
This pass is divided into a number of smaller parts which will be described in the following sub-sections.
Before the input is read, the procedure open scanner input file asks for an input filename [openfiles].
The user is asked whether he wants the screen module to operate in trace mode or in fast mode, which is signaled to the screen module by the procedure inform screen [screen 2.1.4].
The listing and scanner module are initialized by calling the procedures init listing [listing 1] and init scanner [scanner 1]. The listing module has to be initialized before the scanner module, because the scanner directly outputs the first line of the input file to the listing module. The listing module cannot be initialized earlier because the input filename is used in the heading on each page of the listing.
This is done by calling the parser procedure from the parser module. Before this is done, however, the procedure init level stack [screen 2.2.1] is called to display the level stack on the screen of the terminal.
After the entire input has been read a summary of the number of errors is printed in the listing by the procedure fin errors [errors 1] and the level stack is removed by calling the procedure purge level stack [screen 2.2.2].
As we saw in the outline of the program, the second pass is subdivided into three main parts. These parts test the grammar, calculate the attribute relations, and transform the attribute assignments, during which the visibility and consistency of these are tested. If serious errors are found, then they are reported and the rest of the passes are skipped. The three parts are described in the following subsections.
In this subsection we describe the tests that involve the global properties of the grammar read by the first pass. The subdivision of this part is:
testing grammar :
BEGIN
test all classes defined; [pass2 1]
test deterministic; [pass2 2]
test reachability(concrete); [pass2 3]
test reachability(complete); [pass2 3]
test termination; [pass2 4]
END
In this part the attribute relations that make use of the class rules are calculated and are simultaneously checked for correctness. This is done by the procedure gen all attributes [pass2 5].
In the first pass the semantic rules were tested using a number of local typing constraints. In this part of the second pass all other checks are performed. The most complicated test is the consistency test. To perform this test the entire set of attribute assignments are being rearranged. During this transformation process the visibility of the attributes is checked by making use of the class rules. This is done by the procedure transform [trans 1], which is called with the value of the variable with tracing, whose value is determined by the options [parser 2].
The parameter trans errors contains the number of errors found during the transformation process. If errors are found the following passes will not be executed.
The third pass tests whether the given grammar can be implemented according to the flat implementation method. This test is performed by the function flatimplementable [depend 1]. If this is not possible the dependency graph will not be generated and also the rest of the passes will be skipped. If the grammar is flat implementable, the dependency graph is generated by the procedure generate all dependencies [depend 4]. If there are more attribute-element pairs than can be represented in this implementation, the generated graph cannot be represented correctly, and the rest of the passes are aborted.
In this pass the Simple Multi-Pass algorithm is applied to the dependency graph generated by the previous pass. This is done by calling the function smp algorithm [allsmp 3], which returns TRUE whenever a solution is found, otherwise FALSE. The solution, if found, is represented by the variables partition, part dir, one pass and passes, which are given to the function as parameters.
In this last pass the actual evaluator is generated if the user requests it. The generation is based on the input grammar and the best Simple Multi-Pass solution that has been found in the previous pass. The generation is done by calling the procedure gen program [genera 1].
In this phase the program asks the user what information he wants in the listing file. These questions can be structured in the following way:
finalization :
IF user wants names
THEN BEGIN
ask whether user wants all names;
print binary tree
END;
IF user wants statistics
THEN print performance
The procedure print tree [printtree 1] prints the contents of the binary tree. The procedure perf print [perform 1] prints the performance statistics.
This module uses declarations from the following modules:
definitions, openfiles, perform, listing, screen, errors, scanner, bintree, parser, printtree, trans, allsmp, depend, pass2, generator.
In the following subsections we will give a list of imported declarations listed by module.
PROCEDURE initialize_screen( ... ;vt100 : boolean); PROCEDURE inform_screen(tracing : boolean); PROCEDURE finalize_screen; PROCEDURE add_screen_info( ... ); PROCEDURE write_elapsed_time; PROCEDURE init_level_stack; PROCEDURE purge_level_stack; PROCEDURE writeln_screen( ... ); PROCEDURE wait( sec : real);
VAR with_scan_echo ,
with_dep_info ,
with_gen_echo : boolean;
TYPE perf_process = ( ... ,perf_2_cl, perf_2_reach,
perf_2_term, perf_2_attr, ... )
PROCEDURE perf_init;
PROCEDURE perf_start_time(i : perf_process);
PROCEDURE perf_end_time(i : perf_process);
VAR listing : text; PROCEDURE init_listing; PROCEDURE print_page; PROCEDURE print_newline;
PROCEDURE init_errors; PROCEDURE fin_errors;
PROCEDURE open_scanner_input_file; PROCEDURE init_scanner;
PROCEDURE init_tree;
PROCEDURE parser;
PROCEDURE print_tree
PROCEDURE transform(VAR trans_errors : integer;
with_tracing : boolean);
TYPE tpartition TYPE tpart_dir TYPE tset_node FUNCTION smp_algorithm( ... ) : boolean;
FUNCTION flatimplementable : boolean; FUNCTION generate_all_dependencies : boolean;
PROCEDURE test_all_classes_defined; PROCEDURE test_deterministic; TYPE tkind = (r_comp, r_conc); PROCEDURE test_reachability(kind : tkind_reach); PROCEDURE test_termination; PROCEDURE gen_all_attributes;
PROCEDURE gen_program( ... );
[INHERIT ('definitions.pen',
'[-.screen]openfiles.pen',
'perform.pen',
'listing.pen',
'[-.screen]screen.pen',
'errors.pen',
'scanner.pen',
'bintree.pen',
'parser.pen',
'printtree.pen',
'trans.pen',
'allsmp.pen',
'depend.pen',
'pass2.pen',
'generator.pen')]
PROGRAM parsergenerator(output);
VAR
msg : VARYING[80] OF char;
(* the smp-solution *)
partition : tpartition;
part_dir : tpart_dir;
one_pass : tset_node;
passes : integer;
(* PROCEDURES *)
FUNCTION ask_yes_or_no (question: t_question) : boolean;
(* This procedure asks the question and returns TRUE if a Y is given *)
(* and FALSE if a N is given and repeats its question in every other case *)
VAR answer : char;
ok : boolean;
BEGIN
REPEAT
write_screen( question + ' (y/n) ');
readln(answer);
writecr_screen;
ok := answer IN ['Y','y','J','j','N','n'];
IF NOT ok
THEN writeln_screen('answer "y" or "n" ');
UNTIL ok;
ask_yes_or_no := answer IN ['Y','y','J','j']
END;
FUNCTION user_request(question : VARYING[l] OF char; test : boolean) : boolean;
BEGIN
IF test
THEN user_request := TRUE
ELSE IF ask
THEN user_request := ask_yes_or_no(question)
ELSE user_request := FALSE
END;
|
BEGIN
initialize_screen(' AAPT-generator ',ask_yes_or_no('vt100 '));
wait(0.5);
init_errors;
init_tree;
perf_init;
|
add_screen_info('Pass 1 : Scanning and parsing');
open_scanner_input_file;
writeln_screen;
inform_screen(ask_yes_or_no('tracing '));
with_scan_echo := ask_yes_or_no('show scanning ');
init_listing;
init_scanner;
init_level_stack;
parser;
writeln_screen;
writeln_screen;
fin_errors;
purge_level_stack;
add_screen_info('Pass 2 : Semantic checks and transformation');
IF ask_yes_or_no('pass2 ') THEN
|
BEGIN
print_page;
write_elapsed_time;
inform_screen(ask_yes_or_no('tracing '));
init_level_stack; perf_start_time(perf_2_cl);
test_all_classes_defined;
write_elapsed_time;
test_deterministic; perf_end_time (perf_2_cl);
write_elapsed_time; perf_start_time(perf_2_reach);
test_reachability(r_conc);
test_reachability(r_comp); perf_end_time (perf_2_reach);
write_elapsed_time; perf_start_time(perf_2_term);
test_termination; perf_end_time (perf_2_term);
write_elapsed_time; perf_start_time(perf_2_attr);
gen_all_attributes; perf_end_time (perf_2_attr);
write_elapsed_time;
transform(trans_errors, with_tracing);
write_elapsed_time;
purge_level_stack;
IF trans_errors > 0
THEN BEGIN
print_newline;
writev(msg,'MESSAGE: total number of transformation error(s) :',
trans_errors : 4);
writeln_screen(msg);
write(listing, msg);
print_newline;
writev(msg,'WARNING: dependency generation surpressed');
writeln_screen(msg);
write(listing, msg);
print_newline
END
ELSE
IF NOT flatimplementable
THEN BEGIN
print_newline(2);
write(listing, 'NO FLAT IMPLEMENTATION');
print_newline;
writev(msg, 'WARNING: no flat implementation');
writeln_screen(msg);
write(listing, msg);
print_newline
END
ELSE
|
BEGIN
add_screen_info('Pass 3 : Generate dependency graph');
print_page;
write(listing, 'FLAT IMPLEMENTATION');
print_newline(2);
with_dep_info := ask_yes_or_no('dependency info ');
inform_screen(ask_yes_or_no('tracing '));
init_level_stack;
write_elapsed_time;
IF NOT generate_all_dependencies
THEN BEGIN
writev(msg, 'ERROR: too many pairs for this implementation');
writeln_screen(msg);
write(listing, msg);
print_newline;
purge_level_stack
END
ELSE
|
BEGIN
purge_level_stack;
add_screen_info('Pass 4 : Find simple multi-pass solution');
IF NOT smp_algorithm(partition, part_dir, one_pass, passes)
THEN BEGIN
writev(msg, 'ERROR: no Simple Multi-Pass Solution possible');
writeln_screen(msg);
write(listing, msg);
print_newline
END
ELSE
|
BEGIN
add_screen_info('Pass 5 : PASCAL program generation');
IF ask_yes_or_no('generate pascal program ')
THEN BEGIN
inform_screen(ask_yes_or_no('tracing '));
with_gen_echo := ask_yes_or_no('show generation ');
init_level_stack;
gen_program(partition, part_dir, one_pass, passes);
purge_level_stack
END;
END (* pass five *)
END (* pass four *)
END (* pass tree *)
END; (* pass two *)
|
add_screen_info('Finals');
IF user_request('names ', with_names)
THEN BEGIN
with_all_names := user_request('all names ', with_all_names);
print_tree
END;
IF user_request('statistics ',with_statistics)
THEN perf_print(listing);
write_elapsed_time;
finalize_screen
END.
|
My life as a hacker | My home page