Wednesday, May 2, 2012

Context Free Grammar



Context Free Grammar

Context Free grammar or CGF, G is represented by four components that is G= (V, T, P, S), where V is the set of variables, T the terminals, P the set of productions and S the start symbol.
Example: The grammar Gpal for palindromes is represented by
Gpal = ({P}, {0, 1}, A, P)
Where A represents the set of five productions
1. P
2. P0
3. P1
4. P0P0
5. P1P1 
Derivation using Grammar 

Example 1: Leftmost Derivation
The inference that a * (a+b00) is in the language of variable E can be reflected in a derivation of that string, starting with the string E. Here is one such derivation:

E E * E I * E a * E a * (E) a * (E + E) a * (I + E) a * (a + E) a * (a + I) a * (a + I0) a * (a + I00) a * (a + b00)
Leftmost Derivation - Tree


Example 2: Rightmost Derivations
The derivation of Example 1 was actually a leftmost derivation. Thus, we can describe the same derivation by:
E E * E E *(E) E * (E + E)
E * (E + I) E * (E +I0) E * (E + I00) E * (E + b00)
E * (I + b00) E * (a +b00) I * (a + b00) a * (a + b00)
We can also summarize the leftmost derivation by saying
E a * (a + b00), or express several steps of the derivation by expressions such as E * E a * (E).
Rightmost Derivation - Tree

There is a rightmost derivation that uses the same replacements for each variable, although it makes the replacements in different order. This rightmost derivation is:
E E * E E * (E) E * (E + E)
E * (E + I) E * (E + I0) E * (E + I00) E * (E + b00)
E * (I + b00) E * (a + b00) I * (a + b00) a * (a + b00)
This derivation allows us to conclude E a * (a + b00)
Consider the Grammar for string(a+b)*c
EE + T | T
T T * F | F
F ( E ) | a | b | c
Leftmost Derivation
ETT*FF*F(E)*F(E+T)*F(T+T)*F(F+T)*F (a+T)*F (a+F)*F (a+b)*F(a+b)*c
Rightmost derivation
ETT*FT*cF*c(E)*c(E+T)*c(E+F)*c(E+b)*c(T+b)*c(F+b)*c(a+b)*c
Example 2:
Consider the Grammar for string (a,a)
S->(L)|a
L->L,S|S
Leftmost derivation
S(L)(L,S)(S,S)(a,S)(a,a)
Rightmost Derivation
S(L)(L,S)(L,a)(S,a)(a,a)
The Language of a Grammar
If G(V,T,P,S) is a CFG, the language of G, denoted by L(G), is the set of terminal strings that have derivations from the start symbol.
L(G) = {w in T | S w}
Sentential Forms
Derivations from the start symbol produce strings that have a special role called “sentential forms”. That is if G = (V, T, P, S) is a CFG, then any string in (V T)* such that S a is a sentential form. If S a, then is a left – sentential form, and if S a , then is a right – sentential form. Note that the language L(G) is those sentential
forms that are in T*; that is they consist solely of terminals.
For example, E * (I + E) is a sentential form, since there is a derivation
E E * E E * (E) E * (E + E) E * (I + E)
However this derivation is neither leftmost nor rightmost, since at the last step, the middle E is replaced.
As an example of a left – sentential form, consider a * E, with the leftmost derivation.
E E * E I * E a * E
Additionally, the derivation
E E * E E * (E) E * (E + E)
Shows that
E * (E + E) is a right – sentential form.
Ambiguity
A context – free grammar G is said to be ambiguous if there exists some w L(G) which has at least two distinct derivation trees. Alternatively, ambiguity implies the existence of two or more left most or rightmost derivations.
Ex:-
Consider the grammar G=(V,T,E,P) with V={E,I}, T={a,b,c,+,*,(,)}, and productions.
EI,
EE+E,
EE*E,
E(E),
Ia|b|c

Consider two derivation trees for a + b * c.

Now unambiguous grammar for the above
Example:
ET, TF, FI, EE+T, TT*F,
F(E), Ia|b|c
Inherent Ambiguity
A CFL L is said to be inherently ambiguous if all its grammars are ambiguous
Example:Condider the Grammar for string aabbccdd
SAB | C
A aAb | ab
BcBd | cd
C aCd | aDd
D->bDc | bc
Parse tree for string aabbccdd

Applications of Context – Free Grammars
  • Parsers
  • The YACC Parser Generator
  • Markup Languages
  • XML and Document type definitions

No comments:

Post a Comment