Building Parsers with Java™

10.10. Summary

A central problem of parser construction is nondeterminism: Parsers do not always know which path to take as they recognize text. The solution used in this book is to handle recognition at a “set” level. Given a set of partially recognized text strings, each fundamental parser type produces a new set:

• A repetition creates a copy of the initial set, adds a set that results from matching a subparser once, and repeats this process until the subparser can match nothing in the preceding set.

• A sequence matches its subparsers in sequence, starting with the input set. It matches each subparser to the result of the preceding subparser and returns the final set.

• An alternation applies each of its subparsers to each member of the input set ...