TopolearnParsing shows how sentence structure is represented and why ambiguity is the central problem of NLP.
A context-free grammar (CFG) describes sentence structure with rewrite rules. nltk.CFG.fromstring reads them:
S -> NP VP
NP -> Det N | Det N PP | 'I'
VP -> V NP | VP PP
PP -> P NPNon-terminals (S, NP, VP) are expanded until only terminals (quoted words) remain. A parser finds every tree that derives a given token list from the start symbol.
nltk.ChartParser(grammar) uses dynamic programming to store partial results in a chart, avoiding the exponential re-work of naive recursive descent; RecursiveDescentParser and ShiftReduceParser exist for teaching but are slower or incomplete (the recursive descent parser loops on left-recursive rules like VP -> VP PP).
parser.parse(tokens) yields nltk.Tree objects. Trees support tree.label(), tree.leaves(), indexing into children, tree.pretty_print() for an ASCII drawing, and tree.productions().
The classic lesson is ambiguity: "I shot an elephant in my pajamas" has two parses depending on whether the PP attaches to the verb or the noun. Real grammars give sentences hundreds or thousands of parses. Probabilistic CFGs (nltk.PCFG with ViterbiParser) rank them by rule probabilities, and modern parsers (spaCy, Stanza) learn dependency structures from treebanks instead of hand-written rules.
Hand-written CFGs remain useful for small controlled languages, such as command interfaces and form-like queries.
Example
import nltk
grammar = nltk.CFG.fromstring('''
S -> NP VP
PP -> P NP
NP -> Det N | Det N PP | 'I'
VP -> V NP | VP PP
Det -> 'an' | 'my'
N -> 'elephant' | 'pajamas'
V -> 'shot'
P -> 'in'
''')
parser = nltk.ChartParser(grammar)
tokens = "I shot an elephant in my pajamas".split()
trees = list(parser.parse(tokens))
print(len(trees)) # 2 -- structurally ambiguous
for t in trees:
print(t)
# (S (NP I) (VP (VP (V shot) (NP (Det an) (N elephant))) (PP (P in) ...)))
# (S (NP I) (VP (V shot) (NP (Det an) (N elephant) (PP (P in) ...))))
print(trees[0].label(), trees[0].leaves()[:2]) # S ['I', 'shot']Remember
- CFG rules rewrite non-terminals until words remain
- ChartParser finds all parses efficiently with dynamic programming
- Parse results are nltk.Tree objects with label(), leaves(), pretty_print()
- Ambiguity yields many trees; PCFGs and learned parsers rank them
Watch out for
- Using RecursiveDescentParser with a left-recursive rule like VP -> VP PP, which never terminates.