Bottom-up parsing

Bottom-up parsing (shift–reduce)

Start from the words. Push them one at a time onto a stack and, whenever the top of the stack matches the right-hand side of a rule, replace it with the rule’s left-hand side. The parser is data-driven: it only builds what the words support, but it builds it without knowing whether it will fit into a sentence.

Configuration and operations

A configuration is a stack of sub-trees (top on the right) and a position in the input. It starts with an empty stack at position 0.

Shift: Push the next word onto the stack.
Reduce: The top k elements of the stack are Y₁ … Yₖ and there is a rule A → Y₁ … Yₖ (or a lexical entry A → w for a word on top): replace them with a node A having them as daughters. Every applicable reduction, and the shift, is a choice point.
Backtrack: Nothing can be reduced and nothing is left to shift: go back to the last choice point.
Success: The input is read and the stack holds exactly one S.

parse(stack, i):
    if i == n and stack == [S]: return true
    if top(stack) is a word w:                     # tag it before going on
        for each category C with C → w:            # REDUCE (lexical)
            if parse(pop(stack) + [C], i): return true
        return false
    for each rule A → Y1 … Yk with stack ending in Y1 … Yk:    # REDUCE
        if parse(pop k (stack) + [A], i): return true
    if i < n:                                      # SHIFT
        if parse(stack + [w[i]], i + 1): return true
    return false                                   # dead end: BACKTRACK

recognise(sentence) = parse([], 0)

Read backwards, the sequence of reductions of a successful run is a rightmost derivation of the sentence.

Properties

Left recursion is no problem (NP PP is simply reduced to NP), but ε-rules and cycles of unit rules (A → B, B → A) are: they allow reductions that consume nothing, without end.
Useless constituents. The parser builds every constituent the words allow, also those that can never be part of a complete S (a VP at the start of a sentence, for example), because it does not use top-down information.
Exponential with backtracking, like top-down parsing; and the order “reduce first, then shift” is only one possible policy. Shift–reduce conflicts and reduce–reduce conflicts are exactly the choice points.
For deterministic grammars the choice can be made with a parse table and look-ahead: this is LR(k) parsing (Knuth 1965), the basis of compiler generators. Kimball (1973) and much later work discuss which policy (shift or reduce first) matches human attachment preferences such as right association.

In this tool

The forest drawn at each step is the stack: one tree per stack element, with the words still to be read greyed on the right. A word on top of the stack must receive a part of speech before the next word is shifted (otherwise it could never be reduced), which removes many hopeless branches without changing the result.

Try it on an example →

References

Aho, A. V. & Ullman, J. D. (1972). The Theory of Parsing, Translation, and Compiling. Vol. I: Parsing. Englewood Cliffs, NJ: Prentice-Hall.
Knuth, D. E. (1965). On the translation of languages from left to right. Information and Control, 8(6), 607–639.
Jurafsky, D. & Martin, J. H. (2009). Speech and Language Processing (2nd ed.). Upper Saddle River, NJ: Pearson Prentice Hall. Chapter 13, “Syntactic Parsing”.
Bird, S., Klein, E. & Loper, E. (2009). Natural Language Processing with Python. Sebastopol, CA: O’Reilly. Chapter 8, “Analyzing Sentence Structure”. Free online at nltk.org/book.
Grune, D. & Jacobs, C. J. H. (2008). Parsing Techniques: A Practical Guide (2nd ed.). New York: Springer.
Kimball, J. (1973). Seven principles of surface structure parsing in natural language. Cognition, 2(1), 15–47.
Abney, S. P. & Johnson, M. (1991). Memory requirements and local ambiguities of parsing strategies. Journal of Psycholinguistic Research, 20(3), 233–250.