Constructing a Table-Driven Parsing Program

Instead of composing a specific program according to the rules given in the preceding chapter for each language and syntax that arises, one may construct a single, general parsing program. Individual language grammars are then fed to the general program in the form of initial data preceding the sentences that are to be parsed. The general program strictly follows the rules of the simple top-down parsing method, and it is straightforward if the underlying syntax graph is deterministic, that is, if the grammar is such that sentences can be parsed with one symbol of lookahead and without backtracking.

Hence, the grammar, which we assume to be represented in the form of a deterministic set of syntax graphs, is translated into an appropriate data structure instead of into a program structure [5-2]. The natural technique296 for representing a graph is by introducing a node for each symbol and by connecting these nodes by pointers. Hence, the “table” is not a simple array structure. The rules which guide the translation are given below and are self-evident. The nodes of the data structure are records of two variants: one for terminal and the other for non-terminal symbols. The former are identified by the terminal symbol for which they stand, the latter by a pointer to the data structure representing the corresponding non-terminal symbol. Both variants contain two pointers, one designating the symbol that follows, the successor, and the other forming the list of possible alternatives. The resulting data type definition is given in (5.9), and within graphs we will depict a node as

At it turns out, we also need an element to represent the empty sequence, the null symbol. We shall denote it by a terminal element, called empty.

The translation rules from graphs into data structures are analogous to Rules BI through B7.

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

by suitable substitution.

C2. Translate each graph into a data structure according to the subsequent

rules C3 through C5.

C3. A sequence of elements (see picture of Rule B3) is translated into the

following list of data nodes:

C4. The list of alternatives (see picture of Rule B4) is translated into the

data structure

As an example, the graph corresponding to the syntax of Example 5 (Fig. 5.2) results in the structure in Fig. 5.3. The data structure is identified by a header node that contains the name of the non-terminal symbol (goal) for which the structure stands. This header is so far unnecessary, for the

pointer of the goal field could as well be pointing directly at the “entrance” of the appropriate structure. The header may be used, however, to carry a printable name of the structure.

The program to parse a sentence—represented as a sequence of characters on the input file—now consists of a repeated statement describing the transition from one node to a next node. The program is expressed as a procedure describing the interpretation of a graph; if a node representing a non-terminal symbol is encountered, then the interpretation of that graph precedes the completion of the interpretation of the present graph. Hence, the interpretation procedure is activated recursively. If the current symbol (sym) in the input file matches the symbol in the current node of the data structure, then the suc field is selected to indicate the next step, otherwise the alt field.

The parsing program (5.11) has the property of immediately pursuing a new subgoal G whenever one appears, without first inspecting whether or not the current symbol is contained in the set of initial symbols first(G). This implies that the underlying syntax graph must be void of choices between several alternative non-terminal elements. In particular, if a non-terminal symbol is capable of generating the empty sequence, then none of its right parts must start with a non-terminal symbol.

More sophisticated table-driven parsers may readily be derived from (5.11) which operate on less restrictive classes of grammars. Only slight modifications will also enable it to perform backtracking with, however, notable loss of effectiveness.

Representing a syntax by a graph has one decisive disadvantage: computers cannot directly read graphs. But the data structure that drives the parser must somehow be constructed before parsing can start. It is in this respect that the BNF-representation of grammars appears ideal—as input form for general parsing programs. The next section is therefore devoted to the design of a program which reads a sequence of BNF-productions and transforms them according to rules BI through B6 into an internal data structure, upon which the parser (5.11) can operate [5-8].