Parsing Theory

In this chapter we shall consider a general method for deriving deterministic right parsers for context-free grammars. The method will be called “LR(k) parsing”. The acronym “LR(k)” refers to the most general deterministic parsing method in which the input string is parsed (1) in a single Left-to-right scan, (2) producing a Right parse, and (3) using lookahead of length k.

This chapter is devoted to the practical issues involved in the construction and use of deterministic LR(1) parsers. We shall show how the practical versions of LR (1) parsers, most notably the LALR (1) parsers, can be constructed efficiently, and we shall present methods for encoding LR(1) parsers as efficient RAM programs. Two versions of RAM program implementation are considered: in the first implementation the parsing program is table-driven, that is, the rules of the parser are encoded in a two-dimensional array which is simulated by a program body; in the other implementation the tabular information is further transformed into a set of program statements.

In this chapter we shall generalize the notion of strong LL(k) parsing presented in Chapter 5 and consider a method for deterministic left parsing that applies to a slightly wider class of context-free grammars than does the strong LL(k) parsing method. This method will be called “canonical LL(k) parsing”. As in strong LL(k) parsing, the acronym “LL(k)” means that the input string is parsed (1) in a single Left-to-right scan, (2) producing a Left parse, and (3) using lookahead of length k.

In the previous chapters we have seen that the various parsers discussed, at least whenever they are deterministic, detect an error in any nonsentence. This means, that on any nonsentence there is a computation ending with an error configuration. For practical parsers, mere error detection is not enough; the parser should also emit a meaningful error message and recover from the error. A recovery means that the error configuration is transformed into a non-error configuration at which normal parsing can be resumed. Moreover, the transformation should be done so that as few input symbols as possible will be discarded. The goal of the error recovery is to maximize the amount of input text that can be handled in normal parsing mode and thus to detect as many errors as possible. On the other hand, the error recovery should be designed so that as few extraneous messages as possible will be emitted: only actual errors should be reported. Unfortunately, these goals are often contradictory: being able to detect and report many errors will often cause many extraneous error messages, and few extraneous error messages may imply undetected errors. Also it should be noted that a formal analysis of the quality of an error recovery method is difficult, if not impossible, because of the obvious ambiguity in the meaning of the phrase “actual error”.

In the preceding chapters we have studied in detail the major methods of deterministic context-free parsing: strong LL(k) parsing (Chapter 5), simple precedence parsing (Chapter 5), canonical LR(k) parsing, LALR(k) parsing, and SLR(k) parsing (Chapters 6 and 7), and canonical LL(k) parsing (Chapter 8). Each of these methods induces a class of grammars that are “parsable” using that method, that is, a class of grammars for which a deterministic parser employing that method can be constructed. For example, the LL(k) grammars constitute the class of grammars parsable by the LL(k) parsing method. By definition, a context-free grammar is an LL(k) grammar if and only if its canonical LL(k) parser is deterministic.