The Theory of Parsing, Translation, and Compiling, Vol I: Parsing

by Alfred V. Aho

Other authorsJeffrey D. Ullman
Hardcover, 1972

Status

Available

Call number

001.6425

Library's review

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
Show More
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.
Show Less

Publication

Prentice Hall (1972), Hardcover, 542 pages

Language

Original language

English

Physical description

542 p.; 22.9 cm

ISBN

0139145567 / 9780139145568

Local notes

Omslag: Indbundet
Indskannet omslag - N650U - 150 dpi

LL(k), LR(k), LC(k) grammatikker og tilhørende småautomater og et-gennemløbs oversættere. Fokus på teknik snarere end på om sprogkonstruktionerne bliver besværlige at læse og forstå for mennesker.
Page: 0.1319 seconds