Context-free grammar
In formal language theory, a context-free grammar (CFG) is a formal grammar.
Description
A context-free grammar is a formal grammar in which every production rule is of the form
A\ \to\ \alpha
where A is a single nonterminal symbol, and \alpha is a string of terminals and/or nonterminals (\alpha can be empty).
A formal grammar is considered "context free" when its production rules can be applied regardless of the context of a nonterminal.
No matter which symbols surround it, the single nonterminal on the left hand side can always be replaced by the right hand side.
This is what distinguishes it from a context-sensitive grammar.
Such a grammar has long lists of words, and also rules on what types of words can be added in what order.
Higher rules combine several lower rules to make a sentence. Such sentences will be grammatically correct, but may not have any meaning.
Each rule has its own symbol, which can be replaced with symbols representing lower rules, which can be replaced with words. This can also be done in reverse to check if a sentence is grammatically correct.
Languages generated by context-free grammars are known as context-free languages (CFL). Different context-free grammars can generate the same context-free language.
It is important to distinguish properties of the language (intrinsic properties) from properties of a particular grammar (extrinsic properties).
The language equality question (do two given context-free grammars generate the same language?) is undecidable.
Context-free grammars arise in linguistics where they are used to describe the structure of sentences and words in natural language, and they were in fact invented by the linguist Noam Chomsky for this purpose, but have not really lived up to their original expectation.
By contrast, in computer science, as the use of recursively defined concepts increased, they were used more and more.
In an early application, grammars are used to describe the structure of programming languages.
In a newer application, they are used in an essential part of the Extensible Markup Language (XML) called the Document Type Definition.
In linguistics, some authors use the term phrase structure grammar to refer to context-free grammars, whereby phrase structure grammars are distinct from dependency grammars.
In computer science, a popular notation for context-free grammars is Backus–Naur Form, or BNF.
See also
- Context-sensitive grammar
- Deterministic context-free grammar
- Deterministic parsing
- Formal language
- LL parser
External links
- Context-free grammar @ Wikiepedia
