A context-free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a non-terminal symbol and w is a string consisting of terminals and/or non-terminals. The term "context-free" comes from the fact that the non-terminal V can always be replaced by w, regardless of the context in which it occurs. Context free languages are also those which are accepted by finite state automata.
Related categories 1
A Wikipedia article that defines context free grammars and uses them to generate context free languages.
Context-Free Grammars and Parsing
An article defining the grammar and how Binary Normal Form (BNF) is used to parse words in a context free language. An example shows how operator precedence is preserved in a context free grammar.
Formal Grammars and Languages
A survey article on formal systems that define families of formal languages arising in many computer science applications with primary focus on context-free languages.
Push-Down Automata and Context-Free Grammars
Lecture notes defining context free grammars and closure and decidability properties of context free languages. There is a short section showing that natural languages are not context free.
Last update:September 25, 2014 at 21:54:08 UTC