Both authors have had a need for programming tools that could help them write compilers and interpreters. They have written this book to assist others with similar needs in using the strangely-named “lex” and “yacc” programming tools provided on most UNIX systems. A working knowledge of the C programming language is assumed. If you are seeking a simple explanation of what lex and yacc can do, you should look somewhere else. This book provides a graded series of case studies and uses the programs for these case studies as a basis for instruction. Readers with access to the UUNET network can obtain these programs by direct file transfer; other readers will need to type them from the listings supplied.
Chapter 1 introduces the concept of lexical analysis. The authors explain that lex reads a specification file containing regular expressions for pattern matching and generates a C or RATFOR routine that performs lexical analysis. This routine reads a stream of characters and matches sequences that identify tokens (such as series of digits that constitute numbers). The lex specifications themselves are written as rules for matching tokens. Each rule has one or more associated C or RATFOR action statements that are performed when a token is matched.
The acronym “yacc” stands for “yet another compiler-compiler.” It converts a context-free grammar into a set of tables for a simple automaton that executes a parsing algorithm. The grammar is described by production rules. A graded series of case studies is provided. The chapter concludes with a summary illustrating how simple lex and yacc programs can be used together to produce a reasonably complex C program; a hand-coded version of an equivalent C program would require a considerable degree of effort.
For me, it all started to make sense in chapter 2, where I got to build a simple adding machine. The lex specification determines how an integer (such as “157”), an operand (such as “+”), and a terminator (carriage return) can be recognized, and it returns corresponding values. The yacc specification declares what should be done (such as add to a running total) with each of these tokens. The lex and yacc outputs are passed to a C compiler, and an adding machine program is produced.
Chapter 3 takes the reader through the development of a calculator that operates in interpretive mode. The authors introduce lex rules for recognizing real numbers (with optional exponents) as well as integers and provide separate yacc specifications for handling each of these and for error conditions. The special lex and yacc capabilities of the make utility are also mentioned.
Chapter 4 illustrates compiler design through the development of a menu generation language and its associated compiler. It introduces lex rules for recognizing keywords such as “title” and “screen” in that language. The yacc grammar indicates how each of these should be handled; a number of support routines in C are used.
In chapter 5, the menu generation language is extended into a screen generation language that can accommodate multiple screens of arbitrary size. The necessary lex rules and yacc grammar extensions are given, but it is left to the reader to further develop the support routines. The authors point out that many fourth-generation languages actually involve compilation to an intermediate language, which is then executed by a run-time module. An intermediate language may be a traditional language such as Pascal or COBOL, or it may be a special-purpose set of related data structures.
Chapters 6 and 7 are mini reference manuals for lex and yacc. Chapter 8 deals with ambiguities and conflicts in yacc grammars; these can arise through recursive definition of arithmetic operations, and some care is necessary in their resolution. Chapter 9 shows how the simple error reporting and recovery mechanisms provided within yacc can be augmented to provide comprehensive user support in a real situation.
The appendices make brief reference to the Flex and Bison equivalents for lex and yacc. These have been developed under the GNU project of the Free Software Foundation and are used on some UNIX systems. The authors mention some of their differences and additional features.
The examples contain some minor errors and omissions, and I had to make slight modifications to some of the code in order for it to work on my (fairly standard) system. I am unaware of any other book that would better suit the needs of someone learning to write compilers or interpreters, however. Those who have frequent occasion to develop programs in these categories will find this work a valuable reference; they may also find that its binding does not last the distance.
