This is the second volume of an up-to-date reference work on the theory of deterministic parsing of context-free grammars. Volume II treats the theory of the two most important deterministic parsing methods.

This work is Volume II of a two-volume monograph on the theory of deterministic parsing of context-free grammars. Volume I, "Languages and Parsing" (Chapters 1 to 5), was an introduction to the basic concepts of formal language theory and context-free parsing. Volume II (Chapters 6 to 10) contains a thorough treat ment of the theory of the two most important deterministic parsing methods: LR(k) and LL(k) parsing. Volume II is a continuation of Volume I; together these two volumes form an integrated work, with chapters, theorems, lemmas, etc. numbered consecutively. Volume II begins with Chapter 6 in which the classical con structions pertaining to LR(k) parsing are presented. These include the canonical LR(k) parser, and its reduced variants such as the LALR(k) parser and the SLR(k) parser. The grammarclasses for which these parsers are deterministic are called LR(k) grammars, LALR(k) grammars and SLR(k) grammars; properties of these grammars are also investigated in Chapter 6. A great deal of attention is paid to the rigorous development of the theory: detailed mathematical proofs are provided for most of the results presented.

Autorentext

Seppo Sippu is Professor (Emeritus) of Computer Science at the University of Helsinki, and Eljas Soisalon-Soininen is Professor of Computer Science and Engineering at the Aalto University School of Science. They started their co-work already in the 1970s on the area of compiler construction and parsing. This work culminated in the two-volume book "Parsing Theory" published by Springer 1988 and 1990. Already in the 1980s they gradually moved to data structures and algorithms, and also to databases and indexing, partly inspired by the visit of Dr. Soisalon-Soininen at the University of Karlsruhe as a Humboldt grantee. One important topic in the most recent work has been incorporating index operations into database transactions allowing uniform treatment of them both. Sippu and Soisalon-Soininen have published many articles in peer-reviewed conferences and journals, such as Journal of the ACM, ACM Transactions on Database Systems, The VLDB Journal, and IEEE Transactions on Knowledge and Data Engineering.

Inhalt
6. LR(k) Parsing.- 7. Construction and Implementation of LR(1) Parsers.- 8. LL(k) Parsing.- 9. Syntax Error Handling.- 10. Testing Grammars for Parsability.- Bibliography to Volume II.- Index to Volume II.