A weighted context-free grammar (WCFG) is a context-free grammar

Context-free grammar

In formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....

 where each production has a numeric weight associated with it. The weight of a parse tree

Parse tree

A concrete syntax tree or parse tree or parsing treeis an ordered, rooted tree that represents the syntactic structure of a string according to some formal grammar. In a parse tree, the interior nodes are labeled by non-terminals of the grammar, while the leaf nodes are labeled by terminals of the...

 in a WCFG is the weight of the rule used to produce the top node, plus the weights of its children. A special case of WCFGs are stochastic context-free grammar

Stochastic context-free grammar

A stochastic context-free grammar is a context-free grammar in which each production is augmented with a probability...

s, where the weights are (logarithm

Logarithm

The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...

s of) probabilities

Probability

Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...

.

An extended version of the CYK algorithm

CYK algorithm

The Cocke–Younger–Kasami algorithm is a parsing algorithm for context-free grammars. It employs bottom-up parsing and dynamic programming....

can be used to find the "lightest" (least-weight) derivation of a string given some WCFG.