Techniques for searching, parsing, and matching (Second edition)

These lecture notes present some basic techniques for: (i) exploring search spaces, (ii) parsing context-free languages, and (iii) matching patterns in strings. These techniques are taught in a course on Automata, Languages, and Translators at the University of Roma Tor Vergata. We assume that the reader is familiar with the basic notions of Automata Theory and Formal Languages. These notions can be found in many books such as [Har78,HoU79,Pet07]. Some of the algorithms we have presented in these notes 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/. (Recall that this Java version allows the use of parametrized types, also called generics.) All Java programs have been compiled using the Java compiler 1.5.0-13 running under Mac OS X 10.4.11 Darwin 8.11.1. For the Prolog language the reader may refer to [ClM84]. The Prolog language incorporates a backtracking mechanism which is useful for exploring search spaces and solving parsing and matching problems.