Techniques for Searching, Parsing, and Matching

Description

In this book the author presents some techniques for exploring trees and graphs. He illustrates the linear search technique and the backtracking technique, and as instances of tree exploration methods he presents various algorithms for parsing subclasses of context-free languages. He also illustrates some tree and graph exploration and manipulation methods by presenting, among others, algorithms for visiting trees, evaluating Boolean expressions, proving propositional formulas, computing paths in graphs, and performing string matching. This book has been used for advanced undergraduate and graduate courses on automata and formal languages, and assumes some prior exposure to the basic notions in that area. Sample programs are presented in Java and Prolog. Preface Contents CHAPTER 1 Preliminary Definitions on Languages and Grammars 1.1. Free Monoids and Languages 1.2. Formal Grammars CHAPTER 2 Exploring Search Spaces 2.1. Exploring Linear Search Spaces 2.2. Backtracking Algorithms 2.2.1. Dispositions. 2.2.2. Combinations. 2.2.3. n-Queens. 2.3. Visiting Trees While Looking for Good Nodes 2.3.1. Depth First Visit of Trees: Basic Version. 2.3.2. Depth First Visit of Trees: Burstall’s Version. 2.3.3. Breadth First Visit of Trees. CHAPTER 3 Chop-and-Expand Parsers for Context-Free Languages 3.1. Chop-and-Expand Context-Free Parser in a Functional Language 3.2. Chop-and-Expand Context-Free Parser in Java 3.3. Chop-and-Expand Context-Free Parser in a Logic Language CHAPTER 4 Parsers for Deterministic Context-Free Languages: LL(k) Parsers 4.1. Introduction to LL(k) Parsing 4.2. LL(1) Parsers 4.3. LL(k) Parsers (for k ≥ 1) 4.4. Time Complexity of of LL(k) Parsing CHAPTER 5 Parsers for Deterministic Context-Free Languages: LR(k) Parsers 5.1. Introduction to LR(k) Parsing 5.2. LR(0) Parsers 5.2.1. Avoiding the Powerset Construction for LR(0) Parsing. 5.2.2. Remarks on the Hypotheses for LR(k) Parsing. 5.3. SLR(1) Parsers 5.4. LR(1) Parsers 5.4.1. Avoiding the Powerset Construction for LR(k) Parsing. 5.4.2. More Remarks on the Hypotheses for LR(k) Parsing. 5.5. LALR(1) Parsers 5.6. Time Complexity of LR(k) Parsing 5.7. Complexity of Parsing Subclasses of Context-Free Languages 5.8. Subclasses of Context-free Languages 5.9. Derivation of Equivalent LR(1) Grammars from LR(k) Grammars 5.10. Conventions for LL(k) and LR(k) Parsing CHAPTER 6 Parsers for Operator Grammars and Parser Generators 6.1. Operator-Precedence Parsers 6.2. Use of Parser Generators 6.2.1. Generation of Parsers Using Bison. 6.2.2. Generation of Lexical Analyzers Using Flex. 6.2.3. Suggestions for Constructing Parsers. 6.3. Summary on Parsers of Context-Free Languages 6.3.1. Summary on LR(0) and LR(1) Parsing. CHAPTER 7 Visits of Trees and Graphs and Evaluation of Expressions 7.1. Depth First Visit of Trees 7.2. Evaluator of Boolean Expressions 7.3. A Theorem Prover for the Propositional Calculus 7.4. Encoding of n-ary Trees Using Binary Trees 7.5. Minimal Spanning Tree of an Undirected Graph CHAPTER 8 Path Problems in Directed Graphs 8.1. Matrix Multiplication Algorithms 8.2. Comparing Matrix Multiplication Algorithms 8.3. Fast Boolean Matrix Multiplication 8.4. IC-Semirings and Path Problems in Directed Graphs 8.5. Transitive Closure in Directed Graphs: the Reachability Problem 8.6. Reducing Transitive Closure to Boolean Matrix Multiplication 8.7. Transitive Closure in IC-Semirings: the Shortest Path Problem 8.8. Single Source Shortest Paths in Directed Graphs 8.9. From Nondeterministic Finite Automata to Regular Expressions CHAPTER 9 String Matching 9.1. Knuth-Morris-Pratt Pattern Matching 9.1.1. Time Complexity Analysis of the Knuth-Morris-Pratt Algorithm. 9.1.2. Java Implementation of the Knuth-Morris-Pratt Algorithm. 9.2. String Matching in Prolog CHAPTER 10 Supplementary Topics 10.1. Simple Prolog Programs and Parsing Sentences in Prolog 10.2. Decidability Results for LL(k) and LR(k) Grammars and Languages List of Algorithms and Programs Index Bibliography