Parsing theory. Vol. I: Languages and parsing (Q4040284)

Volume I, containing the first five chapters, corresponds to a one- semester introductory course on parsing theory. It should naturally be followed with the volume II contents on LL(k) and LR(k) parsers, for another semester. Volume I reviews the most important results from formal language theory, grammars and finite automata related to parsing. As specific and valuable features of the book we mention at least two: (1) Being a matured field, the authors are concerned not only with the pure results but especially with their (space and time) computational complexity; (2) each chapter is provided with a set of various and interesting exercises, completing the theoretical and practical knowledge, and with interesting bibliographical comments. Chapter 1 reviews strictly necessary mathematical and computer science background: random access machines, decision problems and solvability, rewriting systems, computational complexity. Chapter 2 develops basic algorithms for directed graphs and relations: searching graph algorithms, an efficient algorithm for finding the strongly-connected components for directed graphs, practical algorithms for computing set-valued functions (that subsumes the closure of a relation) and relations operated by multiplication, closure, inverse and union operators. Chapter 3 is devoted to regular languages, their relation to finite automata, their descriptional power and (relative) succinctness, complexity bounds of the (membership, containment, equivalence) decision problems, the design of lexical analysers. Chapter 4 deals with context- free languages (CFL). It contains results on CFL derivational complexity (belonging to the first author - 1982), variants of the well-known deterministic and nondeterministic algorithms for CFL recognition. The first four chapters are a prologue to Chapter 5, that introduces the concept of CFL parsing and its formal model, the pushdown transducer. Relations and complexity results are included (e.g., deterministic pushdown automata can be more succinct than context-free grammars - 1982), efficient strong (deterministic) LL(k) parsers are considered, particular parsing algorithms for LL(1) are derived, simple precedence grammars and parsing are investigated. Volume I is a very good (introductory) textbook and a prologue (Chapter 5, especially) to Volume II of this monograph. The reference to other already basic approaches is sometimes necessary and instructive for the reader.