Parsing theory. Vol. I: Languages and parsing
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.
- Parsing theory. Volume II: LR (k) and LL (k) parsing
- On parsing LL-languages
- scientific article; zbMATH DE number 4100631
- A functional-logic perspective of parsing
- Grammar semantics, analysis and parsing by abstract interpretation
- scientific article; zbMATH DE number 3474967
- Parsing beyond context-free grammars
- On parsing LL-languages
- Parsing as abstract interpretation of grammar semantics
- scientific article; zbMATH DE number 444435
- Producing the left parse during bottom-up parsing
- Regular expressions into finite automata
- Simulation of one-dimensional cellular automata by uniquely parallel parsable grammars.
- Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions
- A characterization of Thompson digraphs.
- Follow automata.
- Bounded-connect noncanonical discriminating-reverse parsers.
- Reducing NFAs by invariant equivalences.
- Size/lookahead tradeoff for \(LL(k)\)-grammars
- Reasoning about strings in databases
- P-hardness of the emptiness problem for visibly pushdown languages
- Bottom-up unranked tree-to-graph transducers for translation into semantic graphs
- Descriptional complexity of regular languages
- Checking determinism of regular expressions with counting
- One-unambiguity of regular expressions with numeric occurrence indicators
- Comparing the size of NFAs with and without \(\epsilon\)-transitions
- Measuring nondeterminism in pushdown automata
- Approximate matching between a context-free grammar and a finite-state automaton
- Parsing beyond context-free grammars
- scientific article; zbMATH DE number 444435 (Why is no real title available?)
- Conversion of regular expressions into realtime automata
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- scientific article; zbMATH DE number 4100631 (Why is no real title available?)
- Parsing theory. Volume II: LR (k) and LL (k) parsing
- Postfix automata
- On the computational complexity of algebraic numbers: the Hartmanis-Stearns problem revisited
- A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton
- Translating regular expressions into small -free nondeterministic finite automata
- Measuring nondeterminism in pushdown automata
- Graph parsing as graph transformation. Correctness of predictive top-down parsers
- Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
- On parsing LL-languages
- The language intersection problem for non-recursive context-free grammars
- Partial derivatives of regular expressions and finite automaton constructions
- Parsing as a lifting problem and the Chomsky-Schützenberger representation theorem
- The categorical contours of the Chomsky-Schützenberger representation theorem
- Computation of distances for regular and context-free probabilistic languages
- The IELR(1) algorithm for generating minimal LR(1) parser tables for non-LR(1) grammars with conflict resolution
This page was built for publication: Parsing theory. Vol. I: Languages and parsing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4040284)