Catalogue of Artificial Intelligence Techniques


Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

Context-free Grammar

Aliases: CFG, Context-free Phrase Structure Grammar

Keywords: context-free rules, non-deterministic parsing, non-terminal symbol, phrase structure rules, rewriting interpretation, terminal symbol, well-formedness

Categories: Natural Language

Author(s): Henry Thompson

A context-free grammar is a collection of context-free phrase structure rules. Each such rule names a constituent type and specifies a possible expansion thereof. The standard notation is:


where LHS names the constituent, and RHS1 through RHSn

the expansion. Such rules are context-free rules because the expansion is unconditional--the environment of the constituent to be expanded is irrelevant. A collection of such rules together with an initial symbol, usually S, is a context-free grammar. The constituents expanded (those appearing on the left-hand side) are called the non-terminals. Those not expanded (appearing only on the right-hand side) are called the terminals. There are two standard ways of interpreting such a grammar as specifying a language. The rewriting interpretation says that a grammar generates the set of strings of terminals which can be produced by the following non-deterministic method:

  1. Write down the initial symbol.
  2. Choose a non-terminal symbol in the string, and a rule from the grammar which expands it. Replace the chosen instance of the non-terminal with the expansion given in the rule.
  3. If no non-terminals remain in the string, the process is complete. Otherwise, go back to step 2.
The well-formedness interpretation actually generates trees, not strings. It simply admits to the language all singly rooted trees whose root is the initial symbol and for each of whose non-leaf nodes there is a rule in the grammar such that LHS

is the node label and RHSn are the labels of its descendants in order.



Add Comment

No comments.