Intuitively, backtracking is the cause for the exponential complexity of the parsers discussed so far, since if a particular subgoal cannot be solved, all the work since the most recently solved goal (for which there are still alternatives) is undone.
The two sentences in Figure 2.9 and the two grammar rules, a standard method of covering the two constructions, illustrate how all three parsing algorithms would fall down in the efficiency stakes.
Consider the case where the 
of in the second sentence in
Figure 2.9 is being analysed using
the two rules also shown, assuming that appropriate rules exist for
the 
, Bob.
The top rule would be analysed first and the word gave
assigned to the category 
, followed by the phrase every
dentist being assigned to the category. The three parsers
so far would then look for the word to which
starts a preposition phrase (
). However, since the next word
is a, backtracking would occur. Assuming there
are no alternatives for the every
dentist, or the gave, the second
rule would be examined.
At this point the word gave would be reassigned
to the category , and likewise for the every
dentist. Redundant computation has clearly been done here.
In an attempt to remove the occurrence of such redundant work, chart, or table parsing was created. These methods use a chart to store the edges of all possible parse trees, and they iteratively scan the sentence to be parsed, building up the table of all possible parses as they go. Thus no backtracking is required, and the exponential complexity of parsing has effectively been removed (although, to actually enumerate every parse would still be an exponential operation).
Two chart parsing techniques are given a brief overview below.
