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 editar

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  . Da mesma forma, a maioria das expressões aritméticas é gerada por gramáticas livres de contexto.

Exemplos editar

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

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]

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

Propriedades de decisão editar

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,  ?

Referências editar

  1. http://www.consiste.dimap.ufrn.br/~david/ENSEIGNEMENT/SUPPORT/330-glc.pdf
  2. http://www.cs.uiuc.edu/class/sp08/cs273/Handouts/closure/cfl-closure.html
  3. http://www.cs.odu.edu/~toida/nerzic/390teched/cfl/cfg.html
  Esta página é somente um esboço. Ampliando-a você ajudará a melhorar a Wikiversidade.