There is a favoured structure for storing ambiguous parse trees. It
is usually called a shared forest, and it is simply a grammar that
generates only the sentence parsed with exactly the same parse trees
as the grammar of the language (up to a renaming homomorphisme for the non-terminal symbols). This applies to Context-Free grammars,
but also to several other formalisms such as Tree-Adjoining Grammars.
It can be used as a generator to enumerate the individual parse-trees.
Shared forests are often presented as a graphs, with various
qualification, but these graphs are only representations of grammars.
They appear in all general context-free parsers in the literature.
Your question is a good question. However, the sentence you emphasize
in boldface is, in my opinion, the wrong way to worry about
representing ambiguity, even though it is the usual way to state it.
When you ask for a data structure, you are asking for a device to do
processing, but you forget to worry about the intrinsic nature of that
device, about the meaning it may have in your model of language
processing. In some sense you emphasize the doing over the understanding.
There is actually an abstract answer that applies to numerous cases,
numerous formalisms, independently of the parsing algorithm used, such
as the CKY algorithm, Earley's algorithm, and many others.
The relevant concept is that of a shared forest. It is a condensed
form of all the correct parse trees for the sentence, However, though
the concept of shared forest was widely used in the parsing
literature, it did take some time to understand what it was, other than a convenient data structure. The understanding opened it to generalizations.
Here I am skipping several fine points, see my answer to another question, for more details.
The basic idea (described in a 1995 paper by Lang and in the Grune-Jacobs book) relies on the fact that context-free languages, and
many other syntactic formalisms are closed under intersection with
regular languages (Type-3 grammars in Chomsky hierarchy). Furthermore, this closure property is constructive,
which means that given a grammar G (in some syntactic formalism, such
as CF grammar, or tree adjoining grammar, or many others) generating all syntactically
correct sentences of the language, and a formal specification R of the regular
language, it is possible to exhibit another grammar F, that generates
only the syntactically correct sentences that belong to the regular
set, with exactly the same ambiguities as with the original grammar G. This
grammar F is a shared forest (there are many equivalent ways of building such a grammar - see Billot & Lang, The structure of shared forests in ambiguous parsing). Basically, the relevant rules of the original grammar are homomorphique images of the rules of the shared forest, through a renaming homomorphism of the non terminals. The shared forest uses "specialized copies" of the non-terminals of the original grammar so as to control more tightly the generative power of its rules.
A set of one sentence is a regular set, and the construction
applies. Then, the shared forest F can be used a a generative grammar
that generates only a single sentence, but with differents parse-trees
corresponding to all the parses with the original grammar G. So, for example, it can be used to enumerate all the correct parse-trees for the sentence.
This can generalize to many situations. For example, when there is
phonological ambiguity, as in the question
Phonological ambiguity that changes the syntactic structure, this ambiguity
regarding the words actually uttered can be represented by a word
lattice, which actually defines formally a regular set of (not
necessarily syntactically correct) sentences.
The same construction intersecting the regular set with the grammar G
can be used, accounting at the same time for lexical/phonological
ambiguity and for syntactic ambiguity.
Now, what about this construction of the intersection. For CF
grammars, there is an old construction that was published some 50
years ago (Bar-Hillel, Perles, Shamir 1961). All later algorithms, such as CKY, Earley, chart parsing,
etc, that produce a shared forest are actually only variants of that
construction that may optimize some steps so as to avoid some useless
construction steps while producing the shared forest F. Similar
constructions exist for many other classes of grammar than the CF
The next issue is to develop techniques to choose the right tree in
the forest. This can be achieved in various ways but remains a very
open topic. For example it is possible to associate features or data
with specific algebraic characteristics (semi-ring) to the lexicon and
parts of speech, together with composition rules associated to the
grammar rules, to identify the "better" parse-tree. The Viterbi
techniques to chose a most-likely parse-tree according to some
probabilities fall in this category. Alternatively, the choice of
correct parse-trees may be postponed to later stages of analysis.
This is (the skeleton of) the whole story, afaik, regarding shared
forest. Much is still being developped on that basis.
It may seem too abstract, but it gives a good and actually simple
mathematical understanding for organizing the technology. But that
does not mean that all is simple when you get into actual details, for
example with sophisticated feature structures.
Another advantage of the approach is that it gives a cleaner view of
issues by separating the operational from the denotational. What this
means is that the relevant entities you may be interested in, such as
trees or forests, are specified by abstract mathematical definitions,
on the basis of desirable properties, without specifying any actual
method to effectively compute them. The operational algorithms that
will compute them (the parsing algorithms) are elaborated separately,
and have to be proved correct with respect to the denotational
definition. This separates the issues of conceptual perspicuity and
computational correctness and effectiveness.
Another point is that the complexity of the relevant structures can be analyzed from the mathematical definitions, independently of the algorithms that computes them.
Finally, to come back to your question, shared forest have gained wide acceptance among NLP practitioners. The abstract view of it as the grammar of an intersection is less well known by those who are not mathematically oriented, though it is nearly 20 years old. This ignorance/rejection of mathematics is unfortunately the source of much waste of time and energy.
Of course, the grammar view of the shared forest is an abstraction, which may be implemented in various ways, some being more easily computed with than others. Hence the grammar is sometimes a bit harder to see when described an an implemented structure in some algorithm descriptions. It may also happen, as in the case of Earley's algorithm, that the parse forest grammar is derived from a binarized version of the original grammar.
Bibliography: search the web with the keywords: parsing intersection forest - many papers are open access somewhere.
Some references on stackexchange: