by Dinesh Thakur

Grammars are used to describe the syntax of a programming language. It specifies the structure of expression and statements.

stmt -> if (expr) then stmt

where stmt denotes statements,

expr denotes expressions.


Types of grammar


• Type 0 grammar

• Type 1 grammar

• Type 2 grammar

• Type 3 grammar


Context Free Grammar


Context free grammar is also called as Type 2 grammar.




A context free grammar G is defined by four tuples as,



G - Grammar

V - Set of variables

T - Set of Terminals

P - Set of productions

S - Start symbol

It produces Context Free Language (CFL) which is defined as,

                   Context Free Language (CFL)



G- Grammar

w - Input string

S - Start symbol

T - Terminal

Hence, CFL is a collection of input strings which are terminals, derived from the start symbol of grammar on multiple steps.




Terminals are symbols from which strings are formed.

• Lowercase letters i.e., a, b, c.

• Operators i.e.,+,-,*·

• Punctuation symbols i.e., comma, parenthesis.

• Digits i.e. 0, 1, 2, · · · ,9.

• Boldface letters i.e., id, if.


Non-terminals are syntactic variables that denote a set of strings.

Uppercase letters i.e., A, B, C.

Lowercase italic names i.e., expr , stmt.

Start symbol is the head of the production stated first in the grammar.

Production is of the form LHS ->RHS (or) head -> body, where head contains only one non-terminal and body contains a collection of terminals and non-terminals.

(eg.) Let G be,

         What is Context Free Grammars? Compiler Design

Context Free Grammars vs Regular Expressions

Grammars are more powerful than regular expressions.

Every construct that can be described by a regular expression can be described by a grammar but not vice-versa.

Every regular language is a context free language but reverse does not hold.


RE= (a I b)*abb (set of strings ending with abb).


              What is Context Free Grammars? Compiler Design



For each state i of the NFA, create a non-terminal Ai.

If state i has a transition to state j on input a, add the production Ai -> aAj.

If state i goes to state j on input e, add the production Ai -> Aj.

If i is an accepting state, add Ai -> Ɛ.

If i is a start state, make Ai be the start symbol of the grammar.