Parsing Techniques (eBook)

Preface to the Second Edition 6
Acknowledgments 9
Preface to the First Edition 10
Contents 13
1 Introduction 23
1.1 Parsing as a Craft 24
1.2 The Approach Used 24
1.3 Outline of the Contents 25
1.4 The Annotated Bibliography 26
2 Grammars as a Generating Device 27
2.1 Languages as Infinite Sets 27
2.2 Formal Grammars 36
2.3 The Chomsky Hierarchy of Grammars and Languages 41
2.4 Actually Generating Sentences from a Grammar 56
2.5 To 60
Shrink 60
or Not 60
To 60
Shrink 60
2.6 Grammars that Produce the Empty Language 63
2.7 The Limitations of CF and FS Grammars 64
2.8 CF and FS Grammars as Transition Graphs 67
2.9 Hygiene in Context-Free Grammars 69
2.10 Set Properties of Context-Free and Regular Languages 74
2.11 The Semantic Connection 76
2.12 A Metaphorical Comparison of Grammar Types 78
2.13 Conclusion 81
Problems 81
3 Introduction to Parsing 83
3.1 The Parse Tree 83
3.2 Two Ways to Parse a Sentence 87
3.3 Non-Deterministic Automata 91
3.4 Recognition and Parsing for Type 0 to Type 4 Grammars 93
3.5 An Overview of Context-Free Parsing Methods 98
3.6 The Strength of a Parsing Technique 106
3.7 Representations of Parse Trees 107
3.8 When are we done Parsing? 115
3.9 Transitive Closure 117
3.10 The Relation between Parsing and Boolean Matrix Multiplication 119
3.11 Conclusion 122
Problems 122
4 General Non-Directional Parsing 125
4.1 Unger’s Parsing Method 126
4.2 The CYK Parsing Method 134
4.3 Tabular Parsing 151
4.4 Conclusion 156
Problems 156
5 Regular Grammars and Finite-State Automata 159
5.1 Applications of Regular Grammars 159
5.2 Producing from a Regular Grammar 163
5.3 Parsing with a Regular Grammar 165
5.4 Manipulating Regular Grammars and Regular Expressions 170
5.5 Manipulating Regular Languages 174
5.6 Left-Regular Grammars 176
5.7 Minimizing Finite-State Automata 178
5.8 Top-Down Regular Expression Recognition 180
5.9 Semantics in FS Systems 182
5.10 Fast Text Search Using Finite-State Automata 183
5.11 Conclusion 184
Problems 185
6 General Directional Top-Down Parsing 187
6.1 Imitating Leftmost Derivations 187
6.2 The Pushdown Automaton 189
6.3 Breadth-First Top-Down Parsing 193
6.4 Eliminating Left Recursion 197
6.5 Depth-First (Backtracking) Parsers 198
6.6 Recursive Descent 199
6.7 Definite Clause Grammars 210
6.8 Cancellation Parsing 214
6.9 Conclusion 219
Problems 219
7 General Directional Bottom-Up Parsing 221
7.1 Parsing by Searching 223
7.2 The Earley Parser 228
7.3 Chart Parsing 248
7.4 Conclusion 255
Problems 255
8 Deterministic Top-Down Parsing 256
8.1 Replacing Search by Table Look-Up 257
8.2 LL(1) Parsing 260
8.3 Increasing the Power of Deterministic LL Parsing 275
8.4 Getting a Parse Tree Grammar from LL(1) Parsing 279
8.5 Extended LL(1) Grammars 280
8.6 Conclusion 281
Problems 281
9 Deterministic Bottom-Up Parsing 283
9.1 Simple Handle-Finding Techniques 285
9.2 Precedence Parsing 286
9.3 Bounded-Right-Context Parsing 295
9.4 LR Methods 298
9.5 LR(0) 300
9.6 LR(1) 310
9.7 LALR(1) 320
9.8 SLR(1) 334
9.9 Conflict Resolvers 335
9.10 Further Developments of LR Methods 336
9.11 Getting a Parse Tree Grammar from LR Parsing 339
9.12 Left and Right Contexts of Parsing Decisions 340
9.13 Exploiting the Left and Right Contexts 343
9.14 358
LR( 358
as an Ambiguity Test 358
9.15 Conclusion 358
Problems 359
10 Non-Canonical Parsers 362
10.1 Top-Down Non-Canonical Parsing 363
10.2 Bottom-Up Non-Canonical Parsing 376
10.3 General Non-Canonical Parsing 396
10.4 Conclusion 398
Problems 398
11 Generalized Deterministic Parsers 400
11.1 Generalized LR Parsing 401
11.2 Generalized LL Parsing 410
11.3 Conclusion 417
Problems 417
12 Substring Parsing 418
12.1 The Suffix Grammar 420
12.2 General (Non-Linear) Methods 421
12.3 Linear-Time Methods for LL and LR Grammars 427
12.4 Conclusion 440
Problems 441
13 Parsing as Intersection 443
13.1 The Intersection Algorithm 444
13.2 The Parsing of FSAs 449
13.3 Time and Space Requirements 454
13.4 Reducing the Intermediate Size: Earley’s Algorithm on FSAs 455
13.5 Error Handling Using Intersection Parsing 457
13.6 Conclusion 459
Problems 459
14 Parallel Parsing 461
14.1 The Reasons for Parallel Parsing 461
14.2 Multiple Serial Parsers 462
14.3 Process-Configuration Parsers 465
14.4 Connectionist Parsers 471
14.5 Conclusion 488
Problems 489
15 Non-Chomsky Grammars and Their Parsers 490
15.1 The Unsuitability of Context-Sensitive Grammars 490
15.2 Two-Level Grammars 493
15.3 Attribute and Affix Grammars 502
15.4 Tree-Adjoining Grammars 509
15.5 Coupled Grammars 517
15.6 Ordered Grammars 519
15.7 Recognition Systems 523
15.8 Boolean Grammars 531
15.9 Conclusion 534
Problems 534
16 Error Handling 537
16.1 Detection versus Recovery versus Correction 537
16.2 Parsing Techniques and Error Detection 539
16.3 Recovering from Errors 542
16.4 Global Error Handling 542
16.5 Regional Error Handling 546
16.6 Local Error Handling 549
16.7 Non-Correcting Error Recovery 556
16.8 Ad Hoc Methods 558
16.9 Conclusion 559
Problems 560
17 Practical Parser Writing and Usage 561
17.1 A Comparative Survey 561
17.2 Parser Construction 566
17.3 A Simple General Context-Free Parser 569
17.4 Programming Language Paradigms 579
17.5 Alternative Uses of Parsing 583
17.6 Conclusion 589
Problems 589
18 Annotated Bibliography 591
18.1 Major Parsing Subjects 592
18.2 Advanced Parsing Subjects 617
18.3 Parsers and Applications 646
18.4 Support Material 654
A Hints and Solutions to Selected Problems 660
Author Index 666
Subject Index 670