Lex & Yacc

lex & yacc shows C programmers how to use two UNIX utilities, lex and yacc, to solve problems in program development.

Lex and yacc were designed as tools to help programmers writing compilers and interpreters, but they have a wide range of applications. Lex, so called because it generates a lexical analyzer, reads a stream of bytes and groups them into tokens. Yacc (which stands for Yet Another Compiler-Compiler) is used to codify the grammar of a language and generates a parser. The parser examines the input tokens and groups them into syntactical units. The value of the tokens can be processed by action routines written in C.

The first part of the book provides a basic understanding of compilers and interpreters. It takes the programmer through a series of extended tutorial examples of increasing complexity.

The second part of the book is devoted to providing detailed technical information necessary for advanced uses of lex and yacc. These chapters discuss the lex and yacc options, ambiguities in a yacc grammar, and debugging.

Appendices cover Flex and GNU Bison, versions of lex and yacc available from the Free Software Foundation. A glossary and index are also provided.

1. Introduction to Lex and Yacc
• Compilers and Interpreters
• Lexical Analysis
• Regular Expressions
• Actions
• A Parser
• The Elements of a Grammar
• A Yacc Grammar
• Summary of Lexical and Parsing Routines
• Abstract Machines
• Finite Automata
• Pushdown Automata
2. The Mechanics of Lex and Yacc
• Using Lex
• Writing a Lex Specification
• Creating Simple Input Scanners
• Using the Full Specification
• Writing a Lexical Analyzer
• Using Yacc
• Writing a Yacc Specification
• A Specification for a Simple Adding Machine
• Writing the Lexical Analyzer
• Creating the Parser
3. Building a Calculator
• The Calculator as Interpreter
• Writing Regular Expressions for Tokens
• Defining Substitution Strings
• Defining the Token Types
• Completeing the Lex Specification
• Creating the Yacc Specification
• Compilation
• Showing the Results
• Lex and Yacc in Makefiles
4. The MGL
• Overview of the MGL
• Developing the MGL
• Building the MGL
• Initalization
• Screen Processing
• Termination
• Sample MGL Code
5. The SQL
• Designing the SQL
• Describing the SQL
• Using Lex to Implement SGL
• Using Yacc to Implement SQL
• Intermediate Langauges
• Using No Intermediate Language
• Using an Intermediate Language
• Using Nontraditional Languages
6. A Reference for Lex Specifications
• Declarations and Definitions Section
• Definitions
• Start States
• Changing Internal tables
• Character Translations
• Rules Section
• UNIX Regular Expression Syntax
• Variables
• Macros
• Routines
• Code Section
• Including Code
7. A Reference for Yacc Specifications
• Declarations Section
• C Declarations
• Union Declarations
• Token Type Declarations
• Nonterminal Type Declarations
• Start Declarations
• Precedence
• Rules Section
• Error Token
• Actions
• Code Section
• main Routine
• yylex Routine
• yyerror Routine
8. Ambiguities and Conflicts in Yacc Grammars
• The Pointer Model and Conflicts
• Types of Conflicts
• State and Conflicts in y.output
• Review of Conflicts in y.output
• Real Examples
9. Error Reporting and Recovery
• Error Reporting
• Error Recovery
• Yacc Error Recovery
• Compiler Error Recovery

1. Lex Options and Error Messages
• Options
• Error Messages
2. Yacc Options and Error Messages
• Options
• Error Messages
3. GNU Bison
4. GNU Flex
5. MGL Compiler Code
• MGL Supporting Code
• MGL Yacc Grammar
• MGL Lex Specification

A not very good introduction to Yacc and Lex.