Simplifies form and Normal form
Simplifies form
Context Free Grammar (CFG)
• A context free grammar is a 4-tuple G=(V,Ʃ,S,P)
where
V &Ʃ are disjoint finite set
S is an element of V and
P is a finite set formulas of the form A → α
V → Non terminal or variable
Ʃ → terminal symbols
S → start symbol
P → production rule or grammar rules
Context Free Grammar (CFG)
Application
• CFG are extensively used to specify the syntax of programming
language.
• CFG is used to develop parser
Definition: Context Free Language
• Language generated by CFG is called context free language
• Let G= (V, Ʃ, S, P) be a CFG. The Language generated by G is
L(G):{x ∈ Ʃ*/S⟹G* x}
• A language L is a context free Language(CFL) if there is a CFG G
so that L=L(G)
Simplified form & Normal forms
• In this section we discuss some slight more straight
forward ways of improving a grammer without
changing the resulting language.
1)eliminating certain types of productions that may
be awkward to work to work.
2)standardizing the productions so that they all have
a certaion normal form.
Simplifies form
• In this simplifies form there is three type
1) Eliminating Null able Variable(Empty Production Removal)
2) Eliminating Unit Production(Unit production removal)
3) Eliminating Useless Productions(Removing Useless)
Eliminating Null able Variable
(Empty Production Removal)
• The productions of context-free grammars can be coerced
into a variety of forms without affecting the expressive power
of the grammars.
• If the empty string does not belong to a language, then there
is a way to eliminate the productions of the form A → ^ from
the grammar.
• If the empty string belongs to a language, then we can
eliminate ^ from all productions save for the single
production S → ^ . In this case we can also eliminate any
occurrences of S from the right-hand side of productions
Eliminating Null able Variable
(Empty Production Removal)
• a nullable variable in a CFG G=(V,Ʃ,S,P) is defined as follows
1) Any variable A for which P contains A → ˄ is nullable
2) if P contain production A → B1B2…..Bn
where B1B2…Bn are nullable variable, then A is nullable.
3) No other variable in V are nullable.
• Example:
S → aX/Yb
X → S/˄
Y → bY/b
Ans:
S → aX/Yb/a
X→S
Y → bY/b
Eliminating Unit Production
(Unit production removal)
Eliminating Unit Production
(Unit production removal)
Eliminating Unit Production
(Unit production removal)
• Example:
S → Aa/B
A → a/bc/B
B → A/bB
Ans:
Unit production are S → B, A → B and B → A
S → Aa/A/bb S → Aa/a/bc/bb
A → a/bc/B A → a/bc/A/bb
A → a/bc/bb B → A/bb
B → A/bb B → a/bc/bb
So CFG after removing unit production is
S → Aa/a/bc/bb
A → a/bc/bb
B → a/bc/bb
Normal forms
definition
Theorem
Example of CFG Conversion
Removing Rules
Removing unit rule
More unit rules
Converting remaining rules
Presentation Outline
• Greibach Normal Form
May 27, 2009 20
Greibach Normal Form
A context free grammar is said to be in
Greibach Normal Form if all productions
are in the following form:
A → αX
• A is a non terminal symbols
• α is a terminal symbol
• X is a sequence of non terminal symbols.
It may be empty.
May 27, 2009 21
Greibach Normal Form
Algorithm to Convert a CFG into Greibach Normal Form
Step1:
If the start symbol S occurs on some right side, create a
new start symbol S’ and a new production S’ → S.
Step 2:
Remove Null productions. (Using the Null production
removal algorithm discussed earlier)
Step 3:
Remove unit productions. (Using the Unit production
removal algorithm discussed earlier)
Step 4:
Remove all direct and indirect left-recursion.
Step 5:
Do proper substitutions of productions to convert it into
the proper form of GNF.
Greibach Normal Form
Example:
S → XA | BB S = A1 A1 → A2A3 | A4A4
B → b | SB X = A2 A4 → b | A1A4
X→b A = A3 A2 → b
A→a B = A4 A3 → a
CNF New Labels Updated CNF
May 27, 2009 23
Greibach Normal Form
Example:
A 1 → A 2A 3 | A 4A 4 First Step
A 4 → b | A 1A 4 AAii →
→ AAjjXXkk jj >> ii
A2 → b Xk is a string of zero
A3 → a
or more variables
A 4 → A 1A 4
May 27, 2009 24
Greibach Normal Form
Example:
First Step
AAii →
→ AAjjXXkk jj >> ii
A 4 → A 1A 4 A 1 → A 2A 3 | A 4A 4
A4 → A2A3A4 | A4A4A4 | b A 4 → b | A 1A 4
A4 → bA3A4 | A4A4A4 | b A2 → b
A3 → a
May 27, 2009 25
Greibach Normal Form
Example:
A1 → A2A3 | A4A4 Second Step
A4 → bA3A4 | A4A4A4 | b
A2 → b
A3 → a Eliminate
Eliminate
Left
Left Recursions
Recursions
A4 → A4A4A4
May 27, 2009 26
Greibach Normal Form
Example:
Second Step
Eliminate
Eliminate
Left
Left
Recursions
Recursions
A4 → bA3A4 | b | bA3A4Z | bZ A1 → A2A3 | A4A4
A4 → bA3A4 | A4A4A4 | b
Z → A4A4 | A4A4Z A2 → b
A3 → a
May 27, 209 27
Greibach Normal Form
Example:
A1 → A2A3 | A4A4
A4 → bA3A4 | b | bA3A4Z | bZ AA →
→ αX
αX
Z → A 4A 4 | A 4A 4 Z
A2 → b GNF
A3 → a
May 27, 2009 28
Greibach Normal Form
Example:
A1 → A2A3 | A4A4
A4 → bA3A4 | b | bA3A4Z | bZ
Z → A4A4 | A4A4 Z
A2 → b
A3 → a
A1 → bA3 | bA3A4A4 | bA4 | bA3A4ZA4 | bZA4
Z → bA3A4A4 | bA4 | bA3A4ZA4 | bZA4 | bA3A4A4 | bA4 | bA3A4ZA4 | bZA4
May 27, 2009 29
Greibach Normal Form
Example:
A1 → bA3 | bA3A4A4 | bA4 | bA3A4ZA4 | bZA4
A4 → bA3A4 | b | bA3A4Z | bZ
Z → bA3A4A4 | bA4 | bA3A4ZA4 | bZA4 | bA3A4A4 | bA4 | bA3A4ZA4 | bZA4
A2 → b
A3 → a
Grammar in Greibach Normal Form
May 27, 2009 30
You
Th ank
14/11/16
