What is Context Free Grammars? Compiler Design

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.