Context-free grammar
(left), and a derivation of a piece of C code (right) from the nonterminal symbol \langle\text{Stmt}\rangle .
≈ 6 min read
Context-free grammar. encyclopegia.org, snapshot enwiki-001374572485. /a/context-free-grammar
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
(left), and a derivation of a piece of C code (right) from the nonterminal symbol \langle\text{Stmt}\rangle . Nonterminal symbols are blue and terminal symbols are red. In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules can be applied to a nonterminal symbol regardless of its context.
In particular, in a context-free grammar, each production rule is of the form A\ \to\ \alpha with A a single nonterminal symbol, and \alpha a string of terminals and/or nonterminals ( \alpha can be empty). Regardless of which symbols surround it, the single nonterminal A on the left hand side can always be replaced by \alpha on the right hand side.
This distinguishes it from a context-sensitive grammar, which can have production rules in the form \alpha A \beta \rightarrow \alpha \gamma \beta with A a nonterminal symbol and \alpha , \beta , and \gamma strings of terminal and/or nonterminal symbols. A formal grammar is essentially a set of production rules that describe all possible strings in a given formal language.
Production rules are simple replacements. For example, the first rule in the picture, \langle\text{Stmt}\rangle \to \langle\text{Id}\rangle = \langle\text{Expr}\rangle ; replaces \langle\text{Stmt}\rangle with \langle\text{Id}\rangle = \langle\text{Expr}\rangle ; . There can be multiple replacement rules for a given nonterminal symbol.
The language generated by a grammar is the set of all strings of terminal symbols that can be derived, by repeated rule applications, from some particular nonterminal symbol ("start symbol"). Nonterminal symbols are used during the derivation process, but do not appear in its final result string. 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 the properties of the language (intrinsic properties) from the 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 a natural language, and they were invented by the linguist Noam Chomsky for this purpose. 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.
A context-free grammar is defined by the 4-tuple G = (V, \Sigma, R, S) , where is a finite set; each element v\in V is called a nonterminal character or a variable. Each variable represents a different type of phrase or clause in the sentence. Variables are also sometimes called syntactic categories.
Each variable defines a sub-language of the language defined by . is a finite set of terminals, disjoint from , which make up the actual content of the sentence. The set of terminals is the alphabet of the language defined by the grammar . is a finite relation in V\times(V\cup\Sigma)^{*} , where the asterisk represents the Kleene star operation.
The members of are called the (rewrite) rules or productions of the grammar (also commonly symbolized by a ). is the start variable (or start symbol), used to represent the whole sentence (or program). It must be an element of .
For any strings u, v\in (V\cup\Sigma)^{*} , we say directly yields , written as u\Rightarrow v\, , if \exists (\alpha, \beta)\in R with \alpha \in V and u_{1}, u_{2}\in (V\cup\Sigma)^{*} such that u\,=u_{1}\alpha u_{2} and v\,=u_{1}\beta u_{2} . Thus, is a result of applying the rule (\alpha, \beta) to .
For any strings u, v\in (V\cup\Sigma)^{*}, we say yields or is derived from if there is a positive integer and strings u_{1}, \ldots, u_{k}\in (V\cup\Sigma)^{*} such that u = u_{1} \Rightarrow u_{2} \Rightarrow \cdots \Rightarrow u_{k} = v . This relation is denoted u ~\stackrel{*}{\Rightarrow}~ v , or u\Rightarrow\Rightarrow v in some textbooks. If k\geq 2 , the relation u ~\stackrel{+}{\Rightarrow}~ v holds.
In other words, (\stackrel{*}{\Rightarrow}) and (\stackrel{+}{\Rightarrow}) are the reflexive transitive closure (allowing a string to yield itself) and the transitive closure (requiring at least one step) of (\Rightarrow) , respectively. The language of a grammar G = (V, \Sigma, R, S) is the set L(G) = \{ w\in\Sigma^{*} : S ~\stackrel{*}{\Rightarrow}~ w\} of all terminal-symbol strings derivable from the start symbol.
A language is said to be a context-free language (CFL), if there exists a CFG , such that L=L(G) . Non-deterministic pushdown automata recognize exactly the context-free languages. The grammar G = (\{S\}, \{\mathrm{a}, \mathrm{b}\}, P, S) , with productions , , , is context-free. It is not proper since it includes an -production.
A typical derivation in this grammar is . This makes it clear that L(G) = \{ww^R:w\in\{a,b\}^*\} . The language is context-free; however, it can be proved that it is not regular.
If the productions , , are added, a context-free grammar for the set of all palindromes over the alphabet is obtained.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1374572485 under CC BY-SA 4.0; modifications have been made.