Language - Context Free Grammar (CFG)



A context-free grammar is:

They are the type 2 of the Chomsky grammar hierarchy.

Context-free grammars :

DTD’s taken as a whole, are really CFG’s.

Context-free grammars are used to put a tree structure on strings, typically text strings.

In context-free grammars, all rules are:

  • one-to-one,
  • one-to-many,
  • or one-to-none.

These rules can be applied regardless of context.

In a context free grammar, each (production|grammar) rule has :

  • a non-terminal symbol as its left-hand side (ie the symbol will not appear in the resulting formal language)
  • and a sequence of zero or more non-terminal and terminal symbols as its right-hand side.

In context-free grammars, terminal symbols never appear on the left hand side of a production rule

Starting from a sentence consisting of a single distinguished nonterminal, called the goal symbol, a given context-free grammar specifies a language, namely, the (perhaps infinite) set of possible sequences of terminal symbols that can result from repeatedly replacing any nonterminal in the sequence with a right-hand side of a production for which the nonterminal is the left-hand side.


Grammar Checking

Rules can be applied in reverse to check if a string is grammatically correct according to the grammar.


Syntactic equations of the form defined in EBNF generate context-free languages.

Context Free meaning

The term context free is due to Chomsky and stems from the fact that substitution of:

  • the symbol left of =
  • by a sequence derived from the expression to the right of =

is always permitted, regardless of the context in which the symbol is embedded within the sentence.

It has turned out that this restriction to context freedom (in the sense of Chomsky) is quite acceptable for programming languages, and that it is even desirable.


A CFG consists of the following components:

  • a set of terminal symbols, which are the characters of the alphabet that appear in the strings generated by the grammar.
  • a set of nonterminal symbols, which are placeholders for patterns of terminal symbols that can be generated by the nonterminal symbols.
  • a set of productions, which are rules for replacing (or rewriting) nonterminal symbols (on the left side of the production) in a string with other nonterminal or terminal symbols (on the right side of the production).
  • a start symbol, which is a special nonterminal symbol that appears in the initial string generated by the grammar.


To generate a string of terminal symbols from a CFG, we:

  • Begin with a string consisting of the start symbol;
  • Apply one of the productions with the start symbol on the left hand size, replacing the start symbol with the right hand side of the production;
  • Repeat the process of selecting nonterminal symbols in the string, and replacing them with the right hand side of some corresponding production, until all nonterminals have been replaced by terminal symbols.

Documentation / Reference

Discover More
Computer Language - (Compiler|Interpreter) - Language translator

Computer Language are written in plain text. However, computers interpret only particular sequence of instructions. This transformation from a plain text language to instructions is called compilation...
Grammar - Hierarchy of grammar (Chomsky)

In the formal languages (of computer science and linguistics), the Chomsky hierarchy is a hierarchy of formal grammars described by Noam Chomsky in 1956. The hierarchy describes the relations between:...
HTML - Grammar

HTML is a Context-free_grammarChomsky Type 2 grammar. See
Grammar Different Structural Trees For The Same Expression
Language - (Grammar | Syntax | Lexicon)

Grammar in the context of a compiler. Ie how to define it. grammar section In processing computer languages, semantic processing generally comes after syntactic processing, but in some cases semantic...
Language - Nonterminal Symbol

A symbol or token is called non terminal when it does not appear in the resulting formal language. They are derived token that are expressed via a rule with a regular expression that contains: either...
Language - Terminal (Symbol|Token)

A symbol or token is called terminal when it appears in the resulting formal language. Terminal Symbol are the characters of the alphabet that appear in the strings generated by the grammar. context-free...
Multilingual Regular Expression Syntax (Pattern)

Regular expression are Expression that defines a pattern in text. This is therefore a language that permits to define structure of a text. They are a mathematically-defined concept, invented by Stephen...
Card Puncher Data Processing
Language - Regular Language

A regular language is a language that can be described by regular expressions. A language which cannot be described by a regular expression is called non-regular. Regular expressions are not very...
Card Puncher Data Processing
What is an Automaton? State Machine

Automata theory is the study of abstract computing devices or machines. The word automata (the plural of automaton) comes from the Greek word αὐτόματα, which means self-acting An automaton consists...
Card Puncher Data Processing
XML - Document Type (Definition|Declaration) (DTD)

Document Type Definition (DTD) is a grammar (language) that defines the schema (ie data structure) of an XML document. It defines constraints on the logical structure supports the use of predefined...

Share this page:
Follow us:
Task Runner