1. Chapter 1 Lex and Yacc

   1. The Simplest Lex Program

   2. Recognizing Words with Lex

      1. Symbol Tables

   3. Grammars

      1. Parser-Lexer Communication

   4. The Parts of Speech Lexer

      1. A Yacc Parser
      2. The Rules Section

   5. Running Lex and Yacc

   6. Lex vs. Hand-written Lexers

   7. Exercises

2. Chapter 2 Using Lex

   1. Regular Expressions

      1. Examples of Regular Expressions

   2. A Word Counting Program

   3. Parsing a Command Line

      1. Start States

   4. A C Source Code Analyzer

   5. Summary

   6. Exercises

3. Chapter 3 Using Yacc

   1. Grammars

      1. Recursive Rules

   2. Shift/Reduce Parsing

      1. What Yacc Cannot Parse

   3. A Yacc Parser

      1. The Definition Section
      2. The Rules Section
      3. Symbol Values and Actions

   4. The Lexer

      1. Compiling and Running a Simple Parser

   5. Arithmetic Expressions and Ambiguity

      1. When Not to Use Precedence Rules

   6. Variables and Typed Tokens

      1. Symbol Values and %union

   7. Symbol Tables

   8. Functions and Reserved Words

      1. Reserved Words in the Symbol Table
      2. Interchangeable Function and Variable Names

   9. Building Parsers with Make

   10. Summary

   11. Exercises

4. Chapter 4 A Menu Generation Language

   1. Overview of the MGL

   2. Developing the MGL

   3. Building the MGL

      1. Initialization

   4. Screen Processing

   5. Termination

   6. Sample MGL Code

   7. Exercises

5. Chapter 5 Parsing SQL

   1. A Quick Overview of SQL

      1. Relational Data Bases
      2. Manipulating Relations

   2. Three Ways to Use SQL

   3. The Syntax Checker

      1. The Lexer
      2. Error and Main Routines

   4. The Parser

      1. Definitions
      2. Top Level Rules
      3. The Schema Sublanguage
         1. Base Tables
         2. View Definition
         3. Privilege Definitions
      4. The Module Sublanguage
         1. Cursor Definitions
      5. The Manipulation Sublanguage
         1. Simple Statements
         2. FETCH Statements
         3. INSERT Statements
         4. DELETE Statements
         5. UPDATE Statements
         6. Scalar Expressions
         7. SELECT Statements
         8. Table Expressions
         9. Search Conditions
      6. Odds and Ends
      7. Using the Syntax Checker
      8. Embedded SQL
         1. Changes to the Lexer
         2. Changes to the Parser
         3. Auxiliary Routines
         4. Using the Preprocessor
      9. Exercises

6. Chapter 6 A Reference for Lex Specifications

   1. Structure of a Lex Specification

      1. Definition Section
      2. Rules Section
      3. User Subroutines

   2. BEGIN

      1. Bugs
         1. Ambiguous Lookahead
      2. AT&T Lex
         1. Flex
      3. Character Translations
      4. Context Sensitivity
         1. Left Context
         2. Right Context
      5. Definitions (Substitutions)

   3. ECHO

      1. Include Operations (Logical Nesting of Files)
         1. File Chaining with yywrap()
         2. File Nesting
         3. AT&T Lex
         4. Flex
         5. MKS Lex
         6. Abraxas Pclex
         7. POSIX Lex

   4. Input from Strings

      1. AT&T Lex
      2. Flex
      3. Abraxas Pclex
      4. MKS Lex
      5. POSIX Lex
      6. input()

   5. Internal Tables (%N Declarations)

      1. lex Library
         1. main()
         2. Other Library Routines

   6. Line Numbers and yylineno

      1. Literal Block

   7. Multiple Lexers in One Program

      1. Combined Lexers
      2. Multiple Lexers
         1. Using the p Flag
         2. Faking It

   8. output()

   9. Portability of Lex Lexers

      1. Porting Lex Specifications
      2. Porting Generated C Lexers
         1. Libraries
         2. Buffer Sizes
         3. Character Sets

   10. Regular Expression Syntax

       1. Metacharacters
       2. POSIX Extensions

   11. REJECT

   12. Returning Values from yylex()

       1. Start States

   13. unput()

   14. yyinput(), yyoutput(), yyunput()

   15. yyleng

   16. yyless()

   17. yylex()

       1. User Code in yylex()

   18. yymore()

   19. yytext

       1. Enlarging yytext
       2. AT&T and MKS Lex
          1. Flex
          2. Pclex

   20. yywrap()

7. Chapter 7 A Reference for Yacc Grammars

   1. Structure of a Yacc Grammar

      1. Symbols
      2. Definition Section
      3. Rules Section
      4. User Subroutines Section

   2. Actions

      1. Embedded Actions
      2. Symbol Types for Embedded Actions
      3. Obsolescent Feature

   3. Ambiguity and Conflicts

      1. Types of Conflicts
         1. Shift/Reduce Conflicts
         2. Reduce/Reduce Conflicts

   4. Bugs in Yacc

      1. Real Bugs
         1. Error Handling
         2. Declaring Literal Tokens
      2. Infinite Recursion
      3. Unreal Bugs
         1. Interchanging Precedences
         2. Embedded Actions

   5. End Marker

   6. Error Token and Error Recovery

   7. %ident Declaration

   8. Inherited Attributes ($0)

      1. Symbol Types for Inherited Attributes

   9. Lexical Feedback

   10. Literal Block

   11. Literal Tokens

   12. Portability of Yacc Parsers

       1. Porting Yacc Grammars
       2. Porting Generated C Parsers
          1. Libraries
          2. Character Codes

   13. Precedence, Associativity, and Operator Declarations

       1. Precedence and Associativity
          1. Precedence
          2. Associativity
       2. Operator Declarations
       3. Using Precedence and Associativity to Resolve Conflicts
       4. Typical Uses of Precedence

   14. Recursive Rules

       1. Left and Right Recursion

   15. Rules

   16. Special Characters

   17. Start Declaration

   18. Symbol Values

       1. Declaring Symbol Types
       2. Calculator Example
       3. Explicit Symbol Types

   19. Tokens

       1. Token Numbers
       2. Token Values

   20. %type Declaration

   21. %union Declaration

   22. Variant and Multiple Grammars

       1. Combined Parsers
       2. Multiple Parsers
          1. Using the -p Flag
          2. Faking It
       3. Recursive Parsing
       4. Lexers for Multiple Parsers

   23. y.output Files

   24. Yacc Library

       1. main()
       2. yyerror()

   25. YYABORT

   26. YYACCEPT

   27. YYBACKUP

   28. yyclearin

   29. yydebug and YYDEBUG

   30. YYDEBUG

       1. yydebug

   31. yyerrok

   32. YYERROR

   33. yyerror()

   34. yyparse()

   35. YYRECOVERING()

8. Chapter 8 Yacc Ambiguities and Conflicts

   1. The Pointer Model and Conflicts

      1. Types of Conflicts
      2. Parser States
      3. Contents of y.output
         1. Reduce/Reduce Conflicts
         2. Shift/Reduce Conflicts
      4. Review of Conflicts in y.output

   2. Common Examples of Conflicts

      1. Expression Grammars

   3. IF—THEN—ELSE

      1. Nested List Grammer

   4. How Do I Fix the Conflict?

   5. IF—THEN—ELSE (Shift/Reduce)

      1. Loop Within a Loop (Shift/Reduce)
      2. Expression Precedence (Shift/Reduce)
      3. Limited Lookahead (Shift/Reduce or Reduce/Reduce)
      4. Overlap of Alternatives (Reduce/Reduce)

   6. Summary

   7. Exercises

9. Chapter 9 Error Reporting and Recovery

   1. Error Reporting

      1. Better Lex Error Reports

   2. Error Recovery

      1. Yacc Error Recovery
      2. Where to Put Error Tokens

   3. Compiler Error Recovery

   4. Exercises

1. Appendix AT&T Lex

   1. Error Messages

2. Appendix AT&T Yacc

   1. Options

   2. Error Messages

3. Appendix Berkeley Yacc

   1. Options

   2. Error Messages

      1. Fatal Errors
      2. Regular Errors
      3. Warnings
      4. Informative Messages

4. Appendix GNU Bison

   1. Differences

5. Appendix Flex

   1. Flex Differences

   2. Options

   3. Error Messages

   4. Flex Versions of Lexer Examples

6. Appendix MKS lex and yacc

   1. Differences

   2. New Features

7. Appendix Abraxas lex and yacc

   1. Differences

   2. New Features

8. Appendix POSIX lex and yacc

   1. Options

   2. Differences

9. Appendix MGL Compiler Code

   1. MGL Yacc Source

   2. MGL Lex Source

   3. Supporting C Code

10. Appendix SQL Parser Code

    1. Yacc Parser

    2. Cross-reference

11. Appendix SQL Parser Code

    1. Lex Scanner

    2. Supporting Code

12. Glossary

13. Bibliography

Our look is the result of reader comments, our own experimentation, and feedback from distribution channels. Distinctive covers complement our distinctive approach to technical topics, breathing personality and life into potentially dry subjects. The animal featured on the cover of lex & yacc is a Victoria crowned pigeon, one of the largest members of the pigeon family. Unlike other birds, the crowned pigeon drinks water by immersing its bill and sucking. Incubation of the eggs (generally two) is shared by these monogamous birds, the male warming them by day, the female by night. The Victoria crowned pigeon is light and dark blue with purple markings and a fanlike head crest of lacy, light blue feathers. Though protected by law in its native country of New Guinea, it is nonetheless an easy target for hunters for its plumage and is in danger of extinction. Unix and its attendant programs can be unruly beasts. Nutshell Handbooks(R) help you tame them.

...

Edie Freedman designed this cover and the entire Unix bestiary that appears on other Nutshell Handbooks. The beasts themselves are adapted from 19th-century engravings from the Dover Pictorial Archive. The cover layout was produced with QuarkXPress 3.1 using the ITC Garamond font.

The inside layout was fomatted in sqtroff using ITC Garamond Light and ITC Garamond Book fonts, and was designed by Edie Freeman. The figures were created in Aldus Freehand 3.1 by Chris Reilley.