Introduction to Context-Free Grammar (CFG)

A grammar is a set of rules that defines which sequences of words form valid sentences in a language. A Context-Free Grammar (CFG) is the most common formalism used in NLP to describe sentence structure.

Formal Definition

A CFG is a 4-tuple G = (N, Σ, R, S):

"Context-free" means each rule's left-hand side is a single non-terminal, applied regardless of surrounding context.

A Simple English Grammar

S  -> NP VP
NP -> Det N | Det Adj N | 'Riya'
VP -> V NP | V
Det -> 'the' | 'a'
Adj -> 'quick' | 'lazy'
N  -> 'dog' | 'cat' | 'book'
V  -> 'chased' | 'reads'

This grammar can generate (and parse) sentences like:

• "Riya reads a book"
• "the quick dog chased the lazy cat"

Building and Testing a CFG in NLTK

import nltk
from nltk import CFG

grammar = CFG.fromstring("""
S -> NP VP
NP -> Det N | Det Adj N | 'Riya'
VP -> V NP | V
Det -> 'the' | 'a'
Adj -> 'quick' | 'lazy'
N -> 'dog' | 'cat' | 'book'
V -> 'chased' | 'reads'
""")

print(grammar.start())        # S
print(grammar.productions())  # list of all production rules

Derivation — Generating a Sentence Step by Step

S
-> NP VP                        (S -> NP VP)
-> Det Adj N VP                 (NP -> Det Adj N)
-> the Adj N VP                 (Det -> 'the')
-> the quick N VP                (Adj -> 'quick')
-> the quick dog VP               (N -> 'dog')
-> the quick dog V NP              (VP -> V NP)
-> the quick dog chased NP          (V -> 'chased')
-> the quick dog chased the lazy cat (NP -> Det Adj N -> ...)

Each line applies exactly one production rule — this sequence is called a derivation, and the tree formed by all the rule applications is a parse tree (covered in the next lesson).

Why CFGs Cannot Capture Everything

CFGs handle hierarchical, recursive structure well (e.g. "the book [that Riya read] [that won an award]") but cannot naturally express certain context-sensitive agreement rules, such as subject-verb number agreement ("the dog runs" vs "the dogs run"), without exploding the rule set with separate singular/plural versions of every rule. This is one motivation for more expressive grammar formalisms (e.g. unification grammars) used in advanced NLP systems — beyond the scope of this course, but good to be aware of.

CFG vs Regular Grammar

CFGs are the theoretical foundation for the parsing algorithms — top-down, bottom-up, and CYK — that we study next.