Gramática
Classificação
Comunicação
Fonética
Fonologia
Morfologia
Sintaxe
Semântica
Etimologia
Estilística
Literatura
Tipos
Descritiva
Gerativa
Formal
Funcional
Normativa
Transformacional
Universal
Implícita
Contrastiva
Reflexiva
Histórica
Artigos Relacionados
Gramática
Linguística
Lexicologia
Retórica
Língua

Em teoria das linguagens formais, uma gramática formal (algumas vezes simplesmente chamada de gramática) é um conjunto de regras de produção de cadeias em uma linguagem formal, ou seja, um objeto que permite especificar uma linguagem ou língua. As regras descrevem como formar cadeias ― a partir do alfabeto da linguagem ― que são válidas de acordo com a sintaxe da linguagem. Uma gramática não descreve significado das cadeias ou o que pode ser feito com elas em um contexto ― apenas suas formas.

A expressão "gramática formal" pode ter os sentidos:

A Teoria da Linguagem Formal, disciplina que estuda gramáticas e linguagens formais, é um ramo da Matemática Aplicada. Suas aplicações podem ser encontradas na Ciência da Computação Teórica, Linguística Teórica, Semântica Formal, Matemática Lógica, entre outras áreas.

Uma gramática formal é um conjunto de regras para se reescrever cadeias, tomando como partida um símbolo inicial, do qual se começa a reescrita. Portanto, uma gramática é normalmente encarada como um gerador de linguagem. Entretanto, ela também pode ser usada como uma base para um reconhecedor ― uma função em computação que determina se uma dada cadeia pertence à linguagem ou está gramaticalmente incorreta. Para descrever tais reconhecedores, a teoria da linguagem formal usa formalismos distintos, conhecidos como Teoria dos Autômatos. Um dos resultados mais interessantes da teoria dos autômatos é que não é possível desenhar um reconhecedor para certas linguagens formais.

Análise sintática é o processo de reconhecer uma elocução (cadeia em linguagem natural) quebrando-a em um conjunto de símbolos e analisando cada um de acordo com a gramática da linguagem. O significado das elocuções da maioria das linguagens está estruturado conforme a sintaxe de tal linguagem — prática conhecida como semântica composicional. Como resultado, o primeiro passo para descrever o significado de uma elocução de uma linguagem é quebrá-la parte por parte, e verificar a sua forma analítica (conhecida como "árvore de análise" em Ciência da Computação, e como "estrutura profunda" em gramática gerativa).

Exemplo introdutório editar

Uma gramática consiste, principalmente, de um conjunto de regras para transformação de cadeias. (Se ela apenas consistisse dessas regras, ela seria considerada um sistema semi-Thue). Para gerar uma cadeia na linguagem, começa-se com uma cadeia que consiste em apenas um símbolo inicial. As regras de produção são, então, aplicadas em uma ordem qualquer, até que uma cadeia que não contenha nem o símbolo inicial, nem os chamados símbolos não terminais, seja produzida. Uma regra de produção é aplicada a uma cadeia substituindo-se uma ocorrência do lado esquerdo da gramática por uma do lado direito. A linguagem formada pela gramática consiste em todas as cadeias distintas que podem ser geradas dessa forma. Qualquer sequência particular de regras de produção sobre o símbolo inicial produz uma cadeia distinta na linguagem. Se existem várias maneiras de gerar a mesma cadeia, a gramática é chamada de ambígua.

Por exemplo, assumimos que o alfabeto consiste de a e b, o símbolo inicial é S, e temos as seguintes regras de produção:

1.  
2.  

Então começamos com S, e podemos escolher uma regra para aplicar a ele. Se nós escolhermos a regra 1, obteríamos a cadeia aSb. Se nós escolhermos a regra 1 outra vez, nós substituiríamos o S do aSb por aSb, e obteríamos a cadeia aaSbb. Se agora nós escolhermos a regra 2, nós substituiríamos o S do aaSbb por ba e obteríamos a cadeia aababb, terminando o processo. Nós podemos escrever essa série de escolhas mais sucintamente, usando símbolos:  . A linguagem da gramática é, então, o conjunto infinito  , em que ak é a repetido k vezes (e n, em particular, representa o número de vezes que a regra de produção 1 foi aplicada).

Definição formal editar

A Sintaxe das Gramáticas editar

Na formalização de gramáticas generativas primeiramente proposta por Noam Chomsky nos anos de 1950,[1][2] uma gramática G era composta pelos seguintes componentes:

  • Um conjunto finito N de símbolos não terminais, que é disjunto das cadeias formadas a partir de G.
  • Um conjunto finito   de símbolos terminais que é disjunto de N.
  • Um conjunto finito P de regras de produção, cada uma com a forma   onde   é o operador de Kleene e   denota a união entre conjuntos. Isso significa que cada regra de produção mapeia uma cadeia de símbolos para outra, onde a primeira contém um número arbitrário de símbolos, dos quais pelo menos um é não terminal. A segunda cadeia consistiria somente da cadeia vazia — ou seja, não contêm símbolos - sendo, às vezes, representada com notações especiais pra evitar confusão ( , e ou  ).
  • Um símbolo diferenciado   que é o símbolo inicial, também chamado de símbolo sentença.

Uma gramática é formalmente definida como uma tupla  . Tal gramática formal é, às vezes, chamada de sistema de reescrita ou de gramática de estrutura de frase na Literatura.[3][4]

A Semântica das Gramáticas editar

A operação sobre uma gramática pode ser definida em termos das relações entre cadeias:

  • Dada uma gramática  , a relação binária   (lê-se G deriva em um passo) sobre cadeias de   é definida por:  
  • A relação    (lê-se G deriva em 0 ou mais passos) é definida como o fecho reflexivo-transitivo de   .
  • Uma forma sentencial é um membro de   que pode ser derivado, partindo do símbolo inicial  , em um número finito de passos; ou seja, uma forma sentencial é um membro de  . Uma forma sentencial que não contém símbolos não terminais (i.e. é um membro de  ) é chamada de sentença.
  • linguagem de  , denotada como  , é definida como todas as sentenças que podem ser derivadas em um número finito de passos partindo do símbolo inicial  ; ou seja, o conjunto  .

Note que a gramática   é efetivamente um sistema semi-Thue  , pois reescreve cadeias exatamente do mesmo jeito; a única diferença está no fato de que nós distinguimos especificamente símbolos não terminais que devem ser reescritos nas regras de reescrita, e estamos apenas interessados em reescritas a partir do símbolo inicial   designado para cadeias sem símbolos não terminais.

Exemplo editar

Para esses exemplos, as linguagens formais estão especificadas utilizando a notação de construção de conjuntos.

Considere a gramática   onde  ,  ,   é o símbolo inicial, e   é composto pelas seguintes regras de produção:

1.  
2.  
3.  
4.  

Essa gramática define a linguagem   onde   denota uma cadeia formada por n consecutivos  's. Dessa forma, a linguagem é o conjunto de cadeias que é composta por um ou mais  's, seguidos pelo mesmo número de  's, seguidos pelo mesmo número de  's.

Alguns exemplos de derivação de cadeias em   são:

  •  
  •  
  •   
(Note a notação:   lê-se "A cadeia P gera a cadeia Q pela regra de produção i ". A parte gerada é, a cada vez, indicada em negrito.)

A Hierarquia de Chomsky editar

 Ver artigo principal: Hierarquia de Chomsky

Quando Noam Chomsky formalizou as gramáticas generativas pela primeira vez em 1956,[1] ele as classificou em tipos hoje conhecidos como pertencentes à hierarquia de Chomsky. A diferença entre esses tipos é que eles têm cada vez mais rigorosas regras de produção e podem expressar menos linguagens formais. Dois importantes tipos são gramáticas livres de contexto (Tipo 2) e gramáticas regulares (Tipo 3). As linguagens que podem ser descritas com tais gramáticas são chamadas linguagens livres de contexto e linguagens regulares, respectivamente. Apesar de menos poderosas que gramáticas irrestritas (Tipo 0), que podem, na verdade, expressar qualquer linguagem que pode ser aceita por uma Máquina de Turing, esses dois tipos restritos de gramática são mais frequentemente usados porque analisadores para eles podem ser eficientemente implementados.[5] Por exemplo, todas linguagens regulares podem ser reconhecidas por uma máquina de estados finitos, e para alguns subconjuntos úteis de gramáticas de livre-contexto existem algoritmos bem conhecidos para gerar analisadores sintáticos eficientes para reconhecer as linguagens correspondentes às gramáticas geradas.

Gramáticas de livre-contexto editar

Uma gramática livre de contexto é uma gramática em que o lado esquerdo de cada regra de produção é formado apenas por um único símbolo não terminal. Essa restrição é não trivial; nem todas as linguagens podem ser geradas por gramáticas livre de contexto. As que podem são chamadas de linguagens livre de contexto.

A linguagem   definida abaixo não é uma linguagem livre de contexto, e isso pode ser rigorosamente provado utilizando o lema do bombeamento para linguagens livres de contexto, mas, por exemplo, a linguagem   (pelo menos 1   seguido pelo mesmo número de  's) é livre de contexto, pois pode ser definida por uma gramática   com  ,  ,   símbolo inicial, e as seguintes regras de produção:

1.  
2.  

Uma linguagem livre de contexto pode ser reconhecida em tempo   (veja: notação Big O) por um algoritmo como algoritmo de Earley. Isso significa que, para toda linguagem livre de contexto, uma máquina cuja entrada é uma cadeia pode ser construída, determinando em tempo   se a cadeia é membro da linguagem, onde   é o comprimento da cadeia.[6] Linguagens determinísticas livres de contexto são um subconjunto de linguagens livres de contexto que podem ser reconhecidas em tempo linear.[7] Existem vários algoritmos que se focam nesse conjunto de linguagens ou algum subconjunto dele.

Gramáticas regulares editar

Nas gramáticas regulares, o lado esquerdo é composto unicamente por símbolos não terminais, mas o lado direito também é restrito. O lado direito pode ser a cadeia vazia, ou um simples símbolo terminal, ou um símbolo terminal seguido de um símbolo não terminal e nada mais. (às vezes é usada uma definição mais ampla: pode-se permitir cadeias mais longas de terminais ou únicos não terminais sem nada mais, tornando as linguagens mais fáceis de se denotar).

A linguagem   definida abaixo não é regular, mas a linguagem   (pelo menos um   seguido por pelo menos um  , onde os números podem ser diferentes) é, já que pode ser definida pela gramática   com  ,  ,   o símbolo inicial, e as seguintes regras de produção:

  1.  
  2.  
  3.  
  4.  
  5.  

Todas as linguagens geradas por gramáticas regulares podem ser reconhecidas em tempo linear por uma máquina de estados finitos. Contudo, na prática, gramáticas regulares são comumente expressas usando expressões regulares. Algumas formas de expressão regular usadas na prática não geram rigorosamente linguagens regulares e não apresentam performance linear de reconhecimento devido a aquelas divergências.

Outras formas de gramáticas generativas editar

Muitas extensões e variações sobre a hierarquia original de Chomsky de gramáticas formais têm sido desenvolvidas, tanto pelos linguistas quanto pelos cientistas da computação, usualmente com o objetivo de aumentar seu poder de expressividade ou de torná-las mais facilmente analisáveis. Algumas formas de gramática desenvolvidas incluem:

Gramáticas recursivas editar

Não se confunda com linguagem recursiva

Uma gramática recursiva é uma gramática que contém regras de produção que são recursivas. Por exemplo, uma gramática para uma linguagem livre de contexto é recursiva à esquerda se existe símbolo não terminal A que pode ser colocado através das regras de produção para produzir uma cadeia com A como o símbolo mais à esquerda.[12] Todos os tipos de gramática da Hierarquia de Chomsky podem ser recursivas.

Gramáticas analíticas editar

Apesar de haver um enorme estoque de literatura sobre algoritmos de análise sintática, a maioria desses algoritmos assume que a linguagem a ser analisada é, inicialmente, descrita por meio de uma gramática formal generativa, e que o objetivo é transformar essa gramática em um analisador sintático que funciona. Ou seja, uma gramática generativa não corresponde, de maneira alguma, ao algoritmo usado para analisar uma linguagem, e vários algoritmos têm restrições diferentes sobre a forma de regras de produção que são consideradas bem formadas.

Uma abordagem alternativa é formalizar a linguagem em termos de uma gramática analítica, o que corresponderia mais diretamente à estrutura e semântica de um analisador sintático para a linguagem. Exemplos de formalismos de gramática analítica incluem os seguintes:

  • A linguagem de máquina implementa diretamente uma gramática analítica irrestrita. Regras de substituição são usadas para transformar uma entrada e produzir saídas e comportamento. O sistema também pode produzir the lm-diagram que mostra o que acontece quando as regras de uma gramática analítica irrestrita estão sendo aplicadas.
  • Linguagem de análise top-down: um formalismo de gramática analítica altamente minimalista desenvolvido no começo dos anos de 1970 para estudar o comportamento de analisadores sintáticos top-down.[13]
  • Gramática de ligação: uma forma de gramática analítica desenhada para a linguística, que deriva a estrutura sintática através do exame das relações de posicionamento entre pares de palavras.[14][15]
  • Gramática de análise de expressões: uma generalização mais recente de uma linguagem de análise top-down. Desenhada levando-se em conta as necessidades práticas de expressividade de uma linguagem de programação e de compiladores.[16]

Teoria da computação editar

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


Referências

  1. a b Chomsky, N. (1 de setembro de 1956). «Three models for the description of language». IRE Transactions on Information Theory. 2 (3): 113-124. ISSN 0096-1000. doi:10.1109/TIT.1956.1056813 
  2. Chomsky, Noam (1957). Syntactic Structures. The Hague: Mouton 
  3. Ginsburg, Seymour (1975). Algebraic and automata theoretic properties of formal languages. [S.l.]: North-Holland. pp. 8–9. ISBN 0-7204-2506-9 
  4. Harrison, Michael A. (1978). Introduction to Formal Language Theory. Reading, Mass.: Addison-Wesley Publishing Company. 13 páginas. ISBN 0-201-02955-3 
  5. Grune, Dick & Jacobs, Ceriel H., Parsing Techniques – A Practical Guide, Ellis Horwood, England, 1990.
  6. Earley, Jay, "An Efficient Context-Free Parsing Algorithm," Communications of the ACM, Vol. 13 No. 2, pp. 94-102, February 1970.
  7. Knuth, Donald E. (1 de dezembro de 1965). «On the translation of languages from left to right». Information and Control. 8 (6): 607-639. doi:10.1016/S0019-9958(65)90426-2 
  8. Joshi, Aravind K., et al., "Tree Adjunct Grammars," Journal of Computer Systems Science, Vol. 10 No. 1, pp. 136-163, 1975.
  9. Koster , Cornelis H. A., "Affix Grammars," in ALGOL 68 Implementation, North Holland Publishing Company, Amsterdam, p. 95-109, 1971.
  10. Knuth, Donald E., "Semantics of Context-Free Languages," Mathematical Systems Theory, Vol. 2 No. 2, pp. 127-145, 1968.
  11. Knuth, Donald E., "Semantics of Context-Free Languages (correction)," Mathematical Systems Theory, Vol. 5 No. 1, pp 95-96, 1971.
  12. Notes on Formal Language Theory and Parsing, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.JPR02
  13. Birman, Alexander, The TMG Recognition Schema, Doctoral thesis, Princeton University, Dept. of Electrical Engineering, February 1970.
  14. Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar," Technical Report CMU-CS-91-196, Carnegie Mellon University Computer Science, 1991.
  15. Sleator, Daniel D. & Temperly, Davy, "Parsing English with a Link Grammar," Third International Workshop on Parsing Technologies, 1993. (Revised version of above report.)
  16. Ford, Bryan, Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking, Master’s thesis, Massachusetts Institute of Technology, Sept. 2002.

Ligações externas editar