Techniques For Searching, Parsing, And Matching

In this book we present some techniques for exploring trees and graphs. We illustrate the linear search technique and the backtracking technique and, as instances of tree exploration methods, we pre­sent various algorithms for parsing subclasses of context–free languages. They include: (i) the chop–and–expand parsers for LL(k) languages, (ii) the shift–and–reduce parsers for LR(k) languages and, among them, the LR(0), the SLR(1), the LR(1), and the LALR(1) parsers, and (iii) the operator–precedence parsers. We illustrate the use of the parser generators Bison and Yacc, and the lexical analyzer generator Flex. We also illustrate some tree exploration and manipulation methods by presenting algorithms for visiting trees, evaluating boolean expressions, proving propositional formulas, and encoding trees. We consider the minimal spanning tree problem in undirected graphs and the shortest path problem in directed graphs. For the latter problem we present the solutions based on boolean matrix multiplication, semirings, and dynamic programming. Finally, we consider the pattern–matching problem and we analyze the Knuth–Morris–Pratt algorithm. In the appendices we present some parsing programs using Prolog, and we briefly recall some decidability results concerning the LL(k) languages and the LR(k) languages.