Gramática livre de contexto
De Wikipedia, a enciclopédia encyclopedia
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.[1]
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.