Skip to main content
SpringerLink
Log in

Techniques for Searching, Parsing, and Matching

  • Textbook
  • © 2021

Overview

Authors:
  1. Alberto Pettorossi

    1. DICII, University of Rome "Tor Vergata", Rome, Italy

    View author publications

    You can also search for this author in PubMed   Google Scholar

  • Presents techniques for exploring trees and graphs, with particular focus on linear search and backtracking
  • Useful for advanced undergraduate and graduate courses on automata and formal languages
  • Sample code presented in Java and Prolog

  • 3404 Accesses

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 16.99 USD 54.99
Discount applied Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 16.99 USD 69.99
Discount applied Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 99.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (10 chapters)

  1. Front Matter

    Pages i-viii
    Download chapter PDF

  2. Preliminary Definitions on Languages and Grammars

    • Alberto Pettorossi
    Pages 1-9

  3. Exploring Search Spaces

    • Alberto Pettorossi
    Pages 11-30

  4. Chop-and-Expand Parsers for Context-Free Languages

    • Alberto Pettorossi
    Pages 31-46

  5. Parsers for Deterministic Context-Free Languages: LL(k) Parsers

    • Alberto Pettorossi
    Pages 47-83

  6. Parsers for Deterministic Context-Free Languages: LR(k) Parsers

    • Alberto Pettorossi
    Pages 85-162

  7. Parsers for Operator Grammars and Parser Generators

    • Alberto Pettorossi
    Pages 163-191

  8. Visits of Trees and Graphs and Evaluation of Expressions

    • Alberto Pettorossi
    Pages 193-254

  9. Path Problems in Directed Graphs

    • Alberto Pettorossi
    Pages 255-279

  10. String Matching

    • Alberto Pettorossi
    Pages 281-292

  11. Supplementary Topics

    • Alberto Pettorossi
    Pages 293-300

  12. Back Matter

    Pages 301-310
    Download chapter PDF
Back to top

Keywords

About this book

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.

Authors and Affiliations

  • DICII, University of Rome "Tor Vergata", Rome, Italy

    Alberto Pettorossi

About the author

Prof. Alberto Pettorossi is a professor of Theoretical Computer Science at the Università di Roma, Tor Vergata. He has extensive experience teaching automata, languages, algorithms, data structures, and verification to undergraduate and graduate students. His research interests and academic publications are in the areas of program transformation, program verification, and software model checking.

Bibliographic Information

  • Book Title: Techniques for Searching, Parsing, and Matching

  • Authors: Alberto Pettorossi

  • DOI: https://doi.org/10.1007/978-3-030-63189-5

  • Publisher: Springer Cham

  • eBook Packages: Computer Science, Computer Science (R0)

  • Copyright Information: Springer Nature Switzerland AG 2021

  • Hardcover ISBN: 978-3-030-63188-8Published: 04 January 2022

  • Softcover ISBN: 978-3-030-63191-8Published: 05 January 2023

  • eBook ISBN: 978-3-030-63189-5Published: 03 January 2022

  • Edition Number: 1

  • Number of Pages: VIII, 310

  • Number of Illustrations: 94 b/w illustrations, 3 illustrations in colour

  • Topics: Theory of Computation, Software Engineering/Programming and Operating Systems

Publish with us

Policies and ethics

Back to top

Search

Navigation