Gramática livre de contexto

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em Linguagem formal, uma gramática livre-do-contexto (GLC) é uma gramática formal em que cada regra de produção é da forma

Vw

onde V é um único símbolo não-terminal(Variável), e w é uma cadeia de terminais e/ou variáveis (w pode ser a cadeia vazia).

As linguagens geradas por gramáticas livres-do-contexto são conhecidas como Linguagens livres-do-contexto.

Gramáticas livres-do-contexto são importantes em Linguística para descrição da estrutura de sentenças e palavras em Língua natural. Em Ciência da computação é importante para descrição da estrutura de Linguagens de programação e outras linguagens artificiais.

Em Linguística, alguns autores usam o termo Gramática de estrutura de frase para se referir a gramáticas livres-do-contexto, como gramáticas de estrutura da frase são diferentes de gramáticas de dependência. Em Ciência da computação, a notação mais popular para gramática livre-do-contexto é a Forma de Backus-Naur(BNF).

História[editar | editar código-fonte]

Desde o tempo de Pāṇini, pelo menos, linguistas tem descrito as gramáticas das linguagens em termos de suas estruturas de bloco, e descrito como as sentenças são construídas recursivamente a partir de frases menores, e eventualmente a partir de palavras ou elementos de palavras individuais.

Uma propriedade essencial dessas estruturas de bloco é que unidades lógicas nunca se sobrepõem. Por exemplo, a sentença:

João, cujo carro azul estava na garagem, caminhou até a loja verde.
John, whose blue car was in the garage, walked to the green store.

pode ser logicamente posta entre parenteses como se segue:

(João, ((cujo carro azul) (estava (na garagem)))), (caminhou (até (a loja verde))).
(John, ((whose blue car) (was (in the garage)))), (walked (to (the green store))).

Uma gramática livre-do-contexto proporciona um mecanismo matemático simples e preciso para descrição dos métodos em que algumas linguagens naturais são construídas a partir de blocos menores, capturando a "estrutura de bloco" das sentenças de uma maneira natural. Sua simplicidade faz o formalismo passível de um rigoroso estudo matemático. Importantes características de sintaxe de linguagem natural como concordância não fazem parte de uma gramática livre-do-contexto, mas a estrutura recursiva básica de sentenças, a maneira pela qual cláusulas são aninhadas em outras cláusulas, e o modo pelo qual listas de adjetivos e advérbios são absorvidos por substantivos e verbos, são descritos precisamente.

O formalismo das gramáticas livres-do-contexto foi desenvolvido nos meados dos anos 1950 por Noam Chomsky, e também sua classificação como um tipo especial de gramática formal (a qual ele chamou de gramática de estrutura de frase).1

No modelo da Gramática gerativa de Chomsky, a sintaxe de linguagem natural era descrita por um conjunto de regras livres-do-contexto combinadas com regras de transformação.

Em trabalhos posteriores (e.g. Chomsky 1981), a ideia de formulação de uma gramática que consistisse de explícita reescrita de regras foi abandonada. Em outros modelos gerativos (e.g. Generalized Phrase Structure Grammar (Gazdar et al. 1985)), gramáticas livres-do-contexto foram tomadas como o mecanismo de toda a sintaxe, eliminando as transformações.

Estruturas de bloco foram introduzidas em linguagens de programação de computadores pelo projeto Algol (1957-1960), que como consequência, também contou com uma gramática livre-do-contexto para descrição da sintaxe resultante Algol. Isto tornou-se uma característica padrão das linguagens de computadores, e a notação para gramáticas usadas em descrições concretas de linguagens de computadores tornaram-se conhecidas por Forma de Backus-Naur.

A característica de "estrutura de bloco" que as gramáticas livres-do-contexto capturaram é tão fundamental para gramática que os termos de sintaxe e gramática são frequentemente identificados como regras das gramáticas livres-do-contexto, especialmente em ciência da computação. Restrições formais não capturadas pela gramática são, então, consideradas partes da "semântica" da linguagem.

Gramáticas livres-do-contexto são simples o suficiente para permitir a construção de eficientes algoritmos de análise, os quais, para uma dada cadeia, determinam se e como essa cadeia pode ser gerada pela gramática. O Algoritmo Earley é um exemplo de um algoritmo do tipo, enquanto os amplamente usados Analisador sintático LR e Analisador sintático LL são algoritmos mais simples que lidam com subconjuntos mais restritivos de gramáticas livres-do-contexto.

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

Uma gramática livre-do-contexto G é definida por uma 4-tupla:

G = (V\,, \Sigma\,, R\,, S\,) onde

1. V\, é um conjunto finito; cada elemento  v\in V é chamado símbolo não-terminal ou variável. Cada variável representa um tipo diferente de cláusula ou frase em uma sentença. As vezes, variáveis também são chamadas de categorias sintáticas. Cada variável define uma sub-linguagem da linguagem definida por G\,.

2. \Sigma\, é um conjunto finito de terminais, disjunto de V\,, o qual origina o real conteúdo da sentença. O conjunto de terminais é o alfabeto da linguagem definida pela gramática G\, .

3. R\, é um relação finita de V\, para (V\cup\Sigma)^{*}. Os membros de R\, são chamados regras de substituição ou produções da gramática. (também, comumente simbolizada por P\,)

4. S\, é a variável inicial (ou símbolo inicial), usado para representar toda a sentença (ou programa). Deve ser um elemento pertencente a V\,.

O asterisco representa a operação Fecho de Kleene ou estrela.

Aplicação de regra[editar | editar código-fonte]

Para qualquer cadeia u, v\in (V\cup\Sigma)^{*}, dizemos que u\, produz v\,, escrito como u\Rightarrow v\,, se \exists (\alpha, \beta)\in R com \alpha \in V e u_{1}, u_{2}\in (V\cup\Sigma)^{*} tal que u\,=u_{1}\alpha u_{2} e v\,=u_{1}\beta u_{2}. Por conseguinte, \! v é o resultado da aplicação da regra \! (\alpha, \beta) para \! u.

Aplicação de regra repetitiva[editar | editar código-fonte]

Para todo u, v\in (V\cup\Sigma)^{*}, u\stackrel{*}{\Rightarrow} v (ou u\Rightarrow\Rightarrow v\, em alguns livros-texto), se \ u_{1}, u_{2}, \cdots u_{k}\in (V\cup\Sigma)^{*}, k\geq 0 tal que u\Rightarrow u_{1}\Rightarrow u_{2}\cdots\Rightarrow u_{k}\Rightarrow v

Linguagem Livre-do-contexto[editar | editar código-fonte]

A linguagem da gramática G = (V\,, \Sigma\,, R\,, S\,) é o conjunto

L(G) = \{ w\in\Sigma^{*} : S\stackrel{*}{\Rightarrow} w\}

Uma linguagem L\, é dita ser uma linguagem livre-do-contexto (LLC), se existe uma GLC G\,, tal que L\,=\,L(G).

GLCs Apropriadas[editar | editar código-fonte]

Uma gramática livre-do-contexto é dita ser apropriada, se

  • ela não tem símbolos inalcançáveis: \forall N \in V: \exists \alpha,\beta \in (V\cup\Sigma)^*: S \stackrel{*}{\Rightarrow} \alpha{N}\beta
  • ela não tem símbolos improdutivos: \forall N \in V: \exists w \in \Sigma^*: N \stackrel{*}{\Rightarrow} w
  • ela não tem e-produções: \forall N \in V, w \in \Sigma^*: (N, w) \in R \Rightarrow w \neq e
  • ela não tem ciclos: \neg\exists N \in V: N \stackrel{*}{\Rightarrow} N

A gramática G = (\{S\} , \{a, b\}, S, P), com produções

S → aSa,
S → bSb,
S → e,

é livre-do-contexto. Uma derivação típica nessa gramática é S → aSa → aaSaa → aabSbaa → aabbaa. Isso torna claro que L(G) = \{ww^R:w\in\{a,b\}^*\}. A linguagem é livre-do-contexto, entretanto, pode ser provado que ela não é regular.

Exemplos[editar | editar código-fonte]

Parenteses bem formados[editar | editar código-fonte]

O exemplo canônico de uma gramática livre-do-contexto é a correspondência de parenteses, que representa o caso geral. Existem dois símbolos terminais "(" e ")" e uma variável S. As regras de produção são

S → SS
S → (S)
S → ()

A primeira regra permite S se multiplicar; a segunda regra permite que S seja inclusa entre parenteses; e a terceira regra finaliza a recursão.

Iniciando com S, e aplicando as regras, pode-se construir:

S → SS → SSS → (S)SS → ((S))SS → ((SS))S(S)
→ ((()S))S(S) → ((()()))S(S) → ((()()))()(S)
→ ((()()))()(())

Parenteses e colchetes aninhados bem formados[editar | editar código-fonte]

Um segundo exemplo canônico é, dois diferentes tipos de correspondência aninhada de parenteses, descrito pelas produções:

S → SS
S → ()
S → (S)
S → []
S → [S]

com símbolos terminais [ ] ( ) e variável S.

A seguinte sequência pode ser derivada a partir dessa gramática:

([ [ [ ()() [ ][ ] ] ]([ ]) ])

Entretanto, não há gramática livre-do-contexto que possa gerar todas as sequências da correspondência de dois diferentes tipos de parenteses, considerando que eles devem corresponder independente da existência do outro tipo de parentese, por exemplo:

[ [ [ [(((( ] ] ] ]))))(([ ))(([ ))([ )( ])( ])( ])

Expressões Algébricas[editar | editar código-fonte]

Aqui esta uma gramática livre-do-contexto para correção sintática de expressões algébricas na forma infixa, com as variáveis x, y e z:

  1. S ? x
  2. S ? y
  3. S ? z
  4. S ? S + S
  5. S ? S - S
  6. S ? S * S
  7. S ? S / S
  8. S ? ( S )

Essa gramática pode, por exemplo, gerar a cadeia

( x + y ) * x - z * y / ( x + x )

como segue:

S (o símbolo inicial)
→ S - S (pela regra 5)
→ S * S - S (pela regra 6, aplicado ao S mais a esquerda)
→ S * S - S / S (pela regra 7, aplicado ao S mais a direita)
→ ( S ) * S - S / S (pela regra 8, aplicado ao S mais a esquerda)
→ ( S ) * S - S / ( S ) (pela regra 8, aplicado ao S mais a direita)
→ ( S + S ) * S - S / ( S ) (etc.)
→ ( S + S ) * S - S * S / ( S )
→ ( S + S ) * S - S * S / ( S + S )
→ ( x + S ) * S - S * S / ( S + S )
→ ( x + y ) * S - S * S / ( S + S )
→ ( x + y ) * x - S * y / ( S + S )
→ ( x + y ) * x - S * y / ( x + S )
→ ( x + y ) * x - z * y / ( x + S )
→ ( x + y ) * x - z * y / ( x + x )

Note que, por baixo várias escolhas foram feitas, escolhas que dizem qual será a regra que vai ser escrita. Essas escolhas parecem bem arbitrárias. Na realidade, elas são, no sentido de que a cadeia gerada sempre é a mesma. Por exemplo, a segunda e terceira produções

→ S * S - S (pela regra 6, aplicada ao S mais a esquerda)
→ S * S - S / S (pela regra 7, aplicada ao S mais a direita)

poderia ser feita na ordem contrária:

→ S - S / S (pela regra 7, aplicada ao S mais a direita)
→ S * S - S / S (pela regra 6, aplicada ao S mais a esquerda)

Igualmente, muitas escolhas foram feitas em cima de qual regrar aplicar a cada S selecionado. Mudar as escolhas feitas e não apenas a ordem em que elas foram feitas geralmente afeta qual cadeia é gerada ao final.

Vamos olhar para isso mais detalhadamente. Considere o Árvore de análise sintática dessa derivação:

           S
           |
          /|\
         S - S
        /     \
       /|\    /|\
      S * S  S / S
     /    |  |    \
    /|\   x /|\   /|\
   ( S )   S * S ( S )
    /      |   |    \
   /|\     z   y   /|\
  S + S           S + S
  |   |           |   |
  x   y           x   x

Começando no topo, passo a passo, um S na árvore é expandido, até que não exista mais S's(variáveis) a serem expandidas. Pegando uma diferente ordem de expansão irá produzir uma derivação diferente, mas na mesma árvore sintática. A árvore sintática irá apenas mudar se nós pegarmos uma diferente regra para aplicar em alguma posição na árvore.

Mas, pode uma árvore sintática diferente produzir a mesma cadeia, que é ( x + y ) * x - z * y / ( x + x ) nesse caso? Sim, para esse caso em particular, isso é possível. Gramáticas com essa propriedade são chamadas ambígua.

Por exemplo, x + y * z pode ser produzido com essas duas árvores sintáticas diferentes:

         S               S
         |               |
        /|\             /|\
       S * S           S + S
      /     \         /     \
     /|\     z       x     /|\
    x + y                 y * z

Entretanto, a linguagem descrita por essa gramática não é inerentemente ambígua: uma gramática alternativa não ambígua pode ser dada para a linguagem, por exemplo:

T → x
T → y
T → z
S → S + T
S → S - T
S → S * T
S → S / T
T → ( S )
S → T

(mais uma vez, pegando S como símbolo inicial).

Forma Normal[editar | editar código-fonte]

Toda gramática livre-do-contexto que não gera uma cadeia vazia pode ser transformada em uma que nenhuma regra tem a cadeia vazia como produto [uma regra com e como produto é chamada e-produção]. Se ela não gera a cadeia vazia, ela irá necessariamente incluir a regra S \rarr \epsilon, mas não há necessidade de outra e-regra. Toda gramática livre-do-contexto sem e-produção tem uma gramática equivalente na Forma Normal de Chomsky ou Forma Normal de Greibach. "Equivalente" aqui significa que duas gramáticas geram a mesma linguagem.

Por causa da especial simplicidade das regras de produção de gramáticas na Forma Normal de Chomsky, essa forma normal tem implicações teóricas e práticas. Por exemplo, dada a gramática livre-do-contexto, alguém pode usar a Forma Normal de Chomky para construir um algoritmo de tempo polinomial que decida se a cadeia dada está na linguagem representada pela gramática (o Algoritmo CYK).

Problemas Indecidíveis[editar | editar código-fonte]

Algumas questões que não são decidíveis por classes de gramáticas mais amplas se tornam decidíveis com gramáticas livres-do-contexto; e.g. o teste de vacuidade de uma gramática (saber se a gramática gera alguma cadeia, qualquer que seja ela), é indecidível para classe de Gramática sensíveis ao contexto, mas é decidível para gramáticas livre-do-contexto.

Ainda assim, muitos problemas permanecem indecidíveis. Exemplos:

Universalidade[editar | editar código-fonte]

Dado uma GLC, ela gera a linguagem que contém todas as possíveis cadeias a serem geradas pelo conjunto de símbolos terminais que são usados em suas regras?

Igualdade de linguagem[editar | editar código-fonte]

Dadas duas GLCs, elas geram a mesma linguagem?

Linguagem inclusa[editar | editar código-fonte]

Dadas duas GLCs, a primeira gramática pode gerar todas as cadeias que a segunda gera?

Estar em um nível mais baixo da hierarquia de Chomsky[editar | editar código-fonte]

Dada uma Gramática sensível ao contexto, ela descreve uma linguagem livre-do-contexto? Dada uma GLC, ela descreve uma linguagem regular?

Cada um desses problemas é indecidível.

Extensões[editar | editar código-fonte]

Uma maneira óbvia para estender o formalismo de gramática livre-do-contexto é permitir que variáveis tenham argumentos, os valores que são passados com as regras. Isso permite características de uma linguagem natural, tais como concordância e referência, analogamente ao correto uso de identificadores em linguagem de programação, que devem ser expressos de maneira natural. E.g. agora, nós podemos facilmente expressar que em sentenças em inglês, o sujeito e verbo devem concordar em número.

Em Ciência da computação, exemplos dessa abordagem incluem Gramática de Afixos, Gramática de atributos, Gramática indexada, e Van Wijngaarden [[Gramática de dois leveis].

Extensões similares existem em linguística.

Outra extensão é permitir que terminais adicionais apareçam no lado esquerdo das regras, restringindo sua aplicação. Isso produz o formalismo de Gramática sensível ao contexto.

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

Chomsky inicialmente esperava superar as limitações de gramáticas livres-do-contexto ao adicionar regras de transformação.1

Tais regras são outro dispositivo padrão em linguística tradicional; e.g. passivação da voz, em português. Grande parte da Gramática gerativa tem se dedicado a encontrar maneiras de aprimorar os mecanismos descritivos de regras de estrutura de frase gramatical e transformação de tal forma possam ser expressas exatamente os tipos de coisas que podem ser expressos em linguagem natural. Permitir transformações arbitrárias não faz com que esse objetivo seja atingido. Eles são muito mais poderosos, sendo Turing completos a não ser que restrições significantes sejam adicionadas (e.g. não permitir transformações que introduzam e então reescrevam símbolos em uma maneira livre-do-contexto. Posição geral de Chomsky sobre a não-gratuidade contexto da linguagem natural tem se mantido desde então Posição geral de Chomsky sobre a não-liberdade de contexto da linguagem natural tem se mantido desde então,2 entretanto seus exemplos específicos a respeito da não adequação de GLCs em termos de uma fraca capacidade gerativa foram mais tarde desaprovadas.3 Gerald Gazdar e Geoffrey Pullum tem discutido que apesar de algumas construções não-livres-de-contexto em linguagem natural (como cross-serial dependencies na Suíça Germânica2 e reduplication em Bambara4 ), a grande maioria das formas em linguagem natural são, de fato livres de contexto.3

Veja também[editar | editar código-fonte]

Algoritmos[editar | editar código-fonte]

Notas[editar | editar código-fonte]

  1. a b Chomsky, Noam. (Sep 1956). "Three models for the description of language". Information Theory, IEEE Transactions 2 (3): 113–124. DOI:10.1109/TIT.1956.1056813.
  2. a b Shieber, Stuart. (1985). "Evidence against the context-freeness of natural language". Linguistics and Philosophy 8 (3): 333–343. DOI:10.1007/BF00630917.
  3. a b Pullum, Geoffrey K.; Gerald Gazdar. (1982). "Natural languages and context-free languages". Linguistics and Philosophy 4 (4): 471–504. DOI:10.1007/BF00360802.
  4. Culy, Christopher. (1985). "The Complexity of the Vocabulary of Bambara". Linguistics and Philosophy 8 (3): 345–351. DOI:10.1007/BF00630918.

Referencias[editar | editar código-fonte]

  • Chomsky, Noam (Sept. 1956). "Three models for the description of language". Information Theory, IEEE Transactions 2 (3).
  • Chomsky, Noam (1957), Syntactic Structures, Den Haag: Mouton.
  • Chomsky, Noam (1965), Aspects of the Theory of Syntax, Cambridge (Mass.): MIT Press.
  • Chomsky, Noam (1981), Lectures on Government and Binding, Dordrecht: Foris.
  • Gazdar, Gerald; Klein, Ewan; Pullum, Geoffrey & Sag, Ivan (1985), Generalized Phrase Structure Grammar, Cambridge (Mass.): Harvard University Press.

Ler mais[editar | editar código-fonte]

  • Michael Sipser. Introduction to the Theory of Computation. [S.l.]: PWS Publishing, 1997. ISBN 0-534-94728-X Section 2.1: Context-Free Grammars, pp. 91–101. Section 4.1.2: Decidable problems concerning context-free languages, pp. 156–159. Section 5.1.1: Reductions via computation histories: pp. 176–183.
Teoria de autômatos: linguagem formal e gramática formal
Hierarquia
Chomsky
Gramática Linguagem Reconhecedor
Tipo-0 Irrestrita Recursivamente enumerável Máquina de Turing
-- -- Recursiva Máquina de Turing que sempre para
Tipo-1 Sensível ao contexto Sensível ao contexto Autômato linearmente limitado
Tipo-2 Livre de contexto Livre de contexto Autômato com pilha
Tipo-3 Regular Regular Autômato finito