A Parser for PL/0

As a first step toward the PL/O compiler a parser is being developed. This can be done strictly according to the parser Construction Rules Bl through B7 outlined in Sect. 5.4. This method, however, is only applicable if the Restrictive Rules 1 and 2 are satisfied by the underlying syntax. We are therefore obliged to verify this condition, as formulated for their application to syntax graphs.

Rule | specifies that every branch emanating from a fork point must lead toward a distinct first symbol. This is very simple to verify on the syntax diagrams of Fig. 5.4. Rule 2 applies to all graphs that can be traversed without reading any symbol. The only such graph in the PL/O syntax is the one describing statements. Rule 2 demands that all first symbols that may follow a statement must be disjoint from initial symbols of statements. Since later on it will be useful to know the sets of initial and following symbols for all graphs, we shall determine these sets for all seven non-terminal symbols (graphs) of the PL/O syntax (except for “program”). Table 5.2 provides the

desired assurance, namely, that the sets of initial and following symbols of statements do not intersect. Application of the parser Construction Rules B1 through B7 is thereby legalized.

The careful reader will have noticed that the basic symbols of PL/O are no longer single characters as in the preceding examples. Instead, the basic symbols are themselves sequences of characters, such as BEGIN, or :=. As in Program 5.3, a so-called scanner is used to take care of the merely representational or lexical aspects of the input sequence of symbols. The scanner is conceived as a procedure getsym whose task is to get the next symbol. The scanner serves the following purposes:

1. It skips separators (blanks).

2. It recognizes reserved words, such as BEGIN, END, etc.

3. It recognizes non-reserved words as identifiers. The actual identifier is assigned to a global variable called id.

4. It recognizes sequences of digits as numbers. The actual value is assigned to a global variable num.

5. It recognizes pairs of special characters, such as :=.

In order to scan the input sequence of characters, getsym uses a local procedure getch whose task is to get the next character. Apart from this main purpose, getch also

1. Recognizes and suppresses line end information.

2. Copies the input onto the output file, thus generating a program listing. 3. Prints a line number or location counter at the beginning of each line.

The scanner constitutes the necessary one-symbol Jookahead. Moreover, the auxiliary procedure getch represents an additional lookahead of one313 character. Therefore, the total lookahead of this compiler is one symbol plus one character.

The details of these routines are evident from Program 5.4 which represents the complete parser for PL/O. In fact, this parser is already extended in the sense that it collects the declared identifiers denoting constants, variables, and procedures in a table. The occurrence of an identifier within a statement then causes a search of this table to determine whether or not the identifier had been properly declared. The lack of such a declaration may duly be regarded as a syntactic error since it is a formal error in the composition of the program text because of the use of an “illegal” symbol. The fact that this error can only be detected by retaining information in a table is a consequence of the inherent context dependence of the language, manifest in the rule that all identifiers have to be declared in the appropriate context. Indeed, practically all programming languages are context sensitive in this sense; nevertheless, the context-free syntax is a most helpful model for these languages and greatly aids in the systematic construction of their recognizers. The framework thus obtained can then very easily be extended to take care of the few context sensitive elements of the language, as witnessed by the introduction of the identifier table in the present parser.

Before constructing the individual parser procedures corresponding to the individual syntax graphs, it is useful to determine how these graphs depend on each other. To this end, a so-called dependence diagram is constructed; it displays the relationships of the individual graphs, i.e., it lists for each graph G all those graphs G, ...G, in terms of which G is defined. Correspondingly, it shows those procedures that will be called by other procedures. The dependence graph for PL/O is shown in Fig. 5.5.

The loops in Fig. 5.5 indicate instances of recursion. It is therefore essential that a language in which the PL/0 compiler is implemented is not burdened by prohibition of recursion. In addition, the dependence diagram also allows drawing conclusions on the hierarchical organization of the parser program. For instance, all routines may be contained in (be declared local to) the routine that parses the construct (program) (which is therefore the main program part of the parser). Furthermore, all routines below <block> may be defined locally to the routine representing the parsing goal <block>. Naturally, all of these routines call upon the scanner getsym, which in turn calls upon getch.