flex & bison by Levine, John -- Read -- Imperial Library of Trantor

Index

flex & bison

SPECIAL OFFER: Upgrade this ebook with O’Reilly Preface

Scope of This Book Conventions Used in This Book Getting Flex and Bison This Book’s Example Files Using Code Examples Safari® Books Online How to Contact Us Acknowledgments

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 Three 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

Functions Other expressions

Select Statements

Select options and table references SELECT table references

Delete Statement Insert and Replace Statements

Replace statement

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

Buffer sizes Character sets

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

A. SQL Parser Grammar and Cross-Reference Glossary Index About the Author Colophon SPECIAL OFFER: Upgrade this ebook with O’Reilly

← Prev
Back
Next →

← Prev
Back
Next →