Focusing on the evolution of programming languages, this book delves into the necessity for a robust methodology in compiler design, emphasizing a syntax-directed approach. It explores how program text is parsed based on formal syntax, with object code generated from the semantics of parsed entities. The text highlights the significance of context-free grammars in describing programming language syntax and discusses the development of efficient deterministic linear-time algorithms for parsing restricted context-free grammars.
Focusing on the concept of transactions in databases, this book delves into the sequence of database actions executed as atomic units of work, essential for application programmers. It highlights the established foundations of transaction processing, tracing its development back to the late 1970s and early 1980s, and explores the implications of these concepts for modern database management and application design.
Volume II of this monograph delves into deterministic parsing of context-free grammars, focusing on LR(k) and LL(k) methods. It builds on Volume I, presenting classical constructions like the canonical LR(k) parser and its variants. The text emphasizes rigorous mathematical proofs and the properties of various grammar classes.
The theory of parsing is an important application area of the theory of formal languages and automata. The evolution of modem high-level programming languages created a need for a general and theoretically dean methodology for writing compilers for these languages. It was perceived that the compilation process had to be "syntax-directed", that is, the functioning of a programming language compiler had to be defined completely by the underlying formal syntax of the language. A program text to be compiled is "parsed" according to the syntax of the language, and the object code for the program is generated according to the semantics attached to the parsed syntactic entities. Context-free grammars were soon found to be the most convenient formalism for describing the syntax of programming languages, and accordingly methods for parsing context-free languages were devel oped. Practical considerations led to the definition of various kinds of restricted context-free grammars that are parsable by means of efficient deterministic linear-time algorithms.
