It works by building tree structures corresponding to every valid substring of the input, and storing them in memory. Then later on, it may combine some of the subtrees to make larger trees, which also need to be stored.
I think that all of us are instinctively terrified by the necessarily exponential behaviour of parsing every
substring. Is this really necessary? As biohisham
mentioned, limiting the ambiguity even in very small ways can help a lot—for example, think of how much natural-language freedom is allowed in Perl programs, which can still be parsed with relatively little memory overhead (I think!).