This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Context-free grammar" – news · newspapers · books · scholar · JSTOR (February 2012) (Learn how and when to remove this message)

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

${\displaystyle A\ \to \ \alpha }$

with ${\displaystyle A}$ a single nonterminal symbol, and ${\displaystyle \alpha }$ a string of terminals and/or nonterminals (${\displaystyle \alpha }$ can be empty). Regardless of which symbols surround it, the single nonterminal ${\displaystyle A}$ on the left hand side can always be replaced by ${\displaystyle \alpha }$ on the right hand side. This distinguishes it from a context-sensitive grammar, which can have production rules in the form ${\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }$ with ${\displaystyle A}$ a nonterminal symbol and ${\displaystyle \alpha }$, ${\displaystyle \beta }$, and ${\displaystyle \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,

${\displaystyle \langle {\text{Stmt}}\rangle \to \langle {\text{Id}}\rangle =\langle {\text{Expr}}\rangle ;}$

replaces ${\displaystyle \langle {\text{Stmt}}\rangle }$ with ${\displaystyle \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.^[2]

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.

Background

Since at least the time of the ancient Indian scholar Pāṇini, linguists have described the grammars of languages in terms of their block structure, and described how sentences are recursively built up from smaller phrases, and eventually individual words or word elements. An essential property of these block structures is that logical units never overlap. For example, the sentence:

John, whose blue car was in the garage, walked to the grocery store.

can be logically parenthesized (with the logical metasymbols ) as follows:

, whose blue car was in the garage, walked to the grocery store.

A context-free grammar provides a simple and mathematically precise mechanism for describing the methods by which phrases in some natural language are built from smaller blocks, capturing the "block structure" of sentences in a natural way. Its simplicity makes the formalism amenable to rigorous mathematical study. Important features of natural language syntax such as agreement and reference are not part of the context-free grammar, but the basic recursive structure of sentences, the way in which clauses nest inside other clauses, and the way in which lists of adjectives and adverbs are swallowed by nouns and verbs, is described exactly.

Context-free grammars are a special form of Semi-Thue systems that in their general form date back to the work of Axel Thue.

The formalism of context-free grammars was developed in the mid-1950s by Noam Chomsky,^[3] and also their classification as a special type of formal grammar (which he called phrase-structure grammars).^[4] Some authors, however, reserve the term for more restricted grammars in the Chomsky hierarchy: context-sensitive grammars or context-free grammars. In a broader sense, phrase structure grammars are also known as constituency grammars. The defining trait of phrase structure grammars is thus their adherence to the constituency relation, as opposed to the dependency relation of dependency grammars. In Chomsky's generative grammar framework, the syntax of natural language was described by context-free rules combined with transformation rules.^[5]

Block structure was introduced into computer programming languages by the Algol project (1957–1960), which, as a consequence, also featured a context-free grammar to describe the resulting Algol syntax. This became a standard feature of computer languages, and the notation for grammars used in concrete descriptions of computer languages came to be known as Backus–Naur form, after two members of the Algol language design committee.^[3] The "block structure" aspect that context-free grammars capture is so fundamental to grammar that the terms syntax and grammar are often identified with context-free grammar rules, especially in computer science. Formal constraints not captured by the grammar are then considered to be part of the "semantics" of the language.

Context-free grammars are simple enough to allow the construction of efficient parsing algorithms that, for a given string, determine whether and how it can be generated from the grammar. An Earley parser is an example of such an algorithm, while the widely used LR and LL parsers are simpler algorithms that deal only with more restrictive subsets of context-free grammars.

Formal definitionsedit

A context-free grammar G is defined by the 4-tuple ${\displaystyle G=(V,\Sigma ,R,S)}$, where^[6]

1. V is a finite set; each element ${\displaystyle 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 G.
2. Σ is a finite set of terminals, disjoint from V, which make up the actual content of the sentence. The set of terminals is the alphabet of the language defined by the grammar G.
3. R is a finite relation in ${\displaystyle V\times (V\cup \Sigma )^{*}}$, where the asterisk represents the Kleene star operation. The members of R are called the (rewrite) rules or productions of the grammar. (also commonly symbolized by a P)
4. S is the start variable (or start symbol), used to represent the whole sentence (or program). It must be an element of V.

Production rule notationedit

A production rule in R is formalized mathematically as a pair ${\displaystyle (\alpha ,\beta )\in R}$, where ${\displaystyle \alpha \in V}$ is a nonterminal and ${\displaystyle \beta \in (V\cup \Sigma )^{*}}$ is a string of variables and/or terminals; rather than using ordered pair notation, production rules are usually written using an arrow operator with ${\displaystyle \alpha }$ as its left hand side and β as its right hand side: ${\displaystyle \alpha \rightarrow \beta }$.

It is allowed for β to be the empty string, and in this case it is customary to denote it by ε. The form ${\displaystyle \alpha \rightarrow \varepsilon }$ is called an ε-production.^[7]

It is common to list all right-hand sides for the same left-hand side on the same line, using | (the vertical bar) to separate them. Rules ${\displaystyle \alpha \rightarrow \beta _{1}}$ and ${\displaystyle \alpha \rightarrow \beta _{2}}$ can hence be written as ${\displaystyle \alpha \rightarrow \beta _{1}\mid \beta _{2}}$. In this case, ${\displaystyle \beta _{1}}$ and ${\displaystyle \beta _{2}}$ are called the first and second alternative, respectively.

Rule applicationedit

For any strings ${\displaystyle u,v\in (V\cup \Sigma )^{*}}$, we say u directly yields v, written as ${\displaystyle u\Rightarrow v\,}$, if ${\displaystyle \exists (\alpha ,\beta )\in R}$ with $$Zdroj:https://en.wikipedia.org?pojem=Context-free_grammar
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.