A context-free grammar (CFG) is a term used in formal language theory to describe a certain type of formal grammar. A context-free grammar is a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements. For example, the rule Replaces with . There can be multiple replacement rules for any given value. For example, means that can be replaced with either or . and but not . Rules can also be applied in reverse to check if a string is grammatically correct according to the grammar. and . If we start with the nonterminal symbol to turn into and

Property Value
dbo:abstract
  • A context-free grammar (CFG) is a term used in formal language theory to describe a certain type of formal grammar. A context-free grammar is a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements. For example, the rule Replaces with . There can be multiple replacement rules for any given value. For example, means that can be replaced with either or . In context-free grammars, all rules are one to one, one to many, or one to none. These rules can be applied regardless of context. The left-hand side of the production rule is also always a nonterminal symbol. This means that the symbol does not appear in the resulting formal language. So in our case, our language contains the letters and but not . Rules can also be applied in reverse to check if a string is grammatically correct according to the grammar. Here is an example context-free grammar which describes all two-letter strings containing the letters and . If we start with the nonterminal symbol then we can use the rule to turn into . We can then apply one of the two later rules. For example, if we apply to the first we get . If we then apply to the second we get . Since both and are terminal symbols, and in context-free grammars terminal symbols never appear on the left hand side of a production rule, there are no more rules that can be applied. This same process can be used, applying the second two rules in different orders in order to get all possible strings within our simple context-free grammar. 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 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. (en)
  • In der Theorie der formalen Sprachen ist eine kontextfreie Grammatik eine formale Grammatik, die nur solche Ersetzungsregeln enthält, bei denen immer genau ein Nichtterminalsymbol auf eine beliebig lange Folge von Nichtterminal- und Terminalsymbolen abgeleitet wird. Die Ersetzungsregeln haben also die Form (mit Nichtterminalsymbol und Zeichenkette bestehend aus Nichtterminal- und/oder Terminalsymbolen). Weil die linke Seite einer Regel nur aus einem einzigen Nichtterminalsymbol besteht, hängt ihre Anwendbarkeit auf eine Zeichenkette nur davon ab, ob das Nichtterminalsymbol in der Zeichenkette vorkommt, nicht aber davon, in welchem Kontext es sich befindet. Die Regeln sind also kontextfrei. Die kontextfreien Grammatiken sind identisch mit den Typ-2-Grammatiken der Chomsky-Hierarchie. (de)
  • En lingüística e informática, una gramática libre de contexto (o de contexto libre) es una gramática formal en la que cada regla de producción es de la forma: V → w Donde V es un símbolo no terminal y w es una cadena de terminales y/o no terminales. El término libre de contexto se refiere al hecho de que el no terminal V puede siempre ser sustituido por w sin tener en cuenta el contexto en el que ocurra. Un lenguaje formal es libre de contexto si hay una gramática libre de contexto que lo genera. Las gramáticas libres de contexto permiten describir la mayoría de los lenguajes de programación, de hecho, la sintaxis de la mayoría de lenguajes de programación está definida mediante gramáticas libres de contexto. Por otro lado, estas gramáticas son suficientemente simples como para permitir el diseño de eficientes algoritmos de análisis sintáctico que, para una cadena de caracteres dada determinen cómo puede ser generada desde la gramática. Los analizadores LL y LR tratan restringidos subconjuntos de gramáticas libres de contexto. La notación más frecuentemente utilizada para expresar gramáticas libres de contexto es la forma Backus-Naur. (es)
  • En linguistique et en informatique théorique, une grammaire algébrique, ou grammaire non contextuelle, aussi appelée grammaire hors-contexte ou grammaire « context-free » est une grammaire formelle dans laquelle chaque règle de production est de la forme où est un symbole non terminal et est une chaîne composée de terminaux et/ou de non-terminaux. Le terme « non contextuel » provient du fait qu'un non terminal peut être remplacé par , sans tenir compte du contexte où il apparaît. Un langage formel est non contextuel (ou hors contexte, ou encore algébrique) s'il existe une grammaire non contextuelle qui l'engendre. Les grammaires algébriques sont suffisamment puissantes pour décrire la partie principale de la syntaxe de la plupart des langages de programmation, avec au besoin quelques extensions. La forme de Backus-Naur est la notation la plus communément utilisée pour décrire une grammaire non contextuelle décrivant un langage de programmation. Dans la hiérarchie de Chomsky ces grammaires sont de type 2. Si on trouve plusieurs termes pour nommer une grammaire algébrique, c'est que le terme anglais « context-free » est malcommode à traduire. Tous les termes donnés plus haut sont employés et équivalents. (fr)
  • In informatica e in linguistica, una grammatica context-free (o libera dal contesto, CFG o non contestuale) è una grammatica formale in cui ogni regola sintattica è espressa sotto forma di derivazione di un simbolo a sinistra a partire da uno o più simboli a destra. Ciò può essere espresso con due simbolismi equivalenti (nel seguito verrà utilizzato il secondo simbolismo): V ::= wV → w dove V è un simbolo non terminale e w è una sequenza di simboli terminali e non terminali. Il termine "context-free" (libera dal contesto) si riferisce al fatto che il simbolo non terminale V può sempre essere sostituito da w, indipendentemente dai simboli che lo precedono o lo seguono. Un linguaggio formale si dice context-free se esiste una grammatica context-free che lo genera. Nella gerarchia di Chomsky le grammatiche libere dal contesto sono dette di Tipo 2. Le grammatiche context-free sono abbastanza potenti da descrivere la sintassi della maggior parte dei linguaggi di programmazione; al tempo stesso, sono abbastanza semplici da consentire un parsing molto efficiente. La notazione formale di Backus-Naur (BNF) è la sintassi più comunemente usata per descrivere grammatiche context-free. Non tutti i linguaggi formali sono context-free — un conosciuto controesempio è il seguente . Questo particolare linguaggio può essere generato da una grammatica di parsing di espressione, un formalismo relativamente nuovo seguito particolarmente dai linguaggi di programmazione. (it)
  • 文脈自由文法(ぶんみゃくじゆうぶんぽう、Context-free Grammar、CFG)とは、言語学や情報工学において全生成規則が以下の形式である形式文法のひとつである。 V → w ここで V は非終端記号であり、w は終端記号と非終端記号から構成される文字列である。「文脈自由」という用語は前後関係に依存せずに非終端記号 V を w に置換できることを意味している。文脈自由文法によって生成される形式言語を文脈自由言語という。 (ja)
  • Gramatyka bezkontekstowa – gramatyka formalna, w której wszystkie reguły wyprowadzania wyrażeń są postaci: , gdzie: – dowolny symbol nieterminalny, jego znaczenie nie zależy od kontekstu, w jakim występuje; – dowolny (być może pusty) ciąg symboli terminalnych i nieterminalnych. Każdy język bezkontekstowy generowany jest przez pewną gramatykę bezkontekstową. (pl)
  • Een contextvrije grammatica is een formele grammatica waarbij alle productieregels de volgende vorm hebben: waarbij V een niet-terminaal symbool is en w een (mogelijk lege) string met terminale en niet-terminale symbolen. Dit soort formele grammatica's worden contextvrij genoemd omdat de manieren waarop een niet-terminaal symbool herschreven kan worden onafhankelijk zijn van de context waarin het zich bevindt. Contextvrije grammatica's genereren contextvrije talen. Contextvrije grammatica's worden veel gebruikt bij het beschrijven en ontwerpen van programmeertalen en compilers, waarbij vaak de notatietechnieken Backus-Naur Form (BNF) of EBNF gebruikt worden.Ze worden ook gebruikt voor het analyseren van de syntaxis van natuurlijke talen. (nl)
  • A gramatica livre de contexto (GLC), em teoria de linguagem formal, é uma gramática formal onde todas as regras de produções são da forma Onde é um símbolo não terminal, e é uma cadeia de terminal e/ou não terminais (pode ser vazia). Uma linguagem formal é considerada “livre do contexto” quando suas regras de produções podem ser aplicadas independentemente do contexto do simbolo não terminal. Não importa quais símbolos existem na GLC, um único símbolo não terminal existente no lado esquerdo de uma regra pode sempre ser substituído pelo lado direito. E isso é o que distingue a GLC da gramática sensível ao contexto (GSC) Essa gramática tem uma longa lista de palavras, e também regras sobre os tipos de palavras que podem ser adicionadas e em qual ordem. Normas superiores combina várias regras inferiores para fazer uma frase. Uma sentença pode ser gramaticalmente correta, mas pode não ter nenhum significado. Cada regra tem o seu próprio símbolo, o qual pode ser substituído com símbolos que representam as regras inferior, que podem ser substituídos com palavras. Isso também pode ser feito na ordem inversa para verificar se uma frase é gramaticalmente correta. Linguagens geradas por gramáticas livres de contexto são conhecidos como linguagens livres de contexto (LLC). Diferentes gramáticas livres de contexto podem gerar a mesma linguagem livre de contexto. O problema da igualdade de idioma (É possível fazer duas dadas gramáticas livres de contexto gerar a mesma língua?) É indecidível. Gramáticas livres de contexto surgiu da linguística, onde são utilizadas para descrever a estrutura das frases e palavras em linguagem natural, e elas foram, de fato, inventada pelo linguista Noam Chomsky para este fim,mas não foram utilizadas da maneira originalmente esperada. Em contrapartida, em ciência da computação, como o uso de conceitos recursivamente definidos aumentou, as GLCs foram usados mais e mais. As primeiras aplicações das gramáticas eram principalmente para descrever a estrutura de linguagens de programação. Uma aplicação mais recente, foi a utilização de GLC em uma parte essencial da Extensible Markup Language (XML) chamada de definição do tipo de documento. Na linguística, alguns autores usam o termo gramática de estrutura frasal para se referir a gramáticas livres de contexto, em que gramática de estrutura frasal são distintas das gramáticas de dependência. Na ciência da computação, uma notação popular para gramáticas livres de contexto é Formalismo de Backus-Naur, ou BNF. (pt)
  • Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются одиночными нетерминалами (объектами, обозначающими какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющими конкретного символьного значения). Смысл термина «контекстно-свободная» заключается в том, что есть возможность применить продукцию к нетерминалу, в отличие от общего случая неограниченной грамматики Хомского, не зависит от контекста этого нетерминала. Язык, который может быть задан КС-грамматикой, называется контекстно-свободным языком или КС-языком. Следует заметить, что по сути КС-грамматика — другая форма БНФ. (ru)
  • 上下文无关文法(英语:context-free grammar,縮寫為CFG),在计算机科学中,若一个形式文法 G = (N, Σ, P, S) 的产生式规则都取如下的形式:V -> w,則謂之。其中 V∈N ,w∈(N∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换,而无需考虑字符 V 出现的上下文。一个形式语言是上下文无关的,如果它是由上下文无关文法生成的(条目上下文无关语言)。 上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法;实际上,几乎所有程序设计语言都是通过上下文无关文法来定义的。另一方面,上下文无关文法又足够简单,使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。例子可以参见 LR 分析器和 LL 分析器。 BNF(巴克斯-诺尔范式)经常用来表达上下文无关文法。 (zh)
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 6759 (xsd:integer)
dbo:wikiPageRevisionID
  • 744554892 (xsd:integer)
dct:subject
rdf:type
rdfs:comment
  • 文脈自由文法(ぶんみゃくじゆうぶんぽう、Context-free Grammar、CFG)とは、言語学や情報工学において全生成規則が以下の形式である形式文法のひとつである。 V → w ここで V は非終端記号であり、w は終端記号と非終端記号から構成される文字列である。「文脈自由」という用語は前後関係に依存せずに非終端記号 V を w に置換できることを意味している。文脈自由文法によって生成される形式言語を文脈自由言語という。 (ja)
  • Gramatyka bezkontekstowa – gramatyka formalna, w której wszystkie reguły wyprowadzania wyrażeń są postaci: , gdzie: – dowolny symbol nieterminalny, jego znaczenie nie zależy od kontekstu, w jakim występuje; – dowolny (być może pusty) ciąg symboli terminalnych i nieterminalnych. Każdy język bezkontekstowy generowany jest przez pewną gramatykę bezkontekstową. (pl)
  • 上下文无关文法(英语:context-free grammar,縮寫為CFG),在计算机科学中,若一个形式文法 G = (N, Σ, P, S) 的产生式规则都取如下的形式:V -> w,則謂之。其中 V∈N ,w∈(N∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换,而无需考虑字符 V 出现的上下文。一个形式语言是上下文无关的,如果它是由上下文无关文法生成的(条目上下文无关语言)。 上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法;实际上,几乎所有程序设计语言都是通过上下文无关文法来定义的。另一方面,上下文无关文法又足够简单,使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。例子可以参见 LR 分析器和 LL 分析器。 BNF(巴克斯-诺尔范式)经常用来表达上下文无关文法。 (zh)
  • A context-free grammar (CFG) is a term used in formal language theory to describe a certain type of formal grammar. A context-free grammar is a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements. For example, the rule Replaces with . There can be multiple replacement rules for any given value. For example, means that can be replaced with either or . and but not . Rules can also be applied in reverse to check if a string is grammatically correct according to the grammar. and . If we start with the nonterminal symbol to turn into and (en)
  • In der Theorie der formalen Sprachen ist eine kontextfreie Grammatik eine formale Grammatik, die nur solche Ersetzungsregeln enthält, bei denen immer genau ein Nichtterminalsymbol auf eine beliebig lange Folge von Nichtterminal- und Terminalsymbolen abgeleitet wird. Die Ersetzungsregeln haben also die Form (mit Nichtterminalsymbol und Zeichenkette bestehend aus Nichtterminal- und/oder Terminalsymbolen). Weil die linke Seite einer Regel nur aus einem einzigen Nichtterminalsymbol besteht, hängt ihre Anwendbarkeit auf eine Zeichenkette nur davon ab, ob das Nichtterminalsymbol (de)
  • En lingüística e informática, una gramática libre de contexto (o de contexto libre) es una gramática formal en la que cada regla de producción es de la forma: V → w Donde V es un símbolo no terminal y w es una cadena de terminales y/o no terminales. El término libre de contexto se refiere al hecho de que el no terminal V puede siempre ser sustituido por w sin tener en cuenta el contexto en el que ocurra. Un lenguaje formal es libre de contexto si hay una gramática libre de contexto que lo genera. (es)
  • En linguistique et en informatique théorique, une grammaire algébrique, ou grammaire non contextuelle, aussi appelée grammaire hors-contexte ou grammaire « context-free » est une grammaire formelle dans laquelle chaque règle de production est de la forme où est un symbole non terminal et est une chaîne composée de terminaux et/ou de non-terminaux. Le terme « non contextuel » provient du fait qu'un non terminal peut être remplacé par (fr)
  • In informatica e in linguistica, una grammatica context-free (o libera dal contesto, CFG o non contestuale) è una grammatica formale in cui ogni regola sintattica è espressa sotto forma di derivazione di un simbolo a sinistra a partire da uno o più simboli a destra. Ciò può essere espresso con due simbolismi equivalenti (nel seguito verrà utilizzato il secondo simbolismo): V ::= wV → w Nella gerarchia di Chomsky le grammatiche libere dal contesto sono dette di Tipo 2. La notazione formale di Backus-Naur (BNF) è la sintassi più comunemente usata per descrivere grammatiche context-free. . (it)
  • Een contextvrije grammatica is een formele grammatica waarbij alle productieregels de volgende vorm hebben: waarbij V een niet-terminaal symbool is en w een (mogelijk lege) string met terminale en niet-terminale symbolen. Dit soort formele grammatica's worden contextvrij genoemd omdat de manieren waarop een niet-terminaal symbool herschreven kan worden onafhankelijk zijn van de context waarin het zich bevindt. Contextvrije grammatica's genereren contextvrije talen. (nl)
  • A gramatica livre de contexto (GLC), em teoria de linguagem formal, é uma gramática formal onde todas as regras de produções são da forma Onde é um símbolo não terminal, e é uma cadeia de terminal e/ou não terminais (Isso também pode ser feito na ordem inversa para verificar se uma frase é gramaticalmente correta. (pt)
  • Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются одиночными нетерминалами (объектами, обозначающими какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющими конкретного символьного значения). Смысл термина «контекстно-свободная» заключается в том, что есть возможность применить продукцию к нетерминалу, в отличие от общего случая неограниченной грамматики Хомского, не зависит от контекста этого нетерминала. (ru)
rdfs:label
  • Context-free grammar (en)
  • Kontextfreie Grammatik (de)
  • Gramática libre de contexto (es)
  • Grammaire non contextuelle (fr)
  • Grammatica libera dal contesto (it)
  • 文脈自由文法 (ja)
  • Contextvrije grammatica (nl)
  • Gramatyka bezkontekstowa (pl)
  • Gramática livre de contexto (pt)
  • Контекстно-свободная грамматика (ru)
  • 上下文无关文法 (zh)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is foaf:primaryTopic of