Gramáticas livres de contexto
Origem: Wikipédia, a enciclopédia livre.
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
onde 
e 
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.
[editar] Ver também
| Teoria de Autômatos: Linguagem formal e gramática formal | |||
|---|---|---|---|
| Hierarquia Chomsky |
Gramática | Linguagem | Reconhecedor |
| Tipo-0 | Estrutura de frase | Recursivamente enumerável | Máquina de Turing |
| -- | Estrutura de frase | Recursiva | Máquina de Turing |
| Tipo-1 | Sensíveis ao contexto | Sensíveis ao contexto | Máquina de Turing com memória limitada |
| Tipo-2 | Livre de contexto | Livre de contexto | Autômato com pilha |
| Tipo-3 | Regular | Regular | Autômato finito |
