Grune / Jacobs Parsing Techniques

A Practical Guide
2. Auflage 2008
ISBN: 978-0-387-68954-8
Verlag: Springer US
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 662 Seiten, eBook

Reihe: Monographs in Computer Science

This second edition of Grune and Jacobs' brilliant work presents new developments and discoveries that have been made in the field. Parsing, also referred to as syntax analysis, has been and continues to be an essential part of computer science and linguistics. Parsing techniques have grown considerably in importance, both in computer science, ie. advanced compilers often use general CF parsers, and computational linguistics where such parsers are the only option. They are used in a variety of software products including Web browsers, interpreters in computer devices, and data compression programs; and they are used extensively in linguistics.

Zielgruppe

Research

Autoren/Hrsg.

Grune, Dick

Jacobs, Ceriel J.H.

Inhaltsverzeichnis

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

Grammars as a Generating Device.- to Parsing.- General Non-Directional Parsing.- Regular Grammars and Finite-State Automata.- General Directional Top-Down Parsing.- General Directional Bottom-Up Parsing.- Deterministic Top-Down Parsing.- Deterministic Bottom-Up Parsing.- Non-Canonical Parsers.- Generalized Deterministic Parsers.- Substring Parsing.- Parsing as Intersection.- Parallel Parsing.- Non-Chomsky Grammars and Their Parsers.- Error Handling.- Practical Parser Writing and Usage.- Annotated Bibliography.