The DICT Development Group

Search for:
Search type:

Database copyright information
Server information
Wiki: Resources, links, and other information

1 definition found
 for context-free grammar
From The Free On-line Dictionary of Computing (18 March 2015) :

  context-free grammar
      (CFG) A grammar where the syntax of each constituent
     ({syntactic category or terminal symbol) is independent of the
     symbols occuring before and after it in a sentence.  A
     context-free grammar describes a context-free language.
     Context-free grammars can be expressed by a set of "production
     rules" or syntactic rules.  For example, a language with symbols
     "a" and "b" that must occur in unequal numbers can be represented
     by the CFG:
      S → U | V
      U → TaU | TaT | UaT
      V → TbV | TbT | VbT
      T → aTbT | bTaT | ε
     meaning the top-level category "S" consists of either a "U" or a
     "V" and so on.  The special category "ε" represents the empty
     string.  This grammar is context-free because each rule has a
     single symbol on its left-hand side.
     Parsers for context-free grammars are simpler than those for
     context-dependent grammars because the parser need only know the
     current symbol.
     Algol was (one of?) the first languages whose syntax was
     described by a context-free grammar.  This became a common
     practice for programming languages and led to the notation for
     grammars called Backus-Naur Form.

Questions or comments about this site? Contact webmaster@dict.org