flex与bison

1．Introducing Flex and Bison 1

Lexical Analysis and Parsing 1

Regular Expressions and Scanning 2

Our First Flex Program 2

Programs in Plain Flex 4

Putting Flex and Bison Together 5

The Scanner as Coroutine 6

Tokens and Values 7

Grammars and Parsing 9

BNF Grammars 10

Bison's Rule Input Language 11

Compiling Flex and Bison Programs Together 13

Ambiguous Grammars:Not Quite 14

Adding a Few More Rules 15

Flex and Bison vs.Handwritten Scanners and Parsers 16

Exercises 17

2．Using Flex 19

Regular Expressions 19

Regular Expression Examples 21

How Flex Handles Ambiguous Patterns 22

Context-Dependent Tokens 22

File I/O in Flex Scanners 23

Reading Several Files 24

The I/O Structure of a Flex Scanner 25

Input to a Flex Scanner 26

Flex Scanner Output 27

Start States and Nested Input Files 28

Symbol Tables and a Concordance Generator 32

Managing Symbol Tables 32

Using a Symbol Table 35

C Language Cross-Reference 38

Exercises 45

3．Using Bison 47

How a Bison Parser Marches Its Input 47

Shift/Reduce Parsing 48

What Bison's LALR(1) Parser Cannot Parse 50

A Bison Parser 51

Abstract Syntax Trees 51

An Improved Calculator That Creates ASTs 52

Literal Character Tokens 54

Building the AST Calculator 57

Shift/Reduce Conflicts and Operator Precedence 57

When Not to Use Precedence Rules 60

An Advanced Calculator 61

Advanced Calculator Parser 64

Calculator Statement Syntax 65

Calculator Expression Syntax 66

Top-Level Calculator Grammar 67

Basic Parser Error Recovery 67

The Advanced Calculator Lexer 68

Reserved Words 69

Building and Interpreting ASTs 70

Evaluating Functions in the Calculator 76

User-Defined Functions 76

Using the Advanced Calculator 78

Exercises 79

4．Parsing SQL 81

A Quick Overview of SQL 81

Relational Databases 82

Manipulating Relations 83

Three Ways to Use SQL 83

SQL to RPN 84

The Lexer 85

Scanning SQL Keywords 86

Scanning Numbers 90

Scanning Operators and Punctuation 91

Scanning Functions and Names 92

Comments and Miscellany 93

The Parser 94

The Top-Level Parsing Rules 96

SQL Expressions 96

Select Statements 101

Delete Statement 106

Insert and Replace Statements 107

Update Statement 110

Create Database 110

Create Table 111

User Variables 114

The Parser Routines 115

The Makefile for the SQL Parser 116

Exercises 117

5．A Reference for Flex Specifications 119

Structure of a Flex Specification 119

Definition Section 119

Rules Section 119

User Subroutines 120

BEGIN 120

C++ Scanners 121

Context Sensitivity 121

Left Context 121

Right Context 122

Definitions(Substitutions) 122

ECHO 123

Input Management 123

Stdio File Chaining 123

Input Buffers 123

Input from Strings 124

File Nesting 124

input() 124

YY_INPUT 125

Flex Library 125

Interactive and Batch Scanners 126

Line Numbers and yylineno 126

Literal Block 126

Multiple Lexers in One Program 127

Combined Lexers 127

Multiple Lexers 128

Options When Building a Scanner 128

Portability of Flex Lexers 129

Porting Generated C Lexers 129

Reentrant Scanners 130

Extra Data for Reentrant Scanners 130

Access to Reentrant Scanner Data 131

Reentrant Scanners,Nested Files,and Multiple Scanners 131

Using Reentrant Scanners with Bison 132

Regular Expression Syntax 132

Metacharacters 132

REJECT 135

Returning Values from yylex() 135

Start States 135

unput() 137

yyinput() yyunput() 137

yyleng 137

yyless() 137

yylex() and YY_DECL 138

yymore() 138

yyrestart() 139

yy_scan_string and yy_scan_buffer 139

YY_USER_ACTION 139

yywrap() 139

6．A Reference for Bison Specifications 141

Structure of a Bison Grammar 141

Symbols 141

Definition Section 142

Rules Section 142

User Subroutines Section 142

Actions 142

Embedded Actions 143

Symbol Types for Embedded Actions 144

Ambiguity and Conflicts 144

Types of Conflicts 144

Shift/Reduce Conflicts 144

Reduce/Reduce Conflicts 145

%expect 145

GLR Parsers 145

Bugs in Bison Programs 146

Infinite Recursion 146

Interchanging Precedence 146

Embedded Actions 146

C++ Parsers 147

%code Blocks 147

End Marker 147

Error Token and Error Recovery 147

%destructor 148

Inherited Attributes($0) 148

Symbol Types for Inherited Attributes 149

%initial-action 149

Lexical Feedback 150

Literal Block 151

Literal Tokens 151

Locations 152

%parse-param 152

Portability of Bison Parsers 153

Porting Bison Grammars 153

Porting Generated C Parsers 153

Libraries 153

Character Codes 153

Precedence and Associativity Declarations 154

Precedence 154

Associativity 154

Precedence Declarations 154

Using Precedence and Associativity to Resolve Conflicts 155

Typical Uses of Precedence 155

Recursive Rules 155

Left and Right Recursion 156

Rules 157

Special Characters 158

%start Declaration 159

Symbol Values 160

Declaring Symbol Types 160

Explicit Symbol Types 160

Tokens 161

Token Numbers 161

Token Values 161

%type Declaration 162

%union Declaration 163

Variant and Multiple Grammars 163

Combined Parsers 163

Multiple Parsers 165

Using %name-prefix or the-p Flag 165

Lexers for Multiple Parsers 165

Pure Parsers 165

y.output Files 166

Bison Library 167

main() 167

yyerror() 167

YYABORT 168

YYACCEPT 168

YYBACKUP 168

yyclearin 169

yydebug and YYDEBUG 169

YYDEBUG 169

yydebug 169

yyerrok 169

YYERROR 170

yyerror() 170

yyparse() 171

YYRECOVERING() 171

7．Ambiguitiesand Conflicts 173

The Pointer Model and Conflicts 173

Kinds of Conflicts 175

Parser States 176

Contents of name.output 178

Reduce/Reduce Conflicts 178

Shift/Reduce Conflicts 180

Review of Conflicts in name.output 182

Common Examples of Conflicts 183

Expression Grammars 183

IF/THEN/ELSE 185

Nested List Grammar 186

How Do You Fix the Conflict? 187

IF/THEN/ELSE(Shift/Reduce) 188

Loop Within a Loop(Shift/Reduce) 190

Expression Precedence(Shift/Reduce) 191

Limited Lookahead(Shift/Reduce or Reduce/Reduce) 191

Overlap of Alternatives(Reduce/Reduce) 192

Summary 194

Exercises 194

8．Error Reporting and Recovery 197

Error Reporting 197

Locations 199

Adding Locations to the Parser 200

Adding Locations to the Lexer 201

More Sophisticated Locations with Filenames 202

Error Recovery 204

Bison Error Recovery 205

Freeing Discarded Symbols 206

Error Recovery in Interactive Parsers 206

Where to Put Error Tokens 207

Compiler Error Recovery 208

Exercises 208

9．Advanced Flexand Bison 209

Pure Scanners and Parsers 209

Pure Scanners in Flex 210

Pure Parsers in Bison 212

Using Pure Scanners and Parsers Together 213

A Reentrant Calculator 214

GLR Parsing 230

GLR Version of the SQL Parser 231

C++ Parsers 234

A C++ Calculator 235

C++ Parser Naming 235

A C++ Parser 236

Interfacing a Scanner with a C++ Parser 239

Should You Write Your Parser in C++? 241

Exercises 241

Appendix:SQL Parser Grammar and Cross-Reference 243

Glossary 259

Index 263