flex & bison

Table of Contents......Page 7
Scope of This Book......Page 15
Conventions Used in This Book......Page 16
This Book’s Example Files......Page 17
How to Contact Us......Page 18
Acknowledgments......Page 19
Lexical Analysis and Parsing......Page 21
Our First Flex Program......Page 22
Programs in Plain Flex......Page 24
Putting Flex and Bison Together......Page 25
The Scanner as Coroutine......Page 26
Tokens and Values......Page 27
Grammars and Parsing......Page 29
BNF Grammars......Page 30
Bison’s Rule Input Language......Page 31
Compiling Flex and Bison Programs Together......Page 33
Ambiguous Grammars: Not Quite......Page 34
Adding a Few More Rules......Page 35
Flex and Bison vs. Handwritten Scanners and Parsers......Page 36
Exercises......Page 37
Regular Expressions......Page 39
Regular Expression Examples......Page 41
Context-Dependent Tokens......Page 42
File I/O in Flex Scanners......Page 43
Reading Several Files......Page 44
The I/O Structure of a Flex Scanner......Page 45
Input to a Flex Scanner......Page 46
Flex Scanner Output......Page 47
Start States and Nested Input Files......Page 48
Managing Symbol Tables......Page 52
Using a Symbol Table......Page 55
C Language Cross-Reference......Page 58
Exercises......Page 65
How a Bison Parser Matches Its Input......Page 67
Shift/Reduce Parsing......Page 68
What Bison’s LALR(1) Parser Cannot Parse......Page 70
Abstract Syntax Trees......Page 71
An Improved Calculator That Creates ASTs......Page 72
Literal Character Tokens......Page 74
Building the AST Calculator......Page 77
Shift/Reduce Conflicts and Operator Precedence......Page 78
When Not to Use Precedence Rules......Page 80
An Advanced Calculator......Page 81
Advanced Calculator Parser......Page 84
Calculator Statement Syntax......Page 85
Calculator Expression Syntax......Page 86
Basic Parser Error Recovery......Page 87
The Advanced Calculator Lexer......Page 88
Reserved Words......Page 89
Building and Interpreting ASTs......Page 90
User-Defined Functions......Page 96
Exercises......Page 99
A Quick Overview of SQL......Page 101
Relational Databases......Page 102
Three Ways to Use SQL......Page 103
SQL to RPN......Page 104
The Lexer......Page 105
Scanning SQL Keywords......Page 106
Scanning Numbers......Page 110
Scanning Operators and Punctuation......Page 111
Scanning Functions and Names......Page 112
Comments and Miscellany......Page 113
The Parser......Page 114
SQL Expressions......Page 116
Functions......Page 119
Other expressions......Page 120
Select Statements......Page 121
Select options and table references......Page 122
SELECT table references......Page 123
Delete Statement......Page 126
Insert and Replace Statements......Page 127
Replace statement......Page 129
Create Database......Page 130
Create Table......Page 131
User Variables......Page 134
The Parser Routines......Page 135
The Makefile for the SQL Parser......Page 136
Exercises......Page 137
Definition Section......Page 139
BEGIN......Page 140
Left Context......Page 141
Definitions (Substitutions)......Page 142
Input Buffers......Page 143
File Nesting......Page 144
Flex Library......Page 145
Literal Block......Page 146
Combined Lexers......Page 147
Multiple Lexers......Page 148
Character sets......Page 149
Extra Data for Reentrant Scanners......Page 150
Reentrant Scanners, Nested Files, and Multiple Scanners......Page 151
Metacharacters......Page 152
Returning Values from yylex()......Page 155
Start States......Page 156
yyless()......Page 157
yylex() and YY_DECL......Page 158
yywrap()......Page 159
Symbols......Page 161
Actions......Page 162
Embedded Actions......Page 163
Shift/Reduce Conflicts......Page 164
GLR Parsers......Page 165
Embedded Actions......Page 166
Error Token and Error Recovery......Page 167
Inherited Attributes ($0)......Page 168
%initial-action......Page 169
Lexical Feedback......Page 170
Literal Tokens......Page 171
%parse-param......Page 172
Character Codes......Page 173
Precedence Declarations......Page 174
Recursive Rules......Page 175
Left and Right Recursion......Page 176
Rules......Page 177
Special Characters......Page 178
%start Declaration......Page 179
Explicit Symbol Types......Page 180
Token Values......Page 181
%type Declaration......Page 182
Combined Parsers......Page 183
Pure Parsers......Page 185
y.output Files......Page 186
yyerror()......Page 187
YYBACKUP......Page 188
yyerrok......Page 189
yyerror()......Page 190
YYRECOVERING()......Page 191
The Pointer Model and Conflicts......Page 193
Kinds of Conflicts......Page 195
Parser States......Page 196
Reduce/Reduce Conflicts......Page 198
Shift/Reduce Conflicts......Page 200
Review of Conflicts in name.output......Page 202
Expression Grammars......Page 203
IF/THEN/ELSE......Page 205
Nested List Grammar......Page 206
How Do You Fix the Conflict?......Page 207
IF/THEN/ELSE (Shift/Reduce)......Page 208
Loop Within a Loop (Shift/Reduce)......Page 210
Limited Lookahead (Shift/Reduce or Reduce/Reduce)......Page 211
Overlap of Alternatives (Reduce/Reduce)......Page 212
Exercises......Page 214
Error Reporting......Page 217
Locations......Page 219
Adding Locations to the Parser......Page 220
Adding Locations to the Lexer......Page 221
More Sophisticated Locations with Filenames......Page 222
Error Recovery......Page 224
Bison Error Recovery......Page 225
Error Recovery in Interactive Parsers......Page 226
Where to Put Error Tokens......Page 227
Exercises......Page 228
Pure Scanners and Parsers......Page 229
Pure Scanners in Flex......Page 230
Pure Parsers in Bison......Page 232
Using Pure Scanners and Parsers Together......Page 233
A Reentrant Calculator......Page 234
GLR Parsing......Page 250
GLR Version of the SQL Parser......Page 251
C++ Parsers......Page 254
C++ Parser Naming......Page 255
A C++ Parser......Page 256
Interfacing a Scanner with a C++ Parser......Page 259
Exercises......Page 261
Appendix. SQL Parser Grammar and Cross-Reference......Page 263
Glossary......Page 279
Index......Page 283