Header Ads Widget

Context free grammar

Context free grammar

Context free grammar is a formal grammar which is used to generate all possible strings in a given formal language.

Context free grammar G can be defined by four tuples as:

  1. G= (V, T, P, S)  

Where,

G describes the grammar

T describes a finite set of terminal symbols.

V describes a finite set of non-terminal symbols

P describes a set of production rules

S is the start symbol.

In CFG, the start symbol is used to derive the string. You can derive the string by repeatedly replacing a non-terminal by the right hand side of the production, until all non-terminal have been replaced by terminal symbols.

Example:

L= {wcwR | w € (a, b)*}

Production rules:

  1. S → aSa  
  2. S → bSb  
  3. S → c  

Now check that abbcbba string can be derived from the given CFG.

  1. S ⇒ aSa  
  2. S ⇒ abSba  
  3. S ⇒ abbSbba  
  4. S ⇒ abbcbba  

By applying the production S → aSa, S → bSb recursively and finally applying the production S → c, we get the string abbcbba.

Capabilities of CFG

There are the various capabilities of CFG:

  • Context free grammar is useful to describe most of the programming languages.
  • If the grammar is properly designed then an efficientparser can be constructed automatically.
  • Using the features of associatively & precedence information, suitable grammars for expressions can be constructed.
  • Context free grammar is capable of describing nested structures like: balanced parentheses, matching begin-end, corresponding if-then-else's & so on.

Post a Comment

0 Comments