Saturday, December 18, 2010

Context Free Grammar

Context Free Grammar (CFG)


  • A Context Free Grammar is a "Machine" that creates a Language.
  • A Language created by a Context Free Grammar is called a Context Free Language (CFL).
  • The Class of Context Free Languages properly contains the class of Regular Language.



Applications of CFG.


  • CFG are extensively used to specify the syntax of programming Languages, and now the structure of document like XML's Document Type Definition
  • CFG used to develop Parser. (Specification and Compilation of Programming Language)
Meaning of Context Free?

If at some point in a derivation we have obtained a string α containing the variable A, then we may continue by substituting β  for A, No matter what the string α1  and α2 are. That is independent of the Context.