# Construção de compiladores/Linguagens livres de contexto

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:
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:
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

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 $S\to SS~|~(S)~|~\lambda$. Da mesma forma, a maioria das expressões aritméticas é gerada por gramáticas livres de contexto.

## Exemplos

Uma linguagem livre de contexto é $L=\{a^{n}b^{n}:n\geq 1\}$, a linguagem de todas as cadeias de caracteres não vazias de tamanho par, as primeiras metades sempre preenchidas com "$a$s" e as segundas metades sempre preenchidas com "$b$"s. $L$ é gerada pela gramática $S\to aSb~|~ab$, e é aceita pelo autômato de pilha $M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},\{q_{f}\})$, em que $\delta$ é definido da seguinte forma:
$\delta (q_{0},a,z)=(q_{0},a)$ $\delta (q_{0},a,a)=(q_{0},a)$ $\delta (q_{0},b,a)=(q_{1},x)$ $\delta (q_{1},b,a)=(q_{1},x)$ $\delta (q_{1},b,z)=(q_{f},z)$
$\delta (estado_{1},leitura,desempilha)=(estado_{2},empilha)$
Em que z é a pilha de símbolos inicial e x significa desempilhar.

## Propriedades de fechamento

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:
* o fecho de Kleene $L^{*}$ de L
* a imagem φ(L) de L sob um homorfismo φ
* a concatenação $L\circ P$ de L e P
* a união $L\cup P$ de L e P
* a interseção (com uma linguagem regular) $L\cap D$ de L e D
Linguagens livres de contexto não são fechadas em complemento, interseção ou diferença.

## Propriedades de decisão

Os seguintes problemas são indecidíveis para quaisquer gramáticas livres de contexto A e B:
* $L(A)=L(B)$?
* $L(A)\cap L(B)=\emptyset$ ?
* $L(A)=\Sigma ^{*}$ ?
* $L(A)\subseteq L(B)$ ?
Os seguintes problemas são decidíveis para quaisquer linguagens livres de contexto:
* $L(A)=\emptyset$?
* $L(A)$ é finito?
* Dada a palavra w, $w\in L(A)$?