Constructing a Parser for a Given Syntax

A program which accepts and parses a language is readily derived from its deterministic syntax graph (if such a graph exists). The graph essentially represents the flowchart of the program. In developing this program, however,292 one is well-advised to strictly follow a given set of translation rules similar to those that may have led from a BNF to a graph representation of the syntax in the first place. These rules are listed below. They are applicable in a specific framework. This framework consists of a main program in which the procedures corresponding to the various subgoals are embedded and of a routine to proceed to the next symbol.

For the sake of simplicity, let us assume that the sentence to be parsed is represented by the file input and that terminal symbols are individual characters. We now postulate the existence within this framework of a character variable ch that always represents the next symbol being read. Stepping to the next symbol is then expressed by the statement

The main program now consists of an initial statement to read the first character, followed by a statement activating the main parsing goal. The individual routines corresponding to parsing goals or graphs are obtained by obeying the following rules. Let the statement obtained by translating the graph S be denoted by 7(S).

Bl. Reduce the system of graphs to as few individual graphs as possible

by appropriate substitutions.

B2. Translate each graph into a procedure declaration according to the

subsequent rules B3 through B7.

where L, denotes the set of initial symbols of the construct S(L;=first(S))). Note: if L; consists of a single symbol a, then of course “ch in L,” should be expressed as “ch = a”.

where 7(S) is the translation of S according to rules B3 through B7, and L is the set L = first(S) (see preceding note).

where error is a routine called when an ill-formed construct is encountered.

The application of these rules is now demonstrated by translating the reduced graph of Example 5 (Fig. 5.2) into a recognizer program (Program 5.1).

During this translation some obvious programming rules have been freely applied in order to simplify the program. A literal translation would have resulted, for example, in the fourth line reading

which can obviously be reduced into the simpler form presented in the program. Also the read statements in the fifth and seventh lines resulted from similar reductions.

It seems sensible to find out where such reductions are possible in general and then to represent them directly in terms of the graph. The two relevant cases are covered by the following additional rules:

The procedure error has so far been left unspecified on purpose. Since we are now only interested in finding out whether an input sequence is well- or ill-formed, we may think of this procedure as a program terminator. Naturally, in practice, more refined principles of coping with ill-formed sentences have to be used. This will be the subject of Sect. 5.9.