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 ...