如果你需要分析或处理Linux或Unix中的文本数据，这本有用的书籍就向你讲解了如何使用flex和bison迅速解决问题。《flex与bison》被期待已久，是经典O'Reilly系列书籍《lex & yacc》的续篇。在原书出版以来的近20年中，flex和bison已被证明比原来的Unix工具更可靠、更强大。

《flex与bison》一书涵盖了Linux和Unix程序开发中相同的重要核心功能，以及一些重要的新主题。你会找到适用于新手的修订教程和适用于高级用户的参考资料，以及对每个程序的基本用法的解释，并且运用它们创建简单、独立的应用程序。有了《flex与bison》，你会发现这些灵活的工具提供的广泛用途。

Preface

1. Introducing Flex and Bison

 Lexical Analysis and Parsing

 Regular Expressions and Scanning

Our First Flex Program

Programs in Plain Flex

Putting Flex and Bison Together

The Scanner as Coroutine

Tokens and Values

 Grammars and Parsing

BNF Grammars

Bison's Rule Input Language

Compiling Flex and Bison Programs Together

 Ambiguous Grammars: Not Quite

 Adding a Few More Rules

 Flex and Bison vs. Handwritten Scanners and Parsers

 Exercises

2. Using Flex

 Regular Expressions

Regular Expression Examples

How Flex Handles Ambiguous Patterns

Context-Dependent Tokens

 File I/O in Flex Scanners

 Reading Several Files

 The I/O Structure of a Flex Scanner

Input to a Flex Scanner

Flex Scanner Output

 Start States and Nested Input Files

 Symbol Tables and a Concordance Generator

Managing Symbol Tables

Using a Symbol Table

 C Language Cross-Reference

 Exercises

3. Using Bison

 How a Bison Parser Matches Its Input

 Shift/Reduce Parsing

What Bison's LALR(1) Parser Cannot Parse

 A Bison Parser

 Abstract Syntax Trees

 An Improved Calculator That Creates ASTs

Literal Character Tokens

Building the AST Calculator

 Shift/Reduce Conflicts and Operator Precedence

When Not to Use Precedence Rules

 An Advanced Calculator

Advanced Calculator Parser

Calculator Statement Syntax

Calculator Expression Syntax

Top-Level Calculator Grammar

Basic Parser Error Recovery

The Advanced Calculator Lexer

Reserved Words

Building and Interpreting ASTs

Evaluating Functions in the Calculator

User-Defined Functions

 Using the Advanced Calculator

 Exercises

4. Parsing SQL

 A Quick Overview of SQL

Relational Databases

 Manipulating Relations

 hree Ways to Use SQL

 SQL to RPN

 The Lexer

Scanning SQL Keywords

Scanning Numbers

Scanning Operators and Punctuation

Scanning Functions and Names

Comments and Miscellany

 The Parser

The Top-Level Parsing Rules

SQL Expressions

Select Statements

Delete Statement

Insert and Replace Statements

Update Statement

Create Database

Create Table

User Variables

The Parser Routines

 The Makefile for the SQL Parser

 Exercises

5. A Reference for Flex Specifications

 Structure of a Flex Specification

Definition Section

Rules Section

User Subroutines

 BEGIN

 C++ Scanners

 Context Sensitivity

Left Context

Right Context

 Definitions (Substitutions)

 ECHO

 Input Management

Stdio File Chaining

Input Buffers

Input from Strings

File Nesting

input()

YY_INPUT

 Flex Library

 Interactive and Batch Scanners

 Line Numbers and yylineno

 Literal Block

 Multiple Lexers in One Program

Combined Lexers

Multiple Lexers

 Options When Building a Scanner

 Portability of Flex Lexers

Porting Generated C Lexers

 Reentrant Scanners

Extra Data for Reentrant Scanners

Access to Reentrant Scanner Data

Reentrant Scanners, Nested Files, and Multiple Scanners

Using Reentrant Scanners with Bison

 Regular Expression Syntax

Metacharacters

 REJECT

 Returning Values from yylex()

 Start States

 unput()

 yyinput() yyunput()

 yyleng

 yyless()

 yylex() and YY_DECL

 yymore()

 yyrestart()

 yy_scan_string and yy_scan_buffer

 YY_USER_ACTION

 yywrap()

6. A Reference for Bison Specifications

 Structure of a Bison Grammar

Symbols

Definition Section

Rules Section

User Subroutines Section

 Actions

Embedded Actions

Symbol Types for Embedded Actions

 Ambiguity and Conflicts

Types of Conflicts

Shift/Reduce Conflicts

Reduce/Reduce Conflicts

%expect

GLR Parsers

 Bugs in Bison Programs

Infinite Recursion

Interchanging Precedence

Embedded Actions

 C++ Parsers

 %code Blocks

 End Marker

 Error Token and Error Recovery

%destructor

 Inherited Attributes ($0)

Symbol Types for Inherited Attributes

 %initial-action

 Lexical Feedback

 Literal Block

 Literal Tokens

 Locations

 %parse-param

 Portability of Bison Parsers

Porting Bison Grammars

Porting Generated C Parsers

Libraries

Character Codes

 Precedence and Associativity Declarations

Precedence

Associativity

Precedence Declarations

Using Precedence and Associativity to Resolve Conflicts

Typical Uses of Precedence

 Recursive Rules

Left and Right Recursion

 Rules

 Special Characters

 %start Declaration

 Symbol Values

Declaring Symbol Types

Explicit Symbol Types

 Tokens

Token Numbers

Token Values

%type Declaration

%union Declaration

 Variant and Multiple Grammars

Combined Parsers

 Multiple Parsers

Using %name-prefix or the -p Flag

Lexers for Multiple Parsers

Pure Parsers

 y.output Files

 Bison Library

main()

yyerror()

 YYABORT

 YYACCEPT

 YYBACKUP

 yyclearin

 yydebug and YYDEBUG

YYDEBUG

yydebug

 yyerrok

 YYERROR

 yyerror()

 yyparse()

 YYRECOVERING()

7. Ambiguities and Conflicts

 The Pointer Model and Conflicts

 Kinds of Conflicts

 Parser States

 Contents of name.output

 Reduce/Reduce Conflicts

 Shift/Reduce Conflicts

 Review of Conflicts in name.output

 Common Examples of Conflicts

Expression Grammars

IF/THEN/ELSE

Nested List Grammar

 How Do You Fix the Conflict?

IF/THEN/ELSE (Shift/Reduce)

Loop Within a Loop (Shift/Reduce)

Expression Precedence (Shift/Reduce)

Limited Lookahead (Shift/Reduce or Reduce/Reduce)

Overlap of Alternatives (Reduce/Reduce)

 Summary

 Exercises

8. Error Reporting and Recovery

 Error Reporting

 Locations

Adding Locations to the Parser

Adding Locations to the Lexer

More Sophisticated Locations with Filenames

 Error Recovery

 Bison Error Recovery

Freeing Discarded Symbols

Error Recovery in Interactive Parsers

Where to Put Error Tokens

 Compiler Error Recovery

 Exercises

9. Advanced Flex and Bison

 Pure Scanners and Parsers

Pure Scanners in Flex

Pure Parsers in Bison

Using Pure Scanners and Parsers Together

A Reentrant Calculator

 GLR Parsing

GLR Version of the SQL Parser

 C++ Parsers

A C++ Calculator

C++ Parser Naming

A C++ Parser

Interfacing a Scanner with a C++ Parser

Should You Write Your Parser in C++ ?

 Exercises

Appendix: SQL Parser Grammar and Cross-Reference

Glossary

Index