Context-free Grammar (CFG)

A context-free grammar (CFG) is a set of rules that define how to build a language, where a language just means a set of valid strings. Each rule replaces one symbol with other symbols, and only a single non-terminal is replaced at a time. This is something like regex where we can replace certain words using re.sub(), etc.

That single-symbol restriction is what makes the grammar context free, because the rules will happen to the corpus regardless of the context.

A CFG by itself only says which strings are legal. It becomes useful once a parser such as shift-reduce parsing walks a real sentence against it.

Components

The category names in the rules (NP, VP, Det, Nominal) are ordinary grammar terms rather than NLP jargon, and they are defined in Linguistic Basics.

Component	Meaning	Example
Terminals	the words or letters used as the basic building block of a sentence	the, dog, chased
Non-Terminals	a sub-language inside the grammar, an abstract category or a placeholder	NP, VP, Nominal
Start Symbol (S)	the special non-terminal that every derivation begins from	S

• terminals are the leaves of the parse tree, so nothing expands out of them
• non-terminals are written in the example as nounPhrase and verbPhrase, shortened to NP and VP
• there is exactly one start symbol per grammar

Rule Notation

• rules are written LHS -> RHS, where the left-hand side is always a single non-terminal
• the pipe | is shorthand for "or", so VP -> V NP | V is 2 separate rules written on 1 line
• the same non-terminal can appear on both sides, which is recursion and is what lets a finite grammar describe infinitely many sentences

Example: an English fragment

Grammar Rule	Example
S -> NP VP	I + want a morning flight
NP -> Pronoun	I
NP -> Proper-Noun	Los Angeles
NP -> Det Nominal	a + flight
Nominal -> Nominal Noun	morning + flight
Nominal -> Noun	flights
VP -> Verb	do
VP -> Verb NP	want + a flight
VP -> Verb NP PP	leave + Boston + in the morning
VP -> Verb PP	leaving + on Thursday
PP -> Preposition NP	from + Los Angeles

• Nominal -> Nominal Noun is recursive, so it stacks modifiers such as "morning flight" and "early morning flight"

Example: an arithmetic grammar

CFG is not limited to language. The same notation describes expressions, written here in BNF style where ::= replaces the arrow.

<start> ::= <exp>
<exp>   ::= <exp><op><exp> | (<exp>) | <coef>*<var> | <var>
<op>    ::= + | - | * | /
<coef>  ::= a | b
<var>   ::= x | y

CFG in NLTK

from nltk import CFG
 
grammar = CFG.fromstring("""
  S -> NP VP
  NP -> Det N
  VP -> V NP | V
  Det -> 'the' | 'a'
  N -> 'dog' | 'cat' | 'cookie'
  V -> 'chased' | 'slept' | 'ate' | 'saw'
""")
 
sentences = ['the dog chased the cat', 'the cat slept', 'the dog ate a cookie']
print(grammar)

Grammar with 13 productions (start state = S)
    S -> NP VP
    NP -> Det N
    VP -> V NP
    VP -> V
    Det -> 'the'
    Det -> 'a'
    N -> 'dog'
    N -> 'cat'
    N -> 'cookie'
    V -> 'chased'
    V -> 'slept'
    V -> 'ate'
    V -> 'saw'

Counting productions

The grammar was typed as 6 lines but prints as 13 productions, because every | alternative is counted as its own production. Terminals are quoted in NLTK, and non-terminals are bare.

• CFG.fromstring() takes the rules as a triple-quoted string
• the start state is taken from the first rule, so S here