Construção de compiladores/Linguagens livres de contexto

Origem: Wikilivros, livros abertos por um mundo aberto.

Na teoria de linguagens formais, uma linguagem livre de contexto é uma linguagem gerada por alguma gramática livre de contexto. O conjunto de todas as linguagens livres de contexto é idêntico ao conjunto de linguagens aceitas por um autômato de pilha. De acordo com a Hierarquia de Chomsky, linguagens livres de contexto são Tipo-2.

As gramáticas livres de contexto são da seguinte forma:

V -> w

de modo que 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 precisar entender seu contexto.

Um exemplo que facilita a compreensão do que são linguagens livres de contexto é a frase:

  • 1. "Fui à biblioteca hoje."


a palavra "biblioteca" independente da frase indica todo espaço (concreto, virtual ou híbrido) destinado a uma coleção de informações de quaisquer tipos, sejam escritas em folhas de papel (monografias, enciclopédias, dicionários, manuais, etc) ou ainda digitalizadas e armazenadas em outros tipos de materiais, tais como CD, fitas, VHS, DVD e bancos de dados.

Por sua vez, na frase:

  • 2. "Fui à sede beber água porque estava com sede."


a palavra "sede" em sua segunda ocorrência indica uma sensação de caráter geral, iniciada por estímulos originados dentro do próprio organismo e não do meio ambiente. Na primeira aparição, a palavra "sede" é um centro administrativo.

Dessa forma, na frase 1 a palavra biblioteca é livre de contexto, e a palavra sede da frase 2 é dependente de contexto.

Define-se 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.

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

Aplicações[editar | editar código-fonte]

Tais linguagens são importantes para definir linguagens de programação. Por exemplo, as linguagens que requerem o balanceamento de parênteses são geradas pela gramática . Da mesma forma, a maioria das expressões aritméticas é gerada por gramáticas livres de contexto.

Exemplos[editar | editar código-fonte]

Uma linguagem livre de contexto é , a linguagem de todas as cadeias de caracteres não vazias de tamanho par, as primeiras metades sempre preenchidas com "s" e as segundas metades sempre preenchidas com ""s. é gerada pela gramática , e é aceita pelo autômato de pilha , em que é definido da seguinte forma:





Em que z é a pilha de símbolos inicial e x significa desempilhar.

Propriedades de fechamento[editar | editar código-fonte]

Linguagens livres de contexto são fechadas nas seguintes operações. Se L e P são linguagens livres de contexto e D é uma linguagem regular, as seguintes linguagens também são livres de contexto:

Linguagens livres de contexto não são fechadas em complemento, interseção ou diferença.

Propriedades de decisão[editar | editar código-fonte]

Os seguintes problemas são indecidíveis para quaisquer gramáticas livres de contexto A e B:

  • ?
  •  ?
  •  ?
  •  ?

Os seguintes problemas são decidíveis para quaisquer linguagens livres de contexto:

  • ?
  • é finito?
  • Dada a palavra w, ?