| dbpprop:abstract
|
- In formal language theory, a context-free grammar (CFG) is a grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (possibly empty). Thus, the difference with arbitrary grammars is that the left hand side of a production rule is always a single nonterminal symbol rather than a string of terminal and/or nonterminal symbols. The term "context-free" expresses the fact that nonterminals are rewritten without regard to the context in which they occur. A formal language is context-free if some context-free grammar generates it. These languages are exactly all languages that can be recognized by a non-deterministic pushdown automaton. Context-free grammars play a central role in the description and design of programming languages and compilers. They are also used for analyzing the syntax of natural languages.
- Die kontextfreien Grammatiken sind eine Klasse formaler Grammatiken und sind identisch mit den Typ-2-Grammatiken der Chomsky-Hierarchie.
- V lingvistice a informatice označuje pojem bezkontextová gramatika (CFG) formální gramatiku, ve které mají všechna přepisovací pravidla tvar A → β kde A je neterminál a β je řetězec terminálů a/nebo neterminálů. Název „bezkontextová“ vychází ze skutečnosti, že neterminál se může přepsat na β bez ohledu na okolní kontext. Jazyky generované bezkontextovými gramatikami se nazývají bezkontextové. Bezkontextová gramatika je speciálním případem gramatiky kontextové (kontext je prázdný).
- En lingüística e informática, una gramática libre de contexto 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 síntaxis 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 como 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.
- Yhteydetön kielioppi tai kontekstiton kielioppi on kielitieteessä ja tietojenkäsittelytieteessä formaali kielioppi, jossa jokainen kirjoitussääntö on muotoa V → w missä V on välike (välisymboli) ja w päätemerkeistä (päätesymboleista) ja/tai välikkeistä koostuva merkkijono. Korvauksen voi tehdä aina riippumatta V:n kontekstista eli sitä ympäröivistä symboleista; tästä nimi yhteydetön tai kontekstiton. Formaali kieli on yhteydetön jos sen tuottaa yhteydetön kielioppi.
- En linguistique et en informatique, une grammaire non contextuelle, grammaire hors-contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de production (ou simplement production) est de la forme V → w où V est un symbole non terminal et w est une chaîne composée de terminaux et/ou de non-terminaux. Le terme « non contextuel » provient du fait qu'un non-terminal V peut toujours être remplacé par w, sans prendre en compte son contexte. Un langage formel est non contextuel (ou hors-contexte) s'il existe une grammaire non contextuelle qui le génère. Les grammaires non contextuelles sont suffisamment puissantes pour décrire la syntaxe de la plupart des langages de programmation, avec au besoin quelques extensions; la syntaxe de la majorité des langages de programmation est en fait spécifiée à l'aide de grammaires non contextuelles. Ces grammaires sont cependant suffisamment simples pour permettre la création d'analyseurs syntaxiques efficaces qui, pour une chaîne donnée, déterminent si et comment elle peut être générée à partir de la grammaire. Voir l'analyse Earley pour un exemple d'un tel algorithme. Les analyses LR et les analyses LL sont des méthodes pour analyser des sous-ensembles plus restrictifs de grammaires hors-contexte. La BNF est la notation la plus communément utilisée pour décrire une grammaire non contextuelle.
- A nyelvészetben és az informatikában a környezetfüggetlen nyelvtan, angol kifejezéssel és rövidítéssel context-free grammar (CFG) egy formális nyelvtan, amelyben minden produkciós szabály a következő formájú: V → w, ahol V egy nem-terminális szimbólum és w egy jelsorozat, amely terminális és/vagy nem-terminális szimbólumokat tartalmaz. A „környezetfüggetlen” kifejezés abból a tényből ered, hogy a nem-terminális V minden esetben helyettesíthető w-vel, függetlenül attól, hogy milyen környezetben fordul V elő. Egy formális nyelv akkor környezetfüggetlen ha környezetfüggetlen nyelvtan generálja. A környezetfüggetlen nyelvtanok kellően hatékonyak és erősek a legtöbb programozási nyelv szintaxisának leírásához; valójában a legtöbb programozási nyelv szintaxisának meghatározására környezetfüggetlen nyelvtanokat használnak. A környezetfüggetlen nyelvtanok egyszerűen elegendőek egy hatékony elemző algoritmus konstruálásához, amely egy adott jelsorozatról eldönti, hogy létrehozható-e az adott nyelvtan alapján. A BNF a legismertebb jelölési rendszer a környezetfüggetlen nyelvtan kifejezéseinek leírására. Nem minden formális nyelv környezetfüggetlen – a jól ismert az <math> \{ a^n b^n c^n : n \ge 0 \} </math> nyelv. Ez a sajátos nyelv egy parsing expression nyelvtannal generálható, ami viszonylag új formalizmus ami különösen jól illeszkedik a programozási nyelvekhez.
- In informatica e in linguistica, una grammatica context-free (grammatica libera dal contesto o CFG) è 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 ::= w V → 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. 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 <math> \{ a^n b^n c^n : n \ge 0 \} </math>. Questo particolare linguaggio può essere generato da una grammatica di parsing di espressione, un formalismo relativamente nuovo seguito particolarmente dai linguaggi di programmazione.
- 文脈自由文法（ぶんみゃくじゆうぶんぽう、Context-free Grammar、CFG）とは、言語学や情報工学において全生成規則が以下の形式である形式文法のひとつである。 ここで V は非終端記号であり、w は終端文字と非終端記号から構成される文字列である。「文脈自由」という用語は前後関係に依存せずに非終端記号 V を w に置換できることを意味している。文脈自由文法によって生成される形式言語を文脈自由言語という。
- Een context-vrije grammatica is een formele grammatica waarbij alle productieregels de volgende vorm hebben: <math>V \rightarrow w</math> waarbij V een niet-terminaal symbool is en w een string met terminale en niet-terminale symbolen. Dit soort formele grammatica's worden context-vrij genoemd omdat ze toegepast kunnen worden ongeacht de context waarin het niet-terminale symbool V zich bevindt. Een formele taal is een context-vrije taal als het door een context-vrije grammatica gegenereerd kan worden. Context-vrije grammatica's worden veel gebruikt bij het beschrijven en ontwerpen van programmeertalen en compilers. Ze worden ook gebruikt voor het analyseren van de syntaxis van natuurlijke talen.
- Gramatyka bezkontekstowa to gramatyka formalna, w której wszystkie reguły wyprowadzania wyrażeń są postaci: <math>A \rightarrow \Gamma</math> gdzie A jest dowolnym symbolem nieterminalnym i jego znaczenie nie zależy od kontekstu, w jakim występuje, a <math>\Gamma</math> to dowolny (być może pusty) ciąg symboli terminalnych i nieterminalnych. Każdy język bezkontekstowy generowany jest przez pewną gramatykę bezkontekstową.
- Em Teoria da computação as Gramáticas livres de contexto são também conhecidas como Tipo 2 da Hierarquia de Chomsky, são aquelas em que é levantado o condicionamento das substituições impostas pelas regras definidas pelas produções. Este condicionamento é eliminado impondo às produções uma restrição adicional, que restringe as produções à forma geral <math>A\rightarrow \beta</math> onde <math>A\in V_n</math> e <math>\beta\in (V_n\cup V_t)^*</math> Em lingüística e teoria da computação, gramáticas livres de contexto ou gramáticas independentes de contexto, de nível 2 na hierarquia de Chomsky, também chamadas gramáticas algébricas são gramáticas formais cujas regras de produção são da forma seguinte : V → w onde V é um símbolo não-terminal e w é uma cadeia composta de terminais e/ou de não-terminais. O termo « livre de contexto » vem da idéia de que um não-terminal V sempre pode ser trocado por w, sem tomar conta de seu contexto. Definimos uma linguagem formal como livre-de-contexto se existe uma gramática livre-de-contexto que a produz). As gramáticas livres-de-contexto são bastante potentes para descrever a sintaxe da maioria das linguagens de programação, necessitando as vezes algumas extensões; a sintaxe da maioria das linguagens de programação são na verdade especificadas usando gramáticas livres-de-contexto. Essas gramáticas são no entanto bastante simples para permitir a criação de analisadores eficientes, os quais, por uma cadeia definida, determinam como elas podem ser geradas a partir da gramática. Consultar a análise de Earley para um exemplo de um determinado algoritmo. As análises LR e as análises LL aparecem como métodos para analisar sob-conjuntos mais restritivos de gramáticas livres-de-contexto. La BNF (Backus Naur form) é a notação usada com mais frenqüência para descrever uma gramática livre-de-contexto. Forma Normal de Backus
- Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются нетерминалами. Смысл термина «контекстно-свободная» заключается в том, что возможность применить продукцию к нетерминалу, в отличие от общего случая грамматики Хомского, не зависит от контекста этого нетерминала. Язык, который может быть задан КС-грамматикой, называется контекстно-свободным языком или КС-языком. Следует заметить, что по сути КС-грамматика — другая форма БНФ.
- Kontextfri grammatik är en särskild typ av formell grammatik. Kontextfri grammatik förkortas ofta med CFG (av eng. context-free grammar). Kontextfri grammatik beskrevs först av Noam Chomsky i den s.k. Chomskyhierarkin. Det går att skapa mycket effektiva parsrar för kontextfri grammatik. Det finns en uppsjö av sätt att skriva en kontextfri grammatik på men det vanligaste är en uppsättning regler med ett vänster och ett höger-led där vänsterledet består av en icke-terminal symbol (Fraskategori) och där högerledet består av en eller flera terminala eller icke-terminala symboler som vänsterledet kan skrivas om till. Exempel: S --> NP VP NP --> N VP --> V V --> läser N --> barnet Denna lilla grammatik kan bara generera satsen "Barnet läser" genom att S(startsymbol) får skrivas om till NP(nominalfras) följd av en VP(Verbfras). NP får skrivas om till ett N(Substantiv) och VP får skrivas om till V(Verb). Grammatiken tillåter bara ett verb(läser) och ett substantiv(barnet) så följden blir att den bara kan generera frasen "barnet läser".
- 在计算机科学中，若一个形式文法 G = (N, Σ, P, S) 的产生式规则都取如下的形式：V -> w，則称之为上下文无关的，其中 V∈N ，w∈(N∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换，而无需考虑字符 V 出现的上下文。一个形式语言是上下文无关的，如果它是由上下文无关文法生成的（条目上下文无关语言）。 上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法；实际上，几乎所有程序设计语言都是通过上下文无关文法来定义的。另一方面，上下文无关文法又足够简单，使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。例子可以参见 LR 分析器和 LL 分析器。 BNF（巴克斯-诺尔范式）经常用来表达上下文无关文法。
|
| rdfs:comment
|
- In formal language theory, a context-free grammar (CFG) is a grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (possibly empty). Thus, the difference with arbitrary grammars is that the left hand side of a production rule is always a single nonterminal symbol rather than a string of terminal and/or nonterminal symbols.
- Die kontextfreien Grammatiken sind eine Klasse formaler Grammatiken und sind identisch mit den Typ-2-Grammatiken der Chomsky-Hierarchie.
- V lingvistice a informatice označuje pojem bezkontextová gramatika (CFG) formální gramatiku, ve které mají všechna přepisovací pravidla tvar A → β kde A je neterminál a β je řetězec terminálů a/nebo neterminálů. Název „bezkontextová“ vychází ze skutečnosti, že neterminál se může přepsat na β bez ohledu na okolní kontext. Jazyky generované bezkontextovými gramatikami se nazývají bezkontextové.
- En lingüística e informática, una gramática libre de contexto 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.
- Yhteydetön kielioppi tai kontekstiton kielioppi on kielitieteessä ja tietojenkäsittelytieteessä formaali kielioppi, jossa jokainen kirjoitussääntö on muotoa V → w missä V on välike (välisymboli) ja w päätemerkeistä (päätesymboleista) ja/tai välikkeistä koostuva merkkijono. Korvauksen voi tehdä aina riippumatta V:n kontekstista eli sitä ympäröivistä symboleista; tästä nimi yhteydetön tai kontekstiton.
- En linguistique et en informatique, une grammaire non contextuelle, grammaire hors-contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de production (ou simplement production) est de la forme V → w où V est un symbole non terminal et w est une chaîne composée de terminaux et/ou de non-terminaux.
- A nyelvészetben és az informatikában a környezetfüggetlen nyelvtan, angol kifejezéssel és rövidítéssel context-free grammar (CFG) egy formális nyelvtan, amelyben minden produkciós szabály a következő formájú: V → w, ahol V egy nem-terminális szimbólum és w egy jelsorozat, amely terminális és/vagy nem-terminális szimbólumokat tartalmaz.
- In informatica e in linguistica, una grammatica context-free (grammatica libera dal contesto o CFG) è 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 ::= w V → w dove V è un simbolo non terminale e w è una sequenza di simboli terminali e non terminali.
- Een context-vrije grammatica is een formele grammatica waarbij alle productieregels de volgende vorm hebben: <math>V \rightarrow w</math> waarbij V een niet-terminaal symbool is en w een string met terminale en niet-terminale symbolen. Dit soort formele grammatica's worden context-vrij genoemd omdat ze toegepast kunnen worden ongeacht de context waarin het niet-terminale symbool V zich bevindt.
- Gramatyka bezkontekstowa to gramatyka formalna, w której wszystkie reguły wyprowadzania wyrażeń są postaci: <math>A \rightarrow \Gamma</math> gdzie A jest dowolnym symbolem nieterminalnym i jego znaczenie nie zależy od kontekstu, w jakim występuje, a <math>\Gamma</math> to dowolny (być może pusty) ciąg symboli terminalnych i nieterminalnych. Każdy język bezkontekstowy generowany jest przez pewną gramatykę bezkontekstową.
- Em Teoria da computação as Gramáticas livres de contexto são também conhecidas como Tipo 2 da Hierarquia de Chomsky, são aquelas em que é levantado o condicionamento das substituições impostas pelas regras definidas pelas produções.
- Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются нетерминалами.
- Kontextfri grammatik är en särskild typ av formell grammatik. Kontextfri grammatik förkortas ofta med CFG (av eng. context-free grammar). Kontextfri grammatik beskrevs först av Noam Chomsky i den s.k. Chomskyhierarkin. Det går att skapa mycket effektiva parsrar för kontextfri grammatik.
|
![[RDF Data]](/statics/sw-cube.png)
