Catalogue of Artificial Intelligence Techniques
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 names the constituent, and through
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:
- Write down the initial symbol.
- 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.
- If no non-terminals remain in the string, the process is complete. Otherwise, go back to step 2.
is the node label and are the labels of its descendants in order.
- Gazdar, G., Phrase structure grammar, The Nature of Syntactic Representations (Jacobson, P. and Pullum, G.K.
, eds.), D. Reidel Publishing Co., Dordrecht, 1981, pp.131--186.