Context-free grammar

A context-free grammar (= CFG = phrase structure grammar) is a formal grammar.

Isomorphic to a pushdown automaton.

Contents

1   Form

A context-free grammar consists of:

  1. A finite set of terminal symbols, sometimes referred to as "tokens".
  2. A finite set of nonterminals, sometimes called "syntactic variables".
  3. A finite set of productions
  4. A designation of one of the nonterminals as the start symbol.

A production consists of:

  1. A nonterminal, called the head or left side of the production
  2. An arrow
  3. A sequence of terminals or nonterminals, called the body or right side of the production.

2   Properties

A production rule which generates ungrammatical sentences overgenerates.

Nonterminals must be a phrasal category.

Context-free grammars have rules of the type:

A -> B

but no rules of the type:

x A y -> x B C y

where what happens with A depends on its context.

3   Adequacy

The adequacy of context-free grammars for representing the syntax of natural languages has been addressed by many people in different way.

It is unclear if English cannot be represented by context-free grammar, but it can be shown to be inadequate due to is being very complex. [1]

4   Representation

In computer science, a popular notation for context-free grammars is Backus-Naur Form.

In linguistics:

5   See also

6   References

[1]Chomsky 1957