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:

• 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. 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\ge 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 (estad{o}_1,leitura,desempilha)=(estad{o}_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)=\mathrm{\varnothing }$ ?
• $L(A)={\mathrm{\Sigma }}^{*}$ ?
• $L(A)\subseteq L(B)$ ?

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

• $L(A)=\mathrm{\varnothing }$?
• $L(A)$ é finito?
• Dada a palavra w, $w\in L(A)$?

Predefinição:AutoCat