Deep NLP

5 episodes · follows chapter 19 of the textbook

Context-Free Grammars and Constituency Parsing

Constituency from first principles. Constituency and Context-Free Grammars: Grammars as Programs treats grammars as programs: formal languages as sets, CFGs as recursive generators and recognizers, and the Chomsky hierarchy as a hierarchy of machines (regex, recursive descent, general programs). Treebanks, Ambiguity, and Chomsky Normal Form: Why Parses Explode counts ambiguity exactly (Catalan numbers via the recurrence and Raney's lemma) and builds Chomsky normal form. The CKY Algorithm: Parsing as Interval Dynamic Programming derives CKY as interval dynamic programming with backpointers, counts and an animated chart. Statistical and Neural Span Parsing: Probabilities, Heads, and PARSEVAL adds probabilities (PCFG, Viterbi and inside CKY in log space), heads, parent annotation, span-based neural parsing and PARSEVAL. Combinatory Categorial Grammar: Parsing as Type Checking recasts grammar as a type system with CCG.

Progress — loading…

Objectives

Language

  • Identify constituents with substitution, movement, coordination and fragment tests
  • Explain attachment and coordination ambiguity and why treebanks changed parsing research
  • Explain the PCFG independence assumption and the parent-annotation and head-lexicalization fixes
  • Describe span-based neural constituency parsing and evaluate parsers with PARSEVAL
  • Explain how CCG handles non-constituent coordination and relative-clause gaps

Math & data structures

  • Define formal languages and CFGs; prove with pigeonhole that finite automata cannot recognize a^n b^n
  • Derive the Catalan recurrence and closed form (Raney's lemma) and their 4^n growth
  • Derive CKY's recurrence, valid fill orders and O(n^3 |G|) cost; use semirings (bool, count, Viterbi, inside)
  • Estimate PCFGs by MLE and compute tree and sentence probabilities in log space
  • Read CCG categories as directional function types; apply application, composition and type raising

Code

  • nlpcore.structure.cfg: Grammar, Tree, random generation, top-down recognizer with left-recursion curtailment, heads
  • nlpcore.structure.cnf: grammar-level CNF (TERM/BIN/DEL/UNIT) with undo, and tree-level binarization/Markovization
  • nlpcore.structure.cky: CKY with backpointers, counts, event log, fill orders; span-score decoding
  • nlpcore.structure.pcfg: MLE, probabilistic CKY, inside algorithm, toy treebank generator
  • nlpcore.structure.ccg: categories, combinators with semantics, CKY over categories
  • nlpcore.eval.parseval: labeled bracketing P/R/F1 (evalb conventions), crossing brackets, exact match

Episodes

  1. Constituency and Context-Free Grammars: Grammars as Programs18 min · 32 cues

    Constituents, CFG definition, derivations, Chomsky hierarchy, grammars as programs.

  2. Treebanks, Ambiguity, and Chomsky Normal Form: Why Parses Explode19 min · 33 cues

    Penn Treebank, attachment ambiguity, Catalan numbers (Concrete Math), CNF conversion.

  3. The CKY Algorithm: Parsing as Interval Dynamic Programming17 min · 37 cues

    Bottom-up chart parsing DP, O(n³|G|), backpointers.

  4. Statistical and Neural Span Parsing: Probabilities, Heads, and PARSEVAL20 min · 32 cues

    PCFGs, probabilistic CKY, neural span scoring, evaluation (PARSEVAL), heads.

  5. Combinatory Categorial Grammar: Parsing as Type Checking17 min · 31 cues

    Categories as types, function application/composition (a type-checker for language).

Exercises

ExerciseTierLadderTime
A grammar as a dict: random generation, recursive-descent recognition, and the finite-state wall browserPredict · Scratch60 min
Why ambiguity explodes (Catalan numbers three ways) and a language-preserving CNF converter browserPredict · Scratch75 min
CKY as interval DP: chart, backpointers, parse counts and an animation event log browserScratch · Compose75 min
PCFG from a treebank, Viterbi CKY in log space, and PARSEVAL, hardened browserScratch · Harden90 min
Break CKY three ways: wrong fill order, no unary closure, probabilities without logs browserBreak it · Predict60 min
Probe a claim: does parent annotation help a treebank PCFG? (paired seeds, data-size sweep) browserProbe a claim · Predict60 min
Port a minimal span-based neural constituency parser to PyTorch (NumPy reference included) gpuPort · Scratch120 min
A tiny CCG parser as a type checker: categories, application, composition, type raising, semantics browserScratch · Compose · Predict90 min

Labs

Library contributions

Files in nlpcore this module teaches you to write.

Sources

  1. A. Ades & M. Steedman. On the order of words. Linguistics and Philosophy 4(4):517-558, 1982
  2. K. Ajdukiewicz. Die syntaktische Konnexität. Studia Philosophica 1:1-27, 1935
  3. J. K. Baker. Trainable grammars for speech recognition. In Speech Communication Papers for the 97th Meeting of the Acoustical Society of America, 1979 (inside-outside algorithm)unverified
  4. Y. Bar-Hillel. A quasi-arithmetical notation for syntactic description. Language 29:47-58, 1953
  5. Berkeley Neural Parser (benepar), github.com/nikitakit/self-attentive-parser; spaCy plugin · link
  6. Black et al. A Procedure for Quantitatively Comparing the Syntactic Coverage of English Grammars. DARPA Speech and Natural Language Workshop, 1991 (PARSEVAL) · link
  7. Backus-Naur form history: Backus 1959 (IAL/ALGOL 58), Naur and the ALGOL 60 report, Knuth 1964 CACM letter, Ingerman 1967 'Panini-Backus form' · link
  8. N. Chomsky. Three models for the description of language. IRE Transactions on Information Theory IT-2(3):113-124, 1956
  9. N. Chomsky. Syntactic Structures. Mouton, 1957 ('colorless green ideas sleep furiously')
  10. N. Chomsky. On certain formal properties of grammars. Information and Control 2(2):137-167, 1959 (Chomsky normal form)
  11. Church & Patil. Coping with Syntactic Ambiguity or How to Put the Block in the Box on the Table. American Journal of Computational Linguistics 8(3-4):139-149, 1982 · link
  12. John Cocke, credited with an early version of the CKY algorithm (often cited as Cocke & Schwartz 1970)
  13. M. Collins. Three Generative, Lexicalised Models for Statistical Parsing. ACL 1997 · arXiv:cmp-lg/9706022
  14. M. Collins. Head-Driven Statistical Models for Natural Language Parsing. PhD thesis, University of Pennsylvania, 1999
  15. Graham, Knuth & Patashnik, Concrete Mathematics, 2nd ed., sec. 7.5 (convolution recurrence for parenthesizations; Catalan numbers; Raney's lemma; Fuss; Catalan 1830s)
  16. J. Earley. An efficient context-free parsing algorithm. Communications of the ACM 13(2):94-102, 1970 (n^3 general, n^2 unambiguous, linear on a large class)
  17. J. Eisner. Efficient Normal-Form Parsing for Combinatory Categorial Grammar. ACL 1996 · arXiv:cmp-lg/9605038
  18. Geng, Josifoski, Peyrard, West. Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning. EMNLP 2023 · arXiv:2305.13971
  19. Hewitt & Manning. A Structural Probe for Finding Syntax in Word Representations. NAACL 2019 · link
  20. J. Hockenmaier & M. Steedman. CCGbank: A Corpus of CCG Derivations and Dependency Structures Extracted from the Penn Treebank. Computational Linguistics 33(3):355-396, 2007 · link
  21. M. Johnson. PCFG models of linguistic tree representations. Computational Linguistics 24(4):613-632, 1998 (parent annotation)
  22. F. Karlsson. Constraints on multiple center-embedding of clauses. Journal of Linguistics 43(2), 2007 · link
  23. T. Kasami. An efficient recognition and syntax-analysis algorithm for context-free languages. Technical report, 1965 (DTIC AD0631692) · link
  24. Kim, Dyer & Rush. Compound Probabilistic Context-Free Grammars for Grammar Induction. ACL 2019 · arXiv:1906.10225
  25. Kitaev & Klein. Constituency Parsing with a Self-Attentive Encoder. ACL 2018 · arXiv:1805.01052
  26. N. Kitaev, S. Cao, D. Klein. Multilingual Constituency Parsing with Self-Attention and Pre-Training. ACL 2019unverified
  27. Klein & Manning. Accurate Unlexicalized Parsing. ACL 2003 · link
  28. J. Lambek. The mathematics of sentence structure. American Mathematical Monthly 65:134-170, 1958
  29. L. Lee. Fast context-free grammar parsing requires fast Boolean matrix multiplication. arXiv Dec 2001; JACM 49(1):1-15, 2002 · arXiv:cs/0112018
  30. D. Magerman. Statistical decision-tree models for parsing. ACL 1995 (head percolation)
  31. Marcus, Santorini & Marcinkiewicz. Building a Large Annotated Corpus of English: The Penn Treebank. Computational Linguistics 19(2), 1993 (J93-2004) · link
  32. G. van Rossum, P. Galindo Salgado, L. Nikolaou. PEP 617 - New PEG parser for CPython (default in 3.9; old LL(1) parser removed in 3.10) · link
  33. S. Petrov, L. Barrett, R. Thibaux, D. Klein. Learning Accurate, Compact, and Interpretable Tree Annotation. COLING-ACL 2006unverified
  34. G. N. Raney. Functional composition patterns and power series reversion. Transactions of the AMS 94:441-451, 1960 (Raney's cycle lemma) · link
  35. A. Rush. Torch-Struct: Deep Structured Prediction Library. arXiv, Feb 2020 · arXiv:2002.00876
  36. S. Sekine & M. Collins. evalb (1997), the reference PARSEVAL scorer
  37. S. M. Shieber. Evidence against the context-freeness of natural language. Linguistics and Philosophy 8(3):333-343, 1985 (Swiss German cross-serial dependencies)
  38. Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft (Aug 19, 2026), Ch. 19 Context-Free Grammars and Constituency Parsing; Appendices E, F, G · link · §19.1, 19.2, 19.3, 19.4, 19.5, 19.6, 19.7, 19.8, 19.9, 19.10, E, F, G
  39. M. Steedman. The Syntactic Process. MIT Press, 2000
  40. Stern, Andreas & Klein. A Minimal Span-Based Neural Constituency Parser. ACL 2017 · arXiv:1705.03919
  41. L. G. Valiant. General context-free recognition in less than cubic time. Journal of Computer and System Sciences 10(2):308-315, 1975
  42. K. Vijay-Shanker & D. Weir. The equivalence of four extensions of context-free grammars. Mathematical Systems Theory 27(6):511-546, 1994
  43. D. H. Younger. Recognition and parsing of context-free languages in time n^3. Information and Control 10(2):189-208, 1967
  44. L. Zettlemoyer & M. Collins. Learning to Map Sentences to Logical Form: Structured Classification with Probabilistic Categorial Grammars. UAI 2005 · arXiv:1207.1420