Parsing techniques

Contents......Page 13
Preface to the Second Edition......Page 6
Preface to the First Edition......Page 10
1. Introduction......Page 23
1.2 The Approach Used......Page 24
1.3 Outline of the Contents......Page 25
1.4 The Annotated Bibliography......Page 26
2.1.1 Language......Page 27
2.1.2 Grammars......Page 29
2.1.3 Problems with Infinite Sets......Page 30
2.1.4 Describing a Language through a Finite Recipe......Page 34
2.2.1 The Formalism of Formal Grammars......Page 36
2.2.2 Generating Sentences from a Formal Grammar......Page 37
2.2.3 The Expressive Power of Formal Grammars......Page 39
2.3.1 Type 1 Grammars......Page 41
2.3.2 Type 2 Grammars......Page 45
2.3.3 Type 3 Grammars......Page 52
2.3.4 Type 4 Grammars......Page 55
2.4.1 The Phrase-Structure Case......Page 56
2.4.3 The CF Case......Page 58
2.5 To Shrink or Not To Shrink......Page 60
2.6 Grammars that Produce the Empty Language......Page 63
2.7.1 The uvwxy Theorem......Page 64
2.8 CF and FS Grammars as Transition Graphs......Page 67
2.9 Hygiene in Context-Free Grammars......Page 69
2.9.4 Loops......Page 70
2.9.5 Cleaning up a Context-Free Grammar......Page 71
2.10 Set Properties of Context-Free and Regular Languages......Page 74
2.11.1 Attribute Grammars......Page 76
2.11.2 Transduction Grammars......Page 77
2.12 A Metaphorical Comparison of Grammar Types......Page 78
2.13 Conclusion......Page 81
3.1 The Parse Tree......Page 83
3.1.1 The Size of a Parse Tree......Page 84
3.1.2 Various Kinds of Ambiguity......Page 85
3.2 Two Ways to Parse a Sentence......Page 87
3.2.1 Top-Down Parsing......Page 88
3.2.2 Bottom-Up Parsing......Page 89
3.2.3 Applicability......Page 90
3.3 Non-Deterministic Automata......Page 91
3.3.2 Constructing the Control Mechanism......Page 92
3.4.1 Time Requirements......Page 93
3.4.2 Type 0 and Type 1 Grammars......Page 94
3.4.3 Type 2 Grammars......Page 95
3.4.5 Type 4 Grammars......Page 97
3.5.1 Directionality......Page 98
3.5.2 Search Techniques......Page 99
3.5.3 General Directional Methods......Page 100
3.5.4 Linear Methods......Page 102
3.5.5 Deterministic Top-Down and Bottom-Up Methods......Page 104
3.5.6 Non-Canonical Methods......Page 105
3.6 The "Strength" of a Parsing Technique......Page 106
3.7 Representations of Parse Trees......Page 107
3.7.1 Parse Trees in the Producer-Consumer Model......Page 108
3.7.3 Parse Forests......Page 109
3.7.4 Parse-Forest Grammars......Page 113
3.8 When are we done Parsing?......Page 115
3.9 Transitive Closure......Page 117
3.10 The Relation between Parsing and Boolean Matrix Multiplication......Page 119
3.11 Conclusion......Page 122
4. General Non-Directional Parsing......Page 125
4.1.1 Unger's Method without ε-Rules or Loops......Page 126
4.1.2 Unger's Method with ε-Rules......Page 129
4.1.3 Getting Parse-Forest Grammars from Unger Parsing......Page 132
4.2.1 CYK Recognition with General CF Grammars......Page 134
4.2.2 CYK Recognition with a Grammar in Chomsky Normal Form......Page 138
4.2.3 Transforming a CF Grammar into Chomsky Normal Form......Page 141
4.2.4 The Example Revisited......Page 144
4.2.5 CYK Parsing with Chomsky Normal Form......Page 146
4.2.6 Undoing the Effect of the CNF Transformation......Page 147
4.2.7 A Short Retrospective of CYK......Page 150
4.3 Tabular Parsing......Page 151
4.3.1 Top-Down Tabular Parsing......Page 153
4.3.2 Bottom-Up Tabular Parsing......Page 155
4.4 Conclusion......Page 156
5.1.1 Regular Languages in CF Parsing......Page 159
5.1.2 Systems with Finite Memory......Page 161
5.2 Producing from a Regular Grammar......Page 163
5.3 Parsing with a Regular Grammar......Page 165
5.3.1 Replacing Sets by States......Page 166
5.3.2 ε-Transitions and Non-Standard Notation......Page 169
5.4 Manipulating Regular Grammars and Regular Expressions......Page 170
5.4.1 Regular Grammars from Regular Expressions......Page 171
5.4.2 Regular Expressions from Regular Grammars......Page 173
5.5 Manipulating Regular Languages......Page 174
5.6 Left-Regular Grammars......Page 176
5.7 Minimizing Finite-State Automata......Page 178
5.8.1 The Recognizer......Page 180
5.8.2 Evaluation......Page 181
5.9 Semantics in FS Systems......Page 182
5.10 Fast Text Search Using Finite-State Automata......Page 183
5.11 Conclusion......Page 184
6.1 Imitating Leftmost Derivations......Page 187
6.2 The Pushdown Automaton......Page 189
6.3 Breadth-First Top-Down Parsing......Page 193
6.3.2 A Counterexample: Left Recursion......Page 195
6.4 Eliminating Left Recursion......Page 197
6.5 Depth-First (Backtracking) Parsers......Page 198
6.6 Recursive Descent......Page 199
6.6.1 A Naive Approach......Page 201
6.6.2 Exhaustive Backtracking Recursive Descent......Page 205
6.6.3 Breadth-First Recursive Descent......Page 207
6.7.1 Prolog......Page 210
6.7.2 The DCG Format......Page 211
6.7.4 Running Definite Clause Grammar Programs......Page 212
6.8.1 Cancellation Sets......Page 214
6.8.2 The Transformation Scheme......Page 215
6.8.3 Cancellation Parsing with ε-Rules......Page 218
6.9 Conclusion......Page 219
7. General Directional Bottom-Up Parsing......Page 221
7.1.1 Depth-First (Backtracking) Parsing......Page 223
7.1.2 Breadth-First (On-Line) Parsing......Page 224
7.1.3 A Combined Representation......Page 225
7.1.4 A Slightly More Realistic Example......Page 226
7.2.1 The Basic Earley Parser......Page 228
7.2.2 The Relation between the Earley and CYK Algorithms......Page 234
7.2.3 Handling ε-Rules......Page 236
7.2.4 Exploiting Look-Ahead......Page 241
7.2.5 Left and Right Recursion......Page 246
7.3 Chart Parsing......Page 248
7.3.2 A Transitive Closure Algorithm......Page 249
7.3.5 The Agenda......Page 251
7.3.6 Top-Down......Page 253
7.3.7 Conclusion......Page 254
7.4 Conclusion......Page 255
8. Deterministic Top-Down Parsing......Page 256
8.1 Replacing Search by Table Look-Up......Page 257
8.2.1 LL(1) Parsing without ε-Rules......Page 260
8.2.2 LL(1) Parsing with ε-Rules......Page 263
8.2.3 LL(1) versus Strong-LL(1)......Page 268
8.2.4 Full LL(1) Parsing......Page 269
8.2.5 Solving LL(1) Conflicts......Page 272
8.2.6 LL(1) and Recursive Descent......Page 274
8.3.1 LL(k) Grammars......Page 275
8.3.2 Linear-Approximate LL(k)......Page 277
8.3.3 LL-Regular......Page 278
8.4 Getting a Parse Tree Grammar from LL(1) Parsing......Page 279
8.5 Extended LL(1) Grammars......Page 280
8.6 Conclusion......Page 281
9. Deterministic Bottom-Up Parsing......Page 283
9.1 Simple Handle-Finding Techniques......Page 285
9.2 Precedence Parsing......Page 286
9.2.1 Parenthesis Generators......Page 287
9.2.2 Constructing the Operator-Precedence Table......Page 289
9.2.3 Precedence Functions......Page 291
9.2.4 Further Precedence Methods......Page 292
9.3 Bounded-Right-Context Parsing......Page 295
9.3.1 Bounded-Context Techniques......Page 296
9.3.2 Floyd Productions......Page 297
9.4 LR Methods......Page 298
9.5.1 The LR(0) Automaton......Page 300
9.5.2 Using the LR(0) Automaton......Page 303
9.5.3 LR(0) Conflicts......Page 306
9.5.4 ε-LR(0) Parsing......Page 307
9.5.5 Practical LR Parse Table Construction......Page 309
9.6 LR(1)......Page 310
9.6.1 LR(1) with ε-Rules......Page 315
9.6.2 LR(k > 1) Parsing......Page 317
9.6.3 Some Properties of LR(k) Parsing......Page 319
9.7 LALR(1)......Page 320
9.7.1 Constructing the LALR(1) Parsing Tables......Page 322
9.8 SLR(1)......Page 334
9.9 Conflict Resolvers......Page 335
9.10.1 Elimination of Unit Rules......Page 336
9.10.2 Reducing the Stack Activity......Page 337
9.10.5 Incremental Parser Generation......Page 338
9.11 Getting a Parse Tree Grammar from LR Parsing......Page 339
9.12 Left and Right Contexts of Parsing Decisions......Page 340
9.12.1 The Left Context of a State......Page 341
9.12.2 The Right Context of an Item......Page 342
9.13 Exploiting the Left and Right Contexts......Page 343
9.13.1 Discriminating-Reverse (DR) Parsing......Page 344
9.13.2 LR-Regular......Page 347
9.13.3 LAR(m) Parsing......Page 353
9.15 Conclusion......Page 358
10. Non-Canonical Parsers......Page 362
10.1.1 Left-Corner Parsing......Page 363
10.1.2 Deterministic Cancellation Parsing......Page 372
10.1.3 Partitioned LL......Page 373
10.2 Bottom-Up Non-Canonical Parsing......Page 376
10.2.1 Total Precedence......Page 377
10.2.2 NSLR(1)......Page 378
10.2.3 LR(k,∞)......Page 383
10.2.4 Partitioned LR......Page 391
10.3 General Non-Canonical Parsing......Page 396
10.4 Conclusion......Page 398
11. Generalized Deterministic Parsers......Page 400
11.1.1 The Basic GLR Parsing Algorithm......Page 401
11.1.2 Necessary Optimizations......Page 402
11.1.3 Hidden Left Recursion and Loops......Page 406
11.1.4 Extensions and Improvements......Page 409
11.2.1 Simple Generalized LL Parsing......Page 410
11.2.2 Generalized LL Parsing with Left-Recursion......Page 412
11.2.3 Generalized LL Parsing with ε-Rules......Page 414
11.2.4 Generalized Cancellation and LC Parsing......Page 416
11.3 Conclusion......Page 417
12. Substring Parsing......Page 418
12.1 The Suffix Grammar......Page 420
12.2 General (Non-Linear) Methods......Page 421
12.2.1 A Non-Directional Method......Page 422
12.2.2 A Directional Method......Page 426
12.3 Linear-Time Methods for LL and LR Grammars......Page 427
12.3.1 Linear-Time Suffix Parsing for LL(1) Grammars......Page 428
12.3.2 Linear-Time Suffix Parsing for LR(1) Grammars......Page 433
12.3.3 Tabular Methods......Page 437
12.4 Conclusion......Page 440
13. Parsing as Intersection......Page 443
13.1 The Intersection Algorithm......Page 444
13.1.1 The Rule Sets I[sub(rules)], I[sub(rough)], and I......Page 445
13.1.2 The Languages of [sub(rules)], I[sub(rough)], and I......Page 447
13.1.3 An Example: Parsing Arithmetic Expressions......Page 448
13.2.2 Substring Parsing by Intersection......Page 449
13.2.3 Filtering......Page 453
13.3 Time and Space Requirements......Page 454
13.4 Reducing the Intermediate Size: Earley's Algorithm on FSAs......Page 455
13.5 Error Handling Using Intersection Parsing......Page 457
13.6 Conclusion......Page 459
14.1 The Reasons for Parallel Parsing......Page 461
14.2 Multiple Serial Parsers......Page 462
14.3 Process-Configuration Parsers......Page 465
14.3.1 A Parallel Bottom-up GLR Parser......Page 466
14.3.2 Some Other Process-Configuration Parsers......Page 470
14.4.1 Boolean Circuits......Page 471
14.4.2 A CYK Recognizer on a Boolean Circuit......Page 472
14.4.3 Rytter's Algorithm......Page 478
14.5 Conclusion......Page 488
15.1 The Unsuitability of Context-Sensitive Grammars......Page 490
15.1.1 Understanding Context-Sensitive Grammars......Page 491
15.1.4 Error Handling in Context-Sensitive Grammars......Page 492
15.2 Two-Level Grammars......Page 493
15.2.1 VW Grammars......Page 494
15.2.2 Expressing Semantics in a VW Grammar......Page 497
15.2.3 Parsing with VW Grammars......Page 499
15.2.5 Infinite Symbol Sets......Page 501
15.3.1 Attribute Grammars......Page 502
15.3.2 Affix Grammars......Page 505
15.4.1 Cross-Dependencies......Page 509
15.4.2 Parsing with TAGs......Page 514
15.5 Coupled Grammars......Page 517
15.5.1 Parsing with Coupled Grammars......Page 518
15.6.1 Rule Ordering by Control Grammar......Page 519
15.6.2 Parsing with Rule-Ordered Grammars......Page 520
15.6.3 Marked Ordered Grammars......Page 521
15.6.4 Parsing with Marked Ordered Grammars......Page 522
15.7 Recognition Systems......Page 523
15.7.1 Properties of a Recognition System......Page 524
15.7.2 Implementing a Recognition System......Page 526
15.7.4 Expressing Semantics in Recognition Systems......Page 529
15.7.5 Error Handling in Recognition Systems......Page 530
15.8.1 Expressing Context Checks in Boolean Grammars......Page 531
15.8.3 §-Calculus......Page 533
15.9 Conclusion......Page 534
16.1 Detection versus Recovery versus Correction......Page 537
16.2.1 Error Detection in Non-Directional Parsing Methods......Page 539
16.2.4 Error Detection in General Directional Bottom-Up Parsers......Page 540
16.2.6 Error Detection in Deterministic Bottom-Up Parsers......Page 541
16.4 Global Error Handling......Page 542
16.5.1 Backward/Forward Move Error Recovery......Page 546
16.5.2 Error Recovery with Bounded-Context Grammars......Page 548
16.6 Local Error Handling......Page 549
16.6.2 FOLLOW-Set Error Recovery......Page 550
16.6.3 Acceptable-Sets Derived from Continuations......Page 551
16.6.4 Insertion-Only Error Correction......Page 553
16.6.5 Locally Least-Cost Error Recovery......Page 555
16.7.1 Detection and Recovery......Page 556
16.7.2 Locating the Error......Page 557
16.8.1 Error Productions......Page 558
16.9 Conclusion......Page 559
17.1.1 Considerations......Page 561
17.1.2 General Parsers......Page 562
17.1.3 General Substring Parsers......Page 563
17.1.4 Linear-Time Parsers......Page 564
17.1.6 Obtaining and Using a Parser Generator......Page 565
17.2.1 Interpretive, Table-Based, and Compiled Parsers......Page 566
17.2.2 Parsing Methods and Implementations......Page 567
17.3.1 Principles of the Parser......Page 569
17.3.2 The Program......Page 570
17.3.3 Handling Left Recursion......Page 575
17.3.4 Parsing in Polynomial Time......Page 576
17.4.1 Imperative and Object-Oriented Programming......Page 579
17.4.2 Functional Programming......Page 580
17.5.1 Data Compression......Page 583
17.5.2 Machine Code Generation......Page 586
17.6 Conclusion......Page 589
18. Annotated Bibliography......Page 591
18.1.2 General Context-Free Parsing......Page 592
18.1.3 LL Parsing......Page 600
18.1.4 LR Parsing......Page 601
18.1.5 Left-Corner Parsing......Page 608
18.1.6 Precedence and Bounded-Right-Context Parsing......Page 609
18.1.7 Finite-State Automata......Page 612
18.1.8 General Books and Papers on Parsing......Page 615
18.2.1 Generalized Deterministic Parsing......Page 617
18.2.2 Non-Canonical Parsing......Page 621
18.2.3 Substring Parsing......Page 625
18.2.4 Parsing as Intersection......Page 627
18.2.5 Parallel Parsing Techniques......Page 628
18.2.6 Non-Chomsky Systems......Page 630
18.2.7 Error Handling......Page 639
18.2.8 Incremental Parsing......Page 645
18.3.1 Parser Writing......Page 646
18.3.3 Applications......Page 650
18.3.4 Parsing and Deduction......Page 651
18.3.5 Parsing Issues in Natural Language Handling......Page 652
18.4.1 Formal Languages......Page 654
18.4.3 Transformations on Grammars......Page 657
18.4.4 Miscellaneous Literature......Page 658
A. Hints and Solutions to Selected Problems......Page 660
D......Page 666
K......Page 667
R......Page 668
Z......Page 669
B......Page 670
D......Page 671
G......Page 672
L......Page 673
P......Page 674
R......Page 675
T......Page 676
Z......Page 677