AI Glossary / Graphs and symbolic AI / Intermediate
Probabilistic context-free grammar
Definition
A probabilistic context-free grammar, or PCFG, is a context-free grammar whose production rules have probabilities. For each nonterminal symbol, the probabilities of its alternative expansions sum to one. The grammar assigns probabilities to parse trees and, by summing over compatible trees, to strings. It provides a structured way to represent uncertainty about how a sequence is generated or parsed.
What it means
A context-free grammar describes which structures are allowed. A PCFG adds a model of how likely different allowed structures are. If a sentence has several possible parse trees, their probabilities can help rank the interpretations.
The probabilities are conditional on the left-hand-side nonterminal in the basic model. They do not automatically depend on the entire sentence, neighboring words, or the full ancestor structure. This simplifying assumption makes inference manageable but limits how much context a basic PCFG captures. More elaborate parsing models can add information beyond these simple rule probabilities.
How it works
Specify terminal symbols, nonterminal symbols, a start symbol, and production rules. Give each set of alternatives sharing a left-hand side a normalized probability distribution. Generate a tree by selecting expansions until only terminals remain.
The probability of a particular finite parse tree is the product of the probabilities of every rule occurrence used in that tree. A string's probability sums the probabilities of all trees yielding that string. Finding the highest-probability tree and computing the total string probability are different tasks. Dynamic programming can share computations across possible parses rather than enumerating them independently. Recursive grammars also need attention to termination: local rule normalization alone does not guarantee that all probability mass reaches finite strings.
Three practical examples
- A language-processing course can rank alternative grammatical structures for an ambiguous sentence.
- A structured command parser can represent uncertainty among several allowed interpretations within a carefully defined grammar.
- A research prototype can generate synthetic sequences from a grammar and compare their predicted frequencies with sampled outputs, while checking termination and coverage.
Think of it this way
Think of a branching recipe book in which each instruction offers weighted alternatives. A complete cooking path receives a weight from all its choices. The analogy is limited because grammar derivations create hierarchical symbolic structures, and several different derivations can produce the same final sequence of words or symbols.
Worked example
Use an invented grammar with start symbol S. Its rules are S → A B with probability 0.6 and S → C D with probability 0.4. A produces x with probability 0.5 or z with probability 0.5. B always produces y. C always produces x. D produces y with probability 0.25 or w with probability 0.75.
The string x y has two parse trees. The A B tree has probability 0.6 × 0.5 × 1 = 0.3. The C D tree has probability 0.4 × 1 × 0.25 = 0.1. Therefore the total probability of x y is 0.3 + 0.1 = 0.4.
Conditional on observing x y, the A B tree has probability 0.3/0.4 = 0.75 and the C D tree has probability 0.25. The most probable parse has probability 0.3 before conditioning, but the string has probability 0.4. Confusing those quantities loses the contribution of the second derivation.
The other possible strings are z y with probability 0.3 and x w with probability 0.3. Their probabilities, together with x y, sum to 1. This grammar is nonrecursive, so every generated derivation terminates.
Illustrative case study
In a fictional document-processing experiment, a team uses a small grammar to parse standardized request lines. The parser returns one high-scoring tree, and a developer initially labels that score “probability of the text.” A review discovers that some lines have multiple permitted parse trees.
The team separates the best-parse score from the total probability summed over parses and examines ambiguous cases with domain reviewers. It also records which request formats the grammar cannot generate. The case illustrates correct interpretation of model outputs, not evidence that the grammar captures unrestricted natural language.
Common misconceptions and mistakes
A high-probability parse is not necessarily the intended meaning or a true statement. The score reflects the grammar and its learned or assigned probabilities. Missing context, unrepresentative training data, or an inadequate grammar can favor the wrong structure.
Do not add rule probabilities along a single derivation; multiply them. Sum when combining alternative derivations of the same string. Also distinguish zero probability because no rule supports a structure from low probability under an existing rule. Finally, a locally normalized recursive grammar can still place probability on nonterminating derivations, so consistency requires more than checking row sums.
Business use
PCFGs can be useful where transparent hierarchical structure matters and the language is restricted enough to model. They make it possible to inspect which production choices support a parse and to separate grammatical coverage from ranking among alternatives.
For a business-facing parser, evaluate complete tasks: supported formats, ambiguity handling, unknown vocabulary, and consequences of a mistaken interpretation. Provide a review path when multiple parses remain plausible. A probability generated by the grammar should not be presented as a calibrated confidence in a business conclusion without additional validation.
People also ask
Does “context-free” mean the system ignores all context in every sense?
It describes the form of grammar productions and, in a basic PCFG, local conditioning of expansion probabilities. A larger application may still supply context through other components.
Can one string have several probabilities?
It can have several parse-tree probabilities, but its total probability is their sum under the grammar.
Must rule probabilities be learned?
No. They can be specified for a toy model or estimated from data. Their origin and adequacy should be documented.
Check your understanding
In the worked grammar, what is the conditional probability of the C D parse given x y?
Answer: Its joint parse-and-string probability is 0.1, and the total string probability is 0.4. The conditional probability is 0.1/0.4 = 0.25.
Related terms
- Context-free grammar
- Parse tree
- Constituency parsing
- production rule
- probabilistic parsing
- inside algorithm
- Viterbi parsing
- grammar ambiguity
Learn next
Next, compare a maximum-over-parses calculation with a sum-over-parses calculation. Change S → A B to probability 0.4 and S → C D to 0.6, leaving the other rules unchanged. Recompute the two x y tree probabilities, their sum, and the posterior probability of each parse.
More in Graphs and symbolic AI
- Prioritized circumscription - Prioritized circumscription is a form of nonmonotonic reasoning that assigns precedence to predicates being minimized.
- Prioritized sweeping - Prioritized sweeping is a model-based reinforcement-learning and planning technique that concentrates value updates on states likely to be affected by...
- Priority queue - A priority queue is a data structure that returns the item with the best priority according to a specified ordering.
- Probabilistic database - A probabilistic database represents uncertainty about database contents using a probability model.
- Probabilistic Graphical Model - A probabilistic graphical model represents a probability distribution using a graph and associated numerical functions.
- Probabilistic Horn abduction - Probabilistic Horn abduction is a framework that combines logical rules with probabilities assigned to possible hypotheses.
Sources
Jurafsky and Martin, Speech and Language Processing, Statistical Constituency Parsing, section E.1: https://stanford.edu/~jurafsky/slp3/E.pdf . The original-author chapter's PCFG definitions, tree probabilities, conditional parsing, and consistency discussion were read. The symbolic grammar and fictional workflow are original teaching examples.
Previous: Probabilistic classification Next: Probabilistic database