Techniques for Searching, Parsing, and Matching
Fourth Edition
18,00 €
10,8 €
Area 01 – Scienze matematiche e informatiche
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.
pagine: 292
formato: 17 x 24
ISBN: 978-88-548-6235-7
data pubblicazione: Agosto 2013
editore: Aracne
Informativa si avvale di cookie, anche di terze parti, per offrirti il migliore servizio possibile. Cliccando 'Accetto' o continuando la navigazione ne acconsenti l'utilizzo. Per saperne di più