Mostrar código-fonte de Gramática livre de contexto

A '''gramática livre de contexto''' (GLC), em teoria de [[linguagem formal]], é uma gramática formal onde todas as regras de produções são da forma:

* <math>A\ \to\ \alpha</math>

&nbsp;<math>A</math>&nbsp;é um símbolo [[Símbolos terminais e não terminais|não terminal]], e&nbsp;<math>\alpha</math>&nbsp; é uma cadeia de [[Símbolos terminais e não terminais|terminal]] e/ou não terminais&nbsp;(<math>\alpha</math> pode ser vazia).&nbsp;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.&nbsp;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 combinam 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 inferiores, 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 conhecidas como [[Linguagem livre de contexto|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 surgiram da [[linguística]], onde são utilizadas para descrever a estrutura das frases e palavras em [[linguagem natural]], e elas foram, de fato, inventadas 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 usadas 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 [[XML|Extensible Markup Language]] (XML) chamada de definição do tipo de documento.<ref>''Introduction to Automata Theory, Languages, and Computation'', John E. Hopcroft, Rajeen Motwani, Jeffrey D. Ullman, Addison Wesley, 2001, p.191</ref>

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]].

== Antecedentes ==
Desde o tempo de [[Pānini|Pāṇini]], pelo menos, os linguistas têm descrito as [[gramática]]s de línguas em termos de sua estrutura de blocos, e descrito como as sentenças são [[Recursividade|recursivamente]] construídas a partir de frases menores e, eventualmente, palavras individuais ou elementos nominativos. Uma propriedade essencial destas estruturas de bloco é que as unidades lógicas não se sobrepõem. Por exemplo, a frase:

* João, cujo carro azul estava na garagem, andou para o supermercado.
* pode ser logicamente reescrita utilizando-se colchetes como meta-símbolos lógicos '''[]''', como se segue:
* '''['''João'''[''','''['''cujo '''['''carro azul''']] ['''estava '''['''em '''['''a garagem''']]]''',''']]''' '''['''andou '''['''para '''['''o supermercado''']]]'''.


Uma gramática livre de contexto fornece um mecanismo simples e matematicamente preciso para descrever os métodos pelos quais algumas frases em linguagem natural são construídas a partir de blocos menores, capturando a "estrutura de blocos" de frases de uma forma natural. Sua simplicidade faz o formalismo passível de rigoroso estudo matemático. Características importantes da [[sintaxe]] da linguagem natural, como acordo e referência, não fazem parte da gramática livre de contexto. Mas a estrutura recursiva básica de frases, a maneira em que cláusulas se alinham dentro de outras cláusulas, e a maneira em que lista de adjetivos e advérbios são engolidos por substantivos e verbos, são descritas precisamente.

O formalismo de gramáticas livres de contexto foi desenvolvido em meados dos anos 1950 por [[Noam Chomsky]],<ref name="hu106">{{harvtxt|Hopcroft|Ullman|1979}}, p.&nbsp;106.</ref> e também a sua classificação como um [[Hierarquia de Chomsky|tipo especial de gramática formal]] (que ele chamou de [[Gramática de estrutura frasal]]).<ref name="chomsky1956">{{citation
 |último = Chomsky |primeiro = Noam |autorlink =
 |título= Three models for the description of language
 |periódico= Information Theory, IEEE Transactions
 | volume = 2 |número= 3 |páginas= 113–124
 |publicado= |data=setembro de 1956
 | url = http://ieeexplore.ieee.org/iel5/18/22738/01056813.pdf?isnumber=22738&prod=STD&arnumber=1056813&arnumber=1056813&arSt=+113&ared=+124&arAuthor=+Chomsky%2C+N.
 |arquivourl= http://www.chomsky.info/articles/195609--.pdf
 |arquivodata= 2013-10-18
 | doi = 10.1109/TIT.1956.1056813| id = |acessodata= 2007-06-18}}</ref> O que Chomsky chamou de Gramática de estrutura frasal também é conhecido como gramáticas constituintes. , em que gramáticas constituintes estão em contraste com gramáticas de dependência. No quadro [[Gramática gerativa]] de Chomsky, a sintaxe da linguagem natural foi descrita por regras livres de contexto combinadas com regras de transformação.

A ''estrutura de bloco'' foi introduzida nas [[linguagens de programação]] de computador pelo projeto [[Algol]] (1957-1960), que, como consequência, também contou com uma gramática livre de contexto para descrever a resultante sintaxe Algol. Isto tornou-se uma característica padrão das linguagens de computador, e a notação de gramáticas usada em descrições concretas de linguagens de computador veio a ser conhecida como [[Formalismo de Backus-Naur]], em homenagem a dois membros do comitê de design de linguagem Algol.<ref name="hu106"/> O aspecto de "estrutura de bloco" que gramáticas livres de contexto capturam é tão fundamental à gramática, que os termos ''sintaxe'' e ''gramática'' são freqüentemente identificados com regras de gramática livre de contexto, especialmente em ciência da computação. Restrições formais não capturadas pela gramática são, então, consideradas a fazer parte da "semântica" da linguagem.

Gramáticas livres de contexto são simples o suficiente para permitir a construção de algoritmos de [[parsing|análise sintática (ou ''parsing'')]] eficientes que, para uma dada sequência de caracteres, determinam se e como ela pode ser gerada a partir da gramática. Um [[Algoritmo Earley|algoritmo ''parsing Earley'']] é um exemplo de tal algoritmo, enquanto os amplamente utilizados [[Analisador sintático LR|LR]] e [[Analisador sintático LL|LL]] [[parsing]] são algoritmos mais simples que lidam apenas com subconjuntos mais restritivos de gramáticas livres de contexto.

== Definições formais ==
A gramática livre de contexto é definida por uma 4-tuplas.<ref>The notation here is that of {{harvtxt|Sipser|1997}}, p.&nbsp;94. {{harvtxt|Hopcroft|Ullman|1979}} (p.&nbsp;79) define context-free grammars as 4-tuples in the same way, but with different variable names.</ref>

<math>G = (V, \Sigma, R, S)</math> onde:
# V é um conjunto finito; cada elemento&nbsp;<math> v\in V</math> &nbsp;é chamado de símbolo não terminal ou uma variável. Cada variável representa um tipo diferente de frase ou cláusula na sentença. As variáveis são também chamados de categorias sintáticas. Cada variável define uma sub-linguagem da linguagem definida por&nbsp;G.
# <span class="texhtml " contenteditable="false">&#x3A3;</span><span class="texhtml " contenteditable="false"></span>&nbsp;é um conjunto finito de terminais, disjuntos de&nbsp;V,&nbsp; que compõem o conteúdo real da sentença. O conjunto de terminais é o alfabeto da língua definido pela gramática&nbsp;G.
# R é uma relação finito de V para <math>(V\cup\Sigma)^{*}</math>, em que o asterisco representa a operação de[[Fecho de Kleene| fecho de Kleen]].&nbsp;Os membros do&nbsp;R são chamadas as regras de reescrita  ou produções da gramática (também comumente simbolizado por um&nbsp;P)
# S&nbsp;é a variável de início (ou símbolo inicial), usado para representar a frase inteira (ou programa). Ele deve ser um elemento de V.

=== Notação das Regras de Produção ===
A [[Gramática formal|regra de produção]] em&nbsp;R&nbsp;é formalizada matematicamente como um par  <math>(\alpha, \beta)\in R</math>, onde <math>\alpha \in V</math>é um não terminal e&nbsp;<math>\beta \in (V\cup\Sigma)^{*}</math>&nbsp;é uma [[Cadeia de caracteres|cadeia]] de variáveis e / ou terminais; ao invés de usar a notação [[par ordenado]], regras de produção são geralmente escritos usando um operador seta com α como o seu lado esquerdo e&nbsp;&#x3B2; como o seu lado direito:
<math>\alpha\rightarrow\beta</math>.

É permitido que &#x3B2;<span class="texhtml mvar" style="font-style:italic;" contenteditable="false"></span>&nbsp;seja a [[cadeia vazia]], e, neste caso, é habitual designar pelo&nbsp;ε. A forma <math>\alpha\rightarrow\varepsilon</math> é chamada de uma ε-produção.<ref>{{harvtxt|Hopcroft|Ullman|1979}}, pp. 90–92.</ref>

É comum listar todos os lados direito para o mesmo lado esquerdo na mesma linha, utilizando | (o símbolo barra vertical ) para separá-los. Regras&nbsp;.<math>\alpha\rightarrow \beta_1</math> e&nbsp;<math>\alpha\rightarrow\beta_2</math>, portanto, pode ser escrito como <math>\alpha\rightarrow\beta_1\mid\beta_2</math>. Neste caso,<math>\beta_1</math> e&nbsp;<math>\beta_2</math>&nbsp;são chamadas a primeira e segunda alternativa, respectivamente.

=== Aplicação das Regras ===
Para quaisquer cadeias <math>u, v\in (V\cup\Sigma)^{*}</math>,&nbsp;dizemos que u produz diretamente&nbsp;v, escrevendo como  &nbsp;<math>u\Rightarrow v\,</math>, se&nbsp;<math>\exists (\alpha, \beta)\in R</math> sendo<math>\alpha \in V</math> and <math>u_{1}, u_{2}\in (V\cup\Sigma)^{*}</math> de forma que  <math>u\,=u_{1}\alpha u_{2}</math> e&nbsp;<math>v\,=u_{1}\beta u_{2}</math>. Assim, v é o resultado da aplicação da regra <math>(\alpha, \beta)</math> para&nbsp;u.

=== Aplicacão repetida de regras ===
Para quaisquer palavra&nbsp;<math>u, v\in (V\cup\Sigma)^{*}, </math> , dizemos u&nbsp;'''produz&nbsp;'''v, escrevendo como <math>u\stackrel{*}{\Rightarrow} v</math> (ou&nbsp;<math>u\Rightarrow\Rightarrow v\,</math>&nbsp;como em alguns livros didáticos ), se<math>\exists k\geq 1\, \exists \, u_{1}, \cdots, u_{k}\in (V\cup\Sigma)^{*}</math> de forma que<math>u = \, u_{1} \Rightarrow u_{2} \Rightarrow \cdots \Rightarrow u_{k} \, = v</math>. Neste caso, se <math>k\geq 2</math> (i.e., <math>u \neq v</math>), a relação<math>u\stackrel{+}{\Rightarrow} v</math> mantém. Por outras palavras,&nbsp;<math>(\stackrel{*}{\Rightarrow})</math> e<math>(\stackrel{+}{\Rightarrow})</math>&nbsp;são o[[Fechamento| fechamento transitivo reflexivo]](permitindo uma palavra para produzir a si mesma) e o [[Fecho transitivo]]&nbsp;(que requer, pelo menos, uma etapa ) de&nbsp;<math>(\Rightarrow)</math>,  respectivamente.

=== Linguagem livre de contexto ===
A linguagem de uma gramática   <math>G = (V, \Sigma, R, S)</math>&nbsp;é o conjunto
: <math>L(G) = \{ w\in\Sigma^{*} : S\stackrel{*}{\Rightarrow} w\}</math>
Uma linguagem  L&nbsp;é dito ser uma linguagem livre de contexto (CFL), se existe uma GLC L, de tal modo que <math>L\,=\,L(G)</math>.

=== GLC adequadas ===
Uma gramática livre de contexto é dita ser adequada,<ref>{{citation
 |último = Nijholt |primeiro = Anton
 | isbn = 3-540-10245-0
 | mr = 590047
 |página= 8
 |publicado= Springer
 | series = Lecture Notes in Computer Science
 |título= Context-free grammars: covers, normal forms, and parsing
 | volume = 93
 |ano= 1980}}.</ref> se tiver:
* nenhum símbolo inalcançável:<math>\forall N \in V: \exists \alpha,\beta \in (V\cup\Sigma)^*: S \stackrel{*}{\Rightarrow} \alpha{N}\beta</math>
* nenhum símbolo que não possa ser produzido:<math>\forall N \in V: \exists w \in \Sigma^*: N \stackrel{*}{\Rightarrow} w</math>
* nenhuma ε-produção <math>\neg\exists N \in V: (N, \varepsilon) \in R</math>
* nenhum ciclo : <math>\neg\exists N \in V: N \stackrel{+}{\Rightarrow} N</math>
Em teoria da linguagem formal, equivalência fraca de duas gramáticas significa que elas geram o mesmo conjunto de cadeias, ou seja, que a linguagem formal que eles geram é o mesmo. Cada gramática livre de contexto pode ser transformada em uma fracamente equivalente sem símbolos inacessíveis,<ref>Hopcroft & Ullman (1979), p.88, Lemma 4.1</ref> uma fracamente equivalente sem símbolos improdutivos,<ref>Hopcroft & Ullman (1979), p.89, Lemma 4.2</ref>  e uma fracamente equivalente sem ciclos.<ref>This is a consequence of the unit-production elimination theorem in Hopcroft & Ullman (1979), p.91, Theorem 4.4</ref> Cada gramática livre de contexto que não possui produz  ε pode ser transformada em uma fracamente equivalente sem  ε-produções;<ref>Hopcroft & Ullman (1979), p.91, Theorem 4.4</ref> Ao todo, cada tal gramática pode ser transformada em uma GLC adequada fracamente equivalente.

=== Exemplo ===
A gramática  <math>G = (\{S\}, \{a, b\}, P, S)</math>, com as produções:
: <span class="texhtml " contenteditable="false">''S'' &#x2192; ''aSa''</span><span class="texhtml " contenteditable="false"></span>,
: <span class="texhtml " contenteditable="false">''S'' &#x2192; ''bSb''</span><span class="texhtml " contenteditable="false"></span>,
: <span class="texhtml " contenteditable="false">''S'' &#x2192; ''ε''</span><span class="texhtml " contenteditable="false"></span>,

é livre de contexto. Não não é adequada uma vez que inclui um ε-produção. Uma derivação típica nesta gramática é
: <span class="texhtml " contenteditable="false">''S'' &#x2192; ''aSa'' &#x2192; ''aaSaa'' &#x2192; ''aabSbaa'' &#x2192; ''aabbaa''</span><span class="texhtml " contenteditable="false"></span>.
Essa derivação deixa claro que
<math>L(G) = \{ww^R:w\in\{a,b\}^*\}</math>.&nbsp;A linguagem é livre de contexto, no entanto, pode ser provado que não é regular. 

== Exemplos ==

=== Parênteses bem formados ===
O exemplo canônico de uma gramática livre de contexto é o da correspondência de parênteses, que é representante do caso geral. Há dois símbolos terminais "(" e ")" e um símbolo não terminal S. As regras de produção são
: S &#x2192; SS
: S &#x2192; (S)
: S &#x2192; ()
A primeira regra permite que o símbolo S para multiplicar; a segunda regra permite que o símbolo S fique entre parênteses correspondentes; e a terceira regra termina a recursividade.

=== Parênteses aninhados e colchetes bem formados ===
Um segundo exemplo canônico é dois tipos diferentes de correspondência de parênteses aninhados, descritas pelas produções:&nbsp;
: S &#x2192; SS
: S &#x2192; ()
: S &#x2192; (S)
: S &#x2192; []
: S &#x2192; [S]

Com os símbolos terminais [] () e o não terminal S.

A sequencia a seguir pode ser derivads dessa gramática:
: ([ [ [ ()() [ ][ ] ] ]([ ]) ])

No entanto, não há nenhuma gramática livre de contexto para a geração de todas as sequências de colchetes e parenteses, cada uma separadamente em relação desprezando as outras, mas onde os dois tipos não precisam alinhar um dentro da outra, por exemplo:&nbsp;
: [ ( ] )
ou
: [ [ [ [(((( ] ] ] ]))))(([ ))(([ ))([ )( ])( ])( ])

=== A Gramática Regular ===
Toda gramática regular é livre de contexto, mas nem todas as gramáticas livres de contexto são regulares. A gramática livre de contexto seguinte, no entanto, também é regular.
: S &#x2192; a
: S &#x2192; aS
: S &#x2192; bS

Os terminais aqui são a e b, enquanto o único não terminal é S. A linguagem descrita é formada por todas as cadeias não vazias&nbsp;<math>a</math>s e<math>b</math>s que terminam em  <math>a</math>.

Essa [[Gramática regular|gramática é regular]]: nenhuma regra tem mais do que um não terminal em seu lado direito, e cada um desses não terminais é, ao mesmo ao fim do lado direito.

Cada gramática regular corresponde diretamente a um [[autômato finito não determinístico]], por isso sabemos que esta é uma [[linguagem regular]].

Usando a barra vertical, a gramática descrita acima pode ser descrita mais sucintamente do seguinte modo:
: S &#x2192; a | aS | bS

=== Combinando pares ===
Em uma gramática livre de contexto, podemos emparelhar caracteres a forma como fazemos com os [[colchetes]]. O exemplo mais simples:&nbsp;
: S &#x2192; aSb
: S &#x2192; ab
Essa gramática gera a linguagem<math> \{ a^n b^n : n \ge 1 \} </math>,que não é [[Linguagem regular|regular]] ( de acordo com a regra do[[ lema do bombeamento]] para [[linguagens regulares]]).

O caractere especial ε serve para a cadeia vazia. Ao alterar a gramática acima para
: S &#x2192; aSb | ε
obtém-se uma gramática que gera a linguagem&nbsp;<math> \{ a^n b^n : n \ge 0 \} </math>.&nbsp;Esta difere apenas por conter a cadeia vazia, enquanto a gramática original não tem.

=== Expressões Algébricas ===
Aqui está uma gramática livre de contexto para expressões algébricas sintaticamente corretas e [[Notação infixa|infixas]] nas variáveis x, y e z:
# S → x
# S → y
# S → z
# S → S + S
# S → S - S
# S → S * S
# S → S / S
# S → (S)
Essa gramática pode, por exemplo, gerar a cadeia
: (x + y) * x - z * y /  x + x)
como a seguir:
: S (o símbolo inicial)
: &#x2192; S - S (pela regra 5)
: &#x2192; S * S - S (pela regra 6, aplicada à extremidade esquerda S)
: &#x2192; S * S - S / S (pela regra 7, aplicada à extremidade direita S)
: &#x2192; ( S ) * S - S / S (pela regra 8, aplicada à extremidade esquerda S)
: &#x2192; ( S ) * S - S / ( S ) (pela regra 8, aplicada à extremidade direita S)
: &#x2192; ( S + S ) * S - S / ( S ) (etc.)
: &#x2192; ( S + S ) * S - S * S / ( S )
: &#x2192; ( S + S ) * S - S * S / ( S + S )
: &#x2192; ( x + S ) * S - S * S / ( S + S )
: &#x2192; ( x + y ) * S - S * S / ( S + S )
: &#x2192; ( x + y ) * x - S * y / ( S + S )
: &#x2192; ( x + y ) * x - S * y / ( x + S )
: &#x2192; ( x + y ) * x - z * y / ( x + S )
: &#x2192; ( x + y ) * x - z * y / ( x + x )

Note-se que muitas opções foram feitas no andamento como a que foi reescrita vão ser realizadas em seguida. Estas escolhas parecem bastante arbitrárias. Por uma questão de fato, elas são, no sentido de que a cadeia gerada no final é sempre a mesma. Por exemplo, o segundo e terceiro reescritos
: &#x2192; S * S - S (pela regra 6, aplicada à extremidade esquerda  S)
: &#x2192; S * S - S / S  (pela rega 7, aplicada à extremidade direita  S)
pode ser feita na ordem oposta:
: &#x2192; S - S / S (pela regra 7, aplicada à extremidade direita S)
: &#x2192; S * S - S / S (pela regra 6, aplicada à extremidade esquerda  S)
Além disso, muitas escolhas foram feitas para que regra aplicar para cada &nbsp;<code>S</code>&nbsp;selecionado. Mudando as escolhas feitas e não apenas a ordem em que elas foram feitas, geralmente afetam qual terminal da cadeia vem no final.

Vamos olhar isso com mais detalhes. Considere a [[Árvore de análise sintática|árvore de análise]] dessa derivação:
            S
            |
           /|\
          S - S
         /     \
        /|\    /|\
       S * S  S / S
      /    |  |    \
     /|\   x /|\   /|\
    ( S )   S * S ( S )
     /      |   |    \ 
    /|\     z   y   /|\
   S + S           S + S
   |   |           |   |
   x   y           x   x
Começando na parte superior, passo a passo, um S na árvore é expandida, até que não haja mais <code>S</code>&nbsp;não expandido, isto é &nbsp;(não terminais) permanecem.Escolher uma ordem diferente de expansão irá produzir uma derivação diferente, mas a mesma árvore de análise. A árvore de análise só vai mudar se nós escolhemos uma regra diferente para aplicar em alguma posição na árvore.

Porém, pode uma árvore de análise diferente ainda produzir a mesma seqüência terminal, que é<code>( x + y ) * x - z * y / ( x + x </code>&nbsp;nesse caso? Sim, com essa gramática particular, isso é possível. Gramáticas com esta propriedade são chamadas [[Gramática ambígua|ambígua]].

Por exemplo, <code>x + y * z</code> pode ser produzida com estas duas árvores de análise diferentes:
          S               S
          |               |
         /|\             /|\
        S * S           S + S
       /     \         /     \
      /|\     z       x     /|\
     S + S                 S * S
     |   |                 |   |
     x   y                 y   z
No entanto, a'' linguagem'' descrita por esta gramática não é ''inerentemente ambígua'': uma alternativa, gramática não ambígua pode ser dada para o idioma, por exemplo:
: T &#x2192; x
: T &#x2192; y
: T &#x2192; z
: S &#x2192; S + T
: S &#x2192; S - T
: S &#x2192; S * T
: S &#x2192; S / T
: T &#x2192; ( S )
: S &#x2192; T
(mais uma vez escolhendo&nbsp;<code>S</code> como o símbolo de inícial). Essa gramática alternativa produzirá <code>x + y * z</code> com uma árvore de análise similar à esquerda, a cima, isto é, admitindo implicitamente a associação <code>(x + y) * z</code>, que não está de acordo com a precedência do operador padrão.&nbsp;Mais elaboradas, gramáticas não ambígua e livres de contexto podem ser construídas de forma que produzem árvores de análise que obedecem a todas as regras de precedência e associatividade de operadores desejados.

=== Exemplos adicionais ===

==== Exemplo 1 ====
Uma gramática livre de contexto para a linguagem consistindo de todas as cadeias sobre {a, b} contendo um número desigual de a's e b's:&nbsp;
: S &#x2192; U | V
: U &#x2192; TaU | TaT | UaT
: V &#x2192; TbV | TbT | VbT
: T &#x2192; aTbT | bTaT | &#x3B5;
Aqui, o simbolo não terminal T pode gerar todas as cadeias com o mesmo número de a's e b's, o simbolo não terminal U gera todas as cadeias com mais a's do que de b's e o simbolo  não terminal V gera todas as cadeias com menos a's do que b's. Omitindo a terceira alternativa na regra para U e V não restringe a linguagem da gramática.

==== Exemplo 2 ====
Outro exemplo de uma linguagem não regular é <math> \{ b^n a^m b^{2n} : n \ge 0, m \ge 0 \} </math>. É livre de contexto, uma vez que pode ser gerado pela seguinte gramática livre de contexto:
: S &#x2192; bSbb | A
: A &#x2192; aA | &#x3B5;

==== Outros exemplos ====
As [[Lógica de primeira ordem|regras de formação]] para os termos e fórmulas da lógica formal se encaixam na definição de gramática livre de contexto, exceto que o conjunto de símbolos pode ser infinito e pode haver mais do que um símbolo de inicial.

=== Derivações e árvores de sintaxe ===
A ''derivação ''de uma cadeia de caracteres para uma gramática é uma sequência de aplicações de regras de gramática que transforma o símbolo inicial na cadeia. Uma derivação prova que a sequência pertence à linguagem da gramática.

A derivação é totalmente determinada fornecendo em cada passo:
* a regra aplicada nesse passo
*a ocorrência do seu lado esquerdo para o qual é aplicado
Para maior clareza, a cadeia intermediária geralmente é dada também.

Por exemplo, com a gramática:
  (1)  S → S + S
  (2)  S → 1
  (3)  S → a
a cadeia:
 1 + 1 + a
pode ser derivada com a derivação:
 S
    → (regra 1 do primeiro S)
  S+S
    → (regra 1 do segundo S)
  S+S+S
    → (regra 2 do segundo S)
  S+1+S
    → (regra 3 do terceiro S)
  S+1+a
    → (regra 2 do primeiro S)
  1+1+a
Muitas vezes, uma estratégia que é seguida deterministicamente determina o próximo não terminal que vai ser reescrito: &nbsp;
* em uma ''derivação mais à esquerda'', é sempre o simbolo não terminal mais à esquerda l;&nbsp;
* em uma ''derivação mais à direita'', é sempre o simbolo  não terminal à direita.&nbsp;
Diante de tal estratégia, uma derivação é completamente determinada pela sequência de regras aplicadas. Por exemplo, a derivação mais à esquerda
 S
   → (regra 1 do primeiro S) S+S
   → (regra 2 do primeiro S) 1+S
   → (regra 1 do primeiro S) 1+S+S
   → (regra 2 do primeiro S) 1+1+S
   → (regra 3 do primeiro S) 1+1+a
pode ser resumido como
 regra 1, regra 2, regra 1, a regra 2, regra 3
A distinção entre derivação mais à esquerda e mais à direita derivação é importante porque, na maioria dos  [[parsers]] a transformação da entrada é definida por dar um pedaço de código para cada regra gramatical que é executado sempre que a regra é aplicada.
Por isso, é importante saber se o parser  determina o tipo de derivação mais a esquerda ou à direita, porque isso determina a ordem em que as partes de código vai ser executado. Veja por exemplo uma analisadores LL e analisadores LR.

A derivação também impõe em certo sentido, uma estrutura hierárquica na cadeia que vai ser derivada. Por exemplo, se a cadeia "1 + 1 + a" é derivada de acordo com a derivação mais à esquerda:
: S &#x2192; S + S (1)
: &nbsp;&nbsp; &#x2192; 1 + S (2)
: &nbsp;&nbsp; &#x2192; 1 + S + S (1)
: &nbsp;&nbsp; &#x2192; 1 + 1 + S (2)
: &nbsp;&nbsp; &#x2192; 1 + 1 + a (3)
a estrutura da cadeia seria:
: { { 1 }<sub>S</sub> + { { 1 }<sub>S</sub> + { a }<sub>S</sub> }<sub>S</sub> }<sub>S</sub>
onde { ... }<sub>S</sub> indica uma sub-cadeia reconhecida como parte de S. Esta hierarquia pode também ser visto como uma árvore:
            S
           /|\
          / | \
         /  |  \
        S  '+'  S
        |      /|\
        |     / | \
       '1'   S '+' S
             |     |
            '1'   'a'
Esta árvore é chamada uma [[Árvore de análise sintática|árvore de análise]] ou "árvore de sintaxe concreta" da cadeia, por contraste com a [[Árvore sintática abstrata|árvore de sintaxe abstrata]]. Neste caso que foi apresentado, as derivações mais à esquerda e à direita definem a mesma árvore de análise; No entanto, existe um outro (mais à direita) derivação da mesma cadeia
: S &#x2192; S + S (1)
: &nbsp;&nbsp; &#x2192; S + a (3)
: &nbsp;&nbsp; &#x2192; S + S + a (1)
: &nbsp;&nbsp; &#x2192; S + 1 + a (2)
: &nbsp;&nbsp; &#x2192; 1 + 1 + a (2)
e isso define o seguinte árvore de análise: 
            S
           /|\
          / | \
         /  |  \
        S  '+'  S
       /|\      |
      / | \     |
     S '+' S   'a'
     |     |
    '1'   '1'
Se, para certas cadeias na linguagem da gramática, há mais de uma árvore de análise, então, a gramática é dito ser uma [[gramática ambígua]]. Essas gramáticas são geralmente difíceis de analisar porque o analisador não pode sempre decidir qual regra gramatical tem que ser aplicada. Normalmente, a ambiguidade é uma característica da gramática, não da linguagem, e uma gramática não ambígua pode ser encontrada que gera a mesma linguagem livre de contexto. No entanto, há certas línguas que só podem ser geradas por gramáticas ambíguas; tais linguagens são chamadas de [[Gramática ambígua|linguagens inerentemente ambíguas]].

== Forma Normal ==
Toda gramática livre de contexto que não gera a cadeia vazia pode ser transformado em um em que não há ε-produção (isto é, uma regra que tem a cadeia vazia como um produto). Se uma gramática faz gerar a cadeia vazia, será necessário incluir a regra<math>S \rarr \epsilon</math>, mas não há necessidade de nenhuma outra regra ε. Toda gramática livre de contexto sem ε-produção tem uma gramática equivalente em[[Forma Normal de Chomsky| forma normal de Chomsky]] ou [[forma normal de&nbsp;Greibach]]. "Equivalente", aqui, significa que as duas gramáticas gerar a mesma língua.

A forma especialmente simples de regras de produção em gramáticas na Forma Normal de Chomsky tem implicações teóricas e práticas. Por exemplo, dada uma gramática livre de contexto pode-se usar a Forma Normal de Chomsky para construir um algoritmo de tempo polinomial que decide se uma determinada cadeia está na linguagem representado pela gramática ou não (o [[algoritmo CYK]]).

== Propriedades de fechamento ==
Linguagens livres de contexto são fechados sob [[união]], [[concatenação]], [[Fecho de Kleene]],<ref>Hopcroft & Ullman (1979), p.131, Theorem 6.1</ref> de [[Operações em cadeias de caracteres]](em particular [[homomorfismo]]),<ref>Hopcroft & Ullman (1979), p.131-132, Theorem 6.2</ref> [[Homomorfismo|homomorfismo inverso]],<ref>Hopcroft & Ullman (1979), p.132-134, Theorem 6.3</ref> e intersecção com uma linguagem regular.<ref>Hopcroft & Ullman (1979), p.135-136, Theorem 6.5</ref> Elas não estão fechadas sob intersecção geral (por consequência não são fechadas no [[Complementar|complemento]]) e diferença de conjunto.<ref>Hopcroft & Ullman (1979), p.134-135, Theorem 6.4</ref>

== Problemas decidíveis ==
Existem algoritmos para decidir se uma linguagem livre de contexto está vazio, e se ele é finito.<ref>Hopcroft & Ullman (1979), p.137-138, Theorem 6.6</ref>

== Problemas indecidíveis ==
Algumas perguntas que são indecidíveis para as classes mais amplas de gramáticas se tornam decidíveis para gramáticas livres de contexto; por exemplo. o problema da vacuidade (se a gramática gera alguma cadeia de terminais), é indecidível para [[gramáticas sensíveis ao contexto]], mas decidível para gramáticas livres de contexto.

No entanto, muitos problemas são indecidíveis até mesmo para gramáticas livres de contexto. Alguns exemplos são:

=== Universalidade ===
Dada uma GLC, ela gera a linguagem de todas as cadeias sobre o alfabeto de símbolos terminais utilizados nas suas regras?<ref name="sipser">{{harvtxt|Sipser|1997}}, Theorem 5.10, p. 181.</ref><ref name="hu281"/>

Uma redução pode ser mostrada desse problema para o problema indecidível bem conhecido de se determinar se uma [[máquina de Turing]] aceita uma entrada particular (o [[Problema da parada]]). A redução utiliza o conceito de um [[histórico de computação]], uma cadeia que descreve toda a computação de uma [[máquina de Turing]]. Uma GLC pode ser construída  de forma que ela gera todas as cadeias que são histórias de computação de não aceitação para uma máquina de Turing particular sobre uma determinada entrada, e, portanto, ela irá aceitar todas as cadeias apenas se a máquina não aceita essa entrada.

=== Igualdade de linguagem ===
Dado duas GLCs, eles geram a mesma língua?<ref name="hu281">{{harvtxt|Hopcroft|Ullman|1979}}, p. 281.</ref><ref name="eom"/>

A indecidibilidade do problema é uma consequência direta do anterior: é impossível até mesmo decidir se uma GLC é equivalente a GLC trivial  que define a linguagem de todas as cadeias.

=== Inclusão de linguagem ===
Dadas duas GLCs, pode o primeiro gerar todas as cadeias que o segundo pode gerar?<ref name="hu281"/><ref name="eom"/>

Se este problema foi decidível, em seguida, a igualdade de linguagem pode ser decidida também: dois GLCs G1 e G2 gerar a mesma língua se L(G1) é um subconjunto de L(G2) e L(G2) é um subconjunto de L(G1).

=== Estar em um nível inferior ou superior da hierarquia de Chomsky ===
Usando o teorema de Greibach, pode ser demonstrado que os dois seguintes problemas são indecidíveis:
* Dada uma [[gramática sensível ao contexto]], ela descreve uma linguagem livre de contexto?
* Dada uma gramática livre de contexto, ela descreve uma [[Linguagem regular]]?<ref name="hu281"/><ref name="eom">{{citation|título=Encyclopaedia of mathematics: an updated and annotated translation of the Soviet "Mathematical Encyclopaedia"|primeiro =Michiel|último =Hazewinkel|publicado=Springer|ano=1994|isbn=978-1-55608-003-6|em=Vol. IV, p. 56|url=http://books.google.com/books?id=s9F71NJxwzoC&pg=PA56}}.</ref>

=== Ambiguidade de gramática ===
Dada uma GLC, ela é [[Gramática ambígua|ambígua]]?

A indecidibilidade deste problema resulta do fato de que, se existe um algoritmo para determinar a ambiguidade existente, o [[problema da correspondência de Post]] poderia ser decidido, que é conhecido como sendo indecidível.

===  Disjunção de linguagem ===
Dadas duas GLCs, existe alguma cadeia produzida a partir de ambas as gramáticas?

Se o problema era decidível, o problema indecidível da Problema da correspondência de Post poderia ser decidido, para uma dada cadeia<math>\alpha_1, \ldots, \alpha_N, \beta_1, \ldots, \beta_N</math> sobre algum alfabeto&nbsp;<math>\{a_1, \ldots, a_k\}</math>, let the grammar {{Tmath|G_1}} consist of the rule
: <math>S \to \alpha_1 S \beta_1^{rev} | \cdots | \alpha_N S \beta_N^{rev} | b</math>;
onde <math>\beta_i^{rev}</math>&nbsp;denota a [[cadeia inversa]]&nbsp;<math>\beta_i</math> and <math>b</math> não ocorre entre o  <math>a_i</math>; ;e deixe gramática  {{Tmath|G_2}} consistir da a regra
: <math>T \to a_1 T a_1 | \cdots | a_k T a_k | b</math>;
Então o problema de Post dado por<math>\alpha_1, \ldots, \alpha_N, \beta_1, \ldots, \beta_N</math> tem uma solução se e somente se  {{Tmath|L(G_1)}}&nbsp;e{{Tmath|L(G_2)}}  compartilham uma cadeia derivável.

== Extensões ==
Uma maneira óbvia de estender o formalismo gramática livre de contexto é permitir não terminais de ter argumentos, cujos valores são repassados dentro das regras.Isso permite que recursos de linguagem naturais, tais como acordo e referência, e análogos de linguagens de programação, tais como o uso correto e definição de identificadores, para ser expressa de um modo natural. Por exemplo. agora podemos facilmente expressar que, em frases em inglês, o sujeito e o verbo deve concordar em número. Em ciência da computação, exemplos dessa abordagem incluem gramáticas de afixos,[[Gramática de atributos| gramáticas de atributos]], gramáticas indexada e Van Wijngaarden gramáticas de dois níveis. Extensões semelhantes existem em linguística.

Uma '''gramática livre de contexto estendida''' (ou '''gramática parte direita regular''') é aquele em que o lado direito das regras de produção é permitido ser uma [[expressão regular]] sobre os terminais e não terminais da gramática. Gramáticas livres de contexto estendida descrever exatamente linguagem livre de contexto.<ref>{{citar web| url=http://www.engr.mun.ca/~theo/Courses/fm/pub/context-free.pdf |título=A Short Introduction to Regular Expressions and Context-Free Grammars |acessodata=24 de agosto de 2012 |autor =Norvell, Theodore |páginas=4}}</ref>

Outra extensão é permitir símbolos terminais adicionais, para aparecer no lado esquerdo de regras, restringindo a sua aplicação. Isso produz o formalismo das[[Gramática sensível ao contexto| gramáticas sensíveis ao contexto.]]

== Subclasses ==
Há um número de subclasses importantes das gramáticas livres de contexto:
* [[Analisador sintático LR|LR (k)]] gramáticas (também conhecido como [[Gramática livre de contexto determinística|gramáticas livres de contexto determinísticos]]) permitem [[Análise sintática (computação)|analisar]] (reconhecimento de cadeias) com [[Autômato com pilha determinístico|autômatos pilha determinísticos]] (APD), mas eles só podem descrever [[Linguagem livre de contexto determinística|linguagens livres de contexto deterministas]].

* Simples LR, Look-Ahead LR gramáticas são subclasses que permitem uma maior simplificação da análise. SLR e LALR são reconhecidos usando o mesmo APD como LR, mas com tabelas simples, na maioria dos casos.

* [[Analisador sintático LL|LL (k) e LL (*)]] gramáticas permitem a análise por construção direta de uma derivação mais à esquerda tal como descrito acima, e descreve um número menor de linguagens.

* Gramáticas simples são uma subclasse da LL (1) gramáticas, são interessantes principalmente pela sua propriedade teórica em que a igualdade de linguagem de gramáticas simples é decidível, enquanto a inclusão de linguagem não é.

* Gramáticas Bracketed têm a propriedade de que os símbolos terminais são divididos em pares de colchetes esquerdo e direito que sempre combinam em regras.

* [[Gramática Linear|Gramáticas lineares]] não têm regras com mais do que um não terminal no lado direito.

* [[Gramática regular|Gramáticas regulares]] são uma subclasse de gramáticas lineares e descrevem as [[linguagens regulares]], ou seja, eles correspondem a [[Máquina de estados finitos|Autômatos Finitos]] e e[[Expressão regular|xpressões regulares]].
LR análise estende LL análise para apoiar uma maior gama de gramáticas; por sua vez, análise [[Analisador sintático GLR|generalizada LR]] estende LR análise para apoiar gramáticas livres de contexto arbitrárias. Em gramáticas LL e gramáticas LR, elas essencialmente executam a LL análise e a LR análise, respectivamente, enquanto em gramáticas não determinísticas, é tão eficaz como pode ser esperado. Embora GLR análise foi desenvolvido na década de 1980 muitas novas definições de idioma e [[Compilador de compilador|geradores de análise]] continuam a basear-se em LL, LR LALR ou analisar até os dias atuais.

== Aplicações linguísticas ==
[[Chomsky]] inicialmente esperou superar as limitações de gramáticas livres de contexto, adicionando [[Gramática transformacional|regras de transformação]].<ref name="chomsky1956"/>

Tais regras são outro dispositivo padrão em linguísticas tradicionais; por exemplo [[Voz verbal|forma passiva]] em inglês. Grande parte da[[ gramática gerativa]] tem se dedicado a encontrar formas de aperfeiçoar os mecanismos descritivos da frase-estrutura gramatical e transformação de tal forma que governa exatamente os tipos de coisas que podem ser expressas em linguagem natural. Permitindo transformações arbitrárias não cumprem essa meta: elas são muito poderosas demais, sendo [[Turing completa]] a menos que restrições significativas são adicionados (por exemplo, não há transformações que introduzem e, em seguida, reescrever símbolos de uma forma livre de contexto).

Posição geral de [[Chomsky]] sobre não-liberdade-de-contexto  da linguagem natural tem se mantido desde então,<ref name="shieber1985">{{citation |título=Evidence against the context-freeness of natural language |ano=1985 |último =Shieber |primeiro =Stuart |periódico=Linguistics and Philosophy | volume=8 |páginas=333–343 | url=http://www.eecs.harvard.edu/~shieber/Biblio/Papers/shieber85.pdf | doi=10.1007/BF00630917 |número=3}}.</ref> embora seus exemplos específicos sobre a inadequação de gramáticas livres de contexto, em termos de sua capacidade geradora fraca foram mais tarde desmentida.<ref name="pullum-gazdar1982">{{citation |título=Natural languages and context-free languages |ano=1982 |último =Pullum |primeiro =Geoffrey K. |coautor=Gerald Gazdar |periódico=Linguistics and Philosophy | volume=4 |páginas=471–504 | doi=10.1007/BF00360802 |número=4}}.</ref> [[Gerald Gazdar]] e [[Geoffrey Pullum]] argumentaram que, apesar de algumas construções não-livre de contexto em linguagem natural (tais como dependências cross-série em [[Suíço-alemão]]<ref name="shieber1985"/> e [[reduplicação]] em [[Língua bambara|Bambara]]<ref name="culy1985">{{citation |título=The Complexity of the Vocabulary of Bambara |ano=1985 |último =Culy |primeiro =Christopher |periódico=Linguistics and Philosophy | volume=8 |páginas=345–351 | doi=10.1007/BF00630918 |número=3}}.</ref>), a grande maioria dos formulários em linguagem natural são, de facto livre de contexto.<ref name="pullum-gazdar1982"/>

== Teoria da computação ==
{{Teoria da computação}}

== Ver também ==
* [[Gramática de análise sintática de expressão]]
* [[Gramática livre de contexto estocástica]]
* [[Lema do bombeamento para linguagens livre de contexto]]

=== Algoritmos de análise ===
* [[Algoritmo CYK]]
* [[Analisador sintático GLR]]
* [[Analisador sintático LL]]
* [[Algoritmo Earley]]

== Referências ==
{{Reflist|colwidth = 30em}}

== Fontes ==
* <cite class="citation" id="CITEREFHopcroftUllman1979" contenteditable="false">[[John Hopcroft|Hopcroft, John E.]]; [[Jeffrey Ullman|Ullman, Jeffrey D.]] (1979), ''Introduction to Automata Theory, Languages, and Computation'', Addison-Wesley</cite><span class="Z3988" title="ctx_ver=Z39.88-2004&rfr_id=info%3Asid%2Fen.wikipedia.org%3AContext-free+grammar&rft.aufirst=John+E.&rft.aulast=Hopcroft&rft.au=Ullman%2C+Jeffrey+D.&rft.btitle=Introduction+to+Automata+Theory%2C+Languages%2C+and+Computation&rft.date=1979&rft.genre=book&rft.pub=Addison-Wesley&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook" contenteditable="false">&nbsp;</span>. Chapter 4: Context-Free Grammars, pp.&nbsp;77–106; Chapter 6: Properties of Context-Free Languages, pp.&nbsp;125–137.
* <cite class="citation" id="CITEREFSipser1997" contenteditable="false">[[Michael Sipser|Sipser, Michael]] (1997), ''Introduction to the Theory of Computation'', PWS Publishing, [[International Standard Book Number|ISBN]]&nbsp;0-534-94728-X</cite><cite class="citation" id="CITEREFSipser1997" contenteditable="false"></cite><span class="Z3988" title="ctx_ver=Z39.88-2004&rfr_id=info%3Asid%2Fen.wikipedia.org%3AContext-free+grammar&rft.aufirst=Michael&rft.aulast=Sipser&rft.btitle=Introduction+to+the+Theory+of+Computation&rft.date=1997&rft.genre=book&rft.isbn=0-534-94728-X&rft.pub=PWS+Publishing&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook" contenteditable="false">&nbsp;</span>. Chapter 2: Context-Free Grammars, pp.&nbsp;91–122; Section 4.1.2: Decidable problems concerning context-free languages, pp.&nbsp;156–159; Section 5.1.1: Reductions via computation histories: pp.&nbsp;176–183.
* <cite class="citation book" contenteditable="false">J. Berstel, L. Boasson (1990).  </cite><cite class="citation book" contenteditable="false">Jan van Leeuwen, ed. ''Context-Free Languages''. </cite><cite class="citation book" contenteditable="false">Handbook of Theoretical Computer Science '''B'''. Elsevier. pp.&nbsp;59–102.</cite><span class="Z3988" title="ctx_ver=Z39.88-2004&rfr_id=info%3Asid%2Fen.wikipedia.org%3AContext-free+grammar&rft.au=J.+Berstel%2C+L.+Boasson&rft.btitle=Context-Free+Languages&rft.date=1990&rft.genre=book&rft.pages=59-102&rft.pub=Elsevier&rft.series=Handbook+of+Theoretical+Computer+Science&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook" contenteditable="false">&nbsp;</span>

[[Categoria:Linguagens formais]]
[[Categoria:Tópicos em linguagens de programação]]