Introdução à Teoria dos 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:

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

Tais linguagens são importantes para definir linguagens de programação. ^[1]. 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:^[2]