Context Free Grammar (CFG)

In this article, we have explained Context Free Grammar (CFG) in depth along with examples and real life applications of Context Free Grammar (CFG). This is one of the most important concept in Theory of Computation.

Table of contents:

  1. What is Context Free Grammar (CFG)?
  2. Example of Context Free Grammar
  3. Properties of Context Free Grammar
  4. Application of Context Free Grammar (CFG)

Let us get started.

What is Context Free Grammar (CFG)?

Context Free Grammar is defined as a 4 tuple G = (V, Σ, R, S) where:

  1. V is a finite set of elements known as variables.
  2. Σ is a finite set of elements known as terminals
  3. V ∩ Σ = Null (empty set)
  4. S is an element of V and is known as start variable.
  5. R is a fine set of elements known as rule. Each rule is like A -> w where A belongs to V and w belongs to union of (V and Σ)*. The * denotes repetation of elements.

An example of Context Free Grammer is:

G = (V, Σ, R, S) where:

  • V = {S}
  • Σ = {(, )}
  • S = S
  • R = { S -> e, S -> (S), S -> SS }

The above Context Free Grammer is for Balanced Parentheses expressions consisting of round bracket only ().

Definitions of Context Free Grammers:

  • If A is an element in V and u, y and w are strings in (V union Σ)* and there is a rule A -> w in R, then the string uwv can be derived in one step from string uAv and can be written as:
uAv => uwv.
  • If G is a Context Free Grammer and u and v are strings in (V union Σ), then v can be derived from u and write this as u => v if one of the following two conditions hold true: 1. u = v. 2. For K >= 2 and a sequence u1, u2, ..., uK of strings in (V union Σ)* such that:

2.1. u = u1
2.2. v = uK
2.3. u1 => u2 => ... => uK

  • G is a Context Free Grammer. The language of G is defined to be the set of all strings in Σ* that can be derived for start variable S in V:

L(G) = { w belongs to Σ* : S => w}

  • A language L is called Context Free Language if there is a Context Free Grammer G such that L(G) = L.

Example of Context Free Grammar

This is the example of a Context free grammar (CFG) for Balanced Parentheses:

  • V = {S}
  • Σ = {(, )}
  • S = S
  • R = { S -> e, S -> (S), S -> SS }

Let us assume we want to arrive at the balanced expression (())()() using our context free grammer G.

The steps are:

S => SS
=> (S)S
=> (S)SS
=> (SS)SS
=> ((S)S)SS
=> (()S)SS
=> (())SS
=> (())(S)S
=> (())()S
=> (())()(S)
=> (())()()

To get the complete idea of this Context Free Grammer, go through this article.

Properties of Context Free Grammar

Following are the properties of Context Free Grammer:

  • All Regular Languages along with some Non-regular Languages are Context Free Language. Context Free Language is a language based on a Context Free Grammer.

Therefore, all Regular Languages = Context Free Languages.
Some / not all Non-regular Languages = Context Free Languages.

If a Language L is not a Context Free Language, then the language L is a Non-regular Language.

  • Σ is an alphabet and L is a proper subset of Σ*. If L is a Regular Language, then L is a Context Free Language. A Context Free Grammer G can be converted to another Context Free Grammer G' such that L(G) = L(G') and the rules of G' are in restricted form that is Chomsky Normal Formal.

  • Σ is an alphabet and L is a proper subset of Σ* and L is a Context Free Language. Then, there exists a Context Free Grammer G in Chomsky Normal Formal whose language is L = L(G).

Applications of Context Free Grammar (CFG)

  • Context Free Grammers are used in Compilers (like GCC) for parsing. In this step, it takes a program (a set of strings).

  • Context Free Grammers are used to define the High Level Structure of a Programming Languages.

  • Every Context Free Grammer can be converted to a Parser which is a component of a Compiler that identifies the structure of a Program and converts the Program into a Tree.

  • Document Type Definition in XML is a Context Free Grammer which describes the HTML tags and the rules to use the tags in a nested fashion.

Following is the Context Free Grammer for HTML (with limited tags):

  • Char -? a | A | . . .

  • Text -> λ | Char Text

  • Doc -> λ | Element Doc

  • Element -> Text | < EM > Doc < /EM >|< P > Doc |< OL > List < /OL >

  • List -> λ | ListItem List

  • ListItem -> < li > Doc

  • All finite set of strings are Regular Languages. All Regular Language is a Context Free Language. Hence, all Programming Languages are Context Free Languages / can be represented by a Context Free Grammer.

  • Algebraic Expressions can be represented using Context Free Grammer. For example, this is the rules of a Context Free Grammer for syntactically correct Infix expression using 3 variables (x, y, z):

  • S -> empty

  • S -> (S)

  • S -> x

  • S -> y

  • S -> z

  • S -> S + S

  • S -> S – S

  • S -> S * S

  • S -> S / S

Following is the Context Free Grammer for an Imperative Programming Language Brainfuck:

G = (V, Σ, R, S)

where:

V = {Program, Instr}
Σ = {+, -, >, <, , , ., [, ]}
S = Program

R =

  • Program -> ε
  • Program -> Instr Program
  • Instr -> '+'
  • Instr -> '-'
  • Instr -> '>'
  • Instr -> '<'
  • Instr -> ','
  • Instr -> '.'
  • Instr -> '[' Program ']'

There are syntax features that cannot be represented with a Context Free Grammer such as:

  • Indentation
  • Whitespace
  • Typedef in C and C++ Programming Languages
  • Macro and Templates in Programming Languages like Lisp, C++, Haskell, Nim and others.

Therefore, Programming Languages / Real life programs are not represented purely by Context Free Grammer.

  • Complete Sentences in English Language can be generated using Context Free Grammer. For example:

G is a Context Free Grammer

V = {S, < Noun phrase >, < V erb phrase >, < Adjective phrase >,
< Noun >, < V erb >, < Adjective >}

Start variable = S

Σ = {big, stout, Kiao, bought, white, car, Henry, cheese, ate, green}

Rules:

  • S -> < Noun phrase > < Verb phrase >
  • < Noun phrase > -> < Noun >|< Adjective phrase >< Noun > | λ
  • < V erb phrase > -> < V erb >< Noun phrase >
  • < Adjective phrase > -> < Adjective phrase >< Adjective > | λ
  • < Noun > -> Kiao | car | Henry | cheese
  • < V erb > -> bought | ate
  • < Adjective > -> big | stout | white | green

Example of sentences generated using it are:

  • Kiao bought car
  • Henry ate cheese
  • Kiao bought big car

It also generates some invalid sentences:

  • big cheese ate Henry

  • First Order Logic: Terms and formulas of Formal Logic are Context Free Grammer with the exception of the set of variables which can be infinite along with multiple start variables.

With this article at OpenGenus, you must have the complete idea of Context Free Grammer which is one of the most important ideas in Theory of Computation.