Inclusive choice is used to accommodate ambiguity by expanding all alternative right-hand-sides of grammar rules.
[3] However, more sophisticated top-down parsers have been created by Frost, Hafiz, and Callaghan,[4][5] which do accommodate ambiguity and left recursion in polynomial time and which generate polynomial-sized representations of the potentially exponential number of parse trees.
A compiler parses input from a programming language to an internal representation by matching the incoming symbols to production rules.
A non-ambiguous language may be parsed by an LL(1) grammar where the (1) signifies the parser reads ahead one token at a time.
However, recent research demonstrates that it is possible to accommodate left-recursive grammars (along with all other forms of general CFGs) in a more sophisticated top-down parser by use of curtailment.
[6] That algorithm was extended to a complete parsing algorithm to accommodate indirect (by comparing previously computed context with current context) as well as direct left-recursion in polynomial time, and to generate compact polynomial-size representations of the potentially exponential number of parse trees for highly ambiguous grammars by Frost, Hafiz and Callaghan in 2007.
[7][8] When top-down parser tries to parse an ambiguous input with respect to an ambiguous CFG, it may need exponential number of steps (with respect to the length of the input) to try all alternatives of the CFG in order to produce all possible parse trees, which eventually would require exponential memory space.
The problem of exponential time complexity in top-down parsers constructed as sets of mutually recursive functions has been solved by Norvig in 1991.
[10] Using PEG's, another representation of grammars, packrat parsers provide an elegant and powerful parsing algorithm.