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 and returns an accumulation of the resulting sets.
A terminal finds assemblies in the input set that start with some element. The terminal creates an output set from copies of these assemblies, removing the sought element from each copy.
These set operations empower the parsing of an infinite variety of languages, including the query, logic, and imperative languages that lie ahead in this book.
