Here's a theoretical problem I've encountered in the development of my Cyan? compiler.
When collapsible non-terminals are used, certain grammars that were previously ambiguous become unambiguous. The collapsing of the non-terminals sometimes removes information about the order in which a sentence was derived, so that in effect the order of non-terminal expansions in the (non-collapsed) parse tree may become irrelevant as they always produce the same (collapsed) parse tree.
Consider the grammar
S → aS | Sa | a
which generates the language a+, and the sentence
aa. This sentence has two unique derivations:
S ⇒ aS ⇒ aa
S ⇒ Sa ⇒ aa
This means that the grammar is ambiguous, and would be rejected by a
standard CFG parser. If, however, the S's in the right-hand side
of S → aS and S → Sa are collapsible, then
the grammar is in fact unambiguous. Which particular rule were used in the
derivation of aa would be irrelevant since in either case the
parse tree would collapse to S ⇒ aa.
The problem I've encountered, then, is to determine in general when collapsible non-terminals have removed an ambiguity from a grammar. If a previously ambiguous grammar were now unambiguous, then at the ambiguous steps the parser could just arbitrarily pick one derivation to pursue, knowing that it wouldn't affect the final parse tree.