Grune - Parsing Techniques - Practical Guide 2e (Springer, 2008).pdf - Computer Science - sigebryht

Monographs in Computer Science

Editors

David Gries

Fred B. Schneider

Monographs in Computer Science

Abadi and Cardelli, A Theory of Objects

Benosman and Kang [editors], Panoramic Vision: Sensors, Theory, and Applications

Bhanu, Lin, Krawiec, Evolutionary Synthesis of Pattern Recognition Systems

Broy and Stølen, Specification and Development of Interactive Systems: FOCUS on

Streams, Interfaces, and Refinement

Brzozowski and Seger, Asynchronous Circuits

Burgin, Super-Recursive Algorithms

Cantone, Omodeo, and Policriti, Set Theory for Computing: From Decision Procedures

to Declarative Programming with Sets

Castillo, Gutiérrez, and Hadi, Expert Systems and Probabilistic Network Models

Downey and Fellows, Parameterized Complexity

Feijen and van Gasteren, On a Method of Multiprogramming

Grune and Jacobs, Parsing Techniques: A Practical Guide, Second Edition

Herbert and Spärck Jones [editors], Computer Systems: Theory, Technology, and

Applications

Leiss, Language Equations

Levin, Heydon, Mann, and Yu, Software Configuration Management Using VESTA

Mclver and Morgan [editors], Programming Methodology

Mclver and Morgan [editors], Abstraction, Refinement and Proof for Probabilistic

Systems

Misra, A Discipline of Multiprogramming: Programming Theory for Distributed

Applications

Nielson [editor], ML with Concurrency

Paton [editor], Active Rules in Database Systems

Poernomo, Crossley, and Wirsing, Adapting Proof-as-Programs: The Curry-Howard

Protocol

Selig, Geometrical Methods in Robotics

Selig, Geometric Fundamentals of Robotics, Second Edition

Shasha and Zhu, High Performance Discovery in Time Series: Techniques and Case

Studies

Tonella and Potrich, Reverse Engineering of Object Oriented Code

Dick Grune

Ceriel J.H. Jacobs

Parsing Techniques

A Practical Guide

Second Edition

Dick Grune and Ceriel J.H. Jacobs

Faculteit Exacte Wetenschappen

Vrije Universiteit

De Boelelaan 1081

1081 HV Amsterdam

The Netherlands

Series Editors

David Gries

Department of Computer Science

Cornell University

4130 Upson Hall

Ithaca, NY 14853-7501

USA

Fred P. Schneider

Department of Computer Science

Cornell University

4130 Upson Hall

Ithaca, NY 14853-7501

USA

ISBN-13: 978-0-387-20248-8

e-ISBN-13: 978-0-387-68954-8

Library of Congress Control Number: 2007936901

written permission of the publisher (Springer Science+Business Media LLC, 233 Spring Street,

New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly

analysis. Use in connection with any form of information storage and retrieval, electronic

adaptation, computer software, or by similar or dissimilar methodology now known or hereafter

developed is forbidden.

The use in this publication of trade names, trademarks, service marks and similar terms, even if

they are not identified as such, is not to be taken as an expression of opinion as to whether or

not they are subject to proprietary rights.

Printed on acid-free paper.

(SB)

9 8 7 6 5 4 3 2 1

springer.com

Preface to the Second Edition

As is ﬁt, this second edition arose out of our readers’ demands to read about new

developments and our desire to write about them. Although parsing techniques is

not a fast moving ﬁeld, it does move. When the ﬁrst edition went to press in 1990,

there was only one tentative and fairly restrictive algorithm for linear-time substring

parsing. Now there are several powerful ones, covering all deterministic languages;

we describe them in Chapter 12. In 1990 Theorem 8.1 from a 1961 paper by Bar-

Hillel, Perles, and Shamir lay gathering dust; in the last decade it has been used to

create new algorithms, and to obtain insight into existing ones. We report on this in

Chapter 13.

More and more non-Chomsky systems are used, especially in linguistics. None

except two-level grammars had any prominence 20 years ago; we now describe six

of them in Chapter 15. Non-canonical parsers were considered oddities for a very

long time; now they are among the most powerful linear-time parsers we have; see

Chapter 10.

Although still not very practical, marvelous algorithms for parallel parsing have

been designed that shed new light on the principles; see Chapter 14. In 1990 a gen-

eralized LL parser was deemed impossible; now we describe two in Chapter 11.

Traditionally, and unsurprisingly, parsers have been used for parsing; more re-

cently they are also being used for code generation, data compression and logic

language implementation, as shown in Section 17.5. Enough. The reader can ﬁnd

more developments in many places in the book and in the Annotated Bibliography

in Chapter 18.

Kees van Reeuwijk has — only half in jest — called our book “a reservation

for endangered parsers”. We agree — partly; it is more than that — and we make

no apologies. Several algorithms in this book have very limited or just no practical

value. We have included them because we feel they embody interesting ideas and

offer food for thought; they might also grow and acquire practical value. But we

also include many algorithms that do have practical value but are sorely underused;

describing them here might raise their status in the world.

Grune - Parsing Techniques - Practical Guide 2e (Springer, 2008).pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: