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:
é 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 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 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 Extensible Markup Language (XML) chamada de definição do tipo de documento.Introduction to Automata Theory, Languages, and Computation, John E. Hopcroft, Rajeen Motwani, Jeffrey D. Ullman, Addison Wesley, 2001, p.191
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āṇini, pelo menos, os linguistas têm descrito as gramáticas de línguas em termos de sua estrutura de blocos, e descrito como as sentenças são 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,, p. 106. e também a sua classificação como um tipo especial de gramática formal (que ele chamou de Gramática de estrutura frasal). 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. 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 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 parsing Earley é um exemplo de tal algoritmo, enquanto os amplamente utilizados LR e 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.The notation here is that of , p. 94. (p. 79) define context-free grammars as 4-tuples in the same way, but with different variable names.
onde: V é um conjunto finito; cada elemento é 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 G. Σ é um conjunto finito de terminais, disjuntos de V, que compõem o conteúdo real da sentença. O conjunto de terminais é o alfabeto da língua definido pela gramática G. R é uma relação finito de V para , em que o asterisco representa a operação de fecho de Kleen. Os membros do R são chamadas as regras de reescrita ou produções da gramática (também comumente simbolizado por um P) S é 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 regra de produção em R é formalizada matematicamente como um par , onde é um não terminal e é uma 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 β como o seu lado direito: .
É permitido que β seja a cadeia vazia, e, neste caso, é habitual designar pelo ε. A forma é chamada de uma ε-produção., pp. 90–92.
É comum listar todos os lados direito para o mesmo lado esquerdo na mesma linha, utilizando | (o símbolo barra vertical ) para separá-los. Regras . e , portanto, pode ser escrito como . Neste caso, e são chamadas a primeira e segunda alternativa, respectivamente.
Aplicação das Regras Para quaisquer cadeias , dizemos que u produz diretamente v, escrevendo como , se sendo and de forma que e . Assim, v é o resultado da aplicação da regra para u.
Aplicacão repetida de regras Para quaisquer palavra , dizemos u produz v, escrevendo como (ou como em alguns livros didáticos ), se de forma que. Neste caso, se (i.e., ), a relação mantém. Por outras palavras, e são o fechamento transitivo reflexivo(permitindo uma palavra para produzir a si mesma) e o Fecho transitivo (que requer, pelo menos, uma etapa ) de , respectivamente.
Linguagem livre de contexto A linguagem de uma gramática é o conjunto
Uma linguagem L é dito ser uma linguagem livre de contexto (CFL), se existe uma GLC L, de tal modo que .
GLC adequadas Uma gramática livre de contexto é dita ser adequada,. se tiver: nenhum símbolo inalcançável: nenhum símbolo que não possa ser produzido: nenhuma ε-produção nenhum ciclo : 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,Hopcroft & Ullman (1979), p.88, Lemma 4.1 uma fracamente equivalente sem símbolos improdutivos,Hopcroft & Ullman (1979), p.89, Lemma 4.2 e uma fracamente equivalente sem ciclos.This is a consequence of the unit-production elimination theorem in Hopcroft & Ullman (1979), p.91, Theorem 4.4 Cada gramática livre de contexto que não possui produz ε pode ser transformada em uma fracamente equivalente sem ε-produções;Hopcroft & Ullman (1979), p.91, Theorem 4.4 Ao todo, cada tal gramática pode ser transformada em uma GLC adequada fracamente equivalente.
Exemplo A gramática , com as produções: S → aSa, S → bSb, S → ε,
é livre de contexto. Não não é adequada uma vez que inclui um ε-produção. Uma derivação típica nesta gramática é S → aSa → aaSaa → aabSbaa → aabbaa. Essa derivação deixa claro que . 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 → SS S → (S) S → () 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: S → SS S → () S → (S) S → [] S → [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: [ ( ] ) 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 → a S → aS S → 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 s es que terminam em .
Essa 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 → 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: S → aSb