http://wiki.karljones.com/index.php?action=history&feed=atom&title=Context-free_grammar 2026-10-23T21:42:33Z Revision history for this page on the wiki MediaWiki 1.24.2 http://wiki.karljones.com/index.php?title=Context-free_grammar&diff=14928&oldid=prev 2016-05-09T14:49:09Z

<p>Created page with &quot;In <a href="/index.php/Formal_language" title="Formal language">formal language</a> theory, a &#039;&#039;&#039;context-free grammar&#039;&#039;&#039; (&#039;&#039;&#039;CFG&#039;&#039;&#039;) is a <a href="/index.php/Formal_grammar" title="Formal grammar">formal grammar</a>. == Description == A context-free grammar is a <a href="/index.php/Formal_grammar" title="Formal grammar">formal grammar</a> in which ev...&quot;</p> <p><b>New page</b></p><div>In [[formal language]] theory, a '''context-free grammar''' ('''CFG''') is a [[formal grammar]].<br /> <br /> == Description ==<br /> <br /> A context-free grammar is a [[formal grammar]] in which every production rule is of the form<br /> <br /> A\ \to\ \alpha<br /> <br /> where A is a single nonterminal symbol, and \alpha is a string of terminals and/or nonterminals (\alpha can be empty).<br /> <br /> A formal grammar is considered &quot;context free&quot; when its production rules can be applied regardless of the context of a nonterminal.<br /> <br /> No matter which symbols surround it, the single nonterminal on the left hand side can always be replaced by the right hand side.<br /> <br /> This is what distinguishes it from a [[context-sensitive grammar]].<br /> <br /> Such a grammar has long lists of words, and also rules on what types of words can be added in what order.<br /> <br /> Higher rules combine several lower rules to make a sentence. Such sentences will be grammatically correct, but may not have any meaning.<br /> <br /> Each rule has its own symbol, which can be replaced with symbols representing lower rules, which can be replaced with words.<br /> This can also be done in reverse to check if a sentence is grammatically correct.<br /> <br /> Languages generated by context-free grammars are known as context-free languages (CFL). Different context-free grammars can generate the same context-free language.<br /> <br /> It is important to distinguish properties of the language (intrinsic properties) from properties of a particular grammar (extrinsic properties).<br /> <br /> The language equality question (do two given context-free grammars generate the same language?) is undecidable.<br /> <br /> 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.<br /> <br /> By contrast, in [[computer science]], as the use of [[recursively]] defined concepts increased, they were used more and more.<br /> <br /> In an early application, grammars are used to describe the structure of [[programming languages]].<br /> <br /> In a newer application, they are used in an essential part of the [[Extensible Markup Language]] (XML) called the [[Document Type Definition]].<br /> <br /> 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.<br /> <br /> In [[computer science]], a popular notation for context-free grammars is [[Backus–Naur Form]], or BNF.<br /> <br /> == See also ==<br /> <br /> * [[Context-sensitive grammar]]<br /> * [[Deterministic context-free grammar]]<br /> * [[Deterministic parsing]]<br /> * [[Formal language]]<br /> * [[LL parser]]<br /> <br /> == External links == <br /> <br /> * [https://en.wikipedia.org/wiki/Deterministic_context-free_grammar Context-free grammar] @ Wikiepedia<br /> <br /> [[Category:Computer science]]<br /> [[Category:Computing]]<br /> [[Category:Formal languages]]</div>

Karl Jones