Flex & Bison (1ST)

Flex & Bison (1ST)

  • ただいまウェブストアではご注文を受け付けておりません。 ⇒古書を探す
  • 製本 Paperback:紙装版/ペーパーバック版/ページ数 271 p.
  • 言語 ENG,ENG
  • 商品コード 9780596155971
  • DDC分類 005

Full Description


If you need to parse or process text data in Linux or Unix, this classic book explains how to use flex and bison to solve your problems quickly - whether you're interpreting code, configuration files, or any other structured format. "Flex and Bison" is the long-awaited sequel to the classic O'Reilly book, "Lex and Yacc". In the nearly two decades since that book was published, the "Flex and Bison" utilities have proven to be more reliable and more powerful than the original Unix tools. This book covers the same core functionality vital to Linux and Unix program development, along with several important new topics. This thoroughly updated edition will help you: address syntax crunching that regular expressions tools can't handle; build compilers and interpreters, and handle a wide range of text processing functions; learn key programming techniques, including syntax trees and symbol tables; implement a full SQL grammar, with complete sample code; and, use new features such as pure (reentrant) lexers and parsers, powerful GLR parsers, and interfaces to C++.This book includes revised tutorial sections for novice users and reference sections for advanced users, with chapters that explain each utility's basic usage and simple, stand-alone applications. Dive into "Flex and Bison" and discover the wide range of uses these flexible tools provide.

Table of Contents

Preface                                            xiii
Introducing Flex and Bison 1 (18)
Lexical Analysis and Parsing 1 (1)
Regular Expressions and Scanning 2 (7)
Our First Flex Program 2 (2)
Programs in Plain Flex 4 (1)
Putting Flex and Bison Together 5 (1)
The Scanner as Coroutine 6 (1)
Tokens and Values 7 (2)
Grammars and Parsing 9 (5)
BNF Grammars 10 (1)
Bison's Rule Input Language 11 (2)
Compiling Flex and Bison Program 13 (1)
Together
Ambiguous Grammars: Not Quite 14 (1)
Adding a Few More Rules 15 (1)
Flex and Bison vs. Handwritten Scanners 16 (1)
and Parsers
Exercises 17 (2)
Using Flex 19 (28)
Regular Expression 19 (4)
Regular Expression Examples 21 (1)
How Flex Handles Ambiguous Patterns 22 (1)
Context-Dependent Tokens 22 (1)
File I/O in Flex Scanners 23 (1)
Reading Several Files 24 (1)
The I/O Structure of a Flex Scanner 25 (3)
Input on a Flex Scanner 26 (1)
Flex Scanner Output 27 (1)
Start States and Nested Input Files 28 (4)
Symbol Tables and Concordance Generator 32 (6)
Managing Symbol Tables 32 (3)
Using a Symbol Table 35 (3)
C Language Cross-Reference 38 (7)
Exercises 45 (2)
Using Bison 47 (34)
How a Bison Parser Matches Its Input 47 (1)
Shift/Reduce Parsing 48 (3)
What Bison's LALR(1) Parser Cannot Parse 50 (1)
A Bison Parser 51 (1)
Abstract Syntax Trees 51 (1)
An Improved Calculator that Creates ASTs 52 (5)
Literal Character Tokens 54 (3)
Building the AST Calculator 57 (1)
Shit/Reduce Conflicts and Operator 57 (4)
Precedence
When Not to Use Precedence Rules 60 (1)
An Advanced Calculator 61 (18)
Advanced Statement Syntax 64 (1)
Calculator Statement Syntax 65 (1)
Calculator Expression Syntax 66 (1)
Top-Level Calculator Grammar 67 (1)
Basic Parser Error Recovery 67 (1)
The Advanced Calculator Lexer 68 (1)
Reserved Words 69 (1)
Building and Interpeting ASTs 70 (6)
Evaluating Funcations in the Calculator 76 (1)
User-Defined Functions 76 (3)
Using the Advacned Calculator 79 (1)
Exercises 79 (2)
Parsing SQL 81 (38)
A Quick Overview of SQL 81 (2)
Relational Databases 82 (1)
Manipulating Relations 83 (1)
Three Ways to Use SQL 83 (1)
SQL to RPN 84 (1)
The Lexer 85 (9)
Scanning SQL Keywords 86 (4)
Scanning Numbers 90 (1)
Scanning Operators and Punctuation 91 (1)
Scanning Functions and Names 92 (1)
Comments and Miscelany 93 (1)
The Parser 94 (22)
The Top-Level Parsing Rules 96 (1)
SQL Expressions 96 (5)
Select Statements 101 (5)
Delete Statement 106 (1)
Insert and Replace Statments 107 (3)
Update Statement 110 (1)
Create Database 110 (1)
Create Table 111 (3)
User Variables 114 (1)
The Parser Routines 115 (1)
The Makefile for the SQL Parser 116 (1)
Exercises 117 (2)
A Reference for Flex Specifications 119 (22)
Structure of a Flex Specification 119 (2)
Definition Section 119 (1)
Rules Section 120 (1)
User Subroutines 120 (1)
BEGIN 121 (1)
C++ Scanners 121 (1)
Context Sensitivity 121 (1)
Left Context 121 (1)
Right Context 122 (1)
Definitions (Substitutions) 122 (1)
ECHO 123 (1)
Input Management 123 (2)
Stdio File Chaining 123 (1)
Input Buffers 123 (1)
Input from Strings 124 (1)
File Nesting 124 (1)
input() 124 (1)
YY_INPUT 125 (1)
Flex Library 125 (1)
Interactive and Batch Scanners 126 (1)
Line Numbers and yylineno 126 (1)
Literal Block 127 (1)
Multiple Lexers in One Program 127 (1)
Combined Lexers 127 (1)
Multiple Lexers 128 (1)
Options When Building a Scanner 128 (1)
Portability of Flex Lexers 129 (1)
Porting Generated C Lexers 129 (1)
Reentrant Scanners 130 (2)
Extra Data for Reentrant Scanners 130 (1)
Access to Reentrant Scanner Data 131 (1)
Reentrant Scanners, Nested Files, and 131 (1)
Multiple Scanners
Using Reentrant Scanners with Bison 132 (1)
Regular Expression Syntax 132 (3)
Metacharacters 132 (3)
Reject 135 (1)
Returning Values from yylex() 135 (1)
Start States 135 (1)
unput() 135 (2)
yyinputO yyunput() 137 (1)
yyleng 137 (1)
yyless() 137 (1)
yylexO and YY_DECL 138 (1)
yymore() 138 (1)
yyrestart() 139 (1)
yy_scan_string and yy_scan_buffer 139 (1)
YY_USER_ACTION 139 (1)
yywrap() 139 (2)
A Reference for Bison Specifications 141 (32)
Structure of a Bison Grammar 141 (1)
Symbols 141 (1)
Definition Section 142 (1)
Rules Section 142 (1)
User Subroutines Section 142 (1)
Actions 142 (2)
Embedded Actions 143 (1)
Symbol Types for Embedded Actions 144 (1)
Ambiguity and Conflicts 144 (2)
Types of Conflicts 144 (1)
Shift/Reduce Conflicts 144 (1)
Reduce/Reduce Conflcits 145 (1)
% expect 145 (1)
GLR Parsers 145 (1)
Bugs in Bison Programs 146 (1)
Infinite Recursion 146 (1)
Interchanging Precedence 146 (1)
Embedded Actions 146 (1)
C++ Parsers 147 (1)
%code Blocks 147 (1)
End Marker 147 (1)
Error Token and Error Recovery 147 (1)
% destructor 148 (1)
Inherited Attributes ($0) 148 (1)
Symbol Types for Inherited Attributes 149 (1)
% initial-action 149 (1)
Lexical Feedback 150 (1)
Literal Block 151 (1)
Literal Tokens 151 (1)
Locations 152 (1)
%parse-param 152 (1)
Portability of Bison Parsers 153 (1)
Porting Bison Grammars 153 (1)
Porting Generated C Parsers 153 (1)
Libraries 153 (1)
Character Codes 153 (1)
Precedence and Associativity Declarations 154 (1)
Precedence 154 (1)
Associativity 154 (1)
Precedence Declarations 154 (1)
Using Precedence and Associativity to 155 (1)
Resolve Conflicts
Typical Uses of Precedence 155 (1)
Recursive Rules 155 (2)
Left and Right Recursion 156 (1)
Rules 157 (1)
Special Characters 158 (1)
% start Declaration 159 (1)
Symbol Values 160 (1)
Declaring Symbol Types 160 (1)
Explicit Symbol Types 160 (1)
Tokens 161 (2)
Token Numbers 161 (1)
Token Values 161 (1)
%type Declaration 162 (1)
%union Declaration 163 (1)
Variant and Multiple Grammars 163 (2)
Combined Parsers 165 (1)
Multiple Parsers 165 (1)
Using % name-prefix or the -p Flag 165 (1)
Lexers for Multiple Parsers 165 (1)
Pure Parsers 165 (1)
y.output Files 166 (1)
Bison Library 167 (1)
main() 167 (1)
yyerrorO 167 (1)
YYABORT 168 (1)
YYACCEPT 168 (1)
YYBACKUP 168 (1)
yyclearin 169 (1)
yydebug and YYDEBUG 169 (1)
YYDEBUG 169 (1)
yydebug 169 (1)
yyerrok 169 (1)
YYERROR 170 (1)
yyerrorO 170 (1)
yyparseO 171 (1)
YYRECOVERING0 171 (2)
Ambiguities and Conflicts 173 (24)
The Pointer Model and Conflicts 173 (2)
Kinds of Conflicts 175 (1)
Parser States 176 (2)
Contents of name.output 178 (1)
Reduce/Reduce Conflicts 178 (2)
Shift/Reduce Conflicts 180 (2)
Review of Conflicts in name.output 182 (1)
Common Examples of Conflicts 183 (4)
Expression Grammars 183 (2)
IF/THEN/ELSE 185 (1)
Nested List Grammar 186 (1)
How Do You Fix the Conflict? 187 (7)
IF/THEN/ELSE (Shift/Reduce) 188 (2)
Loop Within a Loop (Shift/Reduce) 190 (1)
Expression Precedence (Shift/Reduce) 191 (1)
Limited Lookahead (Shift/Reduce or 191 (1)
Reduce/Reduce)
Overlap of Alternatives (Reduce/Reduce) 192 (2)
Summary 194 (1)
Exercises 194 (3)
Error Reporting and Recovery 197 (12)
Error Reporting 197 (2)
Locations 199 (5)
Adding Locations to the Parser 200 (1)
Adding Locations to the Lexer 201 (1)
More Sophisticated Locations with 202 (2)
Filenames
Error Recovery 204 (1)
Bison Error Recovery 205 (3)
Freeing Discarded Symbols 206 (1)
Error Recovery in Interactive Parsers 206 (1)
Where to Put Error Tokens 207 (1)
Compiler Error Recovery 208 (1)
Exercises 208 (1)
Advanced Flex and Bison 209 (34)
Pure Scanners and Parsers 209 (21)
Pure Scanners in Flex 210 (2)
Pure Parsers in Bison 212 (1)
Using Pure Scanners and Parsers Together 213 (1)
A Reentrant Calculator 214 (16)
GLR Parsing 230 (4)
GLR Version of the SQL Parser 231 (3)
C++ Parsers 234 (7)
A C++ Calculator 235 (1)
C++ Parser Naming 235 (1)
A C++ Parser 236 (3)
Interfacing a Scanner with a C++ Parser 239 (2)
Should You Write Your Parser in C++ ? 241 (1)
Exercises 241 (2)
Appendix: SQL Parser Grammar and Cross-Reference 243 (16)
Glossary 259 (4)
Index 263