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,
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,
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).
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.