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,
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.
Dinesh Thakur holds an B.C.A, MCSE, MCDBA, CCNA, CCNP, A+, SCJP certifications. Dinesh authors the hugely popular Computer Notes blog. Where he writes how-to guides around Computer fundamental , computer software, Computer programming, and web apps. For any type of query or something that you think is missing, please feel free to Contact us.
Related Articles
Basic Courses
Advance Courses
All Interview