Parsing Techniques: A Practical Guide

Front Cover
Springer Science & Business Media, Oct 29, 2007 - Computers - 662 pages
0 Reviews

Parsing, also referred to as syntax analysis, has been and continues to be an essential part of computer science and linguistics. Today, parsing techniques are also implemented in a number of other disciplines, including but not limited to, document preparation and conversion, typesetting chemical formulae, and chromosome recognition.

This second edition presents new developments and discoveries that have been made in the field. Parsing techniques have grown considerably in importance, both in computational linguistics where such parsers are the only option, and computer science, where advanced compilers often use general CF parsers. Parsing techniques provide a solid basis for compiler construction and contribute to all existing software: enabling Web browsers to analyze HTML pages and PostScript printers to analyze PostScript. Some of the more advanced techniques are used in code generation in compilers and in data compression.

In linguistics, the importance of formal grammars was recognized early on, but only recently have the corresponding parsing techniques been applied. Also their importance as general pattern recognizers is slowly being acknowledged. This text Parsing Techniques explores new developments, such as generalized deterministic parsing, linear-time substring parsing, parallel parsing, parsing as intersection, non-canonical methods, and non-Chomsky systems.

To provide readers with low-threshold access to the full field of parsing techniques, this new edition uses a two-tiered structure. The basic ideas behind the dozen or so existing parsing techniques are explained in an intuitive and narrative style, and problems are presented at the conclusion of each chapter, allowing the reader to step outside the bounds of the covered material and explore parsing techniques at various levels. The reader is also provided with an extensive annotated bibliography as well as hints and partial solutions to a number of problems. In the bibliography, hundreds of realizations and improvements of parsing techniques are explained in a much terser, yet still informal, style, improving its readability and usability.

The reader should have an understanding of algorithmic thinking, especially recursion; however, knowledge of any particular programming language is not required.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Selected pages

Contents

962 LR𝓴 1 Parsing
297
963 Some Properties of LR𝓴 Parsing
299
97 LALR1
300
971 Constructing the LALR1 Parsing Tables
302
972 Identifying LALR1 Conflicts
314
99 Conflict Resolvers
315
910 Further Developments of LR Methods
316
9102 Reducing the Stack Activity
317

22 Formal Grammars
14
222 Generating Sentences from a Formal Grammar
15
223 The Expressive Power of Formal Grammars
17
23 The Chomsky Hierarchy of Grammars and Languages
19
232 Type 2 Grammars
23
233 Type 3 Grammars
30
234 Type 4 Grammars
33
235 Conclusion
34
242 The CS Case
36
25 To Shrink or Not To Shrink
38
26 Grammars that Produce the Empty Language
41
27 The Limitations of CF and FS Grammars
42
272 The uvw Theorem
45
29 Hygiene in ContextFree Grammars
47
291 Undefined NonTerminals
48
295 Cleaning up a ContextFree Grammar
49
210 Set Properties of ContextFree and Regular Languages
52
211 The Semantic Connection
54
2112 Transduction Grammars
55
2113 Augmented Transition Networks
56
213 Conclusion
59
Introduction to Parsing
61
311 The Size of a Parse Tree
62
312 Various Kinds of Ambiguity
63
313 Linearization of the Parse Tree
65
321 TopDown Parsing
66
322 BottomUp Parsing
67
323 Applicability
68
33 NonDeterministic Automata
69
331 Constructing the NDA
70
34 Recognition and Parsing for Type 0 to Type 4 Grammars
71
342 Type 0 and Type 1 Grammars
72
343 Type 2 Grammars
73
344 Type 3 Grammars
75
35 An Overview of ContextFree Parsing Methods
76
352 Search Techniques
77
353 General Directional Methods
78
354 Linear Methods
80
355 Deterministic TopDown and BottomUp Methods
82
356 NonCanonical Methods
83
357 Generalized Linear Methods
84
37 Representations of Parse Trees
85
371 Parse Trees in the ProducerConsumer Model
86
372 Parse Trees in the Data Structure Model
87
374 ParseForest Grammars
91
38 When are we done Parsing?
93
39 Transitive Closure
95
310 The Relation between Parsing and Boolean Matrix Multiplication
97
311 Conclusion
100
General NonDirectional Parsing
103
41 Ungers Parsing Method
104
412 Ungers Method with εRules
107
413 Getting ParseForest Grammars from Unger Parsing
110
42 The CYK Parsing Method
112
422 CYK Recognition with a Grammar in Chomsky Normal Form
116
423 Transforming a CF Grammar into Chomsky Normal Form
119
424 The Example Revisited
122
425 CYK Parsing with Chomsky Normal Form
124
426 Undoing the Effect of the CNF Transformation
125
427 A Short Retrospective of CYK
128
428 Getting ParseForest Grammars from CYK Parsing
129
431 TopDown Tabular Parsing
131
432 BottomUp Tabular Parsing
133
44 Conclusion
134
Regular Grammars and FiniteState Automata
137
512 Systems with Finite Memory
139
513 Pattern Searching
141
53 Parsing with a Regular Grammar
143
531 Replacing Sets by States
144
532 εTransitions and NonStandard Notation
147
54 Manipulating Regular Grammars and Regular Expressions
148
541 Regular Grammars from Regular Expressions
149
542 Regular Expressions from Regular Grammars
151
55 Manipulating Regular Languages
152
56 LeftRegular Grammars
154
57 Minimizing FiniteState Automata
156
58 TopDown Regular Expression Recognition
158
582 Evaluation
159
59 Semantics in FS Systems
160
510 Fast Text Search Using FiniteState Automata
161
511 Conclusion
162
General Directional TopDown Parsing
165
62 The Pushdown Automaton
167
63 BreadthFirst TopDown Parsing
171
631 An Example
173
64 Eliminating Left Recursion
175
65 DepthFirst Backtracking Parsers
176
66 Recursive Descent
177
661 A Naive Approach
179
662 Exhaustive Backtracking Recursive Descent
183
663 BreadthFirst Recursive Descent
185
67 Definite Clause Grammars
188
672 The DCG Format
189
673 Getting Parse Tree Information
190
68 Cancellation Parsing
192
682 The Transformation Scheme
193
683 Cancellation Parsing with εRules
196
69 Conclusion
197
General Directional BottomUp Parsing
199
71 Parsing by Searching
201
712 BreadthFirst OnLine Parsing
202
713 A Combined Representation
203
714 A Slightly More Realistic Example
204
72 The Earley Parser
206
722 The Relation between the Earley and CYK Algorithms
212
723 Handling εRules
214
724 Exploiting LookAhead
219
725 Left and Right Recursion
224
73 Chart Parsing
226
731 Inference Rules
227
733 Completion
229
736 TopDown
231
737 Conclusion
232
74 Conclusion
233
Deterministic TopDown Parsing
234
81 Replacing Search by Table LookUp
236
82 LL1 Parsing
239
822 LL1 Parsing with εRules
242
823 LL1 versus StrongLL1
247
824 Full LL1 Parsing
248
825 Solving LL1 Conflicts
251
826 LL1 and Recursive Descent
253
83 Increasing the Power of Deterministic LL Parsing
254
832 LinearApproximate LLk
256
833 LLRegular
257
84 Getting a Parse Tree Grammar from LL1 Parsing
258
85 Extended LL1 Grammars
259
86 Conclusion
260
Deterministic BottomUp Parsing
263
91 Simple HandleFinding Techniques
265
92 Precedence Parsing
266
921 Parenthesis Generators
267
922 Constructing the OperatorPrecedence Table
269
923 Precedence Functions
271
924 Further Precedence Methods
272
93 BoundedRightContext Parsing
275
931 BoundedContext Techniques
276
932 Floyd Productions
277
94 LR Methods
278
95 LR0
280
952 Using the LR0 Automaton
283
953 LR0 Conflicts
286
954 εLR0 Parsing
287
955 Practical LR Parse Table Construction
289
96 LR1
290
961 LR1 with εRules
295
9103 Regular Right Part Grammars
318
9106 Recursive Ascent
319
912 Left and Right Contexts of Parsing Decisions
320
9121 The Left Context of a State
321
9122 The Right Context of an Item
322
913 Exploiting the Left and Right Contexts
323
9131 DiscriminatingReverse DR Parsing
324
9132 LRRegular
327
9133 LARm Parsing
333
914 LR𝓴as an Ambiguity Test
338
NonCanonical Parsers
342
101 TopDown NonCanonical Parsing
344
1012 Deterministic Cancellation Parsing
353
1013 Partitioned LL
354
1014 Discussion
357
1021 Total Precedence
358
1022 NSLR1
359
1023 LR𝓴
364
1024 Partitioned LR
372
103 General NonCanonical Parsing
377
104 Conclusion
379
Generalized Deterministic Parsers
381
111 Generalized LR Parsing
382
1112 Necessary Optimizations
383
1113 Hidden Left Recursion and Loops
387
1114 Extensions and Improvements
390
112 Generalized LL Parsing
391
1122 Generalized LL Parsing with LeftRecursion
393
1123 Generalized LL Parsing with εRules
395
1124 Generalized Cancellation and LC Parsing
397
113 Conclusion
398
Substring Parsing
399
121 The Suffix Grammar
401
122 General NonLinear Methods
402
1221 A NonDirectional Method
403
1222 A Directional Method
407
123 LinearTime Methods for LL and LR Grammars
408
1231 LinearTime Suffix Parsing for LL1 Grammars
409
1232 LinearTime Suffix Parsing for LR1 Grammars
414
1233 Tabular Methods
418
1234 Discussion
421
Parsing as Intersection
425
131 The Intersection Algorithm
426
1311 The Rule Sets Irules Irough and I
427
1312 The Languages of Irules Irough and I
429
Parsing Arithmetic Expressions
430
132 The Parsing of FSAs
431
1323 Filtering
435
133 Time and Space Requirements
436
Earleys Algorithm on FSAs
437
135 Error Handling Using Intersection Parsing
439
136 Conclusion
441
Parallel Parsing
443
142 Multiple Serial Parsers
444
143 ProcessConfiguration Parsers
447
1431 A Parallel Bottomup GLR Parser
448
1432 Some Other ProcessConfiguration Parsers
452
144 Connectionist Parsers
453
1442 A CYK Recognizer on a Boolean Circuit
454
1443 Rytters Algorithm
460
145 Conclusion
470
NonChomsky Grammars and Their Parsers
472
1511 Understanding ContextSensitive Grammars
474
1512 Parsing with ContextSensitive Grammars
475
1515 Alternatives
476
1521 VW Grammars
477
1522 Expressing Semantics in a VW Grammar
480
1523 Parsing with VW Grammars
482
1524 Error Handling in VW Grammars
484
153 Attribute and Affix Grammars
485
1532 Affix Grammars
488
154 TreeAdjoining Grammars
492
1542 Parsing with TAGs
497
155 Coupled Grammars
500
1551 Parsing with Coupled Grammars
501
156 Ordered Grammars
502
1562 Parsing with RuleOrdered Grammars
503
1563 Marked Ordered Grammars
504
1564 Parsing with Marked Ordered Grammars
505
157 Recognition Systems
506
1571 Properties of a Recognition System
507
1572 Implementing a Recognition System
509
1573 Parsing with Recognition Systems
512
1575 Error Handling in Recognition Systems
513
158 Boolean Grammars
514
1582 Parsing with Boolean Grammars
516
159 Conclusion
517
Error Handling
521
162 Parsing Techniques and Error Detection
523
1622 Error Detection in FiniteState Automata
524
1625 Error Detection in Deterministic TopDown Parsers
525
163 Recovering from Errors
526
165 Regional Error Handling
530
1652 Error Recovery with BoundedContext Grammars
532
166 Local Error Handling
533
1661 Panic Mode
534
1663 AcceptableSets Derived from Continuations
535
1664 InsertionOnly Error Correction
537
1665 Locally LeastCost Error Recovery
539
167 NonCorrecting Error Recovery
540
1672 Locating the Error
541
168 Ad Hoc Methods
542
1682 Empty Table Slots
543
Practical Parser Writing and Usage
545
1712 General Parsers
546
1713 General Substring Parsers
547
1714 LinearTime Parsers
548
1715 LinearTime Substring Parsers
549
172 Parser Construction
550
1722 Parsing Methods and Implementations
551
173 A Simple General ContextFree Parser
553
1732 The Program
554
1733 Handling Left Recursion
559
1734 Parsing in Polynomial Time
560
174 Programming Language Paradigms
563
1742 Functional Programming
564
1743 Logic Programming
567
1752 Machine Code Generation
570
1753 Support of Logic Languages
573
Annotated Bibliography
575
181 Major Parsing Subjects
576
1813 LL Parsing
584
1814 LR Parsing
585
1815 LeftCorner Parsing
592
1816 Precedence and BoundedRightContext Parsing
593
1817 FiniteState Automata
596
1818 General Books and Papers on Parsing
599
182 Advanced Parsing Subjects
601
1822 NonCanonical Parsing
605
1823 Substring Parsing
609
1824 Parsing as Intersection
611
1825 Parallel Parsing Techniques
612
1826 NonChomsky Systems
614
1827 Error Handling
623
1828 Incremental Parsing
629
183 Parsers and Applications
630
1832 ParserGenerating Systems
634
1834 Parsing and Deduction
635
1835 Parsing Issues in Natural Language Handling
636
184 Support Material
638
1842 Approximation Techniques
641
1844 Miscellaneous Literature
642
Hints and Solutions to Selected Problems
644
Author Index
651
Subject Index
655
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page 10 - A, B, AA, AB, BA, BB, AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB, AAAA.