Concept

Context-free grammar

Overview

In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules

can be applied to a nonterminal symbol regardless of its context.

In particular, in a context-free grammar, each production rule is of the form

→

{\displaystyle A\ \to \ \alpha }

with

{\displaystyle A}

a single nonterminal symbol, and

{\displaystyle \alpha }

a string of terminals and/or nonterminals (

{\displaystyle \alpha }

can be empty). Regardless of which symbols surround it, the single nonterminal

{\displaystyle A}

on the left hand side can always be replaced by

{\displaystyle \alpha }

on the right hand side. This distinguishes it from a context-sensitive grammar, which can have production rules in the form

→

{\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }

with

{\displaystyle A}

a nonterminal symbol and

{\displaystyle \alpha }

{\displaystyle \beta }

, and

{\displaystyle \gamma }

strings of terminal and/or nonterminal symbols.

A formal grammar is essentially a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements. For example, the first rule in the picture,

⟨

Stmt

⟩

→

⟨

⟩

⟨

Expr

⟩

;

{\displaystyle \langle {\text{Stmt}}\rangle \to \langle {\text{Id}}\rangle =\langle {\text{Expr}}\rangle ;}

replaces

⟨

Stmt

⟩

{\displaystyle \langle {\text{Stmt}}\rangle }

with

⟨

⟩

⟨

Expr

⟩

;

{\displaystyle \langle {\text{Id}}\rangle =\langle {\text{Expr}}\rangle ;}

. There can be multiple replacement rules for a given nonterminal symbol. The language generated by a grammar is the set of all strings of terminal symbols that can be derived, by repeated rule applications, from some particular nonterminal symbol ("start symbol").

Nonterminal symbols are used during the derivation process, but do not appear in its final result string.

Languages generated by context-free grammars are known as context-free languages (CFL). Different context-free grammars can generate the same context-free language. It is important to distinguish the properties of the language (intrinsic properties) from the properties of a particular grammar (extrinsic properties). The language equality question (do two given context-free grammars generate the same language?) is undecidable.

Context-free grammars arise in linguistics where they are used to describe the structure of sentences and words in a natural language, and they were invented by the linguist Noam Chomsky for this purpose. By contrast, in computer science, as the use of recursively defined concepts increased, they were used more and more. In an early application, grammars are used to describe the structure of programming languages. In a newer application, they are used in an essential part of the Extensible Markup Language (XML) called the document type definition.

In linguistics, some authors use the term phrase structure grammar to refer to context-free grammars, whereby phrase-structure grammars are distinct from dependency grammars. In computer science, a popular notation for context-free grammars is Backus–Naur form, or BNF.

Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).

Possible passages

Found by search and not yet checked by a person; they may only mention the idea in passing.

This language is inarticulate, but it has tone, stress, and meaning. The use of our own language has led us to neglect it so far as to forget it altogether. Let us study children and we shall soon learn it afresh from them.
Jean-Jacques Rousseau, Emile
States what Context-free grammar is.
Read the chapter · Open in the reader
On the other hand an event-particle is defined so as to exhibit this character of being a route of approximation marked out by entities posited in sense-awareness. A definite event-particle is defined in reference to a definite punct in the following manner: Let the condition {sigma} mean the property of covering all the abstractive elements which are members of that punct; so…
Alfred North Whitehead, The Concept of Nature The Tarner Lectures Delivered in Trinity College, November 1919
States what Context-free grammar is.
Read the chapter · Open in the reader
An abstractive hierarchy is called ‘finite’ if it stops at a finite grade of complexity. It is called ‘infinite’ if it includes members belonging respectively to all degrees of complexity. It is to be noted that the base of an abstractive hierarchy may contain any number of members, finite or infinite. Further, the infinity of the number of the members of the base has nothing to do with the question as to whether…
Alfred North Whitehead, Science and the modern world
States what Context-free grammar is.
Read the chapter · Open in the reader

Context-free grammar

Overview

Possible passages

Related ideas

Opposing perspectives

Place in the tradition