Turn Desktop View Off
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.

 

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,

                   Context Free Language (CFL)

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,

         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.

(eg.)

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

 Grammar

              What is Context Free Grammars? Compiler Design

Rules

 

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.