IMPROVEMENTS TO BACKTRACK PARSERS ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Though stack-based backtrack parsing is simple and algorithmically elegant, it is unfortunately not very practical. The following are some improvements one can make, and they are interesting because similar techniques can be used to improve chart-parsers. But even with these improvements, backtrack parsers incur exponential running time (in the length n of a sentence) in the worst case, unlike chart-parsers, which are O(n^3) in the worst case. 1. PREVENT INFINITE LOOPING. ~~~~~~~~~~~~~~~~~~~~~~~~ For top-down backtrack parsers, infinite regresses can occur for left-recursive sets of rules like Nbar --> Nbar PP (here a single rule creates the problem) or even unitary ones like AP[attr] --> AP[pred], AP[pred] --> AP[attr]. (The first creates an attributive AP, i.e., one that can be placed as a modifier in front of a noun, out of a predicative AP, i.e., one that can come after verbs like "is" or "seems" in a sentence; the second rule does the converse. This is fairly plausible, because some adjectives, like "pink", seem to be inherently predicative -- e.g., "the flower is pink", yet can be put in modifier position, as in "pink flower"; others, like "phony", seem inherently attributive -- e.g., "phony van Gogh painting", yet can be put in predicative position, as in "this van Gogh painting is phony".) In a top-down parser, an infinite regress can be avoided for left-recursive rule sets just by preferring shorter states (fewer expected constituents) to longer ones, *provided* that the left- recursive set involves at least one nonunitary rule. That's because cyclic use of rules will generate more and more expected constituents, and when this gets larger than the number of remaining words, we know it can't be right (assuming that there are no "epsilon productions" -- ones with a null RHS). For unitary cycles, we just need to keep track of which states we've created at each position, and not duplicate such states. For bottom-up parsers (of the kind we've considered), only unitary cycles can give an infinite regress (again, assuming no epsilon rules), and can again be avaoided by not creating identical states at the same word position. 2. DELETE NON-VIABLE STATES ~~~~~~~~~~~~~~~~~~~~~~~~ In a stack-based bottom-up parsing, we may find ourselves doing shifts or reductions on the right end of the state that can't possibly fit with the left part of the state. For example, in the grammar we used for "The rich benefit the most", we can get to a state (NP) at position 4, and when we shift in Det (for "the") we get the non-viable state (NP Det), i.e., this simply is not a sequence of constituents allowed by the grammar. Other non-viable states that occur in the example are (Det A V), (Det A N Det), and several others. These can be precomputed from the grammar and hence prevented from being generated during parsing. This is a technique used in LR(k) parsing of programs (parsing with k lookahead symbols) 3. USE TOP-DOWN FILTERING ~~~~~~~~~~~~~~~~~~~~~~ In a top-down parser, we can avoid applying rules X --> Y1 Y2 ... if the leftmost category Y1 of the expanded category X cannot possibly be initiated by the word that must be matched next. For example, in "The rich benefit the most", when we have already parsed "The rich benefit" as an NP, and are thus left with a state (VP) at position 4, there is no point in applying any of the three VP expansions, because the grammar doesn't allow a VP to start with at Det (which is the category of the next word, "the"). Again these "reachability" relations can be precomputed, and used to filter out many useless actions in parsing.