Context-Free Grammar
Tutorial Section
Context-Free Grammar
Learn the mathematical rules of Context-Free Grammars used to define and evaluate Constituency structure in language.
Context-Free Grammars (CFG)
A Context-Free Grammar (CFG) is a mathematical system of strict rewriting rules used to generate syntactically valid sentences in a language. It forms the backbone of Constituency Parsing.
It is called "context-free" because the left-hand side of every rule consists of a single non-terminal symbol, meaning the rule can be applied regardless of the surrounding context.
Anatomy of a CFG
A simple CFG for English contains rules written as A → B C (meaning "A consists of B and C").
Lexicon Rules (Emits Words)
Det → "the" | "a"
Noun → "dog" | "cat"
Verb → "chased" | "saw"
Prep → "with" | "in"
Noun → "dog" | "cat"
Verb → "chased" | "saw"
Prep → "with" | "in"
Structural Rules (Combines phrases)
S → NP VP
NP → Det Noun
VP → Verb NP
NP → Det Noun
VP → Verb NP
Generating a Sentence
Starting from the ROOT state S (Sentence), we apply the substitution rules from top to bottom:
1. S
2. NP VP
3. Det Noun VP
4. "the" "dog" VP
5. "the" "dog" Verb NP
6. "the" "dog" "chased" Det Noun
7. "The dog chased the cat."
The Problem with Hand-Coded CFGs: Linguistic ambiguity is massive. You can write 1,000 rules, and an English sentence will still find a way to be ambiguous (e.g., prepositional attachment: "I shot an elephant in my pajamas"). Therefore, modern NLP uses Probabilistic Context-Free Grammars (PCFGs), adding mathematical probabilities learned from data to every rule to pick the "most likely" valid tree.