Gramática livre de contexto

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em Teoria da computação as Gramáticas livres de contexto, também conhecidas como gramáticas 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

A\rightarrow \beta

onde A\in V_n e \beta\in (V_n\cup V_t)^*

Em linguí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 seguinte forma :

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

A sintaxe da maioria das linguagens de programação é especificada usando gramáticas livres de contexto. Geralmente a sintaxe dessas linguagens é bastante simples, de modo a permitir a criação de analisadores sintáticos eficientes. O Algoritmo de Earley é um método geral para reconhecer se uma cadeia faz parte da linguagem de uma gramática livre de contexto. As linguagens LR e LL são subconjuntos mais restritivos da classe de linguagens livres de contexto.

A Forma de Backus-Naur (BNF) é a notação usada com mais freqüência para descrever uma gramática livre de contexto.

Ver também[editar | editar código-fonte]

Teoria de autômatos: linguagem formal e gramática formal
Hierarquia
Chomsky
Gramática Linguagem Reconhecedor
Tipo-0 Irrestrita Recursivamente enumerável Máquina de Turing
-- -- Recursiva Máquina de Turing que sempre para
Tipo-1 Sensível ao contexto Sensível ao contexto Autômato linearmente limitado
Tipo-2 Livre de contexto Livre de contexto Autômato com pilha
Tipo-3 Regular Regular Autômato finito