 |
|
| |
|
|
|
|
|
Context-free grammar - Examples | | Context-free grammar - Examples: Encyclopedia II - Context-free grammar - Examples | |
Context-free grammar - Example 1.
A simple context-free grammar is
S → aSb | ε
where | is a logical OR, and is used to separate multiple options for the same non-terminal—ε stands for an empty string. This grammar generates the language which is not regular.
Context-free grammar - Example 2.
Here is a context-free grammar for syntactically correct infix algebraic expressions in the variables x, y and z:
S → x | y | z | S + S | S - S | S * S | S/S | (S)
This grammar can, for example, generat ...
See also:Context-free grammar, Context-free grammar - Formal definition, Context-free grammar - Examples, Context-free grammar - Example 1, Context-free grammar - Example 2, Context-free grammar - Example 3, Context-free grammar - Example 4, Context-free grammar - Other examples, Context-free grammar - Derivations and syntax trees, Context-free grammar - Normal forms, Context-free grammar - Undecidable problems, Context-free grammar - Properties of context-free languages | | | Context-free grammar, Context-free grammar - Derivations and syntax trees, Context-free grammar - Example 1, Context-free grammar - Example 2, Context-free grammar - Example 3, Context-free grammar - Example 4, Context-free grammar - Examples, Context-free grammar - Formal definition, Context-free grammar - Normal forms, Context-free grammar - Other examples, Context-free grammar - Properties of context-free languages, Context-free grammar - Undecidable problems, Parsing, Formal grammar, Parsing expression grammar | | |
| | | Context-free grammar: Encyclopedia II - Context-free grammar - Examples
Context-free grammar - Examples
Context-free grammar - Example 1
A simple context-free grammar is
S → aSb | ε
where | is a logical OR, and is used to separate multiple options for the same non-terminal—ε stands for an empty string. This grammar generates the language which is not regular.
Context-free grammar - Example 2
Here is a context-free grammar for syntactically correct infix algebraic expressions in the variables x, y and z:
S → x | y | z | S + S | S - S | S * S | S/S | (S)
This grammar can, for example, generate the string "( x + y ) * x - z * y / ( x + x )".
Context-free grammar - Example 3
A context-free grammar for the language consisting of all strings over {a,b} which contain a different number of a's than b's is
S → U | V
U → TaU | TaT
V → TbV | TbT
T → aTbT | bTaT | ε
Here, T can generate all strings with the same number of a's as b's, U generates all strings with more a's than b's and V generates all strings with fewer a's than b's.
Context-free grammar - Example 4
Another example of a context free language is . This is not a regular language, but it is context free as it can be generated by the following CFG (Context Free Grammar):
S → aSc | B
B → bBc | ε
Context-free grammar - Other examples
Context-free grammars are not limited in application to mathematical ("formal") languages. The grammar of Lojban, a spoken artificial language with an immense expressive power, is also context-free, and unambiguous. The ancient Indian linguist Panini described Sanskrit using a context-free grammar. Recently, it has been suggested that a class of Tamil poetry called Venpa is governed by a context-free grammar.
Other related archivesBackus-Naur Form, CYK algorithm, Chomsky normal form, Earley parser, Formal grammar, Greibach normal form, LL parsers, LR, LR parsers, Lojban, Panini, Parsing, Parsing expression grammar, Sanskrit, Tamil, Turing machine, Venpa, abstract syntax tree, ambiguous grammar, computer science, context-free, context-sensitive, context-sensitive languages, counterexample, formal grammar, formal language, formalism, linguistics, logical OR, non-terminal symbol, parsers, parsing algorithms, parsing expression grammar, programming languages, pumping lemma, push-down automata, regular, regular grammar, regular language, syntax
 Adapted from the Wikipedia article "Examples", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki |
|
|
|
More material related to Context-free Grammar can be found here:
|
|
|
« Back
|
Search the Global Oneness web site |
|
|
|
|
|
|
