BookBody

Sec. 9.7]

Further developments of LR methods

221

many other algorithms are known for this problem. There exist simple and complicated variants and improvements, gaining factors of 5 or 10 over the simple channel algorithm. See for instance, DeRemer and Pennello [LR 1982] and the Park, Choe and Chang [LR 1985, 1987] versus Ives [LR 1986, 1987] discussion. Bermudez and Logothetis [LR 1989] present a remarkably elegant interpretation of LALR(1) parsing.

9.7.4 Incremental parsing

In incremental parsing, the structured input (a program text, a structured document, etc.) is kept in linear form together with a parse tree. When the input is (incrementally) modified by the user, for instance, by typing or deleting a character, it is the task of the incremental parser to update the corresponding parse tree, preferably at minimum cost. This requires serious measures inside the parser, to quickly determine the extent of the damage done to the parse tree, localize its effect and take remedial steps. Formal requirements for the grammar to make this easier have been found. See for instance, Degano, Mannucci and Mojana [LR 1988] and many others in Section 13.6.

9.7.5 Incremental parser generation

In incremental parser generation, the parser generator keeps the grammar together with its parsing table(s) and has to respond quickly to user-made changes in the grammar, by updating and checking the tables. Research on this is in its infancy. See Heering, Klint and Rekers [LR 1989] and Horspool [LR 1989].

9.7.6 LR-regular

Rather than trying to resolve inadequate states by looking ahead a fixed number of tokens, we can have an FS automaton for each inadequate state that is sent off up the input stream; the state in which this automaton stops is used as a look-ahead. This parsing technique is called LR-regular. See Cˇ ulik and Cohen [LR 1973].

A variant of this method reads in the entire input into an array and runs a single FS automaton (derived from the grammar) backwards over the array, recording the state of the automaton with each token. Next, during (forward) LR parsing, these recorded states rather than the tokens are used as look-aheads.

9.7.7 Recursive ascent

In Sections 8.2.6 and 8.4 we have seen that an LL parser can be implemented conveniently using recursive descent. Analogously, an LR parser can be implemented using recursive ascent, but the required technique is not nearly as obvious as in the LL case. The key idea is to have the recursion stack mimic the LR parsing stack. To this end there is a procedure for each state; when a token is to be shifted to the stack, the procedure corresponding to the resulting state is called instead. This indeed constructs the correct recursion stack, but causes problems when a reduction has to take place: a dynamically determined number of procedures has to return in order to unstack the right-hand side. A simple technique to achieve this is to have two global variables, one, Nt, holding the non-terminal recognized and the second, l, holding the length of the right-hand side. All procedures will check l and if it is non-zero, they will decrease l by one and return immediately. Once l is zero, the procedure that finds that situation will call the appropriate state procedure based on Nt. For details see Roberts [LR 1988, 1989, 1990] and Kruseman Aretz [LR 1988]. The advantage of recursive ascent over table-driven is its potential for high-speed parsing.

222

Deterministic bottom-up parsing

[Ch. 9

9.8 TOMITA’S PARSER

Now that we have seen the precise criteria for the existence of an LR-like parser for a grammar, i.e., that there is a handle-recognizing finite-state automaton with no inadequate states for that grammar, we become interested in the grammars for which the criteria are not completely fulfilled and for which the automaton has some inadequate states. Tomita [CF 1986] has given an efficient and very effective approach to such grammars.

Tomita’s method can be summarized as doing breadth-first search as in Section 7.1.2 over those parsing decisions that are not solved by the LR automaton (which can be LR(1), LALR(1), SLR(1), LR(0), precedence or even simpler), while at the same time keeping the partial parse trees in a form akin to the common representation of Section 7.1.3. More precisely, whenever an inadequate state is encountered on the top of the stack, the following steps are taken:

1.For each possible reduce in the state, a copy of the stack is made and the reduce is applied to it. This removes part of the right end of the stack and replaces it with a non-terminal; using this non-terminal as a move in the automaton, we find a new state to put on the top of the stack. If this state allows again reductions, this copy step is repeated until all reduces have been treated, resulting in equally many stack copies.

2.Stacks that have a right-most state that does not allow a shift on the next input token are discarded (since they resulted from incorrect guesses). Copies of the next input token are shifted onto the remaining stacks.

There are a number of things to be noted here. First, if the automaton uses look-ahead, this is of course taken into account in deciding which reduces are possible in step 1 (ignoring this information would not be incorrect but would cause more stacks to be copied and subsequently discarded). Second, the process in step 1 may not terminate. If a grammar has loops (rules of the form A → B, B → A) reduction will alternate between A and B. There are two solutions: upon creating a stack, check if it is already there (and then ignore it) or check the grammar in advance for loops (and then reject it). Third, if all stacks are discarded in step 2 the input was in error, at that specific point.

SS -> E #

E -> E + E

E -> d

Figure 9.38 A moderately ambiguous grammar

The above forms the basic mechanism of the Tomita parser. Since simple stack duplication may cause a proliferation of stacks and is apt to duplicate much information that is not in need of duplication, two optimizations are used in the practical form of the parser: combining equal states and combining equal stack prefixes. We shall demonstrate all three techniques using the grammar of Figure 9.38 as an example. The grammar is a variant of that of Figure 3.1 and is moderately ambiguous. Its LR(0) automaton is shown in Figure 9.39; it has one inadequate state, . Since the grammar is ambiguous, there is not much point in using a stronger LR method. For more (and larger!) examples see Tomita [CF 1986].

Sec. 9.8]			Tomita’s parser							223
					6
				S->E#
1				3	#					4
S-> E#							E->E+ E
			E	S->E #	+
E-> E+E							E-> E+E
				E->E +E
E-> d							E-> d
2		d		d		5			E	+

E->d

E->E+E

E->E +E

Figure 9.39 LR(0) automaton to the grammar of Figure 9.38

9.8.1 Stack duplication

Refer to Figure 9.40, in which we assume the input d+d+d#. The automaton starts in state (a). The steps shift (b), reduce, shift, shift (c) and reduce (d) are problem-free and bring us to state . The last state, however, is inadequate, allowing a reduce and a shift. True to the breadth-first search method and in accordance with step 1 above, the stack is now duplicated and the top of one of the copies is reduced (e1) while the other one is left available for a subsequent shift (e2). Note that no further reduction is possible and that both stacks now have a different top state. Both states allow a shift and then another (f1, f2) and then a reduce (g1, g2). Now both stacks carry an inadequate state on top and need to be duplicated, after which operation one of the copies undergoes a reduction (h1.1, h1.2, h2.1, h2.2). It now turns out that the stack in h2.1 again features an inadequate state after the reduction; it will again have to be duplicated and have one copy reduced. This gives the stack in h2.1a. Now all possible reductions have been done and it is time for a shift again. Only state allows a shift on #, so the other stacks are discarded and we are left with i1.1 and i2.1a. Both require a reduction, yielding j1.1 and j2.1a, which are accepting states. The parser stops and has found two parsings.

In order to save space and to avoid cluttering up the pictures, we have not shown the partial parse trees that resulted from the various reductions that have taken place. If we had done so, we would have found the two S’s in j.1.1 and j.2.1a holding the parse trees of Figure 9.41.

9.8.2 Combining equal states

Examining Figure 9.40 f and g, we see that once both stacks have the same state on top, further actions on both stacks will be identical, and the idea suggests itself to combine the two stacks to avoid duplicate work. This approach is depicted in Figure 9.42(f) and (g) (Figure 9.42(a) to (e) are identical to those of Figure 9.40 and are not shown). That this is, however, not entirely without problems becomes evident as soon as we need to do a reduce that spans the merge point. This happens in (g), which also features an inadequate state. Now a number of things happen. First, since the state is inadequate, the whole set of combined stacks connected to it are duplicated. One copy (h3) is left for the shift, the other is subjected to the reduce. This reduce, however, spans the merge

224				Deterministic bottom-up parsing			[Ch. 9
a						d+d+d#	shift
b	d					+d+d#	reduce, shift, shift
c	E +		d			+d#	reduce
d	E + E					+d#	duplicate to e1 and
							e2; reduce e1
e1		E				+d#	shift, shift, to f1
e2	E +		E			+d#	shift, shift, to f2
f1		E		+ d		#	reduce to g1
f2	E +		E + d			#	reduce to g2
g1		E		+ E		#	duplicate to h1.1 and
							h1.2; reduce h1.1
g2	E + E + E					#	duplicate to h2.1 and
							h2.2; reduce h2.1
h1.1			E			#	shift to i1.1
h1.2		E		+ E		#	discard
h2.1	E +			E		#	reduce again, to h2.1a
h2.2	E +		E + E			#	discard
h2.1a		E				#	shift to i2.1a
i1.1			E		#		reduce to j1.1
i2.1a		E			#		reduce to j2.1a
j1.1				S			accept
j2.1a		S					accept

Figure 9.40	Sequence of stack configurations while parsing d+d+d#
			S			S
		E	#		E	#
	E	+	E	E	+	E
E	+	E	d	d	E	+ E
d		d			d	d

Figure 9.41 Parse trees in the accepting states of Figure 9.40

point (state ) and extends up both stacks, comprising a different left-most E in both branches. To perform it properly, the stack combination is undone and the reduce is applied to both stacks (h1, h2). The reduce in (h2) results again in state , which necessitates another copy operation (h2.1, h2.2) and a reduce on one of the copies (h2.1).

Now the smoke has cleared and we have obtained five stacks (h1, h2.1, h2.2 and a double h3) having four tops, two of which (h1 and h2.1) carry the state , while the other two (h2.2 and h3) carry a . These can be combined into two bundles (h’ and h"). Next the shift of # obliterates all stacks with top state (i). State , which is now on

Sec. 9.8]

f

g

g’

g"

g’.1

g’.2

h1

h2

h3

h2.1

h2.2

h’

h"

i

i’

i"

j1

j2

				Tomita’s parser		225
	E		+ d		#	reduce to g
E +		E +
	E		+ E		# duplicate to g’, g"
E +		E +
	E		+ E		#	for reduce; undo
E +		E +				combination: g’.1, g’.2
	E		+ E		#	for shift: h3
E +		E +
	E		+ E		#	reduce to h.1
E +		E + E			#	reduce to h.2
			E		#	shift
E +			E		#	reduce again, h2.1, h2.2
	E		+ E		#	shift
E +		E +
	E				#	shift
E +			E		#	shift
			E		#	shift to i
	E
	E		+
E +		E + E			#	discard
E +			E
			E	#		for reduce; undo
	E					combination, i’, i"
			E	#		reduce to j1
	E			#		reduce to j2
			S			accept
	S					accept

Figure 9.42 Stack configurations with equal-state combination

226

Deterministic bottom-up parsing

[Ch. 9

top, induces a reduce spanning a merge point, the combined stack is split and the reduce is applied to both stacks, resulting in the two parsings for d+d+d# (j1, j2).

Although in this example the stack combinations are undone almost as fast as they are performed, stack combination greatly contributes to the parsers efficiency in the general case. It is essential in preventing exponential growth wherever possible. Note, however, that, even though the state in i is preceded by E in all branches, we cannot combine these E’s since they differ in the partial parse trees attached to them.

9.8.3 Combining equal stack prefixes

When step 1 above calls for the stack to be copied, there is actually no need to copy the entire stack; just copying the top states suffices. When we duplicate the stack of Figure 9.40(d), we have one forked stack for (e):

e’	E + E	+d#

Now the reduce is applied to one top state and only so much of the stack is copied as is subject to the reduce:

e		E		+d#	shift
		E + E			shift

In our example almost the entire stack gets copied, but if the stack is somewhat larger, considerable savings can result.

Note that the title of this section is in fact incorrect: in practice no equal stack prefixes are combined, they are never created in the first place. The pseudo-need for combination arises from our wish to explain first the simpler but impractical form of the algorithm in Section 9.8. A better name for the technique would be “common stack prefix preservation”.

Both optimizations can combine to produce shuntyard-like stack constellations

like the one in Figure 9.43; here Tomita’s notation is used, in which

represents a

state and a symbol.

The reader may verify that the constellation represents seven

stacks.

Figure 9.43 Stack constellation with combined heads and tails, in Tomita’s notation

9.8.4 Discussion

We have explained Tomita’s parser using an LR(0) table; in his book Tomita uses an SLR(1) table. In fact the method will work with any bottom-up table or even with no table at all. The weaker the table, the more non-determinism will have to be resolved by breadth-first search, and for the weakest of all tables, the absent table, the method

Sec. 9.8]

Tomita’s parser

227

degenerates into full breadth-first search. Since the latter is involved in principle in all variants of the method, the time requirements are in theory exponential; in practice they are very modest, generally linear or slightly more than linear and almost always less than those of Earley’s parser or of the CYK parser, except for very ambiguous grammars.

9.9 NON-CANONICAL PARSERS

All parsers treated so far in this chapter are “canonical parsers”, which means that they identify the productions in reverse right-most order. A “non-canonical parser” identifies the productions in arbitrary order, or rather in an unrestricted order. Removing the restriction on the identification order of the productions makes the parsing method stronger, as can be expected. Realistic examples are too complicated to be shown here (see Tai [LR 1979] for some), but the following example will demonstrate the principle.

SS -> P Q | R S

P -> a

Q -> b c

R -> a

S -> b d

Figure 9.44 A short grammar for non-canonical parsing

The grammar of Figure 9.44 produces two sentences, abc and abd. Suppose the input is abc. The a can be a P or an R; for both, the look-ahead is a b, so an LR(1) parser cannot decide whether to reduce to P or to R and the grammar is not LR(1). Suppose, however, that we leave the undecidable undecided and search on for another reducible part (called a phrase in non-canonical parsing to distinguish it from the “handle”). Then we find the tokens bc, which can clearly be reduced to Q. Now, this Q provides the decisive look-ahead for the reduction of the a. Since P can be followed by a Q and R cannot, reduction to P is indicated based on look-ahead Q; the grammar is NCLR(1) (Non-Canonical LR(1)). We see that in non-canonical parsers the look-ahead sets contain non-terminals as well as terminals.

There are disadvantages too. After each reduce, one has to rescan possibly large parts of the stack. This may jeopardize the linear time requirement, although with some dexterity the problem can often be avoided. A second problem is that rules are recognized in essentially arbitrary order which makes it difficult to attach semantics to them. A third point is that although non-canonical parsers are more powerful than canonical ones, they are only marginally so: most grammars that are not LR(1) are not NCLR(1) either.

Overall the advantages do not seem to outweigh the disadvantages and noncanonical parsers are not used often. See, however, Salomon and Cormack [LR 1989].

Non-canonical precedence parsing has been described by Colmerauer [Precedence 1970].

228

Deterministic bottom-up parsing

[Ch. 9

9.10 LR(k) AS AN AMBIGUITY TEST

It is often important to be sure that a grammar is not ambiguous, but unfortunately it can be proved that there cannot be an algorithm that can, for every CF grammar, decide whether it is ambiguous or unambiguous. This is comparable to the situation described in 3.5.2, where the fundamental impossibility of a recognizer for Type 0 grammars was discussed. (See Hopcroft and Ullman [Books 1979, p. 200]). The most effective ambiguity test for a CF grammar we have at present is the construction of the corresponding LR(k) automaton, but it is of course not a perfect test: if the construction succeeds, the grammar is guaranteed to be unambiguous; if it fails, in principle nothing is known. In practice, however, the reported conflicts will often point to genuine ambiguities. Theoretically, the construction of an LR-regular parser (see 9.7.6) is an even stronger test, but the choice of the look-ahead automaton is problematic.

10

Error handling

Until now, we have discussed parsing techniques while largely ignoring what happens when the input contains errors. In practice, however, the input often contains errors, the most common being typing errors and misconceptions, but we could also be dealing with a grammar that only roughly, not precisely, describes the input, for instance in pattern matching. So, the question arises how to deal with errors. A considerable amount of research has been done on this subject, far too much to discuss in one chapter. We will therefore limit our discussion to some of the more well-known error handling methods, and not pretend to cover the field; see Section 13.11 for more in-depth information.

10.1 DETECTION VERSUS RECOVERY VERSUS CORRECTION

Usually, the least that is required of a parser is that it detects the occurrence of one or more errors in the input, that is, we require error detection. The least informative version of this is that the parser announces: “input contains syntax error(s)”. We say that the input contains a syntax error when the input is not a sentence of the language described by the grammar. All parsers discussed in the previous chapters (except operator-precedence) are capable of detecting this situation without extensive modification. However, there are few circumstances in which this behaviour is acceptable: when we have just typed a long sentence, or a complete computer program, and the parser only tells us that there is a syntax error somewhere, we will not be pleased at all, not only about the syntax error, but also about the quality of the parser or lack thereof.

The question as to where the error occurs is much more difficult to answer; in fact it is almost impossible. Although some parsers have the correct-prefix property, which means that they detect an error at the first symbol in the input that results in a prefix that cannot start a sentence of the language, we cannot be sure that this indeed is the place in which the error occurs. It could very well be that there is an error somewhere before this symbol but that this is not a syntax error at that point. There is a difference in the perception of an error between the parser and the user. In the rest of this chapter, when we talk about errors, we mean syntax errors, as detected by the parser.

So, what happens when input containing errors is offered to a parser with a good error detection capability? The parser might say: “Look, there is a syntax error at position so-and-so in the input, so I give up”. For some applications, especially highly

230

Error handling

[Ch. 10

interactive ones, this may be satisfactory. For many, though, it is not: often, one would like to know about all syntax errors in the input, not just about the first one. If the parser is to detect further syntax errors in the input, it must be able to continue parsing (or at least recognizing) after the first error. It is probably not good enough to just throw away the offending symbol and continue. Somehow, the internal state of the parser must be adapted so that the parser can process the rest of the input. This adaptation of the internal state is called error recovery.

The purpose of error recovery can be summarized as follows:

an attempt must be made to detect all syntax errors in the input;

equally important, an attempt must be made to avoid spurious error messages. These are messages about errors that are not real errors in the input, but result from the continuation of the parser after an error with improper adaptation of its internal state.

Usually, a parser with an error recovery method can no longer deliver a parse tree

if the input contains errors. This is sometimes the cause of considerable trouble. In the presence of errors, the adaptation of the internal state can cause semantic actions associated with grammar rules to be executed in an order that is impossible for syntactically correct input, which sometimes leads to unexpected results. A simple solution to this problem is to ignore semantic actions as soon as a syntax error is detected, but this is not optimal and may not be acceptable. A better option is the use of a particular kind of error recovery method, an error correction method.

Error correction methods transform the input into syntactically correct input, usually by deleting, inserting, or changing symbols. It should be stressed that error correction methods cannot always change the input into the input actually intended by the user, nor do they pretend that they can. Therefore, some authors prefer to call these methods error repair methods rather than error correction methods. The main advantage of error correction over other types of error recovery is that the parser still can produce a parse tree and that the semantic actions associated with the grammar rules are executed in an order that could also occur for some syntactically correct input. In fact, the actions only see syntactically correct input, sometimes produced by the user and sometimes by the error corrector.

In summary, error detection, error recovery, and error correction require increasing levels of heuristics. Error detection itself requires no heuristics. A parser detects an error, or it does not. Determining the place where the error occurs may require heuristics, however. Error recovery requires heuristics to adapt the internal parser state so that it can continue, and error correction requires heuristics to repair the input.

10.2 PARSING TECHNIQUES AND ERROR DETECTION

Let us first examine how good the parsing techniques discussed in this book are at detecting an error. We will see that some parsing techniques have the correct-prefix property while other parsing techniques only detect that the input contains an error but give no indication where the error occurs.

10.2.1 Error detection in non-directional parsing methods

In Section 4.1 we saw that Unger’s parsing method tries to find a partition of the input sentence that matches one of the right-hand sides of the start symbol. The only thing that we can be sure of in the case of one or more syntax errors is, that we will find no