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.

**Definition**

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

G=(V,T,P,S)

where,

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,

where,

L-Language

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.

**Conventions**

** 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,

## 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.

(eg.)

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

** Grammar**

** **

**Rules**

For each state i of the NFA, create a non-terminal A_{i}.

If state i has a transition to state *j *on input *a, *add the production A_{i} -> *aA _{j}. *

If state i goes to state *j *on input *e, *add the production A_{i} -> *A _{j}.*

If i is an accepting state, add A_{i} -> Ɛ.

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