NA

Indeholder "Preface", "0. Mathematical preliminaries", " 0.1 Concepts from Set Theory", " 0.1.1 Sets", " 0.1.2 Operations on Sets", " 0.1.3 Relations", " 0.1.4 Closures of Relations", " 0.1.5 Ordering Relations", " 0.1.6 Mappings", " Exercises ", " 0.2 Sets of Strings", " 0.2.1 Strings", " 0.2.2 Languages", " 0.2.3 Operations on Languages", " Exercises", " 0.3 Concepts from Logic", " 0.3.1 Proofs", " 0.3.2 Proofs by Induction", " 0.3.3 Logical Connectives", " Exercises", " Bibliograpic Notes", " 0.4 Procedures and Algorithms", " 0.4.1 Procedures", " 0.4.2 Algorithms", " 0.4.3 Recursive Functions", " 0.4.4 Specification of Procedures", " 0.4.5 Problems", " 0.4.6 Post's Correspondence Problem", " Exercises", " Bibliograpic Notes", " 0.5 Concepts from Graph Theory", " 0.5.1 Directed Graphs", " 0.5.2 Directed Acyclic Graphs", " 0.5.3 Trees", " 0.5.4 Ordered Graphs", " 0.5.5 Inductive Proofs Involving Dags", " 0.5.6 Linear Orders from Partial Orders", " 0.5.7 Representations for Trees", " 0.5.8 Paths Through a Graph", " Exercises", " Bibliograpic Notes", "1. An Introduction to Compiling", " 1.1 Programming Languages", " 1.1.1 Specification of Programming Languages", " 1.1.2 Syntax and Semantics", " Bibliographic Notes", " 1.2 An Overview of Compiling", " 1.2.1 The Portions of a Compiler", " 1.2.2 Lexical Analysis", " 1.2.3 Bookkeeping", " 1.2.4 Parsing", " 1.2.5 Code Generation", " 1.2.6 Code Optimization", " 1.2.7 Error Analysis and Recovery", " 1.2.8 Summary", " Exercises", " Bibliograpic Notes", " 1.3 Other Applications of Parsing and Translating Algorithms", " 1.3.1 Natural Languages", " 1.3.2 Structural Description of Patterns", " Bibliograpic Notes", "2. Elements of Language Theory", " 2.1 Representations for Languages", " 2.1.1 Motivation", " 2.1.2 Grammars", " 2.1.3 Restricted Grammars", " 2.1.4 Recognizers", " Exercises", " Bibliographic Notes", " 2.2 Regular Sets, Their Generators, and Their Recognizers", " 2.2.1 Regular Sets and Regular Expressions", " 2.2.2 Regular Sets and Right-Linear Grammars", " 2.2.3 Finite Automata", " 2.2.4 Finite Automata and Regular Sets", " 2.2.5 Summary", " Exercises", " Bibliographic Notes", " 2.3 Properties of Regular Sets", " 2.3.1 Minimization of Finite Automata", " 2.3.2 The Pumping Lemma for Regular Sets", " 2.3.3 Closure Properties of Regular Sets", " 2.3.4 Decidable Questions About Regular Sets", " Exercises", " Bibliographic Notes", " 2.4 Context free Languages", " 2.4.1 Derivation Trees", " 2.4.2 Transformations on Context-Free Grammars", " 2.4.3 Chomsky Normal Form", " 2.4.4 Greibach Normal Form", " 2.4.5 An Alternative Method of Achieving Greibach Normal Form", " Exercises", " Bibliographic Notes", " 2.5 Pushdown Automata", " 2.5.1 The Basic Definition", " 2.5.2 Variants of Pushdown Automata", " 2.5.3 Equivalence of PDA Languages and CFL's", " 2.5.4 Deterministic Pushdown Automata", " Exercises", " Bibliographic Notes", " 2.6 Properties of Context Free Languages", " 2.6.1 Ogden's Lemma", " 2.6.2 Closure Properties of CFL's", " 2.6.3 Decidability Results", " 2.6.4 Properties of Deterministic CFL's", " 2.6.5 Ambiguity", " Exercises", " Bibliographic Notes", "3. Theory of Translation", " 3.1 Formalisms for Translations", " 3.1.1 Translation and Semantics", " 3.1.2 Syntax-Directed Translation Schemata", " 3.1.3 Finite Transducers", " 3.1.4 Pushdown Transducers", " Exercises", " Bibliographic Notes", " 3.2 Properties of Syntax Directed Translations", " 3.2.1 Characterizing Languages", " 3.2.2 Properties of Simple SDT's", " 3.2.3 A Hierarchy of SDT's", " Exercises", " Bibliographic Notes", " 3.3 Lexical nalysis", " 3.3.1 An Extended Language for Regular Expressions", " 3.3.2 Indirect Lexical Analysis", " 3.3.3 Direct Lexical Analysis", " 3.3.4 Software Simulation of Finite Transducers ", " Exercises", " Bibliographic Notes", " 3.4 Parsing", " 3.4.1 Definition of Parsing", " 3.4.2 Top-Down Parsing", " 3.4.3 Bottom-Up Parsing", " 3.4.4 Comparison of Top-Down and Bottom-Up Parsing", " 3.4.5 Grammatical Covering", " Exercises", " Bibliographic Notes", "4. General Parsing Methods", " 4.1 Backtrack Parsing", " 4.1.1 Simulation of a PDT", " 4.1.2 Informal Top-Down Parsing", " 4.1.3 The Top-Down Parsing Algorithm", " 4.1.4 Time and Space Complexity of the Top-Down Parser", " 4.1.5 Bottom-Up Parsing", " Exercises", " Bibliographic Notes ", " 4.2 Tabular Parsing Methods", " 4.2.1 The Cocke-Younger-Kasami Algorithm", " 4.2.2 The Parsing Method of Earley", " Exercises", " Bibliographic Notes", "5. One-Pass No Backtrack Parsing", " 5.1 LL(k) Grammars", " 5.1.1 Definition of LL(k) Grammar", " 5.1.2 Predictive Parsing Algorithms", " 5.1.3 Implications of the LL(k) Definition", " 5.1.4 Parsing LL(1) Grammars", " 5.1.5 Parsing LL(k) Grammars", " 5.1.6 Testing for the LL(k) Condition", " Exercises", " Bibliographic Notes", " 5.2 Deterministic Bottom-Up Parsing", " 5.2.1 Deterministic Shift-Reduce Parsing", " 5.2.2 LR(k) Grammars", " 5.2.3 Implications of the LR(k) Definition", " 5.2.4 Testing for the LR(k) Condition", " 5.2.5 Deterministic Right Parsers for LR(k)", " 5.2.6 Implementation of LL(k) and LR(k) Parsers", " Exercises", " Bibliographic Notes", " 5.3 Precedence Grammars", " 5.3.1 Formal Shift-Reduce Parsing Algorithms", " 5.3.2 Simple Precedence Grammars", " 5.3.3 Extended Precedence Grammars", " 5.3.4 Weak Precedence Grammars", " Exercises", " Bibliographic Notes", " 5.4 Other Classes of Shift-Reduce Parsable Grammars", " 5.4.1 Bounded-Right-Context Grammars", " 5.4.2 Mixed Strategy Precedence Grammars", " 5.4.3 Operator Precedence Grammars", " 5.4.4 Floyd-Evans Production Language", " 5.4.5 Chapter Summary", " Exercises", " Bibliographic Notes ", "6. Limited Backtrack Parsing Algorithms", " 6.1 Limited Backtrack Top-Down Parsing", " 6.1.1 TDPL", " 6.1.2 TDPL and Deterministic Context-Free Languages", " 6.1.3 A Generalization of TDPL", " 6.1.4 Time Complexity of GTDPL Languages", " 6.1.5 Implementation of GTDPL Programs", " Exercises", " Bibliographic Notes ", " 6.2 Limited Backtrack Bottom-Up Parsing", " 6.2.1 Noncanonical Parsing", " 6.2.2 Two-Stack Parsers", " 6.2.3 Colmerauer Precedence Relations", " 6.2.4 Test for Colmerauer Precedence", " Exercises", " Bibliographic Notes ", "Appendix", " A.1 Syntax for an Extensible Base Language", " A.2 Syntax of SNOBL4 Statements", " A.3 Syntax for PL360", " A.4 A Syntax-Directed Translation Scheme for PAL", "Bibliography", "Index to Lemmas, Theorems and Algorithms", "Index to volume I".

Bogen er en ganske nydelig lærebog i parserteori anno 1972. Desværre eller heldigvis er den blevet spist af tidens tand for det er let at lave simpel parsing i diverse script-sprog og tilsvarende svært at lave fx en god konkurrent til en af de gængse compilere til fx C++ fordi både sprog og kodegenerering er komplicerede udover hvad en enkelt person nemt kan overskue. ( )