Sentence Analysis

The task of language translators or processors is primarily not the generation but the recognition of sentences and sentence structure. This implies that the generating steps which lead to a sentence must be reconstructed upon reading the sentence, and that its generation steps must be retraced. This is generally a very complicated and sometimes even impossible task. Its complexity intimately depends on the kind of production rules used to define the language. It is the task of the theory of syntax analysis to develop recognizing algorithms for languages with rather complicated structural rules. Here, however, our goal is to outline a method for constructing recognizers that are sufficiently simple and efficient to serve in practice. This implies nothing less than that the computational effort to analyze a sentence must be a linear function of the length of the sentence; in the very worst case the dependency function may be n-log n, where n is the sentence length. Clearly, we cannot be bothered with the problem of finding a recognition algorithm for any given language, but we will work pragmatically in the reverse direction: define an efficient algorithm and then determine the class of languages that can be treated by it [5-3].

A first consequence of the basic efficiency requirement is that the choice of every analysis step must depend only on the present state of computation and on a single next symbol being read. Another most important requirement is that no step will have to be revoked later on. These two requirements are commonly known under the technical term one-symbol-lookahead without backtracking.

The basic method to be explained here is called top-down parsing because it consists of trying to reconstruct the generating steps (which in general form a structural tree) from their start symbol to the final sentence, from the284 top down [5-5 and 5-6]. Let us start by revisiting Example 1: We are given the sentence, Dogs eat, and we must determine whether or not it belongs to the language. This, by definition, is only the case if it can be generated from the start symbol <sentence>. From the grammatical rules it is evident that it can only be a sentence if it is a subject followed by a predicate. We now divide the remaining task; first, we determine whether or not some initial part of the sentence may be generated from the symbol <subject>. This is indeed so since dogs can be directly generated; the symbol dogs is checked off in the input sentence (i.e., we advance our reading position), and we proceed to the second task: checking whether or not the remaining part can be generated from the symbol <predicate>. Since this is again the case, the result of the analysis process is affirmative. We may visualize this process by the following trace, showing on the left the tasks still ahead and on the right the part of the input still remaining unread.

A second example shows the trace of the analysis process of the sentence xyyz according to the productions of Example 2.

Since the process of retracing the generating steps of a sentence is called parsing, what is described above is a parsing algorithm. In the two examples the individual replacement steps could decidedly be taken upon inspection of the single next symbol in the input sequence. Unfortunately, this is not always possible, as is evident from the following example:

and get stuck. The difficulty arises in the very first step in which the decision about replacing S by A or B cannot be taken by looking at the first symbol only. A possible solution lies in simply proceeding according to one of the possible options and to retreat along the taken path of pursued subgoals if no further progress is possible. This action is called backtracking. In the language of Example 3, there is no limit to the number of steps that may have to be “undone.” This situation is clearly most undesirable; hence, those language structures that lead to backtracking should be identified and avoided in practical applications. Consequently, we shall decree that we will only consider grammar systems satisfying the following restriction that specifies that the initial symbols of alternativé right parts of productions be distinct.

the sets of initial symbols of all sentences that can be generated from the &7s must be disjoint, i.e.,

The set first(€) is the set of all terminal symbols that can appear in the first position of sentences derived from €. Let this set be computed according to the following rules:

1. The first symbol of the argument is terminal:

2. The first symbol is a non-terminal symbol with the derivation rule

In Example 3, we notice that x € first(A) and x © first(B). Hence Rule | is violated by the first production. It is indeed trivial to find a syntax for the286 language of Example 3 that satisfies Rule |. The solution lies in delaying the factoring until all x’s have been dealt with. The following productions are equivalent with those of (5.5) in the sense that they generate the same set of sentences:

Unfortunately, Rule 1 is not strong enough to shield us from further trouble. Consider

Here, € denotes the null sequence of symbols. As we try to parse the sentence x, we may proceed into the following “dead alley”:

The trouble arose because we should have followed the production 4 ::= € instead of A::= x. This situation is called the null string problem, and it arises only for non-terminal symbols that can generate the empty sequence. In order to avoid it, we postulate

For every symbol A € N which generates the empty sequence (A ~> €), the set of its initial symbols must be disjoint from the set of symbols that may follow any sequence generated from A, i.e.,

The set follow(A) is computed by considering every production P, of the form

and taking the set S, = first(y,). follow(A) is the union of all such sets S,. If at least one , is capable of generating the empty sequence, then the set follow(X) has to be included in fo/low(A) as well. In Example 4, Rule 2 is violated for the symbol A since

The usual way of expressing a repeated pattern of symbols is by using a recursive definition of a sentential construct. For example, the production

describes the set of sequences B, BB, BBB,.... Its use, however, is now

The two restrictive rules obviously prohibit the use of left recursive definitions. A simple method used to avoid these forms is by either using right recursion

or by extending the symbolism of BNF to allow to express replication explicitly; we shall do so by letting {B} denote the set of sequences

Of course, one must be aware that every such construct is capable of generating the empty sequence. (The brackets { and } are meta-symbols of extended

From the preceding argument and from the transformation of the productions (5.5) into (5.5a) it may appear that the “trick” of transforming grammars might be the panacea to all problems of syntax analysis. We must, however, keep in mind that sentential structure is instrumental in defining sentential meaning, that explanations of the meaning of a sentential construct are usually expressed in terms of the meaning of the sentential components. Take, for example, the language of expressions consisting of operands a, b, c and the minus sign meaning subtraction.

According to this grammar, the sentence a—b—c has a structure that can be expressed by using parentheses as follows: ((a—b)—c). However, if the grammar is transformed into the syntactically equivalent but left recursion free form

then the same sentence would be given another structure, namely, the one expressed as (a—(b—c)). Considering the conventional meaning of subtraction, we see that the two forms are not at all semantically equivalent.

The lesson, then, is that when defining a language with an inherent meaning, one must always be aware of the semantic structure when devising its syntactic structure because the latter must reflect the former.