CFG from rules to parse trees

CKY parsing (Cocke–Kasami–Younger)

CKY fills a triangular table bottom-up. Cell [i, j] holds every category that can span words i+1 … j. The cells for single words come from the lexicon; every longer span is built by combining two adjacent shorter spans with a binary rule. Because each cell is filled once, the whole table costs O(n³) steps.

The grammar must be binary

The classic algorithm requires Chomsky Normal Form: every rule is A → B C or A → w. Here two relaxations are used (in the spirit of Lange & Leiß 2009): rules longer than two are binarised on the fly, and unary rules A → B are applied by closure inside each cell.

VP → V NP PP     becomes     VP → V VP|NP_PP
                             VP|NP_PP → NP PP

The auxiliary categories (in grey italics in the tool) are removed again when the parse trees are read off.

The algorithm

for j = 1 … n:                                   # column by column, left to right
    T[j−1, j] = { A : A → w(j) is in the lexicon }
    close T[j−1, j] under unary rules
    for i = j−2 down to 0:                       # each column bottom-up
        for k = i+1 … j−1:                       # every split point
            for each rule A → B C with B ∈ T[i, k] and C ∈ T[k, j]:
                add A to T[i, j]   (remember B, C and k)
        close T[i, j] under unary rules A → B
accept iff S ∈ T[0, n]

Remembering how each entry was built (back-pointers) turns the recogniser into a parser; an entry built in several ways packs an ambiguity, as in the Earley chart.

Properties

• O(n³ · |G|) time and O(n²) cells, for any grammar in the required form; left recursion plays no role.
• Purely bottom-up: it builds every constituent the words allow, including those that cannot be part of any complete parse (empty cells and useless entries are visible in the table).
• The natural basis of probabilistic parsing (PCFGs: keep the best probability per category and cell, the Viterbi version, or sum them, the inside algorithm) and of many neural constituency parsers that score spans.
• Found independently by Cocke, by Kasami (1965) and by Younger (1967).

In this tool

Each step adds one category to a cell; the cells it was built from are tinted and the current cell is outlined. An “empty cell” step shows a span for which no rule applies. The list of binarised rules is under the table.

References

1. Kasami, T. (1965). An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages. Scientific Report AFCRL-65-758. Bedford, MA: Air Force Cambridge Research Laboratory.
2. Younger, D. H. (1967). Recognition and parsing of context-free languages in time n³. Information and Control, 10(2), 189–208.
3. Cocke, J. & Schwartz, J. T. (1970). Programming Languages and Their Compilers: Preliminary Notes. New York: Courant Institute of Mathematical Sciences, New York University.
4. Lange, M. & Leiß, H. (2009). To CNF or not to CNF? An efficient yet presentable version of the CYK algorithm. Informatica Didactica, 8.
5. Hopcroft, J. E., Motwani, R. & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Boston: Addison-Wesley.
6. Graham, S. L., Harrison, M. A. & Ruzzo, W. L. (1980). An improved context-free recognizer. ACM Transactions on Programming Languages and Systems, 2(3), 415–462.
7. Jurafsky, D. & Martin, J. H. (2009). Speech and Language Processing (2nd ed.). Upper Saddle River, NJ: Pearson Prentice Hall. Chapter 13, “Syntactic Parsing”.
8. 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.
9. Grune, D. & Jacobs, C. J. H. (2008). Parsing Techniques: A Practical Guide (2nd ed.). New York: Springer.