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 present various algorithms for parsing subclasses of contextfree 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), 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 KnuthMorris-Pratt algorithm. In Chapter 10 we present some parsing programs written in Prolog, and we briefly recall some decidability results concerning the LL(k) languages and the LR(k) languages. This book was written for a course on Automata, Languages, and Translators, taught at the University of Rome "Tor Vergata". We assume that the reader is familiar with the basic notions of Automata Theory and Formal Languages. Some of the algorithms we have presented are written in Java 1.5 and some others in Prolog. For the Java language the reader may refer to the Java Tutorial at http://java.sun.com/docs/books/tutorial/. All Java programs have been compiled using the Java compiler 1.8.0 25 running under Mac OS X 10.15.4 Darwin 19.4.0. For the Prolog language the reader may refer to http://lpn.swi-prolog.org/. The Prolog language incorporates a backtracking mechanism that can be used for exploring search spaces and solving parsing and matching problems.