Yacc traditionally supports only a very specialised subset of grammars -- LALR1 with some weak static ambiguity resolution strategies.
The Felix system is based on Scott McPeaks Elkhound, which is a Generalised LR, or GLR, parser. This system support all grammars, whilst parsing SLR grammars just as efficiently as Yacc (namely, in linear space and time).
GLR handles ambiguity by spawning multiple concurrent threads for all alternatives wherever the SLR(1) prediction is inadequate. These threads process the token stream sychronously, so there is never any backtracking. Instead, alternatives which would be tried in sequence by a backtracking algorithm are all tried at once.
Consequently, GLR can eat up exponentially large amounts of memory, and finally return all possible parse trees.
In practice, this doesn't happen. First, one of the threads can reach an impasse where it can't handle the next token, and it is automatically dropped as an alternative, in the same way a failure in a backtracking algorithm drops the current parse -- however unlike backtracking, that's the end of it: the viable alternatives are already being parsed in parallel.
For many nonterminals, two alternative productions are encoded precisely to handle the union of two sets of cases. At some point during the parse then, one of the productions must fail on for any input not in the common subset of the cases. In that case, GLR drops the failed parse attempt automatically.
When the input is in the common subset, however, the algorithm cannot know what to do. By default, both parses will be continued, causing a bifurcation in the parse of a production trying to process that symbol during *its* parse.
That divergence can only be eliminated automatically if the whole containing production is subsequently failed, in which case both subparses will be dropped.
For this reason, at the end of the parsing of a
a non-terminal, the client has an oppotunity to
pick between the parses.
6.1. top level parser
6.2. nested parser
6.3. Parser shortcuts
6.4. Mixed Mode Arithmetic