5.6 Summary

This chapter discusses parser generators, a much-researched and developed area of computer science.

The space occupied by the generated parse tables is considerable, containing thousands of entries. LL(1) tables are smaller than LALR(1), by a ratio of about two-to-one. LR(1) tables are too large to be practical.

Timewise, both LL(1) and LR-family parsers are linear for the average case (in the number of tokens processed).

It is easier to write a grammar for LR-family parsers than for LL(1) parsers since LL requires that there be no left-recursion or common prefixes.

Most language designers produce a LALR(1) grammar to describe their language.

The LR-family grammars can also handle a wider range of language constructs; in fact the language constructs generated by LL(1) grammars are a proper subset of the LR(1) constructs.

For the LR-family the language constructs recognized are:

where << means much smaller and < means smaller.

The drivers for both LL(1) and LR-family parsers are easy to write. Table generation is easier for LL(1) than it is for LR-family parser generators.

Error handling is similar for both LL(1) and LR-family parsers, with LL(1) being somewhat simpler. Error handing in parser generators is still developing, and the Related Reading section contains many references to past and recent work in this area.

Overall, for parser generation the choice is between LALR(1) and LL(1), with the decision often being made based upon the nature of a grammar. If a grammar already exists and it is LL(1), then that is probably the method of choice. If the grammar is still to be written or the prewritten grammar is not LL(1), then the method of choice is probably LALR(1).

Send questions and comments to: Karen Lemone