CFG from rules to parse trees

Parsing as search

A context-free grammar says which trees are well formed; it does not say how to find the tree of a given sentence. A parsing algorithm is a strategy for exploring the space of possible partial trees, and the strategies differ in two choices: where the information comes from (the grammar, top-down, or the words, bottom-up) and what to do when more than one rule applies.

The first three algorithms on this site are backtracking parsers. They build one partial tree at a time, take the first applicable rule at every choice point and, when they reach a dead end, go back to the last choice point and try the next alternative. They are simple and close to how a person might work through a sentence, but they can redo the same work many times (exponential time in the worst case) and some of them do not terminate on some grammars.

Earley and CKY are chart (tabular, dynamic-programming) parsers. They never build the same sub-constituent twice: every partial result is stored once in a chart, together with all the ways it can be built. They run in polynomial time, O(n³) in the length of the sentence, and represent all the parses of an ambiguous sentence at once.

The order in which nodes are built

The three backtracking strategies visit the same tree in different orders. The numbers show when each node is announced: top-down predicts a node before its daughters (pre-order), bottom-up builds it after all of them (post-order), and left-corner announces it right after its first daughter.

Comparison

Memory and human sentence processing

Psycholinguists have used these strategies as models of the human parser. A recurring argument (Johnson-Laird 1983; Abney & Johnson 1991; Resnik 1992) looks at how much has to be kept in memory, that is, how many incomplete constituents are pending, for different kinds of embedding. People handle long left-branching and right-branching structures easily, but have trouble with centre-embedding (the rat the cat the dog chased killed ate the malt).

Only left-corner parsing with eager composition (attaching a projected node to its goal as soon as possible, see the left-corner page) matches the human profile. Abney & Johnson (1991) also discuss the other side of the trade-off: the more eagerly a strategy commits to structure, the more local ambiguity it must resolve early. Probabilistic versions of the chart parsers led to measures of word-by-word processing difficulty such as surprisal, computed with a probabilistic Earley parser (Stolcke 1995; Hale 2001).

Notation used on this site

• A grammar is G = ⟨N, Σ, P, S⟩: categories N, words Σ, rules P, start symbol S. Rules are written A → α; lexical rules Det → the are kept in a separate lexicon.
• Positions are counted between words: 0 before the first word, n after the last. A constituent “over [i, j]” covers words i+1 … j.
• In the trees, a dashed box is a predicted node not yet found; a dashed line links a goal to the sub-tree being built for it; the highlighted node is the one changed by the current step.
• All five algorithms here assume a grammar without ε-rules (A → ε).

References

1. Aho, A. V. & Ullman, J. D. (1972). The Theory of Parsing, Translation, and Compiling. Vol. I: Parsing. Englewood Cliffs, NJ: Prentice-Hall.
2. Grune, D. & Jacobs, C. J. H. (2008). Parsing Techniques: A Practical Guide (2nd ed.). New York: Springer.
3. Sikkel, K. (1997). Parsing Schemata: A Framework for Specification and Analysis of Parsing Algorithms. Berlin: Springer.
4. Shieber, S. M., Schabes, Y. & Pereira, F. C. N. (1995). Principles and implementation of deductive parsing. Journal of Logic Programming, 24(1–2), 3–36.
5. Kay, M. (1980). Algorithm Schemata and Data Structures in Syntactic Processing. Technical Report CSL-80-12, Xerox PARC. Reprinted in B. J. Grosz, K. Sparck Jones & B. L. Webber (Eds.), Readings in Natural Language Processing (1986), Morgan Kaufmann.
6. Jurafsky, D. & Martin, J. H. (2009). Speech and Language Processing (2nd ed.). Upper Saddle River, NJ: Pearson Prentice Hall. Chapter 13, “Syntactic Parsing”.
7. Jurafsky, D. & Martin, J. H. Speech and Language Processing (3rd ed. draft), chapter on context-free grammars and constituency parsing. Online at web.stanford.edu/~jurafsky/slp3.
8. 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.
9. Pereira, F. C. N. & Shieber, S. M. (1987). Prolog and Natural-Language Analysis. CSLI Lecture Notes 10. Stanford, CA: CSLI Publications.
10. Covington, M. A. (1994). Natural Language Processing for Prolog Programmers. Englewood Cliffs, NJ: Prentice-Hall.
11. Johnson-Laird, P. N. (1983). Mental Models: Towards a Cognitive Science of Language, Inference, and Consciousness. Cambridge: Cambridge University Press.
12. Abney, S. P. & Johnson, M. (1991). Memory requirements and local ambiguities of parsing strategies. Journal of Psycholinguistic Research, 20(3), 233–250.
13. Resnik, P. (1992). Left-corner parsing and psychological plausibility. In COLING 1992 Volume 1: The 14th International Conference on Computational Linguistics. aclanthology.org/C92-1032
14. Kimball, J. (1973). Seven principles of surface structure parsing in natural language. Cognition, 2(1), 15–47.
15. Stolcke, A. (1995). An efficient probabilistic context-free parsing algorithm that computes prefix probabilities. Computational Linguistics, 21(2), 165–201.
16. Hale, J. (2001). A probabilistic Earley parser as a psycholinguistic model. In Proceedings of the Second Meeting of the North American Chapter of the Association for Computational Linguistics (NAACL 2001). aclanthology.org/N01-1021