Top-down parsing

Top-down parsing (recursive descent)

Start from S and rewrite the leftmost goal with a rule, again and again, until the goal is a part of speech that can be checked against the next word. The parser predicts structure before seeing the words that justify it: it is goal-driven, or hypothesis-driven.

Configuration and operations

A configuration is a list of goals (categories still to be found, leftmost first) and a position in the input. It starts with the goal list [S] at position 0.

Predict: The first goal is a category A: replace it with the right-hand side of a rule A → Y₁ … Yₖ. Every rule for A is a choice point.
Match: The first goal is a part of speech that the next word has in the lexicon: remove the goal and read the word.
Backtrack: No operation applies (or the goals and the input do not run out together): return to the most recent choice point and take its next alternative.
Success: No goals are left and every word has been read.

parse(goals, i):                          # i = next word to read
    if goals is empty: return i == n
    X, rest = first(goals), others(goals)
    if X → w[i] is in the lexicon:          # MATCH
        if parse(rest, i + 1): return true
    for each rule X → Y1 … Yk, in order:    # PREDICT (choice point)
        if parse(Y1 … Yk + rest, i): return true
    return false                            # dead end: BACKTRACK

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

The tree is the record of the predictions: each Predict step adds the daughters of a node, so a successful run is a leftmost derivation S ⇒ … ⇒ w₁ … wₙ read off from left to right.

Properties

Left recursion makes it loop. With a rule such as NP → NP PP, predicting NP puts NP back as the first goal without reading a word, so a depth-first parser can expand it forever. The usual remedies are to rewrite the grammar without left recursion, or to stop a branch when there are more goals than words left (a bound that works because there are no ε-rules).
Wasted predictions. The parser expands rules that cannot start with the next word, and only finds out when it reaches the parts of speech. Looking at the next word first (a look-ahead table, or the left-corner relation) avoids most of this.
Repeated work. After backtracking it rebuilds sub-trees it had already found (e.g. the same NP under two different VP rules). In the worst case the running time is exponential in the length of the sentence.
Deterministic versions for restricted grammars (LL(k): predict using k words of look-ahead, no backtracking) are standard in compilers (Aho & Ullman 1972).

In this tool

The “Goals” row is the goal list; dashed nodes in the tree are the goals still to be proved. Rules are tried in the order you wrote them; the parser stops a left-recursive branch as soon as a category has been predicted on the same word more times than there are words left, and reports the infinite loop that a real depth-first parser would enter. Try the left-recursion example to see it.

Try it on an example → See it loop on left recursion →

References

Aho, A. V. & Ullman, J. D. (1972). The Theory of Parsing, Translation, and Compiling. Vol. I: Parsing. Englewood Cliffs, NJ: Prentice-Hall.
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.
Pereira, F. C. N. & Shieber, S. M. (1987). Prolog and Natural-Language Analysis. CSLI Lecture Notes 10. Stanford, CA: CSLI Publications.
Covington, M. A. (1994). Natural Language Processing for Prolog Programmers. Englewood Cliffs, NJ: Prentice-Hall.
Grune, D. & Jacobs, C. J. H. (2008). Parsing Techniques: A Practical Guide (2nd ed.). New York: Springer.
Abney, S. P. & Johnson, M. (1991). Memory requirements and local ambiguities of parsing strategies. Journal of Psycholinguistic Research, 20(3), 233–250.